12
$\begingroup$

Lets say we start at point 1. Each successive point you have a, say, 2/3 chance of increasing your position by 1 and a 1/3 chance of decreasing your position by 1. The walk ends when you reach 0.

The question, what is the probability that you will eventually reach 0?

Also, is there any generalization for different probabilities or different starting positions or different rules (say you increase 2 and decrease 1)?

NOTE: I have never taken a course that considered random walks. So, if possible, could no prior knowledge of random walks be assumed?

$\endgroup$

4 Answers 4

21
$\begingroup$

One asks for the probability $r$ starting at $1$ to eventually reach $0$. The dynamics is invariant by translations hence $r$ is also the probability starting at $2$ to eventually reach $1$. Consider the first step of a random walk starting at $1$. Either the first step is to $0$ then one hits $0$ eventually since one is already at $0$. Or the first step is to $2$ then to hit $0$, one must first hit $1$ starting from $2$ and after that, hit $0$ starting from $1$. This yields the equation $r=\frac13+\frac23r^2$, whose solutions are $r=1$ and $r=\frac12$.

If $r=1$, let us assume the random walk continues with the same dynamics after its first return to $0$. The new portion of the walk is distributed as before hence one returns to $0$ a second time. And so on, hence, calling $X_n$ the position at time $n$, one sees that $X_n=0$ for infinitely many times $n$.

Consider now the homogeneous random walk $(Y_n)$ on the whole integer line whose steps are $+1$ and $-1$ with probabilities $\frac23$ and $\frac13$ respectively. Then $Y_n=Z_1+\cdots+Z_n$ where $(Z_n)$ is i.i.d. and $\mathrm E(Z_n)=\frac13(-1)+\frac23(+1)=\frac13\gt0$. By the strong law of large numbers, $\frac1nY_n\to\frac13$. One can recover $(X_n)$ from $(Y_n)$ through the change of time $\tau_{n+1}=\min\{k\gt\tau_n\mid Y_k\geqslant0,\,Y_k\ne Y_{\tau_n}\}$ for every $n\geqslant0$, and $\tau_0=0$. Then $X_n=Y_{\tau_n}$ and $\tau_n\geqslant n$ hence $\frac1nX_n=\frac1nY_{\tau_n}\geqslant\frac1{\tau_n}Y_{\tau_n}$. One sees that $\liminf\limits_{n\to\infty}\frac1nX_n\geqslant\lim\limits_{n\to\infty}\frac1nY_n=\frac13$.

This is impossible if $X_n=0$ infinitely often, hence $r=\frac12$.

For a random walk whose steps are $+1$ and $-1$ with probability $p\gt\frac12$ and $1-p$ respectively, the same argument yields $r=\frac{1-p}p$.

For a random walk whose steps are $+2$ and $-1$ with probability $p$ and $1-p$ respectively, the crucial argument that to reach $0$ from $n\gt0$, one must reach $n-1$ from $n$, then reach $n-2$ from $n-1$, and so on, is still valid. Hence $r=pr^3+1-p$. If $r\gt\frac13$ the drift $p(+2)+(1-p)(-1)=3p-1$ is positive and one knows that $r\lt1$ hence $r$ is the positive root of the equation $p(r^2+r)=1-p$, that is, $r=\frac1{2p}\left(\sqrt{4p-3p^2}-p\right)$.

The same trick can be applied to any random walk whose steps are almost surely $\geqslant-1$.

