# Gambler's Ruin Problem with Simple Solution - Different Approach

What is the probability that symmetric simple random walk starting at the origin reaches $$−1$$ before it reaches $$9$$? Briefly explain your answer.

Solution: This is $$p = 1$$ gambler's ruin with states $$0, 1, . . . , 10$$ but the states have been relabelled $$−1, 0, . . . , 9$$. The answer is $$\frac{9}{10}$$ because state 0 is one tenth of the way from $$−1$$ to $$9$$.

Unfortunately, I used a different and rather clumsy way to approach this question.

My attempt was not successful but I was wondering if there is anyone who can tell me how to go further with it and arrive at the solution.

My attempt: I drew it out like birth and death process with 11 states. With $$-1$$ and $$9$$ having the probability of returning to itself as 1 (absorbing state). Let's $$P(X_i)$$ be probability to reach $$-1$$ before reaching $$9$$, starting from $$i$$.

Then I listed out $$P(X_0) = \frac{1}{2} + \frac{1}{2}P(X_1)$$ $$P(X_i) = \frac{1}{2}\left(P(X_{i-1}) + P(X_{i+1})\right) \ \ \text{ for } i \in\{1,2,3,...7\}$$

$$P(X_8) = \frac{1}{2}P(X_7) + 0$$

There are 9 equations and 9 unknowns. We should be able to calculate the result. However, how to go from here?

Hint: The equations $$P\left(X_{i+1}\right) - 2P\left(X_i\right) + P\left(X_{i-1}\right)=0\ \ \ \mathrm{for}\ i=1,2,\dots,7$$ constitute a second-order linear recurrence whose general solution is $$\ P\left(X_n\right) = a + bn\$$ for $$\ n=0,1, \dots, 8\$$, and some constants $$\ a\$$ and $$\ b\$$. The boundary conditions, $$\ P\left(X_0\right) = \frac{1}{2} + \frac{1}{2}P\left(X_1\right)\$$, and $$\ P\left(X_8\right) = \frac{1}{2}P\left(X_7\right)\$$, give you two linear equations to solve for the values of $$\ a\$$ and $$\ b\$$.
The equation $$P(X_i) = \frac{1}{2}\left(P(X_{i-1}) + P(X_{i+1})\right) \: \: \: \; (*)$$ holds for $$i \in\{0,2,3,...8\}$$ since $$P(X_{-1})=1$$ and $$P(X_9)=0$$. Write $$Q_i=P(X_i)-P(X_{i-1})$$ for $$i=0,1,\ldots,9$$. Then by doubling (*) and subtracting $$P(X_{i-1}) + P(X_{i})$$ from both sides, we get that $$Q_i = Q_{i+1}$$ holds for $$i \in\{0,2,3,...8\}$$. Since $$\sum_{i=0}^9 Q_i=-1$$ we conclude that $$Q_i=-1/10$$ for all $$i$$. In particular $$P(X_0)=1+Q_0=9/10$$.