11.5: Tiempo Medio de Primer Paso para Cadenas Ergódicas

En esta sección consideramos dos cantidades descriptivas estrechamente relacionadas de interés para las cadenas ergódicas: el tiempo medio para regresar a un estado y el tiempo medio para pasar de un estado a otro.

\(\mat{P}\)Sea la matriz de transición de una cadena ergódica con estados\(s_1\),\(s_2\),...,\(s_r\). Dejar\(\mat {w} = (w_1,w_2,\ldots,w_r)\) ser el vector de probabilidad único tal que\(\mat {w} \mat {P} = \mat {w}\). Entonces, por la Ley de Grandes Números para las cadenas de Markov, a la larga el proceso pasará una fracción\(w_j\) del tiempo en estado\(s_j\). Así, si empezamos en algún estado, la cadena eventualmente llegará al estado\(s_j\); de hecho, estará en estado\(s_j\) infinitamente a menudo.

Otra forma de ver esto es la siguiente: Formar una nueva cadena de Markov haciendo\(s_j\) un estado absorbente, es decir, definir\(p_{jj} = 1\). Si empezamos en cualquier estado que no sea\(s_j\), este nuevo proceso se comportará exactamente como la cadena original hasta la primera vez que\(s_j\) se alcance ese estado. Dado que la cadena original era una cadena ergódica, era posible llegar\(s_j\) desde cualquier otro estado. Así, la nueva cadena es una cadena absorbente con un solo estado absorbente\(s_j\) que eventualmente se alcanzará. Entonces, si iniciamos la cadena original en un estado\(s_i\) con\(i \ne j\), eventualmente llegaremos al estado\(s_j\).

\(\mat{N}\)Sea la matriz fundamental para la nueva cadena. Las entradas de\(\mat{N}\) dan el número esperado de veces en cada estado antes de la absorción. En cuanto a la cadena original, estas cantidades dan el número esperado de veces en cada uno de los estados antes de llegar a estado\(s_j\) por primera vez. El componente\(i\) th del vector\(\mat {N} \mat {c}\) da el número esperado de pasos antes de la absorción en la nueva cadena, comenzando en estado\(s_i\). En cuanto a la vieja cadena, este es el número esperado de pasos requeridos para llegar al estado\(s_j\) por primera vez a partir del estado\(s_i\).

Tiempo Medio del Primer Pasaje

Si se inicia una cadena ergódica de Markov en estado\(s_i\), el número esperado de pasos\(s_j\) para llegar al estado por primera vez se llama el de\(s_i\) a\(s_j\). Se denota por\(m_{ij}\). Por convención\(m_{ii} = 0\).

[examen 11.5.1] Volvamos al ejemplo del laberinto (Ejemplo [examen 11.3.3]). Haremos de esta cadena ergódica una cadena absorbente haciendo del estado 5 un estado absorbente. Por ejemplo, podríamos suponer que la comida se coloca en el centro del laberinto y una vez que la rata encuentra la comida, se queda a disfrutarla (ver Figura [fig 11.5]).

La nueva matriz de transición en forma canónica es\[\mat {P}\;= \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & \hbox{1}&\hbox{2}&\hbox{3}&\hbox{4}&\hbox{6}&\hbox{7}&\hbox{8} &\hbox{9}&\omit\hfil&\hbox{5}\cr \hbox{1}\strut & 0 &1/2 & 0 & 0 & 1/2 & 0 & 0 & 0 &\omit\kern.5em\vrule\kern-.5em& 0 \cr \hbox{2}\strut &1/3 & 0 &1/3 & 0 & 0 & 0 & 0 & 0 &\omit\kern.5em\vrule\kern-.5em&1/3\cr \hbox{3}\strut & 0 &1/2 & 0 & 1/2 & 0 & 0 & 0 & 0 &\omit\kern.5em\vrule\kern-.5em& 0 \cr \hbox{4}\strut & 0 & 0 &1/3 & 0 & 0 &1/3 & 0 & 1/3 &\omit\kern.5em\vrule\kern-.5em&1/3\cr \hbox{6}\strut &1/3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &\omit\kern.5em\vrule\kern-.5em&1/3\cr \hbox{7}\strut & 0 & 0 & 0 & 0 &1/2 & 0 & 1/2 & 0 &\omit\kern.5em\vrule\kern-.5em&0 \cr \hbox{8}\strut & 0 & 0 & 0 & 0 & 0 &1/3 & 0 & 1/3 &\omit\kern.5em\vrule\kern-.5em&1/3\cr \hbox{9}\strut & 0 & 0 & 0 &1/2 & 0 & 0 & 1/2& 0 &\omit\kern.5em\vrule\kern-.5em& 0 \cr \noalign{\kern-\snellbaselineskip\kern\snellskip} &\multispan 8\strut\hrulefill &\omit\hbox to.5em{\hrulefill}\vrule height \snellskip\kern-.5em&\multispan 1\hrulefill\cr \hbox{5}\strut & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &\omit\kern.5em\vrule\kern-.5em & 1\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ .\] Si calculamos la matriz fundamental\(\mat{N}\), obtenemos\[\mat {N} = \frac18 \pmatrix{ 14 & 9 & 4 & 3 & 9 & 4 & 3 & 2 \cr 6 & 14 & 6 & 4 & 4 & 2 & 2 & 2 \cr 4 & 9 & 14 & 9 & 3 & 2 & 3 & 4 \cr 2 & 4 & 6 & 14 & 2 & 2 & 4 & 6 \cr 6 & 4 & 2 & 2 & 14 & 6 & 4 & 2 \cr 4 & 3 & 2 & 3 & 9 & 14 & 9 & 4 \cr 2 & 2 & 2 & 4 & 4 & 6 & 14 & 6 \cr 2 & 3 & 4 & 9 & 3 & 4 & 9 & 14 \cr}\ .\] El tiempo esperado de absorción para diferentes estados de partida viene dado por el vector\(\mat {N} \mat {c}\), donde\[\mat {N} \mat {c} = \pmatrix{ 6 \cr 5 \cr 6 \cr 5 \cr 5 \cr 6 \cr 5 \cr 6 \cr}\ .\] Vemos que, a partir del compartimento 1, tomará el promedio de seis pasos para llegar a los alimentos. Es claro a partir de la simetría que debemos obtener la misma respuesta para comenzar en el estado 3, 7 o 9. También es claro que debería dar un paso más, comenzando en uno de estos estados, del que comenzaría en 2, 4, 6 u 8. Algunos de los resultados obtenidos de no\(\mat{N}\) son tan obvios. Por ejemplo, observamos que el número esperado de veces en el estado inicial es 14/8 independientemente del estado en el que iniciemos.

