New Problem: Rosencrantz and Guildenstern Are Dead

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

$P(l) \equiv$ Probability that there exists a streak of $l$ consecutive heads or $l$ consecutive tails in the sequence of $n$ tosses, but no streaks longer than $l$ exist.

Find $P(l)$.

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.

6 Responses to “New Problem: Rosencrantz and Guildenstern Are Dead”

1. Nik Says:

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))

2. meichenl Says:

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.

3. New Problem: Parity of Permutations « Arcsecond Says:

[…] 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 […]

4. Nik Says:

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.

5. Nik Says:

Never mind what I just said…

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

6. New Problem: King of the Jungle Plays Tug of War « Arcsecond Says:

[…] 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 […]