3
$\begingroup$

You flip a coin until you get a total of n heads. What is the expected number of flips this will take? In terms of Expectation, E[x] and Variance Var(x).

Edit: The heads don't have to be consecutive.

$\endgroup$
1
  • $\begingroup$ Do you know what is the expected number of flips to get one head? $\endgroup$
    – DirkGently
    Oct 22, 2015 at 18:47

2 Answers 2

6
$\begingroup$

Here is another way to solve it.

Let probability $p$ of flipping a Head and let $N_{k}$ be the number of flips when the $k$th Head has appeared.

Then imagine you are about to flip the first coin. Flipping this coin adds 1 flip to the amount of work we have done. If it is Heads, it reduces the work remaining by 1 flip (so the work remaining is $E[N_{k-1}]$). Otherwise, it doesn't help and we are in the same spot as before, with just as much work remaining even after flipping this coin:

$$E[N_{k}] = 1 + pE[N_{k-1}] + (1-p)E[N_{k}]$$

Solving for $E[N_{k}]$ gives:

$$E[N_{k}] = \frac{1}{p} + E[N_{k-1}]$$

By substituting the recurrence formula in for $E[N_{k-1}]$ we see that

$$E[N_{k}] = \frac{1}{p} + \sum_{j=1}^{k-1} \frac{1}{p} = \sum_{j=1}^{k}\frac{1}{p} = \boxed{\frac{k}{p}}$$

We can push further to get the variance as well. From this point, let's say $p = \frac{1}{2}$ for convenience, though the same derivation will work using $p$ and $(1-p)$ as needed.

Let's start by getting rid of the intuitive recurrence trick for $E[N_{k}]$ and try writing down the probability mass function for $E[N_{k}]$ so that the recurrence is more explicit. For convenience, let $F$ denote the result of the first flip.

$$P(N_{k} = n) = P(N_{k} = n|F = H)P(F = H) + P(N_{k} = n|F = T)P(F = T)$$ $$P(N_{k} = n) = \frac{1}{2}P(N_{k-1} = n - 1) + \frac{1}{2}P(N_{k} = n - 1)$$

The expectation can be written (pulling out the $\frac{1}{2}$ factor, and separating into two sums for the two terms):

$$E[N_{k}] = \frac{1}{2}\sum_{j=k}^{\infty}jP(N_{k-1} = j - 1) + \frac{1}{2}\sum_{j=k}^{\infty}jP(N_{k} = j - 1)$$

Rewrite $j$ as $j - 1 + 1$ inside the summands, allowing you to collect together the $(j - 1)$ terms (to get the sums to match some formula for an expected value we know of), and terms that use the extra $+1$ just summing probabilities. This leads to 4 terms:

$$E[N_{k}] = \frac{1}{2}\sum_{j=k}^{\infty}P(N_{k-1} = j - 1) + \frac{1}{2}\sum_{j=k}^{\infty}(j - 1)P(N_{k - 1} = j - 1) $$ $$ + \frac{1}{2}\sum_{j=k}^{\infty}P(N_{k} = j - 1) + \frac{1}{2}\sum_{j=k}^{\infty}(j - 1)P(N_{k} = j - 1)$$

The first term is just $\frac{1}{2}$ times the sum over all probabilities for values that $N_{k-1}$ can take, so it must be $\frac{1}{2}$. To see it, let $i = j - 1$ to see that the sum goes over all permissible values of $i$ for $P(N_{k-1} = i)$.

The third term has to be $\frac{1}{2}$ for similar reasons. Note that $P(N_{k} = k - 1)$ is obviously $0$, so you can drop the first term of the sum and then change the index to $i = j - 1$ and the sum ranges from $k$ to $\infty$.

The same two index tricks work for the 2nd and 4th terms, but since these involve multiplying by $j - 1$, after the index tricks, the terms are the expected value formulas for $N_{k-1}$ and $N_{k}$ respectively.

As a result, we get the same recurrence formula for $E[N_{k}]$ that we got by appealing to intuition earlier, but this time from expanding out the formal definition of $E[N_{k}]$ in terms of its probability mass function:

$$E[N_{k}] = 1 + \frac{1}{2}E[N_{k - 1}] + \frac{1}{2}E[N_{k}]$$

Since we know $E[N_{k}]$, to get the variance, we must repeat this process for $E[N_{k}^{2}]$, which we can do since we have the probability mass function. I'll go ahead and pull out the factor of $\frac{1}{2}$ again and split into two sums (just putting $j^{2}$ instead of $j$ in the summand of the earlier formula for $E[N_{k}]$):

$$E[N_{k}^{2}] = \frac{1}{2}\sum_{j=k}^{\infty}j^{2}P(N_{k - 1} = j - 1) + \frac{1}{2}\sum_{j=k}^{\infty}j^{2}P(N_{k} = j - 1)$$

This time, we can't just simply transform $j$ to $j - 1 + 1$ to get the summands to match the form of expectations we know. We need $(j - 1)^{2}$, so since $(j - 1)^{2} = j^{2} - 2j + 1$, we need to add and subtract $(-2j + 1)$, and then pull out the extra part into another sum. Once again it results in 4 terms we can individually handle.

$$E[N_{k}^{2}] = \frac{1}{2}\sum_{j=k}^{\infty}(2j - 1)P(N_{k-1} = j - 1) + \frac{1}{2}\sum_{j=k}^{\infty}(j - 1)^{2}P(N_{k-1} = j - 1)$$ $$+ \frac{1}{2}\sum_{j=k}^{\infty}(2j - 1)P(N_{k} = j -1) + \frac{1}{2}\sum_{j=k}^{\infty}(j - 1)^{2}P(N_{k} = j - 1)$$

The same indexing tricks work again, but we get more terms in the result. The factor of 2 on the $2j$ terms will cancel with the $\frac{1}{2}$, meaning both of the "$j$" terms will need us to recursively use the same trick from the steps for $E[N_{k}]$, namely subtracting and adding $1$ to get $j-1$, and pulling out the extra sums.

This will result in the $E[N_{k-1}]$ and $E[N_{k}]$ that we know from before, plus two separate sums over all the probabilities, giving an additional $+2$.

The "$-1$" terms are the same sum over all the probability terms, so these each are $\frac{-1}{2}$ and add together to $-1$.

Finally, as before, we can re-index the "$(j-1)^{2}$" terms to express $E[N_{k-1}^{2}]$ and $E[N_{k}^{2}]$ respectively.

And remember, assuming $p=\frac{1}{2}$ and using the original result, $E[N_{k}] = 2k$.

Putting it all together:

$$E[N_{k}^{2}] = -1 + 2 + E[N_{k-1}] + E[N_{k}] + \frac{1}{2}E[N_{k-1}^{2}] + \frac{1}{2}E[N_{k}^{2}]$$ $$\frac{1}{2}E[N_{k}^{2}] = 1 + 2(k - 1) + 2k + \frac{1}{2}E[N_{k - 1}^{2}]$$ $$E[N_{k}^{2}] = 8k - 2 + E[N_{k - 1}^{2}]$$

and substituting the recurrence in for $E[N_{k-1}^{2}]$ gives

$$E[N_{k}^{2}] = \sum_{j=1}^{k}(8j - 2) = 8\frac{k(k+1)}{2} - 2k = 4k^{2} + 2k$$

Subtract $E[N_{k}]^{2}$ to get the variance:

$$Var(N_{k}) = 4k^{2} + 2k - (2k)^{2} = \boxed{2k}$$

To verify this, we can also solve this by viewing $N_{k}$ as the summation of $k$ independent geometric random variables, where each one describes how many flips until the next Head.

The expected value of each will be $2$ (from $\frac{1}{p}$), and the variance of each is $\frac{1/2}{1/4} = 2$ (from $\frac{1-p}{p^{2}}$).

$$E[N_{k}] = \sum_{i=1}^{k}2 = \boxed{2k}$$ $$Var(N_{k}) = \sum_{i=1}^{k}2 = \boxed{2k}$$

Personally, I never find it easy or intuitive to postulate that a variable like $N_{k}$ happens to be the summation of independent variables with some known distribution. I start to second guess myself that there must be some conditional dependence relationship between the current geometric random variable and the previous ones.

As a result, I find the verbose approach forcing the issue with the actual probability mass function to be more informative and gives more assurance that I'm not misusing intuition or assuming the problem can be decomposed in a way that it cannot.

$\endgroup$
1
  • $\begingroup$ Great thorough answer that deserves a lot of credit. $\endgroup$ Apr 16, 2018 at 23:24
3
$\begingroup$

Let $X_1$ be the number of coin tosses until the first head, $X_2$ be the number of coin tosses after that until the second head, and so on. We want $E[X]$ where $X = X_1 + X_2 + \dots + X_k$. By linearity of expectation, we have $E[X] = E[X_1] + E[X_2] + \dots + E[X_k]$.

For any $i$, $E[X_i]$ is the expected number of coin tosses until a head appears which is equal to $\dfrac{1}{p}$.

Therefore, we have $E[X] = \dfrac1p + \dfrac1p + \dots + \dfrac1p = \dfrac{k}p$. Put $k=n$ to get your answer.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .