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 
with your intuition?

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 
heads.  

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 
return to the initial position.

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

           (1/2)E = 2

                E = 4 

Answer to the 4th question:

 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/