Exact value of probability related to random walk with negative drift

probabilityrandom walkstochastic-processes

This is a sequel to this older question.

Consider the random walk $S_n=\sum_{k=1}^n X_k$ where $(X_n)$ is an i.i.d. sequence of variables with distribution $P(X_n=1)=P(X_n=-2)=\frac{1}{2}$, and let $E=\lbrace \exists n, S_n \geq 1 \rbrace$.

The accepted answer to the linked question shows that $P(E)\leq \frac{\sqrt{5}-1}{2} \approx 0.62$. On the other hand, in the question it is also shown that $P(E)\geq 0.61$. It is therefore natural to ask :

Does $P(E) = \frac{\sqrt{5}-1}{2}$ ?

Best Answer

Yes. There are two ways we can eventually gain a net $+1$ from the start: either

  • the first step is $+1$, or
  • the first step is $-2$, then we eventually gain a net $+1$ from there, then we eventually gain a net $+1$ from there, then we eventually gain a net $+1$ from there.

This gives $P(E) = \frac12 + \frac12P(E)^3$, which has three solutions. We can discard $P(E) = \frac{-\sqrt5 - 1}{2}$ for being negative, and we can discard $P(E) = 1$ by the older question (or because it would violate the central limit theorem), leaving only $P(E) = \frac{\sqrt5 - 1}{2}$.

Related Question