Probability of making it across a path of $n$ tiles through random walk

Question

The problem

Imagine someone moving across a path laid out on a 2D grid:

The white tiles are the path; the surrounding red tiles are, say, deadly lava. They repeatedly move randomly north, east, south, or west, with equal probability, and have to make it from the Start tile to the End tile without stepping onto the lava.

What is the probability $p(n)$ that they succeed on an $n$-square-long path ($n=5$ is shown above)?

---

What I’ve tried

Number the tiles $1, \dots, n$, so that we’re walking from $1$ to $n$.

Call $a_k$ the probability we succeed when starting at the $k$-th tile. Clearly, $a_n = 1$, and we’re interested in the value of $a_1$.

From the $k$-the tile, there’s a 25% chance we move back to tile $k-1$, a 25% chance we move forward to tile $k+1$, and a 50% chance we step north or south onto a red tile and lose. So $a_k = \frac 14 \left( a_{k-1} + a_{k+1} \right)$, where $a_0 = 0$.

Putting the equations for $a_1, \dots, a_{n}$ in a matrix system gets us:

\begin{equation} \newcommand{\mof}{-1/4} \begin{bmatrix} 1 & \mof & 0 & \dots & 0 & 0 & 0 \\ \mof & 1 & \mof & \dots & 0 & 0 & 0 \\ 0 & \mof & 1 & \dots & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \dots & 1 & \mof & 0 \\ 0 & 0 & 0 & \dots & \mof & 1 & \mof \\ 0 & 0 & 0 & \dots & 0 & \color{red}0 & 1 \\ \end{bmatrix} \begin{bmatrix} a_1 \\ a_2 \\ a_3 \\ \vdots \\ a_{n-2} \\ a_{n-1} \\ a_n \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ \vdots \\ 0 \\ 0 \\ 1 \end{bmatrix} \tag{1} \end{equation}

I wrote some Mathematica code to solve this system for a given $n$ and give the value of $a_1$:

p[n_] :=
  LinearSolve[
    Table[If[x == y, 1,
            If[y == n, If[x == n,1,0],
              If[Abs[x - y] == 1, -1/4, 0]]],
          {y, 1, n}, {x, 1, n}],
    Table[If[x == n, 1, 0], {x, 1, n}]
  ][[1]]

The first few values $p(1), p(2), \dots$ are $$ \frac11, \frac1{4}, \frac1{15}, \frac1{56}, \frac1{209}, \frac1{780}, \dots, $$ the inverses of A001353 in the OEIS, which suggests a closed form:

$$p(n) = \frac{2 \sqrt{3}}{\left( 2 + \sqrt{3} \right)^n - \left( 2 - \sqrt{3} \right)^n}$$

But I’m not sure how to get there. I doubt there’s a nice way to solve a system like $(1)$ by hand. Maybe a combinatoric approach yields this formula without taking a detour through solving a system.

Answer 1

You don't need to solve using the matrix. It's valid, but a bit unweildy. The solution is to use the recurrence relation $$ a_k = \frac 14 \left( a_{k-1} + a_{k+1} \right) $$ with boundary conditions $a_0=0$, $a_n=1$.

Rewrite this as: $$ a_{k+1} - 4a_k + a_{k-1} = 0 $$ This has solutions of the form $a_k = A \lambda^k$ where $\lambda$ is a root of the quadratic $$ x^2 - 4x +1 = 0 $$ So $$ \lambda = {4 \pm \sqrt{12}\over 2} = 2 \pm \sqrt{3} $$ And $$ a_k = A(2 + \sqrt{3})^k + B(2 - \sqrt{3})^k $$ for some $A, B$. Applying the boundary conditions sets these and gives the formula at the bottom of the post.