Tiempo medio de recurrencia

Una cantidad que está estrechamente relacionada con el tiempo medio del primer paso es la definida de la siguiente manera. Supongamos que empezamos en estado\(s_i\); considera el tiempo que transcurre antes de volver a\(s_i\) por primera vez. Es claro que debemos regresar, ya que o nos quedamos en\(s_i\) el primer paso o vamos a algún otro estado\(s_j\), y desde cualquier otro estado\(s_j\), eventualmente llegaremos\(s_i\) porque la cadena es ergódica.

Si se inicia una cadena ergódica de Markov en estado\(s_i\), el número esperado de pasos a los que regresar\(s_i\) por primera vez es el para\(s_i\). Se denota por\(r_i\).

Necesitamos desarrollar algunas propiedades básicas del tiempo medio del primer paso. Considere la media del primer tiempo de paso del\(s_i\) al\(s_j\); asuma eso\(i \ne j\). Esto puede calcularse de la siguiente manera: tomar el número esperado de pasos requeridos dado el resultado del primer paso, multiplicar por la probabilidad de que este resultado ocurra, y sumar. Si el primer paso es para\(s_j\), el número esperado de pasos requeridos es 1; si es a algún otro estado\(s_k\), el número esperado de pasos requeridos es\(m_{kj}\) más 1 para el paso ya realizado. Así,\[m_{ij} = p_{ij} + \sum_{k \ne j} p_{ik}(m_{kj} + 1)\ ,\] o, desde\(\sum_k p_{ik} = 1\),\[m_{ij} = 1 + \sum_{k \ne j}p_{ik} m_{kj}\ .\label{eq 11.5.1}\]

De igual manera\(s_i\), a partir de, debe tomar al menos un paso para regresar. Considerar todos los primeros pasos posibles nos da\[\begin{aligned} r_i &=& \sum_k p_{ik}(m_{ki} + 1) \\ &=& 1 + \sum_k p_{ik} m_{ki}\ .\label{eq 11.5.2}\end{aligned}\]

Matriz media de primer paso y matriz de recurrencia media

Definamos ahora dos matrices\(\mat{M}\) y\(\mat{D}\). La entrada\(ij\) th\(m_{ij}\) de\(\mat{M}\) es la media del primer tiempo de paso para pasar de\(s_i\) a\(s_j\) si\(i \ne j\); las entradas diagonales son 0. La matriz\(\mat{M}\) se llama La matriz\(\mat{D}\) es la matriz con todas las entradas 0 excepto las entradas diagonales\(d_{ii} = r_i\). La matriz\(\mat{D}\) se llama Let\(\mat {C}\) be una\(r \times r\) matriz con todas las entradas 1. Usando la Ecuación [eq 11.5.1] para el caso\(i \ne j\) y la Ecuación [eq 11.5.2] para el caso\(i = j\), obtenemos la ecuación de matriz\[\mat{M} = \mat{P} \mat{M} + \mat{C} - \mat{D}\ , \label{eq 11.5.3}\] o\[(\mat{I} - \mat{P}) \mat{M} = \mat{C} - \mat{D}\ . \label{eq 11.5.4}\] Ecuación [eq 11.5.4] con\(m_{ii} = 0\) implica Ecuaciones [eq 11.5.1] y [eq 11.5.2]. Ahora estamos en condiciones de probar nuestro primer teorema básico.

Para una cadena ergódica de Markov, el tiempo medio de recurrencia para el estado\(s_i\) es\(r_i = 1/w_i\), donde\(w_i\) está el componente\(i\) th del vector de probabilidad fija para la matriz de transición. Multiplicando ambos lados de la Ecuación [eq 11.5.4] por\(\mat{w}\) y usando el hecho que\[\mat {w}(\mat {I} - \mat {P}) = \mat {0}\] da\[\mat {w} \mat {C} - \mat {w} \mat {D} = \mat {0}\ .\] Aquí\(\mat {w} \mat {C}\) hay un vector de fila con todas las entradas 1 y\(\mat {w} \mat {D}\) es un vector de fila con la entrada\(i\) th\(w_i r_i\). Así\[(1,1,\ldots,1) = (w_1r_1,w_2r_2,\ldots,w_nr_n)\] y\[r_i = 1/w_i\ ,\] como debía probarse.

[cor 11.5.17] Para una cadena ergódica de Markov, los componentes del vector de probabilidad fija w son estrictamente positivos. Sabemos que los valores de\(r_i\) son finitos y así\(w_i = 1/r_i\) no pueden ser 0.

En Ejemplo [examen 11.3.3] encontramos que el vector de probabilidad fija para el ejemplo de laberinto es\[\mat {w} = \pmatrix{ \frac1{12} & \frac18 & \frac1{12} & \frac18 & \frac16 & \frac18 & \frac1{12} & \frac18 & \frac1{12}}\ .\] Por lo tanto, los tiempos medios de recurrencia están dados por los recíprocos de estas probabilidades. Es decir,\[\mat {r} = \pmatrix{ 12 & 8 & 12 & 8 & 6 & 8 & 12 & 8 & 12 }\ .\]

Al regresar a la Tierra de Oz, encontramos que el clima en la Tierra de Oz podría estar representado por una cadena de Markov con estados lluvia, agradable, y nieve. En la Sección 1.3 encontramos que el vector limitante fue\(\mat {w} = (2/5,1/5,2/5)\). De esto vemos que el número medio de días entre días lluviosos es 5/2, entre días agradables es 5, y entre días nevados es 5/2.

Matriz Fundamental

Ahora desarrollaremos una matriz fundamental para las cadenas ergódicas que jugará un papel similar al de la matriz fundamental\(\mat {N} = (\mat {I} - \mat {Q})^{-1}\) para absorber cadenas. Como fue el caso de las cadenas absorbentes, la matriz fundamental puede ser utilizada para encontrar una serie de cantidades interesantes que involucran cadenas ergódicas. Usando esta matriz, daremos un método para calcular los tiempos medios de primer paso para las cadenas ergódicas que sea más fácil de usar que el método dado anteriormente. Además, declararemos (pero no probaremos) el Teorema del Límite Central para las Cadenas de Markov, cuyo enunciado utiliza la matriz fundamental.

Comenzamos considerando el caso que es la matriz de transición de una cadena regular de Markov. Como no hay estados absorbentes, podríamos tener la tentación\(\mat {Z} = (\mat {I} - \mat {P})^{-1}\) de intentar una matriz fundamental. Pero\(\mat {I} - \mat {P}\) no tiene una inversa. Para ver esto, recordemos que una matriz\(\mat{R}\) tiene un inverso si y sólo si\(\mat {R} \mat {x} = \mat {0}\) implica\(\mat {x} = \mat {0}\). Pero como\(\mat {P} \mat {c} = \mat {c}\) tenemos\((\mat {I} - \mat {P})\mat {c} = \mat {0}\), y así\(\mat {I} - \mat {P}\) no tiene una inversa.

Recordamos que si tenemos una cadena de Markov absorbente, y es la restricción de la matriz de transición al conjunto de estados transitorios, entonces la matriz fundamental podría escribirse como\[\mat {N} = \mat {I} + \mat {Q} + \mat {Q}^2 + \cdots\ .\] La razón por la que esta serie de poder converge es que\(\mat {Q}^n \rightarrow 0\), por lo que esta serie actúa como una serie geométrica convergente.

Esta idea podría incitar a uno a tratar de encontrar una serie similar para cadenas regulares. Como sabemos eso\(\mat {P}^n \rightarrow \mat {W}\), podríamos considerar la serie Ahora\[\mat {I} + (\mat {P} -\mat {W}) + (\mat {P}^2 - \mat{W}) + \cdots\ .\label{eq 11.5.8}\] usamos propiedades especiales de y para reescribir esta serie. Las propiedades especiales son: 1)\(\mat {P}\mat {W} = \mat {W}\) y 2)\(\mat {W}^k = \mat {W}\) para todos los enteros positivos\(k\). Estos hechos son fáciles de verificar, y se dejan como ejercicio (ver Ejercicio [exer 11.5.28]). Usando estos hechos, vemos que\[\begin{aligned} (\mat {P} - \mat {W})^n &=& \sum_{i = 0}^n (-1)^i{n \choose i}\mat {P}^{n-i}\mat {W}^i \\ &=& \mat {P}^n + \sum_{i = 1}^n (-1)^i{n \choose i} \mat {W}^i \\ &=& \mat {P}^n + \sum_{i = 1}^n (-1)^i{n \choose i} \mat {W} \\ &=& \mat {P}^n + \Biggl(\sum_{i = 1}^n (-1)^i{n \choose i}\Biggr) \mat {W}\ .\end{aligned}\] Si ampliamos la expresión\((1-1)^n\), usando el Teorema Binomial, obtenemos la expresión entre paréntesis arriba, excepto que tenemos un término extra (que equivale a 1). Ya que\((1-1)^n = 0\), vemos que la expresión anterior es igual a -1. Así que tenemos\[(\mat {P} - \mat {W})^n = \mat {P}^n - \mat {W}\ ,\] para todos\(n \ge 1\).

Ahora podemos reescribir la serie en [eq 11.5.8] como\[\mat {I} + (\mat {P} - \mat {W}) + (\mat {P} - \mat {W})^2 + \cdots\ .\] Dado que el término\(n\) th en esta serie es igual a\(\mat {P}^n - \mat {W}\), el\(n\) th término va a 0 como\(n\) va al infinito. Esto es suficiente para mostrar que esta serie converge, y suma a la inversa de la matriz\(\mat {I} - \mat {P} + \mat {W}\). Llamamos a esta inversa la asociada con la cadena, y la denotamos por.

En el caso de que la cadena sea ergódica, pero no regular, no es cierto que\(\mat {P}^n \rightarrow \mat {W}\) como\(n \rightarrow \infty\). Sin embargo, la matriz\(\mat {I} - \mat {P} + \mat {W}\) aún tiene una inversa, como ahora mostraremos.

Dejar ser la matriz de transición de una cadena ergódica, y dejar ser la matriz todas cuyas filas son el vector de fila de probabilidad fija para. Entonces la matriz\[\mat {I} - \mat {P} + \mat {W}\] tiene una inversa.

Dejar\(\mat{x}\) ser un vector de columna tal que\[(\mat {I} - \mat {P} + \mat {W})\mat {x} = \mat {0}\ .\] Para probar la proposición, basta con mostrar que debe ser el vector cero. Multiplicando esta ecuación por\(\mat{w}\) y utilizando el hecho de que\(\mat{w}(\mat{I} - \mat{ P}) = \mat{0}\) y\(\mat{w} \mat{W} = \mat {w}\), tenemos\[\mat {w}(\mat {I} - \mat {P} + \mat {W})\mat {x} = \mat {w} \mat {x} = \mat {0}\ .\] Por lo tanto,\[(\mat {I} - \mat {P})\mat {x} = \mat {0}\ .\]

Pero esto significa que\(\mat {x} = \mat {P} \mat {x}\) es un vector de columna fijo para\(\mat{P}\). Por Teorema [thm 11.3.10], esto sólo puede suceder si\(\mat{x}\) es un vector constante. Ya que\(\mat {w}\mat {x} = 0\), y tiene entradas estrictamente positivas, lo vemos\(\mat {x} = \mat {0}\). Esto completa la prueba.

Como en el caso regular, llamaremos a la inversa de la matriz\(\mat {I} - \mat {P} + \mat {W}\) la para la cadena ergódica con matriz de transición, y utilizaremos para denotar esta matriz fundamental.

[examen 11.5.2] Que\(\mat{P}\) sea la matriz de transición para el clima en la Tierra de Oz\[\begin{aligned} \mat{I} - \mat{P} + \mat{W} &=& \pmatrix{ 1 & 0 & 0\cr 0 & 1 & 0\cr 0 & 0 & 1\cr} - \pmatrix{ 1/2 & 1/4 & 1/4\cr 1/2 & 0 & 1/2\cr 1/4 & 1/4 & 1/2\cr} + \pmatrix{ 2/5 & 1/5 & 2/5\cr 2/5 & 1/5 & 2/5\cr 2/5 & 1/5 & 2/5\cr} \cr &=& \pmatrix{ 9/10 & -1/20 & 3/20\cr -1/10 & 6/5 & -1/10\cr 3/20 & -1/20 & 9/10\cr}\ ,\cr\end{aligned}\] Entonces así\[\mat{Z} = (\mat{I} - \mat{P} + \mat{W})^{-1} = \pmatrix{ 86/75 & 1/25 & -14/75\cr 2/25 & 21/25 & 2/25\cr -14/75 & 1/25 & 86/75\cr}\ .\]

Uso de la Matriz Fundamental para Calcular la Matriz Media del Primer Paso

Mostraremos cómo se puede obtener la matriz media de primer paso a partir de la matriz fundamental para una cadena ergódica de Markov. Antes de afirmar el teorema que da los primeros tiempos de paso, necesitamos algunos datos al respecto.

