# Expected number of coin tosses until a run of $k$ successive heads occurs

Suppose each coin toss is independent, what is the expected number of coin tosses until a run of "k" successive heads occur? Tried finding a recursive expression to solve the problem but got completely lost.

• You might want to look here. Commented Jul 27, 2014 at 17:12
• Commented Feb 11, 2019 at 5:22

Let $R_k$ be the number of tosses until the first run of $k$ heads and $E_k := E(R_k)$. The event that the first run of $k$ heads appears is the disjoint union of the event that the first run of $k-1$ heads appears followed by a head and the event that the first run of $k-1$ heads appears followed by a tail followed eventually by a run of $k$ heads.

If the probability of heads is $p$, then using the properties of conditional expectation

$$E_k = p(E_{k-1} + 1)+ (1-p)(E_{k-1} + 1 + E_k)$$

and

$$E_k = \frac1{p}(E_{k-1} +1).$$

Since $E_1 = 1/p$, we can solve recursively to obtain

$$E_k = \sum_{j=1}^{k}p^{-j}= \frac{(\frac1{p})^k-1}{1-p}.$$