Conditional expectation of coin flipping

Question

A fair coin is flipped successively until head appears for the second time. What is the expected number of flips necessary?

I'm not sure if the heads appear in a row or non-consecutively? And how do I approach the problem in the latter case?

Thanks.

Answer 1

Hint:

Write $X= X_1 + X_2$ where $X_1$ is the number of flips until the first head appear and $X_2$ is the number of flips required to get the second head after the first head.

Try to answer the following question: What distribution does $X_i$ follows? Do you know the expectation for that distribution.

Use linearity of expectation.

Answer 2

I think this is called the negative binomial distribution in general. The heads need not appear consecutively, they could be anywhere, e.g. $TTHTTTTH$ etc.

So, what you need effectively is the answer to this question : what is the probability that given a positive integer $k$, the second head appears on the $k$th toss?

For this, note that the probability of a head or tail is $\frac 12$ anyway. Imagine an experiment where a coin is tossed $k$ times. The outcomes will be filled in these boxes : $$ -----...----- $$

Now, we know that if a second head appears on the kth toss, then the last toss of these, the kth toss, was a head. Now, our outcome looks like: $$ ----- ... ----\color{blue}H $$ What do we know now? We know that there has been exactly one head before this. Where could it have occurred? Anywhere before. Hence, any one of these is legitimate: $$ \color{blue}H ----...----\color{blue}H \\ -----...--\color{blue}H -- \color{blue}H \\ ---\color{blue}H-...----\color{blue}H $$
and so on.

Therefore, a successful outcome is obtained as follows : choose a position between $1$ and $k-1$, where the first head will occur, and that determines the outcomes entirely. Hence, the answer is just $\frac{(k-1)}{2^k}$, since we are to choose $1$ position, in $k-1$ ways, and the probability of a head/tail is one-half, to be exponentiated $k$ times since there are $k$ flips of the coin.

Hence, the probability of succeeding at the $k$th toss is precisely $\frac{k-1}{2^k}$. Therefore, the expected value is just the sum $\sum_{k=1}^\infty \frac{k(k-1)}{2^k}$. Can you calculate this value by yourself?

EDIT : The formula comes from differentiation. So what we do is, start with the formula $\sum_{i=0}^\infty x^i = \frac{1}{1-x}$ under $|x| < 1$.

We can differentiate both sides to get $\sum_{i=0}^\infty ix^{i-1} = \frac{1}{(1-x)^2}$.

Multiply both sides by $x$ to get $\sum_{i=0}^\infty ix^i = \frac{x}{(1-x)^2}$.

Repeat the differentiation to get $\sum_{i=0}^\infty i^2x^{i-1} = \frac{(1+x)}{(1-x)^3}$, after simplifying the result of the division rule for differentiation. Multiply again by $x$ to get $\sum_{i=0}^\infty i^2x^i = \frac{x(1+x)}{(1-x)^3}$.

Now, note that $\sum_{k=1}^\infty \frac{k(k-1)}{2^k} = \sum_{k=1}^\infty \frac{k^2}{2^k} - \sum_{k=1}^\infty \frac{k}{2^k}$. If $x = \frac 12$, this is equal to $\frac{x(1+x)}{(1-x)^3} - \frac{x}{(1-x)^2}$, which in our case is $6-2=4$.

Finally, this can be repeated for three heads as follows : instead of choosing one position between $1$ and $k-1$ for a head, you must now choose two succh positions. This is done in $\binom{k-1}{2}$ ways, not $\frac{2(k-1)}{2^k}$, because if you are choosing two positions, then you choose one position, and then while choosing the second one you can't choose the first one again, so the number of possibilities reduces by $1$. So the new probability would just be $\frac{\binom {k-1}2}{2^k} = \frac{(k-1)(k-2)}{2^{k+1}}$.