[thm 11.5.18] Dejar\(\mat{Z} = (\mat{I} - \mat{P} + \mat{W})^{-1}\), y dejar\(\mat{c}\) ser un vector de columna de todos los 1's Entonces\[\mat{Z}\mat{c} = \mat{c}\ ,\]\[\mat{w}\mat{Z} = \mat{w}\ ,\]\(\mat{P}\mat{c} = \mat{c}\) y\[\mat{Z}(\mat{I} - \mat{P}) = \mat{I} - \mat{W}\ .\] Desde y\(\mat{W}\mat{c} = \mat{c}\),\[\mat{c} = (\mat{I} - \mat{P} + \mat{W}) \mat{c}\ .\] Si multiplicamos ambos lados de esta ecuación a la izquierda por\(\mat{Z}\), obtenemos\[\mat{Z}\mat{c} = \mat{c}\ .\]

De igual manera\(\mat{w}\mat{W} = \mat{w}\), ya\(\mat{w}\mat{P} = \mat{w}\) y,\[\mat{w} = \mat{w}(\mat{I} - \mat{P} + \mat{W})\ .\] Si multiplicamos ambos lados de esta ecuación a la derecha por\(\mat{Z}\), obtenemos\[\mat{w}\mat{Z} = \mat{w}\ .\]

Por último, tenemos\[\begin{aligned} (\mat{I} - \mat{P} + \mat{W})(\mat{I} - \mat{W}) &=& \mat{I} - \mat{W} - \mat{P} + \mat{W} + \mat{W} - \mat{W}\\ &=& \mat{I} - \mat{P}\ .\end{aligned}\] Multiplicando a la izquierda por, obtenemos\[\mat{I} - \mat{W} = \mat{Z}(\mat{I} - \mat{P})\ .\] Esto completa la prueba.

El siguiente teorema muestra cómo se pueden obtener los tiempos medios de primer paso a partir de la matriz fundamental.

[thm 11.5.19] La matriz media de primer paso\(\mat{M}\) para una cadena ergódica se determina a partir de la matriz fundamental\(\mat{Z}\) y el vector de probabilidad de fila fija\(\mat{w}\) por\[m_{ij} = \frac{z_{jj} - z_{ij}}{w_j}\ .\] Mostramos en la Ecuación [eq 11.5.4] que\[(\mat {I} - \mat {P})\mat {M} = \mat {C} - \mat {D}\ .\] Así,\[\mat {Z}(\mat {I} - \mat {P})\mat {M} = \mat {Z} \mat {C} - \mat {Z} \mat {D}\ ,\] y a partir de Lema [thm 11.5.18], \[\mat {Z}(\mat {I} - \mat {P})\mat {M} = \mat {C} - \mat {Z} \mat {D}\ .\]Nuevamente usando Lema [thm 11.5.18], tenemos\[\mat {M} - \mat{W}\mat {M} = \mat {C} - \mat {Z} \mat {D}\] o\[\mat {M} = \mat {C} - \mat {Z} \mat {D} + \mat{W}\mat {M}\ .\] De esta ecuación, vemos que\[m_{ij} = 1 - z_{ij}r_j + (\mat{w} \mat{M})_j\ . \label{eq 11.5.6}\] Pero\(m_{jj} = 0\), y así\[0 = 1 - z_{jj}r_j + (\mat {w} \mat {M})_j\ ,\] o\[(\mat{w} \mat{M})_j = z_{jj}r_j - 1\ . \label{eq 11.5.7}\] De Ecuaciones [eq 11.5.6] y [eq 11.5.7], tenemos\[m_{ij} = (z_{jj} - z_{ij}) \cdot r_j\ .\] Since\(r_j = 1/w_j\),\[m_{ij} = \frac{z_{jj} - z_{ij}}{w_j}\ .\]

[examen 11.5.3] (Ejemplo [examen 11.5.2] continuado) En el ejemplo de la Tierra de Oz,\[\mat{Z} = (\mat{I} - \mat{P} + \mat{W})^{-1} = \pmatrix{ 86/75 & 1/25 & -14/75\cr 2/25 & 21/25 & 2/25\cr -14/75 & 1/25 & 86/75\cr}\ .\] encontramos que También hemos visto eso\(\mat {w} = (2/5,1/5, 2/5)\). Entonces, por ejemplo,\[\begin{aligned} m_{12} &=& \frac{z_{22} - z_{12}}{w_2} \\ &=& \frac{21/25 - 1/25}{1/5} \\ &=& 4\ ,\\\end{aligned}\] por Teorema [thm 11.5.19]. Realizando los cálculos para las otras entradas de\(\mat{M}\), obtenemos\[\mat {M} = \pmatrix{ 0 & 4 & 10/3\cr 8/3 & 0 & 8/3\cr 10/3 & 4 & 0\cr}\ .\]

Computación

El programa ErgodicChain calcula la matriz fundamental, el vector fijo, la matriz\(\mat{D}\) de recurrencia media y la matriz media de primer paso\(\mat{M}\). Hemos ejecutado el programa para el modelo de urna Ehrenfest (Ejemplo [examen 11.1.6]). Obtenemos:\[\mat {P} = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & 0 & 1 & 2 & 3 & 4 \cr 0 & .0000 & 1.0000 & .0000 & .0000 & .0000\cr 1 & .2500 & .0000 & .7500 & .0000 & .0000\cr 2 & .0000 & .5000 & .0000 & .5000 & .0000\cr 3 & .0000 & .0000 & .7500 & .0000 & .2500\cr 4 & .0000 & .0000 & .0000 & 1.0000& .0000\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ ;\]

\[\mat {w} = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & 0 & 1 & 2 & 3 & 4\cr & .0625 &.2500 &.3750 &.2500 &.0625\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ ;\]

\[\mat {r} = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & 0 & 1 & 2 & 3 & 4\cr & 16.0000 & 4.0000 & 2.6667 & 4.0000 & 16.0000\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ ;\]

\[\mat {M} = \begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & 0 & 1 & 2 & 3 & 4\cr 0 & .0000 & 1.0000 & 2.6667 & 6.3333 & 21.3333\cr 1 & 15.0000 & .0000 & 1.6667 & 5.3333 & 20.3333\cr 2 & 18.6667 & 3.6667 & .0000 & 3.6667 & 18.6667\cr 3 & 20.3333 & 5.3333 & 1.6667 & .0000 & 15.0000\cr 4 & 21.3333 & 6.3333 & 2.6667 & 1.0000 & .0000\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ .\]

