Expected number of flips until kth head

The trick is to write $X = X_1 + X_2 + \dots + X_k$, where $X_i$ is "the expected number of flips to get the $i$th head after getting the $(i-1)$th head".

Now it is not too hard to see that each $X_i$ is identically distributed and that the probability that $X_i = j$ (for $j \geq 1$) is equal to $p(1-p)^{j-1}$. (In other words, each $X_i$ is a geometric random variable). A simple calculation shows that $\mathbb{E}[X_i] = \frac{1}{p}$, so by linearity of expectation $\mathbb{E}[X] = \frac{k}{p}$.

You want the expected sum of $k$ geometric distributed random variables with iid success parameter $p$.

The expected number of tosses until the first head is $\mathsf E(X_1)= 1/p$

The expected number of tosses after the first until the second head is $\mathsf E(X_2-X_1) = 1/p$.

So the expect number of tosses until the second head is: $\mathsf E(X_2) = 2/p$

And so forth.

Thus the expect number of tosses until the $k$ head is: $\mathsf E(X_k) = k/p$

A way to do this directly is just to set up a recursion. In the first flip, two things can happen

• Heads with prob $p$ (after which we have to wait for $n-1$ heads) and
• Tails with prob $1-p$ (after which we are exactly where we started from).

This gives the recursion

$$E_{n,p} = p (1+E_{n-1,p}) + (1-p)(1+E_{n,p})$$

which solves to

$$E_{n,p} = 1/p + E_{n-1,p}$$

Along with the fact that $E_{0,p} = 0$, this gives the answer $E_{n,p}=n/p$.