# Random walk : probability of reaching value $i$ without passing by negative value $j$

This is just some question that popped out of nowhere while starting studying random walks, and I don't really know how to approach this.

Say I have a random walk that starts at zero, and goes up or down by one at each step with equal probability.

For some integer $i$, we stop the walk whenever it reaches either $i$ or $-i$.

Suppose we are given that the walk stopped by reaching $i$. I'm interested in the minimum value the walk passed through. In other words, for some $0 \geq j > -i$, what it the probability that the walk took value $j$ at some point, but not $j - 1$ ?

To compute $P(j\cap i)$, the probability of reaching $i$ having reached $j$ as minimum, consider playing two games after each other:
1. $G$ Is the game that is won by starting from zero, ending at $j$ without having reached $i$
2. $H$ is the game that is won by starting from $j$, ending at $i$ without having reached $j-1$
For the first one we have $$P(G)=\frac{i}{i+|j|}$$ for the second we have $$P(H)=\frac{1}{1+i+|j|}$$ and so $$P(j\cap i)=P(H)P(G)=\frac{i}{(i+|j|)(1+i+|j|)}$$ and as I understood it, you asked for the conditional probability $P(j\mid i)$ of having reached $j$ as a minimum given that we end at $i$. This should then be $$P(j\mid i)=\frac{P(j\cap i)}{P(i)}=\frac{2i}{(i+|j|)(1+i+|j|)}$$ since $P(i)=\frac12$ if I am not mistaken. This formula should work for $-i<j\leq 0$ then. I calculated a table of probabilities for the example $i=10$ using Wolfram|Alpha. It looks plausible. For one thing, the probabilities sum to $1$, and of course they decrease with $j$ as they should - which is evident from the formula.
• If you don't mind me asking, what makes $P(G) = \frac{i}{i+|j|}$? – jameselmore Apr 3 '15 at 0:56
• Looks great, and that'd answer my question ! But I have the same question as jameselmore. How do you obtain the results for $P(G)$ and $P(H)$ ? – Manuel Lafond Apr 3 '15 at 1:34
• A random walk from $0$ to $n$ where you win by reaching $n$ and loose by reaching $0$ has winning probabilities $P(k)$ given you start from position $k$ that satisfy $P(0)=0,P(n)=1$ and $$P(k)=\tfrac12P(k-1)+\tfrac12P(k+1)$$ for $0<k<n$. Writing this system of equations in matrix form, it becomes evident that it has a unique solution, and one easily checks that $$P(k)=\frac{k}{n}$$ solves it. With $k=i$ and $n=i+|j|$ this corresponds exactly to the situation $G$. – String Apr 3 '15 at 1:40
• To make it explicit: $k$ is the number of steps you are from loosing, and $n$ is the number of steps from loosing to winning. – String Apr 3 '15 at 1:45
• @String Ah thanks. I was able to convince myself about $P(k)$. One last detail. I'd have thought the situation corresponding to $G$ would be to set the starting point $k$ at $j$ instead of $i$. Because we lose upon making $j$ down moves to reach $0$, and win by making $i$ up moves to reach $i + j$. Does that make sense ? – Manuel Lafond Apr 3 '15 at 2:22