# What is the expected number of coin tosses needed to obtain a head?

Due to my recent misunderstandings regarding the 'expected value' concept I decided to post this question. Although I have easily found the answer on the internet I haven't managed to fully understand it.

I understood that the formula for the expected value is:

$$E(x) = x_1p_1 +x_2*p_2 +...+x_np_n$$

The x's are the possible value that the random variable can take and the p's are the probabilites that this certain value is taken.

So, if I get a head on the first try, then $p_1 = \frac{1}{2} , x_1 = 1$ If I get a head on the second try, then $p_2 = \frac{1}{4} , x_2 = 2$

And then, I woudl have that:

$$E(x) = \frac{1}{2}1+ \frac{1}{4}2 +...$$

So my reasoning led me to an inifnite sum which I don't think I can't evaluate it that easy. In the 'standard' solution of this problem, the expected value is found in a reccurisve manner. So the case in which the head doesn't appear in the first toss is treated reccursively. I haven't understood that step.

My questions are: is my judgement correct? How about that reccursion step? Could somebody explain it to me?

• For fun, I would say 2. =) – Vincent Aug 27 '14 at 15:46
• Yes, I knew that too. :D I just didn't know how we found that answer – Bardo Aug 27 '14 at 15:48

Let $X$ be the number of tosses, and let $e=E(X)$. It is clear that $e$ is finite.

We might get a head on the first toss. This happens with probability $\frac{1}{2}$, and in that case $X=1$.

Or else we might get a tail on the first toss. In that case, we have used up $1$ toss, and we are "starting all over again." So in that case the expected number of additional tosses is $e$. More formally, the conditional expectation of $X$ given that the first toss is a tail is $1+e$.

It follows (Law of Total Expectation) that $$e=(1)\cdot\frac{1}{2}+(1+e)\cdot\frac{1}{2}.$$

This is a linear equation in $e$. Solve.

Remark: The "infinite series" approach gives $$E(X)=1\cdot\frac{1}{2}+2\cdot\frac{1}{2^2}+3\cdot\frac{1}{2^3}+\cdots.$$ This series, and related ones, has been summed repeatedly on MSE.

• Conditioning like I did is a totally standard technique in the calculation of expectation. – André Nicolas Aug 27 '14 at 16:01
• Well, perhaps you can use the series approach for general $p$, and the equation $e=p+(1+e)(1-p)$, and see that they give the same answer. – André Nicolas Aug 27 '14 at 16:09
• Given that the first toss is a tail, $E(X)=1+e$. – André Nicolas Aug 27 '14 at 16:10
• It is not true that with probability $1/2$ you will need $1+e$. What is true is that given the first is tail the total expected number of tosses is $1+e$. – André Nicolas Aug 27 '14 at 16:24
• @Bardo Note that in your previous question in my solution we use essentially the same trick (in a slightly more complex situation). – Aahz Aug 27 '14 at 16:34

Your approach is perfectly fine. The probability of getting the first head in the $n$th trial is $\frac{1}{2^n}$, so we have $$\mathbb{E}(x) = \sum_{ n \geq 1} \frac{n}{2^n}.$$ This infinite sum can be calculated in the following way: first note that $\frac{1}{1-x} = \sum_{n \geq 0} x^n$ for $|x|<1$. Differentiating both sides yields $$\frac{1}{(1-x)^2} = \sum_{n \geq 0} n x^{n-1} = \sum_{n \geq 1} n x^{n-1} = \frac1x \sum_{n \geq 1} n x^n.$$ Pluggin in $x = \frac12$ yields $4 = 2 \sum_{n \geq 1} \frac{n}{2^n} = 2 \mathbb{E}(x)$, or $\mathbb{E}(x) = 2$.

The recursive solution goes, I think, as follows: let $\mathbb{E}(x)$ be the expected number of trials needed. Then the expected number of trials needed after the first trial, given that it was not heads, is also $\mathbb{E}(x)$. In other words, the expected (total) number of trials is $\mathbb{E}(x)+1$ in that case. This gives the equation $$\mathbb{E}(x) = \frac12 + \frac12(\mathbb{E}(x)+1)$$ which gives the same answer $\mathbb{E}(x) = 2$.

• It's good to know that my approach wasn't incorrect, it gives me a little confidence. I am no thinking about that reccursion step. – Bardo Aug 27 '14 at 15:54

To make ends meet... You have been explained by several users that, looking at the toss process itself, one sees that the expectation $E(X)$, that you know is $E(X)=S$, with $$S=\sum_{n\geqslant1}\frac{n}{2^n},$$ solves the relation $$E(X)=1+\frac12E(X).$$ It happens that one can also show directly that $$S=1+\frac12S,$$ this relation following from a shift of indexes. To do so, note that $S=R+T$ with $$R=\sum_{n\geqslant1}\frac{1}{2^n},\qquad T=\sum_{n\geqslant1}\frac{n-1}{2^n},$$ hence, using the change of variable $n=k+1$, $$T=\sum_{k\geqslant0}\frac{k}{2^{k+1}}=\frac12\sum_{k\geqslant0}\frac{k}{2^k}=\frac12\sum_{k\geqslant1}\frac{k}{2^k}=\frac12S,$$ hence the proof would be complete if one knew that $$R=1.$$ To show this, use the same trick once again, that is, note that $$R=\frac12+\sum_{n\geqslant2}\frac{1}{2^n}=\frac12+\sum_{k\geqslant1}\frac{1}{2^{k+1}}=\frac12+\frac12\sum_{k\geqslant1}\frac{1}{2^{k}}==\frac12+\frac12R,$$ hence the proof that $S=2$ is complete.

• Yes, I got it...I knew beforehand the trick of shifting indexes, so I totatly understood your argument..But I am still struggling to undesrtande the simpler argument..Thank you very much! – Bardo Aug 27 '14 at 18:29