Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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

while your method might suggest

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.