[Math] Fair coin tosses: Probability of $\geq 4$ consecutive heads

probabilityprobability theory

I know that there are some related questions, but they seem to be overkill for this small exercise.

I have 10 (fair) coin tosses and am interested in the probability that I have at least 4 consecutive heads.

So I had a lot of different ideas, but I think many of them do not work too well.

1) Markov chain: But then, somehow, we need to keep track of the number of coins we have already tossed, so one "loses" the Markov property.

2) count all possibilities: we have $2^{10}$ possibilities in total and can subtract the ones that have at most 3 consecutive heads. But seems to be nasty.

3) recursive equation? Let $p_{i,j}$ for $i \leq j$ be the probability that we have at least $j$ consecutive heads. But also this seems to be not that easy..

So this question is asked in a book in the first chapter, so it shouldn't be too hard?

Best Answer

Let $S_N$ be the set of the strings over the alphabet $\Sigma=\{0,1\}$ with length $N$, avoiding $4$ consecutive $1$'s, and $T_N=|S_N|$. The only possible prefixes of an element of $S_N$ can be: $$0,\quad 10,\quad 110, \quad 1110$$ hence we have: $$ T_N = T_{N-1}+T_{N-2}+T_{N-3}+T_{N-4} $$ and: $$ T_1=2,\quad T_2=4,\quad T_3=8,\quad T_4=15$$ leading to: $$ T_{10}=773.$$ The probability that at least for consecutive heads appear is so: $$ 1-\frac{773}{2^{10}} = \frac{251}{1024}.$$