Maximum run of heads in n coin tosses

Question

Suppose we do 6 coin tosses and we wanna know probability of maximum runs for each number of "k" consecutive heads.

For example HHHTHH counts as 3, HTTHTH counts as 1 and HHTTHH counts as 2. I've written a python script that goes through all 2^6 possibilities and calculates the probability. The way I do it in my script is that I check each possibility, for example HHHTTT and counts the max() number of "H" letter in that string.

This is a sample output for 6 coin tosses:

Max number of 0 Heads in row is 1

Probability: 1.5625 %

Max number of 1 Heads in row is 20

Probability: 31.25 %

Max number of 2 Heads in row is 23

Probability: 35.9375 %

Max number of 3 Heads in row is 12

Probability: 18.75 %

Max number of 4 Heads in row is 5

Probability: 7.8125 %

Max number of 5 Heads in row is 2

Probability: 3.125 %

Max number of 6 Heads in row is 1

Probability: 1.5625 %

My problem is that I need to derive a general result/formula that works for any number of coins "n" and maximum run length "k".

Answer 1

Let $L_n$ be the length of the longest run of heads in a sequence of $n$ coin flips. Then

$$ P(L_n\ge m)=\sum_{r=1}^{n-m+1}(-1)^{r+1}\left[\binom{n-rm}{r}+2\binom{n-rm}{r-1}\right]\cdot\left(\frac12\right)^{r(m+1)} $$

You were asking about $P(L_n=k)$. To find this, use the above formula, and $P(L_n=k)=P(L_n\ge k)-P(L_n>k+1)$.

If you don't want to deal with the above summation, there is a recursive way to compute $P(L_n\ge m)$, which I will denote as $p_{n}$. By conditioning on the last $m$ flips, we have

$$ p_n = (1/2)^m + (1/2)p_{n-1}+(1/2)^2p_{n-2}+\dots+(1/2)^{m}p_{n-m} $$

Both quoted formulae are from Sheldon Ross, A First Course in Probability, 9th Edition, p. 154.