$\endgroup$
4
  • $\begingroup$ I have a very similar question that I would like to close by using a small variant of this. It's probably extremely simple to tweak. What about, instead, if we start at zero and we want to look at the probability of never returning to zero again, using $p > \frac{1}{2}$ like above? Clearly, I can just find the probability of eventually hitting zero and then just taking 1 - (that probability). $\endgroup$
    – user142671
    May 29, 2015 at 20:50
  • 1
    $\begingroup$ @Did Is there a way of solving this using the optional stopping theorem? In particular, when looking at the problem of starting with initial wealth $i$, $0<i<N$ and then attempting to find the probability that we reach $N$ before $0$. When $p=q=1/2$ and the step sizes $X_i$ are both $1,-1$ respectively, we use OST applied to the martingale $S_n=\sum_{i=1}^N X_i$. When $p\neq q$ but we still have equal step sizes, we use the martingale $(q/p)^{S_n}$. But what do we do when $p=q$ and the size of an up step is $2$ and down step is $-1$? $\endgroup$ Jan 26, 2017 at 10:54
  • 1
    $\begingroup$ @mathsquestion88 Sure, look for $a>0$, $a\ne1$, such that $a^{S_n}$ is a martingale. Assuming steps $+2$ and $-1$ with probabilities $p$ and $q=1-p$ respectively, this means that $pa^2+q/a=1$, that is, $pa^2+pa-q=0$. If $p\ne\frac13$, solve for $a\ne1$, rinse, conclude. $\endgroup$
    – Did
    Jan 26, 2017 at 11:12
  • $\begingroup$ @Did, oh I see, thanks for the advice! I'm rather new to this community, so there's many rules I'm not familiar with... I've actually posted the problem though: mathoverflow.net/questions/269839/… $\endgroup$
    – Oliver
    May 19, 2017 at 14:44
8
$\begingroup$

With fancier tools one can extract a bit more information from the problem. Let $p>\frac12$ be the probability of stepping to the right, and let $q=1-p$. For $n\in\Bbb N$ let $P_n$ be the probability of first hitting $0$ in exactly $n$ steps. Clearly $P_n=0$ when $n$ is even, and $P_1=q$. In order to hit $0$ for the first time on the third step you must go RLL, so $P_3=pq^2$. To hit $0$ for the first time in exactly $2k+1$ steps, you must go right $k$ times and left $k+1$ times, your last step must be to the left, and through the first $2k$ steps you must always have made at least as many right steps as left steps. It’s well known that the number of such paths is $C_k$, the $k$-th Catalan number. Thus,

$$P_{2k+1}=C_kp^kq^{k+1}=C_kq(pq)^k=\frac{q(pq)^k}{k+1}\binom{2k}k\;,$$

since $C_k=\dfrac1{k+1}\dbinom{2k}k$. It’s also well known that the generating function for the Catalan numbers is $$c(x)=\sum_{k\ge 0}C_kx^k=\frac{1-\sqrt{1-4x}}{2x}\;,$$ so the probability that the random walk will hit $0$ is

$$\begin{align*} \sum_{k\ge 0}P_{2k+1}&=q\sum_{k\ge 0}C_k(pq)^k\\\\ &=qc(pq)\\\\ &=q\left(\frac{1-\sqrt{1-4pq}}{2pq}\right)\\\\ &=\frac{1-\sqrt{1-4pq}}{2p}\\\\ &=\frac{1-\sqrt{1-4q(1-q)}}{2p}\\\\ &=\frac{1-\sqrt{1-4q+4q^2}}{2p}\\\\ &=\frac{1-(1-2q)}{2p}\\\\ &=\frac{q}p\\\\ &=\frac{1-p}p\;. \end{align*}$$

For the present case, $p=\dfrac23$, this yields the probability $\dfrac12$. Rounded to four decimal places, the probabilities of first hitting $0$ in $1,3,5,7,9,11$, and $13$ steps are:

$$\begin{array}{rcc} \text{Steps}:&1&3&5&7&9&11&13\\ \text{Probability}:&0.3333&0.0747&0.0329&0.0183&0.0114&0.0076&0.0053 \end{array}$$

These already account for $0.4829$ (total calculated before rounding) out of the total probability of $0.5$.

$\endgroup$
1
  • 1
    $\begingroup$ It's interesting that with exactly the same procedure we can easily verify that if p<q we get 1 as expected. $\endgroup$
    – kon psych
    Aug 10, 2019 at 22:12
5
$\begingroup$

Let $P$ be the probability that the drunk will eventually move one unit left. Then $P = \frac13 + \frac23P^2$, because he has a $\frac13$ chance of moving left immediately, and a $\frac23$ chance of moving right, after which he has a $P^2$ chance of eventually moving left twice. Solving this using the usual methods, we get $P=\frac12$.

