Probability to reach $a>0$ before returning to the origin in a one dimensional random walk.

Given a one dimensional random walk where I have $$p$$ probability to go forward and $$q$$ probability to go backwards.

I have to prove that, starting from the origin, the probability of reaching $$a>0$$ before returning to the origin is $$p(1-q_1)$$

Where

$$q_1=\frac{\left(\frac{q}{p}\right)^a-\left(\frac{q}{p}\right)}{\left(\frac{q}{p}\right)^a-1}$$

• The probability should also depend on $a$. Mar 25, 2021 at 18:22
• Is not $q=1-p$? And what is $q_1$?
– user
Mar 25, 2021 at 19:33
• @MishaLavrov it depends! Mar 26, 2021 at 9:49

2 Answers

So first you have to go right, so that introduces a factor of $$p$$. After that, you need to hit $$a$$ before hitting $$0$$ starting at $$1$$. There is a standard way to compute the probability to do that, based on computing the probability to hit $$a$$ before hitting $$0$$ starting at every point in $$0,1,\dots,a$$. The idea is the total probability formula:

$$P(\tau_a<\tau_0 \mid X_0=k)=p P(\tau_a<\tau_0 \mid X_0=k+1) + q P(\tau_a<\tau_0 \mid X_0=k-1).$$

So if $$u(k)=P(\tau_a<\tau_0 \mid X_0=k)$$ then you have the equations

$$u(k)=pu(k+1)+qu(k-1)$$

for $$k=1,2,\dots,a-1,u(0)=0,u(a)=1$$. (Note that $$u(0)$$ is not the quantity that you want; you actually want $$pu(1)$$. This is an annoying thing about the distinction between "hitting" and "returning".)

This system can be solved; the solution is of the form

• $$u(k)=c_1 + c_2 \left ( \frac{1-p}{p} \right )^k$$ if $$p \neq q$$
• $$u(k)=c_1 + c_2 k$$ if $$p=q$$.

Using the BCs you can find $$c_1,c_2$$.

After what Ian's response.

Ian (https://math.stackexchange.com/users/83396/ian), Probability to reach $$a>0$$ before returning to the origin in a one dimensional random walk., URL (version: 2021-03-25): https://math.stackexchange.com/q/4076368

I thought that there was a paralelism between this problem and the gambler's ruin:

Let player A have a capital of $$z$$ and player B have a capital of $$b$$. If we define $$a=z+b$$. And the probability for the player A to win the game is A and the probability for player B to win the game is q. We know that the probability for player A to lose all his money is:

if $$p\neq q$$

$$q_z=\frac{\left(\frac{q}{p}\right)^a-\left(\frac{q}{p}\right)^z}{\left(\frac{q}{p}\right)^a-1}$$ if $$p=q$$ $$q_z=1-\frac{z}{a}$$

So in our model we need to redefine the $$p_0$$ because in the gambler's ruin it's $$0$$ (If you don't have money you can't gamble). But in our game we can actually go forward with a probability of $$p%$$.

In order to achieve the point $$a$$ you first have to start from the point $$z=1$$ for the probability to be defined in the gambler's ruin model. So, as Ian said, we need to go forward with a probability of $$p$$. Once we are in $$z=1$$, we can apply the gambler's ruin model so we have a probability of $$p_1$$ to reach $$a$$.

Finally we multiply all this two probabilities and we have the probability to reach $$a$$ starting from $$0$$. $$pp_1=p(1-q_1)$$