0
$\begingroup$

Consider the Gambler's Ruin Problem: at each play of the game the gambler's fortune increases by one dollar with probability 1/2 or decreases by one dollar with probability 1/2. The game is over when the gambler's fortune either reaches 0 or N dollars. Define $M_{i}$ the mean time (i.e., the mean number of plays) it takes to reach either state 0 or N when the gambler starts the game with i dollars.

a) Explain why $M_{i} = 1 + 1/2M_{i-1} +1/2M_{i+1}$; for i = 1, 2,.... ,N -1:

b) The solution of this recurrence is $M_{i} = -i^2/2+ Ci + D;$ for $i = 0, 1, ... .N,$ for some constants C and D. Find $M_i$ (i.e., find $C$ and $D$ in the above expression). I know how to obtain a, but not sure how to start for b. I tried subbing the quadratic into part a but no luck. Thanks.

$\endgroup$
  • 1
    $\begingroup$ Hint: What is $M_0$ and $M_N$? $\endgroup$ – dromastyx Apr 7 '18 at 13:16
  • $\begingroup$ @dromastyx Are both 0?? $\endgroup$ – Xstuds Apr 8 '18 at 2:21
0
$\begingroup$

If you know what $M_0$ is, say $M_0 = a$, and $M_N$, say $M_N = b$, then you can substitute in to obtain $$ a = M_0 = D \quad\text{and}\quad b = M_N = -N^2/2 + C \cdot N + D, \quad\text{and so}\quad C = (B+N^2/2-a)/N. $$ Now, what are $a$ and $b$? How long does it take to hit either $0$ or $N$ when you start from $0$ and when you start from $N$?

$\endgroup$
  • $\begingroup$ Are both zero?? $\endgroup$ – Xstuds Apr 7 '18 at 22:54
  • $\begingroup$ Exactly! :) -- given this, can you see the solution now? :) $\endgroup$ – Sam T Apr 8 '18 at 21:57

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.