3.7: Resumen

En este capítulo se han desarrollado los resultados básicos sobre las cadenas de Markov de estado finito. Se demostró que los estados de cualquier cadena de estado finito se pueden dividir en clases, donde cada clase es transitoria o recurrente, y cada clase es periódica o aperiódica. Si una clase recurrente es periódica de punto\(d\), entonces los estados en esa clase se pueden dividir en\(d\) subconjuntos donde cada subconjunto tiene transiciones solo al siguiente subconjunto.

Las probabilidades de transición en la cadena de Markov se pueden representar como una matriz\([P]\), y las probabilidades de transición\(n\) -paso están dadas por el producto de la matriz\(\left[P^{n}\right]\). Si la cadena es ergódica, es decir, una clase recurrente aperiódica, entonces el límite de las probabilidades de transición\(n\) -step se vuelve independiente del estado inicial, es decir,\(\lim _{n \rightarrow \infty} P_{i j}^{n}=\pi_{j}\) donde\(\boldsymbol{\pi}=\left(\pi_{1}, \ldots, \pi_{\mathrm{M}}\right)\) se llama la probabilidad de estado estacionario. Así, el valor limitante de\(\left[P^{n}\right]\) es una matriz M por M cuyas filas son todas iguales, es decir, la matriz limitante es el producto\(\boldsymbol{e \pi}\). Las probabilidades de estado estacionario se especifican de manera única por\(\sum_{j} \pi_{i} P_{i j}=\pi_{j}\) y\(\sum_{i} \pi_{i}=1\). Esa solución única debe satisfacer\(\pi_{i}>0\) para todos\(i\). El mismo resultado se mantiene (ver Teorema 3.3.2) para las unichaínas aperidódicas con la excepción de que\(\pi_{i}=0\) para todos los estados transitorios.

Los valores propios y los vectores propios de\([P]\) son útiles de muchas maneras, pero en particular proporcionan resultados precisos sobre cómo\(P_{i j}^{n}\) se acerca\(\pi_{j}\) al aumentar\(n\). Siempre existe un valor propio igual a 1, y su multiplicidad es igual al número de clases recurrentes. Para cada clase recurrente, hay un vector propio izquierdo\(\boldsymbol{\pi}\) de valor propio 1. Es el vector de estado estacionario para la clase recurrente dada. Si una clase recurrente es periódica con punto\(d\), entonces hay valores propios\(d\) correspondientes de magnitud 1 uniformemente espaciados alrededor del círculo unitario. El vector propio izquierdo correspondiente a cada uno es distinto de cero solo en esa clase recurrente periódica.

Todos los demás valores propios de\([P]\) son menores de 1 en magnitud. Si los vectores propios de todo el conjunto de valores propios abarcan M espacio dimensional, entonces se\(\left[P^{n}\right]\) pueden representar por\ ref {3.30} que muestra explícitamente cómo se aborda el estado estacionario para clases de estados recurrentes aperiódicas. Si los vectores propios no abarcan el espacio M, entonces\ ref {3.30} se puede reemplazar por una forma Jordan.

Para una cadena arbitraria de Markov de estado finito, si el estado inicial es transitorio, entonces la cadena de Markov eventualmente entrará en un estado recurrente, y la probabilidad de que esto tome más de\(n\) pasos se acerca a cero geométricamente en\(n\); el Ejercicio 3.18 muestra cómo encontrar la probabilidad de que cada se ingresa la clase recurrente. Dada una entrada en una clase recurrente particular, los resultados sobre las cadenas recurrentes pueden ser utilizados para analizar el comportamiento dentro de esa clase.

Los resultados sobre las cadenas de Markov se extendieron a las cadenas de Markov con recompensas. El uso de funciones de recompensa (o funciones de costo) proporciona una manera sistemática de abordar una gran clase de problemas que van desde tiempos de primer paso hasta programación dinámica. Para las unichaínas, el resultado clave aquí es el Teorema 3.5.2, que proporciona tanto una expresión exacta como una expresión asintótica para la recompensa agregada esperada en n etapas. Las cadenas de Markov con recompensas y múltiples clases recurrentes se manejan mejor considerando las clases recurrentes individuales por separado.

Finalmente, se utilizaron los resultados de las cadenas de Markov con recompensas para entender la teoría de la decisión de Markov. Se desarrolló el algoritmo de programación dinámica Bellman y se discutió y analizó el algoritmo de mejora de políticas. El teorema 3.6.2 demostró la relación entre la política dinámica óptima y la política estacionaria óptima. Esta sección proporcionó solo una introducción a la programación dinámica y omitió toda discusión sobre el descuento (en el que la ganancia futura se considera que vale menos que la ganancia actual debido a las tasas de interés). El desarrollo también se restringió a espacios de estado finito.

Para una revisión de vectores, matrices y álgebra lineal, consulte cualquier texto introductorio sobre álgebra lineal como Strang [19]. Para una lectura adicional sobre la teoría de la decisión de Markov y la programación dinámica, véase Bertsekas, [3]. Bellman [1] es de interés histórico y bastante legible.