Streak!

Fascinated by the beauty of randomness, a Kaboobly Dooist asks the craftsmen to paint a linear wall consisting of 2 16 2^{16} stones in the following way:

For each stone: Flip a coin; If the toss results heads, paint the stone white; If the toss results tails, paint the stone black.

What is the expected longest contiguous streak consisting of consecutive black stones?

If the answer is n n , enter your answer as n \lfloor n \rfloor .

Inspired by Math with Bad Drawings .


The answer is 15.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

http://www.cs.cornell.edu/~ginsparg/physics/INFO295/mh.pdf This link provides a good solution.

[This is not a solution. If you know a solution, please add it]

The following formula appears in this page

log ( n 2 ) log ( 2 ) 1 2 + γ log ( 2 ) \frac{\log \left(\frac{n}{2}\right)}{\log (2)}-\frac{1}{2}+\frac{\gamma }{\log (2)}

However, the answer can be experimentally verified, anyway.

Actually, I almost solved it the following way: tossing a coin 16 times in a row for black stone has the probability ( 1 2 ) 16 \left(\frac{1}{2} \right) ^{16} , for each toss. There are 2 16 2^{16} tosses. Expected value = μ p \mu p . This time, it's the expected value for the probability of tossing 16 coins in a row for black, in 2 16 ) 2^{16}) tosses. Thus, ( 1 2 ) 16 ( 2 16 ) = 1 \left(\frac{1}{2} \right) ^{16}(2^{16})=1 . Hence, this 'adds up.' But apparently 16 tosses is not the answer; 15 is. Why? Because if you do 15, you get 2 2 - which is the reciprocal of the probability of getting a black or a white. So...

1 probability per toss = number of tosses * probability per toss expected contiguous tosses \frac{1}{\text{probability per toss}} = \text{number of tosses * probability per toss}^{\text{ expected contiguous tosses}}

expected contiguous tosses = log probability per toss ( probability per toss * number of tosses ) \Rightarrow \text{expected contiguous tosses} = -\log _{ \text{ probability per toss }}{\left( \text{ probability per toss * number of tosses} \right) }

expected contiguous tosses = 1 log probability per toss ( number of tosses ) \Rightarrow \boxed{ \text{expected contiguous tosses} = -1 - \log _{ \text{ probability per toss }}{\left( \text{ number of tosses} \right) }}

Hence,

So, is this right, or is this just coincidence?

John M. - 6 years, 2 months ago

Log in to reply

This is interesting.

Agnishom Chattopadhyay - 6 years, 2 months ago

According to " The Longest Run of Heads ", Mark F. Schilling, if you flip a fair coin n n times, then the expected length of the longest run is approximately log 2 n + γ log 2 3 2 \log_2 n + \frac{\gamma}{\log 2} - \frac{3}{2} .

Jon Haussmann - 6 years, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...