La probabilidad de lo que es a través de un camino de $n$ azulejos a través de la caminata al azar

Question

El problema

Imagínese que alguien se mueve a través de un camino trazado en 2D de la cuadrícula:

Los azulejos blancos son el camino; los alrededores de tejas rojas son, digamos, mortal de lava. Que en repetidas ocasiones se mueven al azar norte, oriente, suro al oeste, con igual probabilidad, y tiene que hacer desde el Inicio de baldosas para el Final de baldosas sin pisar la lava.

¿Cuál es la probabilidad de $p(n)$ que tienen éxito en un $n$-plaza sendero ($n=5$ se muestra arriba)?

---

Lo he intentado

El número de los azulejos $1, \dots, n$, por lo que estamos caminando de$1$$n$.

Llame a $a_k$ la probabilidad de que tenga éxito cuando se inicia en el $k$-th azulejo. Claramente, $a_n = 1$, y estamos interesados en el valor de $a_1$.

De la $k$-el azulejo, hay un 25% de probabilidades nos desplazamos de nuevo a la teja $k-1$, un 25% de probabilidades de que nos movemos hacia adelante para azulejo $k+1$, y un 50% de probabilidad de que el paso del norte o hacia el sur en una baldosa roja y perder. Por lo $a_k = \frac 14 \left( a_{k-1} + a_{k+1} \right)$ donde $a_0 = 0$.

Poner las ecuaciones para $a_1, \dots, a_{n}$ en una matriz de sistema que nos pone:

$$\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} \etiqueta{1} \end{equation}$$

Escribí algunas código de Mathematica para resolver este sistema por un determinado $n$ y dar el valor de $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]]

El primer par de valores de $p(1), p(2), \dots$ $$\frac11, \frac1{4}, \frac1{15}, \frac1{56}, \frac1{209}, \frac1{780}, \dots,$$ los inversos de A001353 en la OEIS, lo que sugiere una forma cerrada:

$$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)$ por la mano. Tal vez un combinatoric enfoque produce esta fórmula sin tomar un desvío a través de la solución de un sistema.

Answer 1

Usted no necesita para resolver el uso de la matriz. Es válido, pero un poco unweildy. La solución es utilizar la relación de recurrencia $$a_k = \frac 14 \left( a_{k-1} + a_{k+1} \right)$$ con las condiciones de contorno $a_0=0$, $a_n=1$.

Reescribir esto como: $$a_{k+1} - 4a_k + a_{k-1} = 0$$ Esto tiene soluciones de la forma $a_k = A \lambda^k$ donde $\lambda$ es una raíz de la ecuación cuadrática $$x^2 - 4x +1 = 0$$ Así $$\lambda = {4 \pm \sqrt{12}\over 2} = 2 \pm \sqrt{3}$$ Y $$a_k = A(2 + \sqrt{3})^k + B(2 - \sqrt{3})^k$$ para algunos $A, B$. Aplicando las condiciones de frontera conjuntos de estos y da la fórmula en la parte inferior del post.