Associated Topics || Dr. Math Home || Search Dr. Math

Coin Tosses, Dealing Cards...

```
Date: 12/08/98 at 13:15:58
From: Greg
Subject: Discrete Math (Probability and Combination)

1) A fair coin is tossed 4 times. What is the probability that at least
2 heads will occur, given that at least 1 of the first 2 tosses is a
head? What is the probability that at least 2 heads will occur given
that at least one head occurs? Do the results agree with your
intuition?

2) 5 cards are dealt from a perfectly shuffled deck. What is the
probability of being dealt exactly 2 aces, given that you were dealt
the ace of spades? What is the probability of being dealt exactly 2
aces, given that you were dealt at least 1 ace? Do the results agree

3) A fair coin is tossed until the number of heads and the number of
tails differ by 2. What is E, the expected number of tosses?

(Hint: Imagine that N of your friends play this game simultaneously.
Count the total number of tosses. By the definition of E, this total
should be approximately N*E. Further, after 2 tosses some of your
friends have completed their experiment because they got either 2 heads
or 2 tails. Some of your friends got TH or HT and, for these friends,
the experiment is beginning again; i.e., each of these friends should
get approximately E more tosses.)

4) The experiment consists of tossing a fair coin 1000 times. What is
the expected number of times that a head will be immediately followed
by a tail? Does the result agree with your intuition?

(Hint: The ith toss is a winner provided that the (i-1)th toss was a
head and the ith toss is a tail. What is the expected number of
winners on the ith toss?)

Final Hint: (3) and (4) require almost no calculation.
```

```
Date: 12/08/98 at 17:00:28
From: Doctor Anthony
Subject: Re: Discrete Math

Hi Greg -

(1)

The problem asks what is the probability of getting at least two heads
in four coin flips, given that at least one of the first two flips is

We must calculate

Prob(at least 1 head in first 2 flips and at least 2 heads in 4 flips)
----------------------------------------------------------------------
Prob(at least 1 head in first 2 flips)

The probability of at least 1 head in first 2 flips

= 1 - Pr(no heads in first 2 flips)

= 1 - (1/2)(1/2)

=  3/4     (This is the denominator of above expression)

We now find the numerator of the expression quoted above.

Prob at least 2 H's in 4 throws

P(2) =  C(4,2) x (1/2)^2 x (1/2)^2  =  C(4,2) x (1/2)^4
P(3) =                              =  C(4,3) x (1/2)^4
P(4) =                              =  C(4,4) x (1/2)^4
--------------------
Total =    11 x (1/2)^4

From this we subtract the probability of the one excluded case,
namely, 2 T's in the first two throws with the 2 H's in the second 2
throws.   Prob  = (1/2)^4

So the required probability  =  11/16 - 1/16  =  10/16

And so the final required probability

10/16
=  -------
3/4

=   5/6

This agrees with intuition, because the given of at least 1 H in the
first two has a lower probability than at least 1 in 4 tosses.  So in
the former case, we are given something that has a lower probability
and this imposes a greater restriction.

(2)

Given that you have the ace of spades you must select 1 ace from 3 and
3 non-aces from 48 other cards.

C(3,1) x C(48,3)        3 x 17296
Prob =  ----------------   =   -----------  =  0.207635
C(51,4)              249900

The probability of getting at least 1 ace = 1 - Prob(no ace)

C(48,5)
Prob. no ace  = --------  =   0.658842
C(52,5)

So the probability of at least 1 ace = 0.341158

C(4,2) x C(48,3)
Prob(2 aces) =  -----------------  = 0.0399298
C(52,5)

So the required probability = 0.0399298/0.341158

=  0.117042
(3)

Let E be the expected number of tosses. You toss at least twice but
there is a probability of 1/2 (if you get TH or HT) that you will

So we have      E = 2 + (1/2)E

(1/2)E = 2

E = 4

Let a be expected number of tosses to get a sequence HT just after H.
Let b be expected number of tosses to get HT just after T.

E = 1 + (1/2)a + (1/2)b

a = 1 + (1/2)a

(1/2)a = 1   so  a = 2

b = 1 + (1/2)a + (1/2)b

b = 1 + 1 + (1/2)b

(1/2)b = 2   and  b = 4

So  E = 1 + 1 + 2 = 4

And in 1000 tosses we expect to get 1000/4 = 250 cases with the
sequence HT.

- Doctor Anthony, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 02/13/99 at 17:10:43
From: Greg Beck
Subject: Discrete Math (Probability and Combination)

1) There are 2 kinds of particles inside a nuclear reactor. After each
second, an A-particle will split into 3 b-particles and a b-particle
will split into an a-particle and 2 b-particles. How many particles of
each kind are inside the reactor after n seconds? (Initially there are
2-a particles and 3 b-particles.) Deduce a recurrence relation (you are
not required to solve the recurrence relation).

2) How many strings of length n, consisting only of a, b, c, have an
even number of a's? Deduce but you need not solve a recurrence
relation.

3) How many subsets of {1,2...,n} do not contain two consective
integers? Deduce but do not solve a recurrence relation.

4) In how many ways can a set of size n be written as the union of
non-empty disjoint sets? Suppose when n = 3, there are 5 ways: {1}
{2} {3}, {1 2}{3}, {2 3}{1}, {1 2}{3}, and {1 2 3}. Deduce but do not
solve a recurrence relation.
```

