Macalester POTW 1201: Problem 1201. What Goes Up Might Not Come Down

Problem Statement

A random walk on the 2-dimensional integer lattice begins at the origin. At each step, the walker moves one unit either left, right, or up, each with probability \(\frac13\). (No downward steps ever.) A walk is a success if it reaches the point \((1,1)\). What is the probability of success?

Note: One can vary the problem by varying the target point. Eg., use \((1, 0)\) or \((0,1)\) instead. Perhaps there is a good method to resolve the general case of target \((a, b)\).

Source: Bruce Torrence, Randolph-Macon College


An easy relaxation

To solve this problem, let’s consider an easier class of questions first. Suppose that we have a one-dimensional number line, and you start at some arbitrary point \(n\). You can either move left, right, or up. What is the probability that you will hit the origin?

Now, if we’re at point \(n\), one of two things must happen. Either \(n = 0\), in which case we know that we can get to the origin with \(100\%\) probability, or \(n \ne 0\). Let \(P_n\) be the probability that we can reach the origin from \(n\), then inductively: \[P_n = \begin{cases} 1 & n = 0 \\ \frac13 \times 0 + \frac13 \times P_{n-1} + \frac13 \times P_{n+1} & \text{otherwise} \end{cases}\] This reduces to the system where \(P_0 = 1\) and \(P_n = 3P_{n-1} - P_{n-2}\). The characteristic of this recurrence (\(x^2 - 3x + 1\)) has roots \(\gamma,\bar\gamma = \frac{3 \pm \sqrt5}{2}\), which suggests that \(P_n\) will necessarily be in the form of \[P_n = \alpha \gamma^n + \beta \bar\gamma^n, ~~~~ P_0 = 1\] for some \(\alpha, \beta \in \mathbb{R}\).

Now, we have one initial condition, which is only enough to establish that \(\beta = 1 - \alpha\). We need another piece of information in order to solve this system. It turns out that we can use the argument that this probability system must be “stable in the limit” to find another boundary condition:

Lemma: (Stability)\[\lim_{n\to\infty} P_n = 3P_n - P_n \implies \lim_{n\to\infty} P_n = 0 ~~~~ \square\]

This suggests that \(\lim_{n\to\infty} \alpha \gamma^n + \beta \bar\gamma^n = 0\). However, \(|\gamma| > 1\) while \(|\bar\gamma| < 1\), so it must be the case that \(\alpha = 0\) otherwise \(P_n\) diverges. This means that \(\beta = 1 - \alpha = 1\), and \[P_n = \bar\gamma^n ~~~~ \square\]

Onto the real problem

Having seen how we can solve the relaxed toy problem, let’s now turn our attention to the full problem at hand. to make it easier to work with later on, let’s assume that we start off at some arbitrary point \((n,1)\) and we’re going down towards the origin. First, let \(P^{0}_n = \bar\gamma^n\) be the probability that a particle on the \(x\)-axis will be able to random walk to the origin. Next, let \(P^{1}_n\) be the probability that a particle on the next row at column \(n\) will be able to random walk to the origin \((0,0)\). Our problem reduces down to finding an expression for \(P^1_n\).

Now, let \(\hat k\) be the event that a particle walks to a final displacement of \(k\) horizontal steps and immediately takes a vertical step. and let \(s\