coin flip probability problem

[muckyouraces]

if you flipped a coin 100 times, what would be the odds that at least once during those 100 coin flips, it landed on heads 10 times in a row. what about 1000 coin flips?

[pzhon]

100 flips: 4.41372%
1000 flips: 38.545%

Mathematica Code:
<ul type="square">
m1 = Transpose[Table[If[i == j - 1, 1/2, 0], {i, 1, 11}, {j, 1, 11}]]
m2 = Table[If[i == 1 &amp;&amp; j &amp;#8800; 11, 1/2, 0], {i, 11}, {j, 11}]
m3 = Table[If[i == 11 &amp;&amp; j == 11, 1, 0], {i, 11}, {j, 11}]
transmat = m1 + m2 + m3
streak[n_] := N[MatrixPower[transmat, n]].{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

streak[100]
{0.478166, 0.2392, 0.119659, 0.0598588, 0.0299441, 0.0149794, 0.00749338, 0.00374853, 0.00187518, 0.000938052, 0.0441372}

streak[1000]
{0.307426, 0.153788, 0.076932, 0.0384849, 0.0192519, 0.00963067, 0.0048177, 0.00241003, 0.00120561, 0.0006031, 0.38545}[/list]The ith position of streak[n] is the probability that the current streak is i-1 heads, except that the 11th position is the probability that you have ever had 10 or more heads.

[gaming_mouse]

pzhon,

can you explain the methodology a bit more? sorry i'm not familiar with mathematica code....

[pzhon]

I used a transfer matrix.

State 0: No streak of 10 heads yet, and the current streak is 0.
...
State 9: No streak of 10 heads yet, and the current streak is 9.
State 10: There has been a streak of length 10 or more.

We can summarize the results after n tosses by a probability distribution on these 11 states, which is supposed to be returned by streak[n].

For all n,

streak[n]
= transmat . streak[n-1]
= transmat^n . {1,0,0,0,0,0,0,0,0,0,0}

where transmat is a transfer matrix which says the probability of moving from one state to the next.

m1 said that if you have a streak of length n, there is a 1/2 probability that it gets longer by 1.
m2 said that if you have a streak of length less than 10, there is a 1/2 chance that it ends, and so you return to state 0.
m3 said that if you are in state 10, you stay in state 10 with probability 1.
The transfer matrix was built from these.

[gaming_mouse]

Very cool, thanks.

[BruceZ]

[ QUOTE ]
if you flipped a coin 100 times, what would be the odds that at least once during those 100 coin flips, it landed on heads 10 times in a row. what about 1000 coin flips?

[/ QUOTE ]

This post contains a simple Perl script that I wrote awhile back to compute the exact answer to these types of problems, and it links to a post describing how to do the same calculation in Excel. The following is the output of the Perl script for your questions. It agrees exactly with Pzhon's.

<font class="small">Code:</font><hr /><pre>
Probability of 10 events of probability 0.5 in a row in 100 trials = 0.0441372286404217 or 21.6566105485876 to 1

Probability of 10 events of probability 0.5 in a row in 1000 trials = 0.385449752412481 or 1.59437188308236 to 1
</pre><hr />

[R Gibert]

For 10 heads occurring at least once in 100 tosses:

The probability is exactly: 6993823047305143749226306585/158456325028528675187087900672

The odds are exactly:
151462501981223531437861594087 to 6993823047305143749226306585

This assumes fair tosses of a fair coin.

I haven't tried it, but python may not be able to do an exact solution to the 1000 toss case. At least not in the same straight forward way I used.

The method of solution "looks" pretty simple, but isn't really, but it can be found here:

http://mathworld.wolfram.com/Fibonaccin-StepNumber.html