De la matriz media de primer paso, vemos que el tiempo medio para pasar de 0 bolas en urna 1 a 2 bolas en urna 1 es de 2.6667 pasos mientras que el tiempo medio para pasar de 2 bolas en urna 1 a 0 bolas en urna 1 es 18.6667. Esto refleja el hecho de que el modelo exhibe una tendencia central. Por supuesto, al físico le interesa el caso de un gran número de moléculas, o bolas, y así debemos considerar este ejemplo para\(n\) tan grande que no podemos computarlo ni siquiera con una computadora.

Modelo Ehrenfest

(Ejemplo [examen 11.3.4] continuado) Consideremos el modelo Ehrenfest (ver Ejemplo [examen 11.1.6]) para la difusión de gas para el caso general de\(2n\) las bolas. Cada segundo, una de las\(2n\) bolas se elige al azar y se mueve de la urna en la que estaba a la otra urna. Si hay\(i\) bolas en la primera urna, entonces con probabilidad\(i/2n\) sacamos una de ellas y la ponemos en la segunda urna, y con probabilidad\((2n - i)/2n\) sacamos una bola de la segunda urna y la metemos en la primera urna. A cada segundo dejamos que el número\(i\) de bolas en la primera urna sea el estado del sistema. Entonces de estado\(i\) podemos pasar solo a estado\(i - 1\) y\(i + 1\), y las probabilidades de transición están dadas por\[p_{ij} = \left \{ \matrix{ \frac i{2n}\ , & \mbox{if} \,\,j = i-1, \cr 1 - \frac i{2n}\ , & \mbox{if} \,\,j = i+1, \cr 0\ , & \mbox{otherwise.}\cr}\right.\]

Esto define la matriz de transición de una cadena ergódica de Markov no regular (ver Ejercicio [exer 11.3.14]). Aquí al físico le interesan las predicciones a largo plazo sobre el estado ocupado. En Ejemplo [examen 11.3.4], dimos una razón intuitiva para esperar que el vector fijo\(\mat{w}\) sea la distribución binomial con parámetros\(2n\) y\(1/2\). Es fácil comprobar que esto es correcto. Entonces,\[w_i = \frac

ParseError: EOF expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/11:_Cadenas_Markov/11.05:_Tiempo_Medio_de_Primer_Paso_para_Cadenas_Ergódicas), /content/body/div[7]/p[2]/span[4]/span, line 1, column 2

{2^{2n}}\ .\] así el tiempo medio de recurrencia para el estado\(i\) es\[r_i = \frac{2^{2n}}

ParseError: EOF expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/11:_Cadenas_Markov/11.05:_Tiempo_Medio_de_Primer_Paso_para_Cadenas_Ergódicas), /content/body/div[7]/p[2]/span[6]/span, line 1, column 2

\ .\]

Considerar en particular el término central\(i = n\). Hemos visto que este término es aproximadamente\(1/\sqrt{\pi n}\). Así podemos aproximarnos\(r_n\) por\(\sqrt{\pi n}\).

Este modelo se utilizó para explicar el concepto de reversibilidad en sistemas físicos. Supongamos que dejamos que nuestro sistema funcione hasta que esté en equilibrio. En este punto, se hace una película, que muestra el progreso del sistema. Entonces se te muestra la película, y se te pide que digas si la película se mostró en la dirección hacia adelante o hacia atrás. Parecería que siempre debe haber una tendencia a moverse hacia una proporción igual de bolas para que el orden de tiempo correcto sea el que tenga más transiciones de\(i\) a\(i - 1\) si\(i > n\) y\(i\) a\(i + 1\) si\(i < n\).

En la Figura [fig 11.6] se muestran los resultados de simular el modelo de urna Ehrenfest para el caso de\(n = 50\) y 1000 unidades de tiempo, utilizando el programa Ehrenfesturn. La gráfica superior muestra estos resultados graficados en el orden en que ocurrieron y la gráfica inferior muestra los mismos resultados pero con el tiempo invertido. No hay diferencia aparente.

Observamos que si no hubiéramos comenzado en equilibrio, las dos gráficas normalmente se verían bastante diferentes.

Reversibilidad

Si el modelo de Ehrenfest se inicia en equilibrio, entonces el proceso no tiene una dirección aparente del tiempo. La razón de esto es que este proceso tiene una propiedad llamada Definir\(X_n\) para ser el número de bolas en la urna izquierda en el paso\(n\). Podemos calcular, para una cadena ergódica general, la probabilidad de transición inversa:\[\begin{aligned} P(X_{n - 1} = j | X_n = i) &=& \frac{P(X_{n - 1} = j,X_n = i)}{P(X_n = i)} \\ &=& \frac{P(X_{n - 1} = j) P(X_n = i | X_{n - 1} = j)}{P(X_n = i)} \\ &=& \frac{P(X_{n - 1} = j) p_{ji}}{P(X_n = i)}\ .\\\end{aligned}\]

En general, esto dependerá de\(n\), ya\(P(X_n = j)\) y también\(P(X_{n - 1} = j)\) cambiar con\(n\). No obstante, si empezamos con el vector\(\mat{w}\) o esperamos hasta alcanzar el equilibrio, este no será el caso. Entonces podemos definir\[p_{ij}^* = \frac{w_j p_{ji}}{w_i}\] como una matriz de transición para el proceso observado con el tiempo invertido.

Calculemos una probabilidad de transición típica para la cadena inversa\(\mat{ P}^* = \{p_{ij}^*\}\) en el modelo Ehrenfest. Por ejemplo,\[\begin{aligned} p_{i,i - 1}^* &=& \frac{w_{i - 1} p_{i - 1,i}}{w_i} = \frac

ParseError: EOF expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/11:_Cadenas_Markov/11.05:_Tiempo_Medio_de_Primer_Paso_para_Cadenas_Ergódicas), /content/body/div[8]/p[3]/span[2]/span[1], line 1, column 2

{2^{2n}} \times \frac{2n - i + 1}{2n} \times \frac{2^{2n}}

ParseError: EOF expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/11:_Cadenas_Markov/11.05:_Tiempo_Medio_de_Primer_Paso_para_Cadenas_Ergódicas), /content/body/div[8]/p[3]/span[2]/span[2], line 1, column 2

\\ &=& \frac{(2n)!}{(i - 1)!\,(2n - i + 1)!} \times \frac{(2n - i + 1) i!\, (2n - i)!}{2n(2n)!} \\ &=& \frac{i}{2n} = p_{i,i - 1}\ .\\\end{aligned}\]