(Hmm, there's another root at $P=1$. I don't know what to make of that. I hope someone will help out.)

Setting up and solving the equation in a more general case is not hard.

(I first heard this problem posed about a drunk walking home after a long night. His home is at the top of a hill, and he is only one step from the door…)

$\endgroup$
2
  • $\begingroup$ OK. This makes sense. Explaining the second root at P = 1. The equation you gave is a necessary, but not a sufficient condition for P being the probability. So it's possible to have other roots there that aren't necessarily the case. $\endgroup$
    – A.S
    Jun 3, 2012 at 5:12
  • 3
    $\begingroup$ Sure, but I would like to give some reason for ruling out the $P=1$ root, and I can't think of any. $\endgroup$
    – MJD
    Jun 3, 2012 at 5:15
0
$\begingroup$

Define $Y_0 = 0$ and $Y_n = \sum_{i=1}^nX_n$ where $X_1, X_2, \ldots$ is i.i.d. with $P\{X_1 = 1\} = 1 - P\{X_1 = -1\} = \frac{2}{3}$. Consider the hitting times $\tau_k = \min\{n\geq 0: Y_n = k\}$. With these definitions we want to find out $P\{\tau_{-1} < \infty\}$. Note that $$\{\tau_{-1} < \infty\} = \bigcup_{k\geq 1}\{\tau_{-1} < \tau_{k}\}$$ Hence by monotone convergence, $$P\{\tau_{-1} < \infty\} = \lim_{k \to \infty}P\{\tau_{-1} < \tau_{k}\}$$

So we need to compute the limit on the rhs. We will do so by finding an expression for $P\{\tau_{-1} < \tau_{k}\}$. Note that at each step $Y_n$ moves right by $\frac{1}{3}$ on average. So in $m$ steps it moves right by $\frac{m}{3}$ on average. By optional stopping theorem, this is true not just when $m$ is a deterministic number but also when it is a stopping time.

Specifically, we will consider the stopping time $\tau_{-1} \wedge \tau_{k}$, i.e. the time when $Y_n$ hits either $-1$ or $k$ with $k \geq 1$. If I knew the expected value of this stopping time, then I could write $$(-1) \times P\{\tau_{-1} < \tau_{k}\} + (k) \times P\{\tau_{-1} > \tau_{k}\} = \frac{1}{3}E\left[\tau_{-1} \wedge \tau_{k}\right]\qquad\qquad\triangle$$

The lhs is the average position of $Y$ after $\tau_{-1} \wedge \tau_{k}$ steps. The rhs is the average number of steps divided by $3$ since $Y$ moves right by that much.

To compute $E\left[\tau_{-1} \wedge \tau_{k}\right]$, we will use recursion (by conditioning on what happens in the first step). But first note that this expectation is finite since you can bound it by a geometric random variable.

$$E\left[\tau_{-1} \wedge \tau_{k}\right] = 1 + \frac{2}{3}E\left[\tau_{-2} \wedge \tau_{k-1}\right]$$

$$E\left[\tau_{-2} \wedge \tau_{k-1}\right] = 1 + \frac{1}{3}E\left[\tau_{-1} \wedge \tau_{k}\right]+ \frac{2}{3}E\left[\tau_{-3} \wedge \tau_{k-2}\right]$$ $$\vdots$$ $$E\left[\tau_{-k} \wedge \tau_{1}\right] = 1 + \frac{1}{3}E\left[\tau_{-k+1} \wedge \tau_{2}\right]$$

This is a linear system with $k$ equations and $k$ unknowns. I will type out how to solve it quickly later when I have time but for the time being just take it on faith that $$E\left[\tau_{-1} \wedge \tau_{k}\right] = 3\frac{2^k\left(k-1\right)+1}{2^{k+1} - 1}$$

This combined with $\triangle$ gives $$P\{\tau_{-1} < \tau_{k}\} = \frac{2^k-1}{2^{k+1} - 1}$$

The limit of this expression is $\frac{1}{2}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .