Given a gambler's ruin problem where the outcome of each bet is a loss of $1$ with $q = 0.7$ and a win of $2$ with $p = 0.3$. Find the explicit formula for reaching state $10$, starting with $n$ dollars ($n = 0,1,2,...,10$).

My attempt: Let $P_i =$ probability of reaching state $10$ starting in state $i$. Then condition on the first step starting in state $i$, we have:

$P_{i} = p P_{i+2} + q P_{i-1}$ for $i=1,2,\ldots, 9$ ($P_{11} = P_{10}$ since from state $i$, reaching state $11$ is also the same as reaching state $10$).

After I tried very hard to manipulate this recursion, I ended up with $2p_{10} - p_1 - p_2 = \frac{q}{p}P_9$. Using this together with the fact that $\sum_{i=1}^{10}P_i = 1$, we have 2 equations but 3 unknown variables $p_1, p_2, p_9$, so I'm stumbled here.

My question: How could we solve for $p_1$ and $p_2$? Did I set up the recursion incorrectly?

  • $\begingroup$ Why do you say $\sum P_i=1$? That seems unlikely. As to the overall system...well, since $p_0=0$ and $p_{10}=1$ you've got $9$ equations in $9$ unknowns so I assume there is a unique solution (which is likely to be unpleasant). $\endgroup$ – lulu Oct 24 '16 at 0:02
  • 1
    $\begingroup$ You can solve the problem by recurrence relation methods; this requires you to find the roots of $p(x)=0.3x^3-x+0.7$. This turns out to be doable without any fancy machinery because $x=1$ is easily seen to be a root (which would happen regardless of how exactly you chose the value of $p$). Anyway, in your case those roots are all distinct, so the general solution to the recurrence is $P_i=c_1 r_1^i + c_2 r_2^i + c_3 r_3^i$, where $c_1,c_2,c_3$ are arbitrary. Now you're left to choose $c_1,c_2,c_3$ such that $P_0=0,P_{10}=1,P_{11}=1$. $\endgroup$ – Ian Oct 24 '16 at 0:18
  • $\begingroup$ @lulu: because those $P_i$ account for all the possibilities that might occur, don't they?? $\endgroup$ – user177196 Oct 24 '16 at 0:48
  • $\begingroup$ @Ian: thank you for your help. Could you show me how you could derive that $p(x)$ from scratch?I could only get to the recurrence that I stated above, and I could not see how you could get to that nice formula. $\endgroup$ – user177196 Oct 24 '16 at 0:49
  • 1
    $\begingroup$ To do it by recursion methods, as proposed by @Ian, you write your recursion as $pP_{i+2}=P_i-qP_{i-1}$ and then, as is standard for linear recursions, you guess that the solution takes the form $P_n=x^n$. Dividing through by $x^{i-1}$ gives $px^3=x-q$ which is the form he provided. $\endgroup$ – lulu Oct 24 '16 at 1:00

Your Answer

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

Browse other questions tagged or ask your own question.