4
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.