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.


Tags: , , , , , ,

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: