Probability of getting a run of r heads in n coin tosses where run ends at nth coin toss

Question

Looking for a closed form solution. Here is the one of the approaches that a text book presents:

Let $f_{n}$ be the probability of getting run of $r$ heads in $n$ coin flips where run ends at $n$ flips.

• If first toss is a tail, then a run happens in next $n-1$ coin flips. This is probability $q f_{n-1}$

• If first toss is head, then a tail happens and thereafter its equivalent to getting run in next n-2 coin tosses. This is probability $p q f_{n-2}$

and so on..

These are all mutually exclusive, so we add these up to obtain following relationship

$$f_{n} = q f_{n-1} + pq f_{n-2} + p^{2} q f_{n-3} + .... + p^{r-1} q f_{n-r} = \sum_{k=1}^{r} q p^{k-1}f_{n-k} $$

My confusion is does this cover all the possibilities ? What about a sequence of run where we have T H T followed by $s_{n-3}$ instead of H H T $s_{n-3}$ considered above. Here i am referring $s_{n-3}$ to a pattern of heads and tails that's included and counted towards probability $f_{n-3}$

Answer 1

Its because pattern THT $s_{n−3}$ belongs to pattern T $s_{n−1}$ while HHT $s_{n−3}$ doesn't. Infact the summation is of mutually exclusive and exhaustive series that results in overall probability of $f_{n}$.