3
$\begingroup$

Consider a random walk on the integers starting at 0, where in each step you move either 1 or 2 meters (back or forth alike). As soon as you reach either the $N$ or $N+1$ meter mark, you stop. What is the limit $P$ of the probability that you stop at $N$ and not on $N+1$, as $N$ approaches infinity. My intuition tells me that $P$ should be $\Phi-1=0.618...$ but I don't see any slick way to prove it.

More formally: Let $X_0,X_1,X_2,...$ be a Markov chain such that $P(X_0=0)=1$ and for each $i \ge 1$, $P(X_i=x_i|X_{i-1}=x_{i-1})=1/4 \leftrightarrow x_i-x_{i-1} \in \{-2,-1,1,2\}$ I'm asking for the limit $P:=\lim \limits_{N \rightarrow \infty} P\big(\min\{k \in \Bbb N|X_k=N\}<\min\{k \in \Bbb N|X_k=N+1\}\big)$.

1 Answers 1

2

Denote the probability whose limit for $N\to\infty$ you're looking for by $P_N$. Then $P_N$ satisfies the recurrence relation

$ P_N=\frac14\left(P_{N-2}+P_{N-1}+P_{N+1}+P_{N+2}\right)\;, $

which leads to the characteristic equation

$ \lambda^4+\lambda^3-4\lambda^2+\lambda+1=0\;. $

The double root at $\lambda=1$ is readily guessed, and the resulting factorization

$ (\lambda-1)^2(\lambda^2+3\lambda+1)=0 $

yields the additional roots

$\lambda=\frac{-3\pm\sqrt5}2\;.$

The general solution for $P_N$ thus takes the form

$ P_N=c_1+c_2N+c_3\left(\frac{-3+\sqrt5}2\right)^N+c_4\left(\frac{-3-\sqrt5}2\right)^N\;. $

The condition $0\le P_N\le1$ yields $c_2=c_4=0$, so we have

$ P_N=c_1+c_3\left(\frac{-3+\sqrt5}2\right)^N\;. $

The initial conditions $P_0=1$ and $P_{-1}=0$ then yield

$ c_1+c_3=1\;,\\ c_1+c_3\left(\frac{-3-\sqrt5}2\right)=0 $

with solution

$ c_1=\frac{5+\sqrt5}{10}\;,\\ c_3=\frac{5-\sqrt5}{10}\;. $

Thus the limit $P$ is $c_1=(5+\sqrt5)/10\approx0.724$, slightly higher than you guessed.

Here's code that simulates the random walk; the results agree with the analytic result.

Something similar to this problem occurs in analyzing the game of Risk, where one can ask for the probability that a large stack attacking a very large stack will end up with $3$ rather than $2$ troops left. The probabilities for the attacker losing $0$, $1$ or $2$ troops in an attack are $2890/7776$, $2611/7776$ and $2275/7776$, respectively, so the recurrence relation in this case is

$ 7776P_N=2890P_N+2611P_{N-1}+2275P_{N-2}\;, $

with characteristic equation

$ 4886\lambda^2-2611\lambda-2275=0 $

and roots $\lambda=1$ and $\lambda=-2275/4886=-325/698$. Thus we have

$ P_N=c_1+c_2\left(-\frac{325}{698}\right)^{N-2}\;, $

and the initial conditions $P_2=0$ and $P_3=1$ yield

$ c_1+c_2=0\;,\\ c_1-\frac{325}{698}c_2=1 $

with solution

$ c_1=-c_2=\frac{698}{1023}\;, $

so the probability of ending up with $3$ troops is $698/1023$, or about $2$ in $3$. If the probabilities of losing $1$ or $2$ troops were exactly the same, as in your problem, the probability of ending up with $3$ troops would be exactly $2$ in $3$, also slightly higher than the golden ratio.