```
Date: 02/26/99 at 10:43:17
From: greg beck
Subject: Discrete Math (Probability and Combination)

(1) Solve :
a(n) + 3*a(n-1) + 2*a(n-2) = 10    (n >= 2)
a(0) = 2
a(1) = 1

(2) Solve :
a(n) = 2*a(n-1) + 8*a(n-2) + 3*n    (n >= 2)
a(0) = 1
a(1) = 4

(3) Solve :             n
a(n) = a(n-2) + 2      (n >= 2)
a(0) = 1
a(1) = 3

(4) Solve :
a(n) = -a(n-1) + 2*a(n-2) + 1     (for n >= 2)
a(0) = 0
a(1) = 1
```

```
Date: 02/27/99 at 07:33:32
From: Doctor Anthony
Subject: Re: Discrete Math (Probability and Combination)

You have a transition matrix as shown:

(1)
FROM
a      b
TO   a  [ 0      1]
b  [ 3      2]

If you multiply this out a couple of times or use the eigen values
technique for getting the power of a matrix, this tends to the value

3^n[1/4   1/4]
[3/4   3/4]

If you start with a = 2,  b = 3 then the number of either sort after
n generations is

3^n[1/4  1/4]*[2]  = 3^n[ 5/4]  = 5*3^n[1/4]
[3/4  3/4] [3]       [15/4]         [3/4]

(2)

If f(n) is the number of strings with an even number of a's for strings
of length n, then for example:

Strings                     Number
--------                   --------
f(2) = aa                            1
f(3) = aab, aac                      2
f(4) = aabb, aacc, aabc, aaaa        4
f(5) = aabbb, aabbc, aaccb,          6
aaccc, aaaab, aaaac
f(6) = aabbbb, aabbbc, aabbcc,       9
aabccc, aacccc, aaaabb,
aaaabc, aaaacc, aaaaaa

If one examines the pattern, we can see that the number of strings with
two a's goes up by 1 as n increases by 1, and the number of strings
with 4 a's goes up by 1 as n increases by 1. Similarly, the number of
strings with 6 a's goes up by 1 as n increases by 1.

In going from f(4) to f(5), we have 3 strings with 2 a's going up to
4 strings with 2 a's, and 1 string with 4 a's that goes up to 2 strings
with 4 a's.

So, the increase from f(4) to f(5) equals the number of even numbers
that are less than 5. That is two numbers 2 and 4, and we get

f(5) = f(4) + 2

In going from f(5) to f(6) there is an increase of 1 in number of
strings with 2 a's, 4 a's and of course 6 a's. So the total increase
is the number of even numbers less than or equal to 6. There are 3 such
numbers 2, 4 and 6 and so

f(6) = f(5) + 3

The general recurrence formula for this pattern is

f(n) = f(n-1) + Integer value of (n/2)

Try the rest using the concepts I have applied above. I will look at
the others when time permits.

- Doctor Anthony, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 02/27/99 at 10:40:21
From: Doctor Anthony
Subject: Re: Discrete Math (Probability and Combination)

(1)

The difference equation is

u(n+2) + 3u(n+1) + 2 u(n) = 10

We let u(n) = v(n) + w(n) where

v(n+2) + 3v(n+1) + 2v(n) = 0

This corresponds to the 'complementary' function in normal differential
equations. The solution is given by solving

x^2 + 3x + 2 = 0

(x+1)(x+2) = 0    x = -1  and x = -2

So the C.F. is   v(n) = A(-1)^n + B(-2)^n

For w(n) we use a trial solution w(n) = p.n + q,  where p and q are
constants, and substituting into

w(n+2) + 3w(n+1) + 2w(n) = 10

p(n+2)+q + 3p(n+1)+3q + 2p.n+2q = 10

n(p+3p+2p) + 2p+3p + 6q = 10

6p.n + 5p + 6q = 10

and so 6p = 0,  p = 0,   6q = 10,  q = 10/6 =  5/3

and the solution is  w(n) = 5/3

The general solution is

u(n) = A(-1)^n + B(-2)^n + 5/3

u(0) = 2   so   2 = A + B + 5/3        A + B = 1/3
u(1) = 1   so   1 = -A - 2B + 5/3     A + 2B = 2/3
----------------
Subtracting   B = 1/3

and so A = 0

Therefore the solution is   u(n) = (1/3)(-2)^n + 5/3

(2)
u(n+2) - 2u(n+1) - 8u(n) = 3^n

Solve  x^2 - 2x - 8 = 0

(x-4)(x+2) = 0     x = 4  or  -2

v(n) = A(-2)^n + B.4^n

Use a trial solution of the form  w(n) = p.3^n + q

Substitute into  w(n+2) - 2w(n+1) - 8w(n) = 3^n

p.3^(n+2) + q - 2p.3^(n+1) - 2q - 8p.3^n - 8q = 3^n

3^n[9p - 6p - 8p] - 9q = 3^n

So, q = 0, -5p = 1,   and  p = -1/5

Therefore,  w(n) = -(1/5)3^n

The general solution is

u(n) =  A(-2)^n + B.4^n - (1/5).3^n

u(0) = 1  ->  1 = A + B - 1/5       ->  A + B =  6/5
u(1) = 4  ->  4 = -2A + 4B - 3/5   ->  -2A+4B = 17/5

So  2A + 2B = 12/5
-2A + 4B = 17/5
-----------------
6B = 29/5    and  B = 29/30   A = 6/5 - 29/30 = 7/30

Therefore,  u(n) = (7/30)(-2)^n + (29/30)4^n - (1/5).3^n

The others can be done in exactly the same way, so give them a try.

- Doctor Anthony, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Discrete Mathematics
High School Linear Algebra
High School Permutations and Combinations
High School Probability

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search