Cálculos similares para las otras probabilidades de transición lo demuestran\(\mat {P}^* = \mat {P}\). Cuando esto ocurre el proceso se llama Claramente, una cadena ergódica es reversible si, y sólo si, por cada par de estados\(s_i\) y\(s_j\),\(w_i p_{ij} = w_j p_{ji}\). En particular, para el modelo Ehrenfest esto significa eso\(w_i p_{i,i - 1} = w_{i - 1} p_{i - 1,i}\). Así, en equilibrio, los pares\((i, i - 1)\) y\((i - 1, i)\) deberían ocurrir con la misma frecuencia. Si bien muchas de las cadenas de Markov que ocurren en aplicaciones son reversibles, esta es una condición muy fuerte. En Ejercicio [exer 11.5.12] se le pide encontrar un ejemplo de una cadena de Markov que no es reversible.

El teorema del límite central para las cadenas de Markov

Supongamos que tenemos una cadena ergódica de Markov con estados\(s_1, s_2, \ldots, s_k\). Es natural considerar la distribución de las variables aleatorias\(S^{(n)}_j\), lo que denota el número de veces que la cadena está en estado\(s_j\) en los primeros\(n\) pasos. El componente\(j\) th\(w_j\) del vector de fila de probabilidad fija\(\mat{w}\) es la proporción de veces que la cadena está\(s_j\) en estado a largo plazo. De ahí que sea razonable conjeturar que el valor esperado de la variable aleatoria\(S^{(n)}_j\)\(n \rightarrow \infty\), as, es asintótico a\(nw_j\), y es fácil demostrar que este es el caso (ver Ejercicio [exer 11.5.29]).

También es natural preguntarse si existe una distribución limitante de las variables aleatorias\(S^{(n)}_j\). La respuesta es sí, y de hecho, esta distribución limitante es la distribución normal. Al igual que en el caso de los ensayos independientes, se deben normalizar estas variables aleatorias. Así, debemos restar de\(S^{(n)}_j\) su valor esperado, y luego dividirlo por su desviación estándar. En ambos casos, utilizaremos los valores asintóticos de estas cantidades, en lugar de los propios valores. Así, en el primer caso, usaremos el valor\(nw_j\). No está tan claro qué debemos usar en el segundo caso. Resulta que la cantidad\[\sigma_j^2 = 2w_jz_{jj} - w_j - w_j^2 \label{eq 11.5.9}\] representa la varianza asintótica. Armados con estas ideas, podemos exponer el siguiente teorema.

[thm 11.5.20] (Teorema de Límite Central para Cadenas de Markov) Para una cadena ergódica, para cualquier número real\(r < s\), tenemos\[P\Biggl(r <

ParseError: EOF expected (click for details)

Callstack:
    at (Estadisticas/Teoria_de_Probabilidad/Libro:_Probabilidad_Introductoria_(Grinstead_y_Snell)/11:_Cadenas_Markov/11.05:_Tiempo_Medio_de_Primer_Paso_para_Cadenas_Ergódicas), /content/body/div[9]/p[3]/span[4]/span, line 1, column 2

< s\Biggr) \rightarrow {1\over{\sqrt {2\pi}}}\int_r^s e^{-x^2/2}\,dx\ ,\] como\(n \rightarrow \infty\), para cualquier elección de estado inicial, donde\(\sigma_j^2\) está la cantidad definida en la Ecuación [eq 11.5.9].

Observaciones Históricas

Las cadenas de Markov fueron introducidas por Andrevi Andreevich Markov (1856-1922) y fueron nombradas en su honor. Fue un talentoso pregrado que recibió una medalla de oro por su tesis de licenciatura en la Universidad de San Petersburgo. Además de ser un activo investigador matemático y profesor, también estuvo activo en la política y patricipado en el movimiento liberal en Rusia a principios del siglo XX. En 1913, cuando el gobierno celebró el 300 aniversario de la casa de la familia Romanov, Markov organizó una contra-celebración del 200 aniversario del descubrimiento de Bernoulli de la Ley de Grandes Números.

Markov fue llevado a desarrollar cadenas de Markov como extensión natural de secuencias de variables aleatorias independientes. En su primer trabajo, en 1906, demostró que para una cadena de Markov con probabilidades de transición positivas y estados numéricos el promedio de los resultados converge al valor esperado de la distribución limitante (el vector fijo). En un trabajo posterior demostró el teorema del límite central para tales cadenas. Escribiendo sobre Markov, A. P. Youschkevitch comenta:

Markov llegó a sus cadenas partiendo de las necesidades internas de la teoría de la probabilidad, y nunca escribió sobre sus aplicaciones a la ciencia física. Para él los únicos ejemplos reales de las cadenas fueron los textos literarios, donde los dos estados denotaban las vocales y consonantes. ¹⁹

En un artículo escrito en 1913, ²⁰ Markov eligió una secuencia de 20, 000 letras de Pushkin para ver si esta secuencia puede considerarse aproximadamente una cadena simple. Obtuvo la cadena Markov con matriz de transición\[\begingroup \m@th \@tempdima 8.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern 2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern 2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\snellbaselineskip}% & \mbox{vowel} & \mbox{consonant} \cr \mbox{vowel} & .128 & .872 \cr \mbox{consonant} & .663 & .337\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left(\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern 2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\snellbaselineskip}\,\right)$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup\ .\]

El vector fijo para esta cadena es\((.432, .568)\), lo que indica que debemos esperar alrededor de 43.2 por ciento de vocales y 56.8 por ciento de consonantes en la novela, lo que quedó corroborado por el recuento real.

Claude Shannon consideró una interesante extensión de esta idea en su libro ²¹ en el que desarrolló el concepto teórico-informativo de la entropía. Shannon considera una serie de aproximaciones de la cadena de Markov a la prosa inglesa. Lo hace primero por cadenas en las que los estados son letras y luego por cadenas en las que los estados son palabras. Por ejemplo, para el caso de las palabras presenta primero una simulación donde las palabras se eligen de forma independiente pero con frecuencias apropiadas.

REPRESENTANDO Y RÁPIDAMENTE ES UN BUEN APTO O VENIR PUEDE DIFERENTE NATURAL AQUÍ EL A EN VINO EL A DE EXPERTO GRIS VENIR A AMUEBLAR LA LÍNEA MENSAJE TENÍA SER ESTOS.

Luego toma nota del mayor parecido con el texto ordinario en inglés cuando las palabras son elegidas como cadena de Markov, en cuyo caso obtiene

LA CABEZA Y EN ATAQUE FRONTAL A UN ESCRITOR INGLÉS QUE EL CARÁCTER DE ESTE PUNTO ES POR LO TANTO OTRO MÉTODO PARA LAS LETRAS QUE EL TIEMPO DE QUIEN ALGUNA VEZ CONTÓ EL PROBLEMA POR UN INESPERADO.

