Coin flips

Suppose you flip a biased coin (probability of heads is ${p}$, ${0). What is the expected number of flips to get ${r}$ consecutive heads, where ${r}$ is a positive integer?

Let ${T}$ be the number of flips until ${r}$ consecutive heads are observed. Let ${p_k=\mathbb P(T=k)}$, ${k=0,1,2,\ldots}$. Clearly ${p_k=0}$ for ${k and ${p_r=p^r}$. For ${k>r}$, we have

$\displaystyle p_k = p^r(1-p)(1-\mathbb P(T

Let ${P(s)=\mathbb E[s^T]}$ be the probability generating function of ${T}$. Multiplying by ${s^k}$ and summing over ${k>r}$, the left-hand side is

$\displaystyle \sum_{k=r+1}^\infty p_ks^k = P(s) - p^rs^r,$

and the right-hand side

$\displaystyle \sum_{k=r+1}^\infty p^r(1-p)\left(1-\sum_{j=0}^{k-r-1}p_j \right)s^k.$

Reversing the order of summation (${j\leqslant k-r-1}$ implies ${k\geqslant j+r+1}$) yields

\displaystyle \begin{aligned} &p^r(1-p)\left( \sum_{k=r+1}^\infty s^k \right) - p^r(1-p)\sum_{j=0}^\infty p_j\sum_{k=j+r+1}^\infty s^k \\ &=p^r(1-p)\left(\frac{s^{r+1}}{1-s} -\sum_{j=0}^\infty p_j\frac{s^{j+r+1}}{1-s} \right)\\ &=\frac{p^r(1-p)s^{r+1}}{1-s}\left(1 - \sum_{j=0}^\infty p_js^j \right)\\ &=\frac{p^r(1-p)s^{r+1}}{1-s}(1-P(s)). \end{aligned}

Equating the two, we have

$\displaystyle P(s) - p^rs^r = \frac{p^r(1-p)s^{r+1}}{1-s}(1-P(s)),$

and hence

$\displaystyle P(s) = \frac{p^r(s^r-ps^{r+1})}{1-s+p^r(1-p)s^{r+1}}.$

Differentiating, we have

$\displaystyle P'(s) = \frac{p^r(rs^{r-1}-p(r+1)s^r )(1-s + p^r(1-p)s^{r+1} ) - p^r(s^r - ps^{r+1})(-1 + p^r(r+1)(1-p)s^r) }{(1-s+p^r(1-p)s^{r+1})^2}.$

Hence

\displaystyle \begin{aligned} \mathbb E[T] &= \lim_{s\uparrow1}P'(s)\\ &= \frac{p^r(r - p(r+1))p^r(1-p) - p^r(1-p)(-1 + p^r(r+1)(1-p)) }{(p^r(1-p))^2 }\\ &= \frac{p^r(r -p(r+1)) + 1 - p^r(r+1)(1-p) }{p^r(1-p) }\\ &= \frac{1 - p^r((r+1)(1-p+p) - r) ) } {p^r(1-p) }\\ &= \frac{1 - p^r}{p^r(1-p)}. \end{aligned}

In particular, when ${p=\frac12}$, we have

$\displaystyle \mathbb E[T] = \frac{1 - \left(\frac12 \right)^r}{\left(\frac12 \right)^r\left(1-\frac12 \right)}= (1-2^{-r})2^{r+1}=2^{r+1}-2.$