Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$.

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.