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.

  • $\begingroup$ If you don't mind me asking, what makes $P(G) = \frac{i}{i+|j|}$? $\endgroup$ – jameselmore Apr 3 '15 at 0:56
  • $\begingroup$ 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)$ ? $\endgroup$ – Manuel Lafond Apr 3 '15 at 1:34
  • $\begingroup$ 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$. $\endgroup$ – String Apr 3 '15 at 1:40
  • $\begingroup$ 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. $\endgroup$ – String Apr 3 '15 at 1:45
  • $\begingroup$ @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 ? $\endgroup$ – Manuel Lafond Apr 3 '15 at 2:22

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.