# Random Walk solution shortcut

I remember from stochastic processes that certain types of random walks can be simplified into the following:

Probability of eventually winding up at the left stop point = Probability of walking DIRECTLY to the left point without hesitation/(Probability of walking DIRECTLY to the left point without hesitation + Probability of walking DIRECTLY to the right point without hesitation)

What are the criteria that need to be met to use this simplification?

-
Are we to assume that your random walk is 1-Dimensional and with finite states? –  Nicolas Villanueva Jun 7 '11 at 20:05
In a way that is my question... what do we have to assume in order for this to be true? I would think we would have to assume it is a walk where the probability of terminating goes to 1. –  Dan Jun 7 '11 at 20:16
Even for simple random walk this doesn't appear to be true. –  Nate Eldredge Jun 7 '11 at 20:25
Random walks with non zero transition probabilities on a finite segment always terminate with probability 1. –  Did Jun 7 '11 at 20:35

It is true when the required number of steps to the left is equal to the required number of steps to the right.

For example, imagine if there are 6 steps between left and right, i.e. 7 points. Then if the probability of a step left is $\frac{1}{2}$ and of a step right is also $\frac{1}{2}$, the probability of winning from each starting point is:

$$\frac{6}{6}, \frac{5}{6}, \frac{4}{6}, \frac{3}{6}, \frac{2}{6}, \frac{1}{6}, \frac{0}{6}$$

$$\frac{64}{65}, \frac{16}{17}, \frac{4}{5}, \frac{1}{2}, \frac{1}{5}, \frac{1}{17}, \frac{1}{65}.$$

and these are only the same in the middle.

But the probabilities can vary and your algorithm will still work for the cntral starting point. For example, if the probability of a step left is $\frac{1}{3}$ and of a step right is also $\frac{2}{3}$, the probability of winning from each starting point is:

$$\frac{63}{63}, \frac{31}{63}, \frac{15}{63}, \frac{7}{63}, \frac{3}{63}, \frac{1}{63}, \frac{0}{63}$$

and the central $\frac{7}{63}$ is equal to the $\frac{1}{9}$ which your algorithm would give.

It is not hard to generalise this, though it is slightly messy. Measuring steps from right to left, if there are $n$ steps, and the probability of a step to the left is $p$ and to the right $1-p$, then starting at point $i$ (with $i=0$ at the right hand side and $i=n$ at the left) the probability of hitting the left first is

$$Pr_{i} =\frac{p^{n-i}\left( (1-p)^i-p^i\right)}{(1-p)^{n}-p^n}$$

since $Pr_{0}=0$, $Pr_{n}=1$ and $Pr_{i} = p Pr_{i+1} + (1-p) Pr_{i-1}$. [The expression doesn't work if $p=1/2$, but in that case the probability is $Pr_{i} = i/n$].

The only values for which this expression is equal to $\dfrac{p^{2n-i}}{p^{2n-i}+(1-p)^{i}}$ are when $n$ is even and $i=n/2$.

-