Coin flips

Suppose you flip a biased coin (probability of heads is {p}, {0<p<1}). 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<r} and {p_r=p^r}. For {k>r}, we have

\displaystyle p_k = p^r(1-p)(1-\mathbb P(T<k-r)) = p^r(1-p)\left(1-\sum_{j=0}^{k-r-1}p_j\right).

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s