4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Douglas Fir Sep 8 '15 at 3:27
  • 2
    $\begingroup$ 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. $\endgroup$ – Henry Sep 8 '15 at 7:06
7
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.