# Expected value of getting to plus or minus twenty.

We start with our game in the box number $0$. We throw a die with: "$+1$", "$+2$", "$+3$", "$-1$", "$-2$" and "$-3$" written on its faces. After each throw we move to the right of the number of boxes shown by the die. Once we get to the box number $+20$ (or more) or $-20$ (or less) the game is finished. What is the expected value of throw to finish the game?

My first idea was to work with 41 functions from $f_{-20}(n)$ to $f_{+20}(n)$ defined as following:

$f_x(n)$ is the probability that after $n$ throws we are in the box number $x$ without having finished the game before. we can easily see by symmetry that: $$f_x(n)=f_{-x}(n)$$ Therefore we can work with 21 functions. Then I saw that $f_x(0)$ is 0 for every $x$ except $x=1$. And I could find a recurrence relation for every function such as: $f_4(n+1)=\frac{1}{6}\left(f_1( n ) + f_2( n ) +f_3( n ) +f_5( n ) +f_6( n ) +f_7\ (n) \right)$

I'm afraid that I'll have to solve an equation of degree 20 in order to find a formula for $f_{20}(n)$. Then the expected value would be: $$\sum_{i=0}^{\infty}2\cdot f_{20}(i)$$ ($2$ comes from the simmetry)

This approach only gives me a nice hint on how to find a numerical answer with excel, but I don't care about the numerical result, I only mind the proper solution.

I thought that Catalan numbers or the proof of the formula for Catalan numbers might come useful but the only way i could find something useful with them is when the dice has only the faces "+1" and "-1"

• Welcome to Math.SE! Please, consider updating your question to include what you have tried / where you are getting stuck. You will find that people on this site will be significantly faster to help you if you do that; that way, we know exactly what help you need. – Nick Peterson Jul 29 '13 at 12:30
• Thank you. But I didn't have much clue of how I could get to the solution. I've even tried numerically with excel... I'll update the question anyway. – ThePunisher Jul 29 '13 at 12:40
• Looks like a generalized $1D$ Random walk. – Samrat Mukhopadhyay Jul 29 '13 at 13:00
• You can use Martingales to find this out, observe that the process $\{S_n\}$ where $S_n$ is the number of the box at step $n$ is a Martingale. – Samrat Mukhopadhyay Jul 29 '13 at 13:02
• I think the last word is "game." As in, "... to finish the game." – apnorton Jul 29 '13 at 13:15

## 1 Answer

The usual approach is to consider simultaneously the mean $t_x$ of the number of steps needed to reach $+20$ or more or $-20$ or less, starting from each integer value $x$. Then $t_x=0$ for every $|x|\geqslant20$ and, for every $|x|\lt20$, $$t_x=1+\tfrac16(t_{x-3}+t_{x-2}+t_{x-1}+t_{x+1}+t_{x+2}+t_{x+3}).$$ A frequent continuation is to introduce the generating function $$g(s)=\sum_xt_xs^x,$$ and to deduce from the linear system solved by $(t_x)$ and described above, a functional relation solved by $g(s)$. Then the idea is to identify $g(s)$, and finally the constant coefficient $t_0$ of the function $g$.

In the present case, one could use the fact that, due to the symmetry of the model, $(t_x)$ is even hence the linear system involves $20$ nonzero unknown quantities $(t_x)_{0\leqslant x\leqslant19}$ instead of $39$. Likewise, $g(s)=g(1/s)$ for every $s\ne0$. But does this really simplify things?

• Thank you very much, your hint looks powerful but I still have some doubts. Is the mean $t_x$ of the number of step needed the same as the expected value? And how would you work with such a generating function? It would be helpful if you can link me a page where a similar problem with generating functions is tackled. – ThePunisher Aug 1 '13 at 10:05
• In this context, "mean number of steps" = "expected number of steps" (sorry for the confusion). // For a reference, basically every set of lecture notes on random walks includes this, see for example this one available on Lalley's page. – Did Aug 1 '13 at 10:11