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