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"

  • 4
    $\begingroup$ 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. $\endgroup$ – Nick Peterson Jul 29 '13 at 12:30
  • $\begingroup$ 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. $\endgroup$ – ThePunisher Jul 29 '13 at 12:40
  • 2
    $\begingroup$ Looks like a generalized $1D$ Random walk. $\endgroup$ – Samrat Mukhopadhyay Jul 29 '13 at 13:00
  • 1
    $\begingroup$ 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. $\endgroup$ – Samrat Mukhopadhyay Jul 29 '13 at 13:02
  • $\begingroup$ I think the last word is "game." As in, "... to finish the game." $\endgroup$ – apnorton Jul 29 '13 at 13:15

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?

  • $\begingroup$ 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. $\endgroup$ – ThePunisher Aug 1 '13 at 10:05
  • 1
    $\begingroup$ 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. $\endgroup$ – Did Aug 1 '13 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.