El problema
Esta cadena de Markov de tres estados, que se distingue por el hecho de si el gusano es $0,$ $1,$ o $2$ espacios lejos de $C.$ Deje $X_i$ ser la variable aleatoria dando el número de pasos que el gusano se necesita para llegar a $C$ de estado $i\in\{0,1,2\}.$ Su probabilidad de generación de funciones de una cómoda algebraicas manera de codificar las probabilidades de estas variables. No es necesario preocuparse de la analítica de temas como la convergencia: sólo verlas como poder formal de la serie en un símbolo de $t$ dada por
$$f_i(t) = \Pr(X_i=0) + \Pr(X_i=1)t^1 + \Pr(X_i=2)t^2 + \cdots + \Pr(X_i=n)t^n + \cdots$$
Desde $\Pr(X_0=0)=1,$ es trivial que $f_0(t)=1.$ necesitamos encontrar $f_2.$
Análisis y solución de
De estado $1,$ el gusano tiene las mismas posibilidades de $1/2$ de moverse de nuevo al estado $2$ o llegar a $C$. La contabilidad para tomar este paso agrega $1$ a todas las facultades de $t$, equivalente a multiplicar el pgf por $t$, dando
$$f_1 = \frac{1}{2}t\left(f_2 + f_0\right).$$
Del mismo modo, desde el estado $2$ el gusano tiene iguales probabilidades de permanecer en estado de $2$ o llegar a un estado de $1,$ dónde
$$f_2 = \frac{1}{2}t\left(f_2 + f_1\right).$$
La aparición de $t/2$ sugiere que nuestro trabajo será facilitado por la introducción de la variable $x=t/2,$ dando
$$f_1(x) = x(f_2(x) + f_0(x));\quad f_2(x) = x(f_2(x) + f_1(x)).$$
La sustitución de la primera a la segunda y recordando $f_0=1$ da
$$f_2(x) = x(f_2(x) + x(f_2(x) + 1))\tag{*}$$
cuya única solución es
$$f_2(x) = \frac{x^2}{1 - x - x^2}.\tag{**}$$
Me puso de relieve la ecuación de $(*)$ a destacar su simplicidad básica y su similitud formal a la ecuación podríamos obtener al analizar sólo los valores esperados $E[X_i]:$ en efecto, para la misma cantidad de trabajo necesario para encontrar este número, se obtiene la distribución completa.
Implicaciones y simplificación
De manera equivalente, cuando $(*)$ está escrito término a término y los poderes de la $t$ coinciden que afirma que para $n\ge 4,$
$$2^n\Pr(X_2=n) = 2^{n-1}\Pr(X_2=n-1) + 2^{n-2}\Pr(X_2=n-2).$$
Esta es la recurrencia de la famosa secuencia de números de Fibonacci
$$(F_n) = (1,1,2,3,5,8,13,21,34,55,89,144,\ldots)$$
(índice de $n=0$). La solución coincidente $(**)$ es esta secuencia cambiado por dos lugares (porque no hay ninguna probabilidad de que $X_2=0$ o $X_2=1$ y es fácil comprobar que $2^2\Pr(X_2=2)=1=2^3\Pr(X_2=3)$).
En consecuencia
$$\Pr(X_2 = n) = 2^{-n-2}F_{n-2}.$$
Más específicamente,
$$\eqalign{
f_2(t) y= 2^{-2}F_0t^2 + 2^{-3}F_1 t^3 + 2^{-4} F_2 t^4 + \cdots \\
&= \frac{1}{4}t^2 + \frac{1}{8}t^3 + \frac{2}{16}t^4 + \frac{3}{32}t^5 + \frac{5}{64}t^6 + \frac{8}{128}t^7 +\frac{13}{256}t^8 + \cdots.
}$$
La expectativa de $X_2$ es fácil de encontrar mediante la evaluación de la derivada $f^\prime$ y la sustitución de $t=1,$ debido a (la diferenciación de los poderes de la $t$ término por término) esto le da la fórmula
$$f^\prime(1) = \Pr(X_2=0)(0) + \Pr(X_2=1)(1)1^0 + \cdots + \Pr(X_2=n)(n)1^{n-1} + \cdots$$
que, como la suma de las probabilidades de veces que los valores de $X_2,$ es, precisamente, la definición de $E[X_2].$ Tomando la derivada usando $(**)$ produce una fórmula simple para la expectativa.
Algunos breves comentarios
Mediante la expansión de $(**)$ parcial como fracciones, $f_2$ puede ser escrito como la suma de dos series geométricas. Esta muestra de inmediato las probabilidades de $\Pr(X_2=n)$ disminuirá exponencialmente. También produce una forma cerrada para la cola probabilidades de $\Pr(X_2 \gt n).$ Mediante que, podemos calcular que el $\Pr(X_2 \ge 100)$ es un poco menos de $10^{-9}.$
Finalmente, estas fórmulas implican la Proporción áurea $\phi = (1 + \sqrt{5})/2.$ Este número es la longitud de una cuerda de un pentágono regular (de la unidad de lado), produciendo una conexión sorprendente entre puramente combinatoria de la cadena de Markov en el pentágono (el que "sabe" nada acerca de la geometría Euclidiana) y la geometría de un pentágono regular en el plano Euclidiano.
