Limit of a probability regarding a random walk 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)$.
 A: 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.
