Expected number of flips until kth head

Question

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.

Answer 1

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

Answer 2

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$

Answer 3

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

Answer 4

Let $X$ be the random variable representing the number of flips until the $k$th head. Let $X_i$, $i \in \{1, ... k\}$ be the number of flips from the occurrence of the $(i-1)$th head to the $i$th head.

Because geometric random variables are memoryless, we have $$ \mathbb{E}[X_i] = \frac{1}{p} $$

By the linearity of expectation, $$ \mathbb{E}[X] = \sum_{i=1}^k \mathbb{E}[X_i] = \frac{k}{p} $$