: 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:
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 |\| |firstname.lastname@example.org || Beautiful British Columbia Mathematics & Computer Science || (Canada)