Una simulación como la última se lleva a cabo abriendo un libro y eligiendo la primera palabra, digamos que es Luego se lee el libro hasta que la palabra vuelva a aparecer y la palabra posterior a ésta se elija como la segunda palabra, que resultó ser El libro se lee entonces hasta que la palabra vuelva a aparecer y se elija la siguiente palabra, y así sucesivamente.

Otros ejemplos tempranos del uso de cadenas de Markov ocurrieron en el estudio de Galton sobre el problema de la supervivencia de los apellidos en 1889 y en la cadena Markov introducida por P. y T. Ehrenfest en 1907 para difusión. Poincaré en 1912 dicussed barajar cartas en términos de una cadena ergódica de Markov definida en un grupo de permutación. El movimiento browniano, una versión temporal continua de la caminata aleatoria, fue introducido en 1900—1901 por L. Bachelier en su estudio del mercado de valores, y en 1905—1907 en las obras de A. Einstein y M. Smoluchowsky en su estudio de los procesos físicos.

Uno de los primeros estudios sistemáticos de cadenas finitas de Markov fue realizado por M. Frechet. ²² El tratamiento de las cadenas de Markov en términos de las dos matrices fundamentales que hemos utilizado fue desarrollado por Kemeny y Snell ²³ para evitar el uso de valores propios que uno de estos autores encontró demasiado complejos. La matriz fundamental\(\mat{N}\) ocurrió también en el trabajo de J. L. Doob y otros en el estudio de la conexión entre los procesos de Markov y la teoría clásica del potencial. La matriz fundamental\(\mat{Z}\) para las cadenas ergódicas apareció primero en el trabajo de Frechet, quien la utilizó para encontrar la varianza limitante para el teorema del límite central para las cadenas de Markov.

i [exer 11.5.1] Considerar la cadena de Markov con matriz de transición\[\mat {P} = \pmatrix{ 1/2 & 1/2 \cr 1/4 & 3/4}\ .\] Encuentra la matriz fundamental\(\mat{Z}\) para esta cadena. Calcula la matriz media del primer paso usando\(\mat{Z}\).

i [exer 11.5.2] Un estudio de las fortalezas de los equipos de fútbol de la Ivy League muestra que si una escuela tiene un equipo fuerte un año es igualmente probable que tenga un equipo fuerte o equipo promedio el próximo año; si tiene un equipo promedio, la mitad del tiempo es promedio el próximo año, y si cambia es igual de probable que volverse fuerte como débil; si es débil tiene 2/3 de probabilidad de permanecer así y 1/3 de convertirse en promedio.

1. Una escuela tiene un equipo fuerte. En promedio, ¿cuánto tiempo pasará antes de que tenga otro equipo fuerte?
2. Una escuela tiene un equipo débil; ¿cuánto tiempo (en promedio) deben esperar los egresados a un equipo fuerte?

i [exer 11.5.3] Considerar Ejemplo [examen 11.1.2] con\(a = .5\) y\(b = .75\). Supongamos que el Presidente dice que él o ella se postulará. Encuentra el tiempo esperado antes de la primera vez que la respuesta se transmite incorrectamente.

i [exer 11.5.4] Encuentra el tiempo medio de recurrencia para cada estado de Ejemplo [examen 11.1.2] para\(a = .5\) y\(b = .75\). Haga lo mismo para general\(a\) y\(b\).

i [exer 11.5.5] Un troquel se enrolla repetidamente. Demostrar por los resultados de esta sección que el tiempo medio entre ocurrencias de un número dado es 6.

i [exer 11.5.6] Para el ejemplo de la Tierra de Oz (Ejemplo [examen 11.1.1]), convertir la lluvia en un estado absorbente y encontrar la matriz fundamental\(\mat{N}\). Interpretar los resultados obtenidos de esta cadena en términos de la cadena original.

i [exer 11.5.7] Una rata corre por el laberinto mostrado en la Figura [fig 11.6.5]. En cada paso sale de la habitación en la que se encuentra eligiendo al azar una de las puertas que salen de la habitación.

1. Dar la matriz de transición\(\mat{P}\) para esta cadena de Markov.
2. Demostrar que es una cadena ergódica pero no una cadena regular.
3. Encuentra el vector fijo.
4. Encuentra el número esperado de pasos antes de llegar a la Sala 5 por primera vez, comenzando en la Sala 1.

i [exer 11.5.8] Modificar el programa ErgoDicChain para que puedas calcular las cantidades básicas para el ejemplo de cola de Ejercicio [sec 11.3]. [exer 11.3.19]. Interpretar el tiempo medio de recurrencia para el estado 0.

i [exer 11.5.9] Considera una caminata aleatoria sobre un círculo de circunferencia\(n\). El andador da un paso de unidad en sentido horario con probabilidad\(p\) y una unidad en sentido antihorario con probabilidad\(q = 1 - p\). Modifique el programa ErgodicChain para permitirle ingresar\(n\)\(p\) y calcular las cantidades básicas para esta cadena.

1. ¿Para qué valores de esta cadena\(n\) es regular? ¿Ergódica?
2. ¿Cuál es el vector limitante\(\mat{w}\)?
3. Encuentra la matriz media del primer paso para\(n = 5\) y\(p = .5\). Verifica eso\(m_{ij} = d(n - d)\), donde\(d\) esta la distancia en sentido horario de\(i\) a\(j\).

i [exer 11.5.10] Dos jugadores coinciden con centavos y tienen entre ellos un total de 5 centavos. Si en algún momento un jugador tiene todos los centavos, para mantener el juego en marcha, le devuelve uno al otro jugador y el juego continuará. Demuestre que este juego puede formularse como una cadena ergódica. Estudia esta cadena usando el programa ErgoDicChain.

i [exer 11.5.11] Calcular la matriz de transición inversa para el ejemplo Tierra de Oz (Ejemplo [examen 11.1.1]). ¿Esta cadena es reversible?

i [exer 11.5.12] Dé un ejemplo de una cadena de Markov ergódica de tres estados que no es reversible.

i [exer 11.5.13] Dejar\(\mat{P}\) ser la matriz de transición de una cadena ergódica de Markov y\(\mat{P}^*\) la matriz de transición inversa. Demostrar que tienen el mismo vector de probabilidad fija\(\mat{w}\).

i [exer 11.5.14] Si\(\mat{P}\) es una cadena reversible de Markov, ¿es necesariamente cierto que el tiempo medio para pasar de un estado\(i\) a\(j\) otro es igual al tiempo medio para pasar de un estado\(j\) a otro\(i\)? : Prueba el ejemplo Tierra de Oz (Ejemplo [examen 11.1.1]).

