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