# Finding expected value with recursion

We'll start off with an example of a question of finding expected value.

What is the expected number of tries to get $$6$$ when rolling dice?

$$\mathbb{E}[x] =1/6*1 + 5/6 * (1+\mathbb{E}[x]) \implies \mathbb{E}(x)=6$$

I understand the intuition, there is a 1/6 probability of getting 6 in one roll and 5/6 of not getting 6, so we roll again and add 1 to the counter since we have done one roll. I wonder what is the formal proof of such method?

• Google the term "law of total expectation". (My answer below explains what that is and how to use it here.) Oct 10, 2013 at 18:30

$\newcommand{\E}{\operatorname{E}}$Google the term "law of total expectation".

The conditional expected value of a random variable $X$ given the event that another random variable (capital) $Y$ is equal to a particular number (lower-case) $y$ is $$\E(X\mid Y=y).$$ That depends on what number $y$ is: it's a function of $y$. So call it $g(y)$. We have $$\E(X\mid Y=y)=g(y).$$ Then we can define $$\E(X\mid Y) = g(Y),$$ which is a random variable in its own right. The conditional expected value of a random variable $X$ given the value of a random variable $Y$ is another random variable that depends on $Y$.

The law of total expectation says that the expected value of that random variable is the same as the expected value of $X$: $$\E(\E(X\mid Y)) = \E(X).$$

So let $X$ be the number of trials needed to get "$6$" when you throw the die.

Let $Y$ be the number of "$6$"s that appear on the first trial, so $Y$ is either $0$ or $1$.

Then \begin{align} \E(X\mid Y=1) & = 1, \\[6pt] \E(X\mid Y=0) & = \E(X)+1. \end{align} In other words, given that you got a "$6$" on the first trial, the conditional expected value of $X$ is $1$, and given that you failed to get a "$6$" on the first trial, the conditional expected value of $X$ is $1$ more than it would otherwise have been.

Now notice that \begin{align} \E(X\mid Y) = \begin{cases} 1 & \text{with probability }1/6, \\[6pt] 1+\E(X) & \text{with probability }5/6. \end{cases} \end{align}

So $$\E(X) = \E(\E(X\mid Y)) = \frac16\cdot1 + \frac56\cdot(1+\E(X)).$$ So you have an algebraic equation $$w = \frac16\cdot1+\frac56\cdot(1+w).$$

• Sorry for my late reply, how do you explain E(X|Y=0)=E(X)+1 algebraically (not intuitively)? Where does the E(X) come from? Nov 8, 2013 at 6:20
• $\mathbb E(X\mid Y=0)$ $= \sum_{x=1}^\infty x \Pr(X=x\mid Y=0)$ $=\sum_{x=2}^\infty x \Pr(X=x\mid Y=0)$. The lower bound of summation changed from $1$ to $2$ because if $Y=0$ then $X\ne1$, so $\Pr(X=1\mid Y=0)=0$. Next: $\Pr(X=x\mid Y=0)$ $=\Pr(\text{failure on 2nd through$(x-1)$th trials and succes on the next trial} \mid Y=0 )$. By independence of trials, this is equal to $\Pr(\text{$x-2$consecutive failures and then one success})$, but that is the same as $\Pr(X=x-1) = \Pr(X+1 = x)$. So we have $\Pr(X\mid Y=0)=\Pr(X+1=x)$. In short: the conditional distribution of.... Nov 8, 2013 at 19:54
• ... $X$ given that $Y=0$ equals the unconditional distribution of $X+1$. Hence $\mathbb E(X\mid Y=0)=\mathbb E(X+1)$. Nov 8, 2013 at 19:55
• and... how is E(x + 1) = E(x) + 1 ? can you pls make the final connection. I dint understand sorry I am just too weak Dec 6, 2020 at 19:37

The process is memoryless so $\Pr(X=i\mid X \gt n) = \Pr(X=i-n)$.

So $$E[X] = \sum_{i=1}^\infty i \Pr(X=i)$$ $$= \Pr(X=1) + \sum_{i=2}^\infty i \Pr(X=i\mid X \gt 1) \Pr(X \gt 1)$$ $$= \Pr(X=1) + \Pr(X \gt 1) \sum_{j=1}^\infty (1+j) \Pr(X=j)$$ $$= \Pr(X=1) + \Pr(X \gt 1) \sum_{j=1}^\infty \Pr(X=j)+ \Pr(X \gt 1) \sum_{j=1}^\infty j \Pr(X=j)$$ $$= \Pr(X=1) + \Pr(X \gt 1)(1+ E[X])$$

though this is easily simplified to $E[X]= 1 + \Pr(X \gt 1) E[X]$ or $E[X]= 1 / \Pr(X = 1)$.