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}$

  • $\begingroup$ May be its because pattern THT $s_{n-3}$ belongs to pattern T $s_{n-1}$ while HHT $s_{n-3}$ doesn't? I am still confused about it though. Any additional insight will help. $\endgroup$
    – toing
    Commented Apr 2, 2018 at 20:28

1 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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.