# Expected number of flips until kth head

We flip a biased coin (P (head) = p) continously until we observe k heads, and then we stop. Let X be the number of flips. Find E[X].

My intuition tells me this should be a very simple problem, but I'm somehow struggling with it. I've tried to derive the distribution for X, then summing that over k to infinity, but the sum is not easy to evaluate.

Thanks for any help.

• This could be modeled by a negative binomial random variable, as you have independent Bernoulli trials, and you are looking for the n-th success. – Douglas Fir Sep 8 '15 at 3:27
• At an intuition level, heads appear with a rate $p$ and so after $n$ flips you expect $np$ heads. Setting this equal to $k$ would give $n=\frac{k}{p}$. This needs more work to be a proof, but does give the correct answer simply. – Henry Sep 8 '15 at 7:06

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