A coin is tossed, coming up heads with probability $p$. What is the expected number of flips until there are $n$ heads total?

Question

My thought process is: $X$ can only take on values greater than or equal to $n$. (Clearly, we cannot get $n$ heads in less than $n$ flips.) If $X=n$, that means every flip was a head, so this occurs with probability $p^n$. If $X=n+1$, this means there were $n$ heads and $1$ tail, and the tail can be at any one of the first $n$ spots. (It cannot be the $n+1$-th flip as then $X=n$.) So this occurs at probability $(1-p)p^n\binom{n}{1}$. By similar logic, $X=n+k$ with probability $(1-p)^kp^n\binom{n+k-1}{k}$. So we get $$\mathbb{E}(X) = p^n\sum_{k=0}^\infty (n+k)(1-p)^k\binom{n+k-1}{k}.$$

Intuitively, I want to get the number $n/p$ but how to get this from my sum?

Answer 1

Coming up heads with probability $p$ means that in $N\,$ flips we get $n=pN\,$ heads, so $N=n/p$.

Answer 2

Notice that $$ (n+k)\binom{n+k-1}{k} = \frac{(n+k)(n+k-1)!}{(n-1)!k!} = \frac{(n+k)!}{(n-1)!k!} = n\frac{(n+k)!}{n!k!} =n\binom{n+k}{k}, $$

so letting $x = 1 - p$ we can write $$ E(X) = n (1-x)^n \sum_{k=0}^\infty \binom{n+k}{k} x^k. $$ By the ratio test, the series converges when $\lvert x\rvert < 1$.

But, using the fact that $\displaystyle\binom ab = \binom{a-1}{b-1} + \binom{a-1}b$, if $n \geq 1$ we have \begin{align} \sum_{k=0}^\infty \binom{n+k}{k} x^k &= 1 + \sum_{k=1}^\infty \binom{n+k}{k} x^k && \binom{n+0}{0} x^0 = 1 \\ &= 1 + \sum_{k=1}^\infty \left(\binom{n+k-1}{k} + \binom{n+k-1}{k-1}\right) x^k \\ &= \left( 1 + \sum_{k=1}^\infty \binom{n+k-1}{k} x^k\right) + \sum_{k=1}^\infty \binom{n+k-1}{k-1} x^k\\ &= \sum_{k=0}^\infty \binom{n+k-1}{k} x^k + \sum_{m=0}^\infty \binom{n+m}{m} x^{m+1} && k\to m+1\\ &= \sum_{k=0}^\infty \binom{n+k-1}{k} x^k + x\sum_{k=0}^\infty \binom{n+k}{k} x^k && m \to k\\ \end{align}

and therefore $$ (1 - x) \sum_{k=0}^\infty \binom{n+k}{k} x^k = \sum_{k=0}^\infty \binom{(n-1)+k}{k} x^k, $$ so $$ \sum_{k=0}^\infty \binom{n+k}{k} x^k = \frac{1}{1 - x} \sum_{k=0}^\infty \binom{(n-1)+k}{k} x^k. \tag1 $$

This suggest an inductive proof.

Lemma: If $n \geq 0$ and $\lvert x\rvert < 1$, $$\sum_{k=0}^\infty \binom{n+k}{k} x^k = \frac{1}{(1 - x)^{n+1}}.$$

Proof: For the base case $n = 0,$ $$ \sum_{k=0}^\infty \binom{n+k}{k} x^k = \sum_{k=0}^\infty x^k = \frac{1}{1 - x} = \frac{1}{(1 - x)^{n+1}}. $$

Now assume that for some $n = m \geq 0,$ $$\sum_{k=0}^\infty \binom{n+k}{k} x^k = \frac{1}{(1 - x)^{n+1}}.$$

Then by Equation $(1)$ and the inductive hypothesis, $$ \sum_{k=0}^\infty \binom{(m+1)+k}{k} x^k = \frac{1}{1 - x} \sum_{k=0}^\infty \binom{m+k}{k} x^k = \frac{1}{1 - x} \cdot \frac{1}{(1 - x)^{m+1}} = \frac{1}{(1 - x)^{m+2}}, $$ proving the proposition for $n = m + 1$, which completes the inductive step and proves the lemma. $\square$

Then we can conclude that $$ E(X) = n (1-x)^n \sum_{k=0}^\infty \binom{n+k}{k} x^k = n (1-x)^n \cdot \frac{1}{(1 - x)^{n+1}} = \frac{n}{1-x} $$ and therefore $E(X) = n/p.$

---

But I think a far easier method is to define random variables $Y_1,Y_2,\ldots,Y_n$ so that $Y_1$ is the number of flips up to and including the first head, and for $k \geq 2$, $Y_k$ is the number of flips after the $(k-1)$th head, up to and including the $k$th head. Then $$ X = Y_1 + Y_2 + \cdots + Y_n, $$ so by the linearity of expectation, $$ E(X) = E(Y_1) + E(Y_2) + \cdots + E(Y_n), $$ and since $E(Y_k) = 1/p$ for $1 \leq k \leq n$, $$ E(X) = n\cdot \frac1p = \frac np.$$