i [exer 11.5.15] Mostrar que cualquier cadena ergódica de Markov con una matriz de transición simétrica (es decir,\(p_{ij} = p_{ji})\) es reversible.

i [exer 11.5.18] (Crowell ²⁴) Dejar\(\mat{P}\) ser la matriz de transición de una cadena ergódica de Markov. Demuestre eso\[(\mat {I} + \mat {P} +\cdots+ \mat {P}^{n - 1})(\mat {I} - \mat {P} + \mat {W}) = \mat {I} - \mat {P}^n + n\mat {W}\ ,\] y a partir de este espectáculo que\[\frac{\mat {I} + \mat {P} +\cdots+ \mat {P}^{n - 1}}n \to \mat {W}\ ,\] como\(n \rightarrow \infty\).

i [exer 11.5.19] Una cadena ergódica de Markov se inicia en equilibrio (es decir, con vector de probabilidad inicial\(\mat{w}\)). El tiempo medio hasta la siguiente ocurrencia de estado\(s_i\) es\(\bar{m_i} = \sum_k w_k m_{ki} + w_i r_i\). Demostrar eso\(\bar {m_i} = z_{ii}/w_i\), mediante el uso de los hechos que\(\mat {w}\mat {Z} = \mat {w}\) y\(m_{ki} = (z_{ii} - z_{ki})/w_i\).

i [exer 11.5.20] Un juego de dados perpetuo continúa en Charley's Jones entra en Charley's en una noche en la que ya han habido 100 jugadas. Planea jugar hasta la próxima vez que se pongan los ojos de serpiente (un par de unos). Jones se pregunta cuántas veces jugará. Por un lado se da cuenta de que el tiempo promedio entre ojos de serpiente es de 36 por lo que debería jugar unas 18 veces ya que es igualmente probable que haya entrado a ambos lados del punto medio entre ocurrencias de ojos de serpiente. Por otro lado, los dados no tienen memoria, y así parecería que tendría que jugar 36 veces más sin importar cuáles hayan sido los resultados anteriores. ¿Cuál, si alguno, de los argumentos de Jones cree? Utilizando el resultado de Ejercicio [exer 11.5.19], calcular lo esperado para alcanzar los ojos de serpiente, en equilibrio, y ver si esto resuelve la aparente paradoja. Si aún tienes dudas, simula el experimento para decidir qué argumento es el correcto. ¿Se puede dar un argumento intuitivo que explique este resultado?

i [exer 11.5.22] Demostrar que, para una cadena ergódica de Markov (ver Teorema [thm 11.5.19]),\[\sum_j m_{ij} w_j = \sum_j z_{jj} - 1 = K\ .\] La segunda expresión anterior muestra que el número\(K\) es independiente de\(i\). El número\(K\) se llama Un premio se ofreció a la primera persona para dar una razón intuitivamente plausible para que la suma anterior fuera independiente de\(i\). (Véase también Ejercicio [exer 11.5.27].)

i [exer 11.5.23] Considera un juego jugado de la siguiente manera: Se le da una cadena regular de Markov con matriz\(\mat P\) de transición\(\mat{w}\), vector de probabilidad fija y una función de pago\(\mat f\) que asigna a cada estado\(s_i\) una cantidad\(f_i\) que puede ser positiva o negativa. Asumir eso\(\mat {w}\mat {f} = 0\). Ves esta cadena de Markov a medida que evoluciona, y cada vez que estás en el estado\(s_i\) recibes una cantidad\(f_i\). Demuestre que su ganancia esperada después de\(n\) los pasos puede ser representada por un vector de columna\(\mat{g}^{(n)}\), con\[\mat{g}^{(n)} = (\mat {I} + \mat {P} + \mat {P}^2 +\cdots+ \mat {P}^n) \mat {f}.\] Mostrar que como\(n \to \infty\),\(\mat {g}^{(n)} \to \mat {g}\) con\(\mat {g} = \mat {Z} \mat {f}\).

i [exer 11.5.24] Un juego altamente simplificado de “Monopoly” se juega en un tablero con cuatro casillas como se muestra en la Figura [fig 11.7]. Empiezas en GO. Enrolla un dado y se mueve en el sentido de las agujas del reloj alrededor del tablero un número de cuadrados igual al número que aparece en el dado. Usted cobra o paga una cantidad indicada en la plaza en la que aterriza. Luego vuelves a rodar el dado y te mueves alrededor del tablero de la misma manera desde tu última posición. Utilizando el resultado de Ejercicio [exer 11.5.23], estima la cantidad que debes esperar ganar a la larga jugando a esta versión de Monopoly.

i [exer 11.5.28] Mostrar que si\(\mat P\) es la matriz de transición de una cadena regular de Markov, y\(\mat W\) es la matriz cada una de cuyas filas es el vector de probabilidad fija correspondiente a\(\mat {P}\), entonces\(\mat {P}\mat {W} = \mat {W}\), y\(\mat {W}^k = \mat {W}\) para todos los enteros positivos\(k\).

i [exer 11.5.29] Supongamos que una cadena ergódica de Markov tiene estados\(s_1, s_2, \ldots, s_k\). Dejar\(S^{(n)}_j\) denotar el número de veces que la cadena está en estado\(s_j\) en los primeros\(n\) pasos. Dejar\(\mat{w}\) denotar el vector de fila de probabilidad fija para esta cadena. Mostrar que, independientemente del estado inicial, el valor esperado de\(S^{(n)}_j\), dividido por\(n\), tiende a\(w_j\) como\(n \rightarrow \infty\).: Si la cadena comienza en estado\(s_i\), entonces el valor esperado de\(S^{(n)}_j\) viene dado por la expresión\[\sum_{h = 0}^n p^{(h)}_{ij}\ .\]

i [exer 11.5.27] En el transcurso de un paseo con Snell por la avenida Minnehaha en Minneapolisin el otoño de 1983, Peter Doyle ²⁵ sugirió la siguiente explicación para la constancia de (ver Ejercicio [exer 11.5.22]). Elija un estado objetivo de acuerdo con el vector fijo\(\mat{w}\). Comience desde el estado\(i\) y espere hasta el momento\(T\) en que el estado objetivo ocurra por primera vez. \(K_i\)Sea el valor esperado de\(T\). Observe eso\[K_i + w_i \cdot 1/w_i= \sum_j P_{ij} K_j + 1\ ,\] y\[K_i = \sum_j P_{ij} K_j\ .\] por lo tanto Por el principio máximo,\(K_i\) es una constante. ¿Se le habría dado el premio a Pedro?