# Expected number of times a coin is flipped until it lands on "heads"

I found a solution to this problem somewhere but I'm unsure about the solution.

It uses a first time head case and a first time tail case to create a recursive equation and solves for $E(x)$.

$E(x) = p + (1-p)[1+E(x)]$ where $p$ is probability of getting heads, and $E(x)$ is the expected number of coin tosses until landing on heads.

But what if I add the third case too?

$E(x) = p + (1-p)[1+E(x)] + (1-p)^2[2+E(x)]$

That would give me a different answer. Can someone please clarify this to me?

• @fabee $E(x) < p + (1 - p)[1 + E(x)]$ holds true iff $E(x) < p$. How can LHS be always less than RHS? Commented Oct 2, 2015 at 14:41
• What is 'the third case' you added? Commented Oct 2, 2015 at 14:43
• @fabee perhaps you would like to look at my proof below. Commented Oct 2, 2015 at 14:46
• The third case was if we get 2 consecutive tails with probability $(1-p)^2$ but of course the expected value gets increased by 2 just like it's done for first tail (incrementing by 1) Commented Oct 2, 2015 at 14:46
• @PiyushShandilya the thirds case is included in the second term. The second term includes all cases where you don't get heads on the first toss. Commented Oct 2, 2015 at 14:47

The first answer is correct. Let's say we flip a coin with bias $p$ (probability of heads) until it lands on heads, and the number of tosses is $X$. I'll demonstrate a more direct calculation and then you'll see why the recursive calculation works.

$$\mathbb{E}[X] = 1p + 2p(1-p) + 3p(1-p)^2 + 4p(1-p)^3 + \dots$$

This is because if $X = n$, there have been $(n-1)$ tails and then $1$ heads. Now let's try to relate this to your expression. We are going to add $1$ to both sides but on the right hands side it will be in a tricky form.

$$1 = p + p(1-p) + p(1-p)^2 + \dots = P(1) + P(2) + + P(3) \dots$$

So then we have,

$$\mathbb{E}[X] + 1 = 2p + 3p(1-p) + 4p(1-p)^2 + 5p(1-p)^3 + \dots$$

So if we multiply both sides by $(1-p)$ and add $p$ we have,

$$p + (1-p)(\mathbb{E}[X] + 1) = p + 2p(1-p) + 3p(1-p)^3 + \dots = \mathbb{E}[X].$$

That concludes the proof, but how about the intuition. The intuition is that when you start flipping, with probability $p$ you finish on one flip, so let's add $$1 \cdot p$$ to the expectation. With probability $(1-p)$ you get a tails and pretty much start all over again, but of course you have wasted a flip. So we add $$(1-p)(1 + \mathbb{E}[X])$$ to the expectation. Hope that helps. If you have any questions, please comment.

The question does not clearly define the three cases. The problem is either that the cases are not mutually exclusive or that the probability of one of those is wrong. In this answer, I explain the solution for two cases (which is already contained in the question) and (a) solution for three cases.

NB: I assume the coin flips are independent and each particular is heads with probability $$p$$ (and tails when not heads). This seems the intended assumption, but is not clearly stated in the question. Also, I assume the toss resulting in heads is counted in $$x$$.

## Two cases

Since either the first flip is heads (denote by $$H$$), or the first flip is tails ($$T$$) (these two events are mutually exclusive and cover the sample space), the expectation may be decomposed as $$$$E(x) = P(H) \cdot E(x \mid H) + P(T) \cdot E(x \mid T).$$$$ By definition of $$p$$, we have $$P(H) = p$$ and $$P(T) = 1-p$$. $$E(x \mid H)$$ is the expected number of tosses until heads if the first toss results in heads. But in that case, exactly one toss occurs, so $$E(x \mid H) = 1$$. $$E(x \mid T)$$ is the expected number of tosses until heads if the first toss results in tails. Due to the independence assumption, after the first toss the situation is exactly the same as in the beginning, except that we must count the toss already occurred. So, $$E(x \mid T) = 1 + E(x)$$. Substituting all these into the previous equation, we get $$$$E(x) = p + (1-p)\, (1 + E(x)).$$$$

### Three cases

Consider the following three cases:

1. First toss results in heads (denote by $$H$$)
2. First toss results in tails, second in heads (denote by $$TH$$)
3. Both first two tosses result in tails (denote by $$TT$$)

Again, $$H$$,$$TH$$,$$TT$$ are mutually exclusive and cover the entire sample space, so we may write $$$$E(x) = P(H) E(x \mid H) + P(TH) E(x \mid TH) + P(TT)E(x \mid TT).$$$$ $$P(H)$$ and $$E(x \mid H)$$ are as before. $$P(TH)$$ is $$(1-p)\,p$$ and $$P(TT)$$ is $$(1-p)^2$$. $$E(x \mid TH)$$ is the expected number of tosses if the first heads are obtained in the second toss, so $$E(x \mid TH) = 2$$. Finally, if first two tosses result in tails, the situation is exactly like in the beginning, except that one needs to count the two already occurred tosses, so $$E(x \mid TT) = 2 + E(x)$$. Substituting these into the equation above, $$$$E(x) = p + 2\,p\,(1-p) + (1-p)^2\, (2 + E(x)).$$$$

## Conclusion

Both the equation for two cases and the equation for three cases result in $$E(x) = \frac{1}{p}$$.

On the other hand, the recursion in the question looks like $$$$E(x) "=" P(H)\,E(x | H) + P(T)\,E(x | T) + P(TT)\,E(x | TT)$$$$, but this is not valid since $$H$$,$$T$$ and $$TT$$ are not mutually exclusive (indeed, $$TT$$ is contained in $$T$$).

The expected number of steps on the first flip is $$s = E[x]$$.

The first flip must always take place so we must always spend one flip. If we succeed we are done. But, if not, we have to start over so $$s = 1 + (1-p) s$$ So $$s p = 1$$ and $$s = \frac{1}{p}$$.

Another way to write this is: $$s_1 = 1 + (1-p)s_2$$. Since the expected number of steps is the same no matter what iteration we are at we have $$s_1 = s_2 = s_3$$ so we can write

$$s_1 = 1 + (1-p)(1 + (1-p)s_3)$$ This gives $$s = 1 + (1-p) + (1-p)^2 s$$ and $$s (2 -p)p = 2 -p$$ and again $$s = \frac{1}{p}$$.