Probability and Tossing a Coin

Date: 10/25/2004 at 13:21:47
From: Kevin
Subject: Coin Toss... Probability Question

What is the probability for HEAD face up 2 times in a row before TAIL 
face up a total of 10 times (or X times)?  For example,

  T T T T H T T H H = Good
  T T T H T H T T T T H T H T = No Good

I thought of a long way to calculate this, like adding HH, then THH,
then HTHH, HTTHH, but I'm hoping there is a formula for this problem.

Date: 10/25/2004 at 16:54:14
From: Doctor Vogler
Subject: Re: Coin Toss... Probability Question

Hi Kevin,

Thanks for writing to Dr. Math.  This is a counting problem.  You will
always end after, at most, 20 coin tosses.  So the thing to do is 
count how many ways there are for a string of n H's and T's to have 
two H's in a row before getting to 10 T's.  Then the probability of 
any single such string is 2^(-n), so you multiply the probability 
times the count, add those up for n from 1 to 20, and viola!

Now, in order not to count a string twice, we should only count the
ones that END in HH, and (except for the 2-long string HH) they should
end in THH (or they would have ended sooner).  So let's suppose our
string has length n and ends with THH, so there are n-3 letters before
the THH,

  (n-3 letters)THH

and those n-3 letters contain no more than 8 T's (so that there are
fewer than 10 after including the THH) and no double H.  Well, how 
many H's could there be?  There must be at least

  n - 3 - 8 = n - 11

H's (if n > 11, or there could be any number if n <= 11).  So let's
suppose that there are m H's in those first n-3 letters.  Then how
many ways are there to place them in those n-3 places?  You might be
tempted to say

    n-3
  (     ),
     m

also called "n-3 choose m," but you need to account for the fact that
no two H's can be next to one another.  So we might group each H with
the T following it.  Then we have to include the T from the THH, and
then there are n-2 letters, but only n-2-m T's, and we just want to
know which T's have an H before them.  So the answer for a particular
n is that there are

        n-m-2
  sum (       ),
   m      m

where the sum is take from m = max(0,n-11) up to the biggest m with
n-m-2 > m, which is floor((n-2)/2).

Do this sum for each n.  (Why do you get 0 when n > 20?)  Multiply
each result by 2^(-n), and add them all together.

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

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