Suppose you flip a fair coin times. What is the probability distribution for the longest streak of consecutive like outcomes? That is, let

Probability that there exists a streak of consecutive heads or consecutive tails in the sequence of tosses, but no streaks longer than exist.

Find .

In case it helps, here is a picture of a coin.

PS – The picture doesn’t help, but Sacagawea was pretty hot for a 15-year old. Also, she apparently had a small, secondary head growing out the back of her neck.

### Like this:

Like Loading...

*Related*

Tags: coin flip, consecutive heads, consecutive tails, probability, Sacagawea, small mutant baby heads growing out the back of your neck, streaks

This entry was posted on November 29, 2008 at 1:18 am and is filed under problems and solutions. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

December 2, 2008 at 9:38 pm

Probability that,

(l=n) = 1/(2^(n-1))

(l=n-1) = 1/(2^(n-2))

(l=n-2) = 3/(2^(n-1))

(l=n-3) = 1/(2^(n-3))

. . .

. . .

. . .

[ l is the longest streak obtained in all cases]

Similarly, the probability goes on increasing till l=n/2 after which it starts decreasing.

Therefore, probability suggests that the longest streak equals n/2 (incase n is odd, it’ll be the higher of the two median values).

P(l) = (n+2)/(2^(n))

December 2, 2008 at 10:21 pm

Good start, but not completely correct. You have the idea right that you need to count the number of sequences, but you missed some.

You should have

P(l = n-2) = 5/(2^(n-1))

P(l = n-3) = 12/(2^(n-1)) = 3/(2^(n-3))

also, the distribution is not symmetric about l=n/2, and l=n/2 is not the most likely answer. For example, if n=2 billion, it’s saying that the most likely longest streak is 1 billion. But getting one billion heads or tails in a row is extremely rare – it happens with probability 1/2^billion! So the highest probability is actually for a streak much shorter.

December 4, 2008 at 9:35 am

[…] Problem: Parity of Permutations By meichenl The old problem is still unanswered, but I decided not to try to post the solution before I figure out what that […]

December 4, 2008 at 1:26 pm

No, the graph isn’t symmetrical about l=n/2, but the maxima of the curve is at l=n/2.

OK, a billion heads or tails in a row is highly unlikely. So, the solution has to be within reasonable limit. What is that limit? Personally, if I were to get more than 10 like results consecutively, I’d take the rest of the day off.

December 4, 2008 at 1:46 pm

Never mind what I just said…

But the thing about reasonable limit still holds. How do you quantify that?

May 1, 2009 at 5:45 pm

[…] Plays Tug of War By meichenl I have a couple of old problems I haven’t solved yet (1 2), but they’re kind of long, and this one is much shorter. The logic for this puzzle is from […]