Math Forum Discussions

Rob Morewood

Posts: 171
Registered: 12/6/04

Re: coin toss
Posted: Sep 6, 2005 12:54 PM

Plain Text

We were asked (anonymously):

: If you toss 100 coins, what's the probability of getting 5,
: either heads or tails, in a row? 6 in a row?
: How do you figure it out?

Are you asked for "at least" five in a row, or "exactly" five in a row?

I derived a recursive formula which answers the question for "at least"
K in a row the same from a sample of N coins. A small program
(on computer or calculator) quickly gives an approximate answer.
For "exactly" five in a row, something similar might work, but
I'll leave that to someone else. In the following I will explain
the thought process which led to my formula.

It is often helpful to start with something simplier:
Try the calculation with less than 100 coins.

Less than five coins is too simple?
The odds of five in a row with fewer than five coins is ZERO!

Try FIVE coins instead of 100:
- As Dave Chamberlain already noted (by starting small: two coins, then
three coins, etc), the odds of the FIRST five being the same is 1/16.
[The first coin can be either head or tail. The next four must be
the same as the first with probability of 1/2 each: (1/2)^4 = 1/16.]
In fact, Dave found a formula (which I will use much later) for odds
of the first "k" coins the same: 2/2^k.

To go from small to large, induction is often helpful.
Can you use what you already know and just add on the extra bit?

For SIX coins:
- The odds of five in a row among the first five is known (1/16).
- Look at having five in a row, but NOT in the first five.
It must be the last five the same, with the first different.
The odds of that are 1/32.
[The first coin can be either heads or tails. The next five must
all be different from the first with probability 1/2 each.]
These two possibilities are "mutually exclusive".
If the last five are the same with the first coin different,
then there cannot be five the same among the first five.
So we can just add the probabilities: 1/16+1/32=3/32.

Similarily for SEVEN coins:
- The odds of five in a row among the first six is known (3/32).
- Look at having five in a row, but NOT in the first six.
Again, it must be the last five the same with the preceeding coin
(that is the second coin) different. Odds of that are still 1/32.
Total 3/32+1/32=4/32.

Also for EIGHT coins we get 5/32 and for NINE coins we get 6/32.

But for TEN coins there is a problem.
- If the last five coins are the same, with the preceeding coin
different, we could still have the first five coins the same!
The two cases are no longer mutually exclusive.
However, the first five coins are "independant" of the last
five coins and we already know the odds that they do NOT have
five in a row the same (1-1/16). The odds that the last five
coins are the same and different from the preceeding (fifth)
coin is still 1/32.
- So the odds that the last five are the same (different from
the preceeding coin) AND that there are NOT already five in
a row amongst the first five is: 1/32*(1-1/16).
(The odds of having both of two independant events is just
the product of their individual odds.)

So the total odds of finding five in a row among ten coins is:
The odds of five in a row among the first nine PLUS
the odds of the last five the same (different from the preceeding coin)
AND NOT have five the same before the last five (in the first five).
= 6/32 + 1/32*(1-1/16) = 111/512

This last idea can be continued.
The total odds of finding five in a row among ELEVEN coins is:
The odds of five in a row among the first TEN coins PLUS
the odds of the last five the same (different from the preceeding coin)
AND NOT have five the same before the last five (in the first SIX)
= 111/512 + 1/32*(1-3/32) = 251/1024

In general:
The total odds of finding five in a row among N coins is:
The odds of five in a row among the first (N-1) coins PLUS
the odds of the last five the same (different from the preceeding coin)
AND NOT having five the same in the first (N-5).

If we write F_5(N) = the odds of having 5 in a row among N coins.
The above is a recusive formula:
F_5(N) = F_5(N-1) + (1/32)*[1-F_5(N-5)] for N>5.
For N=5, we have F_5(5)=1/16 and for N<5 we have F_5(N)=0 of course.

More generally if F_k(N) = the odds of having k in a row among N coins:

/ 0 N<k
F_k(N) = { 2/2^k N=k
\ F_k(N-1) + [1-F_k(N-k)]/2^k N>k

I don't want to think about finding a closed-form for this,
but it is easily evaluated with a simple program. In REXX:

/* Find the odds of at least Number in a row the same
out of a Total number of coins tossed. */

Say "Enter the number in a row the same:"
Pull Number
Say "Enter the total number of coins tossed:"
Pull Total

/* Trivial odds - fewer coins tossed than wanted in a row. */
Do Count=0 to Number-1
Odds.Count=0
end

/* Dave's formula for tossing a number of coins all the same. */
Odds.Number=2/(2**Number) /* Double * is exponentiation in REXX */

/* Now use the recursive formula */
Do Count=Number+1 to Total
PreviousCount=Count-1
EarlyCount=Count-Number
Odds.Count=Odds.PreviousCount+(1/32)*(1-Odds.EarlyCount)
end

Say "The odds are: " Odds.Total*100"%"

I'll leave it to the readers to translate into your favorite language.
The above produced:

Enter the number in a row the same:
5
Enter the total number of coins tossed:
100
The odds are: 97.1689674%

There are techniques for turning such recursive formulas into
closed form formulas, but I'll go no further for now.

Instead, here is a simplier challenge:

Can you find the expected number (the average number) of sequences
of exactly five coins in a row the same (heads or tails) from a
sequence of 100 random coin tosses?

This is essentially the last question from last year's Hypatia
contest and I think the solution leads (with considerable work)
to a solution for the problem of finding the odds of having at
least one sequence of exactly five in a row the same.

|)|\/| || Crofton House School
|\| |orewood@olc.ubc.ca || Beautiful British Columbia
Mathematics & Computer Science || (Canada)

--
submissions: post to k12.ed.math or e-mail to k12math@k12groups.org
private e-mail to the k12.ed.math moderator: kem-moderator@k12groups.org
newsgroup website: http://www.thinkspot.net/k12math/
newsgroup charter: http://www.thinkspot.net/k12math/charter.html