3
$\begingroup$

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.

$\endgroup$
2

1 Answer 1

5
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .