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

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.