5
$\begingroup$

The problem

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

enter image description here

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Isn't the boundary condition $a_0 = 0$? $\endgroup$ – Theoretical Economist Dec 22 '16 at 11:04
  • $\begingroup$ “This has solutions of the form $a_k = A \lambda^k$ …” Why’s that? (The final formula looks to be of a different form (a sum of terms like $A \lambda^k$), to me.) $\endgroup$ – Lynn Dec 22 '16 at 11:10
  • $\begingroup$ Oops - sorry about the typo. Fixed to read $a_0=0$. Thanks @Economist. $\endgroup$ – Scott Burns Dec 22 '16 at 14:46
  • 1
    $\begingroup$ Why $a_k = A\lambda^k$. Any finite difference equation has solutions of this form. If $\lambda$ satisfies a polynomial $p$ then $A\lambda^k$ is a solution to the difference equation with the same coefficients. Try it out and you'll see that you can always cancel powers of $\lambda$ to get to the polynomial. The reason for the sum is that, because the difference equation is $homogeneous$ (that means it sums to $0$), the sum of any two solutions is also a solution. $\endgroup$ – Scott Burns Dec 22 '16 at 14:51
  • $\begingroup$ @ScottBurns Any finite diff. equation with constant coefficients, that is. $\endgroup$ – The Vee Dec 23 '16 at 4:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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