En probabilidad , una cadena de Markov en tiempo discreto ( DTMC ) es una secuencia de variables aleatorias, conocida como proceso estocástico , en el que el valor de la siguiente variable depende solo del valor de la variable actual, y no de ninguna variable en el pasado. . Por ejemplo, una máquina puede tener dos estados, A y E . Cuando se está en el estado A , existe una probabilidad del 40% de ella se mueve a estado E y una probabilidad del 60% de la misma que queda en el estado A . Cuando está en el estado E , hay un 70% de posibilidades de que se mueva a A y un 30% de posibilidades de que se quede en E. La secuencia de estados de la máquina es una cadena de Markov. Si denotamos la cadena por luego es el estado en el que arranca la máquina y es la variable aleatoria que describe su estado después de 10 transiciones. El proceso continúa para siempre, indexado por los números naturales .
Un ejemplo de un proceso estocástico que no es una cadena de Markov es el modelo de una máquina que tiene los estados A y E y se mueve a A desde cualquier estado con un 50% de probabilidad si alguna vez ha visitado A antes, y un 20% de probabilidad si lo ha hecho. nunca visitó A antes (dejando un 50% u 80% de probabilidad de que la máquina se mueva a E ). Esto se debe a que el comportamiento de la máquina depende de todo el historial; si la máquina está en E , puede tener un 50% o 20% de posibilidades de moverse a A , según sus valores pasados. Por tanto, no tiene la propiedad de Markov .
Una cadena de Markov se puede describir mediante una matriz estocástica , que enumera las probabilidades de pasar a cada estado desde cualquier estado individual. A partir de esta matriz, se puede calcular la probabilidad de estar en un estado particular n pasos en el futuro. El espacio de estados de una cadena de Markov se puede dividir en clases comunicantes que describen qué estados son alcanzables entre sí (en una transición o en muchas). Cada estado puede describirse como transitorio o recurrente, dependiendo de la probabilidad de que la cadena vuelva alguna vez a ese estado. Las cadenas de Markov pueden tener propiedades que incluyen periodicidad, reversibilidad y estacionariedad. Una cadena de Markov de tiempo continuo es como una cadena de Markov de tiempo discreto, pero mueve estados continuamente a través del tiempo en lugar de como pasos de tiempo discretos. Otros procesos estocásticos pueden satisfacer la propiedad de Markov, la propiedad de que el comportamiento pasado no afecta el proceso, solo el estado presente.
Definición
Una cadena de Markov en tiempo discreto es una secuencia de variables aleatorias con la propiedad de Markov , es decir, que la probabilidad de pasar al siguiente estado depende solo del estado actual y no de los estados anteriores:
- si ambas probabilidades condicionales están bien definidas, es decir, si
Los posibles valores de X i forman un conjunto contable S llamado espacio de estados de la cadena. [1]
Las cadenas de Markov a menudo se describen mediante una secuencia de gráficos dirigidos , donde los bordes del gráfico n están etiquetados por las probabilidades de pasar de un estado en el tiempo n a los otros estados en el tiempo n + 1,La misma información está representada por la matriz de transición del tiempo n al tiempo n + 1. Sin embargo, con frecuencia se supone que las cadenas de Markov son homogéneas en el tiempo (ver variaciones a continuación), en cuyo caso el gráfico y la matriz son independientes de n y, por lo tanto, no presentado como secuencias.
Estas descripciones destacan la estructura de la cadena de Markov que es independiente de la distribución inicial. Cuando es homogénea en el tiempo, la cadena se puede interpretar como una máquina de estados que asigna una probabilidad de saltar desde cada vértice o estado a uno adyacente. La probabilidad del estado de la máquina se puede analizar como el comportamiento estadístico de la máquina con un elemento del espacio de estados como entrada, o como el comportamiento de la máquina con la distribución inicial de estados como entrada, donde es el soporte de Iverson . [ cita requerida ]
Variaciones
- Las cadenas de Markov homogéneas en el tiempo (o cadenas de Markov estacionarias) son procesos donde
- para todos n . La probabilidad de la transición es independiente de n . [1]
- Una cadena de Markov con memoria (o una cadena de Markov de orden m )
- donde m es finito, es un proceso que satisface
- En otras palabras, el estado futuro depende de los m estados pasados . Es posible construir una cadena de que tiene la propiedad "clásica" de Markov al tomar como espacio de estados las tuplas m ordenadas de los valores X , es decir. . [ cita requerida ]
transiciones de n pasos
La probabilidad de pasar del estado i al estado j en n pasos de tiempo es
y la transición de un solo paso es
Para una cadena de Markov homogénea en el tiempo:
y
Las probabilidades de transición de n pasos satisfacen la ecuación de Chapman-Kolmogorov , que para cualquier k tal que 0 < k < n ,
donde S es el espacio de estados de la cadena de Markov. [1]
La distribución marginal Pr ( X n = x ) es la distribución entre estados en el tiempo n . La distribución inicial es Pr ( X 0 = x ). La evolución del proceso a través de un paso de tiempo se describe mediante
Comunicar clases y propiedades
Se dice que un estado j es accesible desde un estado i (escrito i → j ) si un sistema iniciado en el estado i tiene una probabilidad distinta de cero de pasar al estado j en algún momento. Formalmente, el estado j es accesible desde el estado i si existe un número entero n ij ≥ 0 tal que
Se dice que un estado i se comunica con el estado j (escrito i ↔ j ) si tanto i → j como j → i . Una clase comunicante es un conjunto máximo de estados C de modo que cada par de estados en C se comunican entre sí. La comunicación es una relación de equivalencia y las clases comunicantes son las clases de equivalencia de esta relación. [1]
Una clase de comunicación se cierra si la probabilidad de dejar la clase es cero, es decir, si i está en C pero j no lo está, entonces j no es accesible desde i . [1] El conjunto de clases que se comunican forma un gráfico acíclico dirigido heredando las flechas del espacio de estado original. Una clase de comunicación se cierra si y solo si no tiene flechas de salida en este gráfico.
Se dice que un estado i es esencial o final si para todo j tal que i → j también es cierto que j → i . Un estado i no es esencial si no es esencial. [2] Un estado es definitivo si y solo si su clase comunicante está cerrada.
Se dice que una cadena de Markov es irreductible si su espacio de estados es una sola clase comunicante; en otras palabras, si es posible llegar a cualquier estado desde cualquier estado. [1] [3]
Periodicidad
Un estado tiene período si alguno regresa al estado debe ocurrir en múltiplos de Pasos de tiempo. Formalmente, el período de estado Se define como
(dónde es el máximo común divisor ) siempre que este conjunto no esté vacío. De lo contrario, el período no está definido. [1] Tenga en cuenta que aunque un estado tiene un punto, puede que no sea posible llegar al estado en pasos. Por ejemplo, suponga que es posible volver al estado en pasos de tiempo; sería , aunque no aparece en esta lista.
Si , entonces se dice que el estado es aperiódico. De lo contrario (), se dice que el estado es periódico con período . La periodicidad es una propiedad de clase, es decir, si un estado tiene un período entonces cada estado en su clase comunicante tiene un punto . [1]
Transitoriedad y recurrencia
Se dice que un estado i es transitorio si, dado que comenzamos en el estado i , existe una probabilidad distinta de cero de que nunca volvamos a i . Formalmente, deje que la variable aleatoria T i sea el primer tiempo de retorno para indicar i (el "tiempo de golpe"):
El número
es la probabilidad de que volvamos al estado i por primera vez después de n pasos. Por lo tanto, el estado i es transitorio si
El estado i es recurrente (o persistente) si no es transitorio. La recurrencia y la fugacidad son propiedades de clase, es decir, se mantienen o no por igual para todos los miembros de una clase que se comunica. [1]
Un estado i es recurrente si y solo si el número esperado de visitas a i es infinito: [1]
Recurrencia positiva
Incluso si el tiempo de golpe es finito con probabilidad 1 , no es necesario que tenga una expectativa finita . El tiempo medio de recurrencia en el estado i es el tiempo de retorno esperado M i :
El estado i es positivo recurrente (o persistente no nulo) si M i es finito; de lo contrario, el estado i es nulo recurrente (o nulo persistente). La recurrencia positiva y nula son propiedades de las clases. [1]
Estados absorbentes
Un estado i se llama absorbente si es imposible salir de este estado. Por lo tanto, el estado i está absorbiendo si y solo si
Si cada estado puede alcanzar un estado absorbente, entonces la cadena de Markov es una cadena de Markov absorbente . [3]
Cadena de Markov reversible
Se dice que una cadena de Markov es reversible si hay una distribución de probabilidad π sobre sus estados tal que
para todos los tiempos ny todos los estados i y j . Esta condición se conoce como condición de equilibrio detallada (o ecuación de equilibrio local).
Considerando un tiempo arbitrario fijo n y usando la abreviatura
la ecuación de equilibrio detallada se puede escribir de forma más compacta como
El único paso de tiempo desde n a n + 1 puede ser pensado como cada persona i que tiene π i dólares inicialmente y el pago de cada persona j una fracción p ij de la misma. La condición de saldo detallada establece que en cada pago, la otra persona devuelve exactamente la misma cantidad de dinero. [4] Claramente, la cantidad total de dinero π que tiene cada persona permanece igual después del intervalo de tiempo, ya que cada dólar gastado se equilibra con el dólar correspondiente recibido. Esto se puede demostrar más formalmente por la igualdad
que esencialmente establece que la cantidad total de dinero que la persona j recibe (incluso de sí mismo) durante el intervalo de tiempo es igual a la cantidad de dinero que paga a otros, lo que equivale a todo el dinero que tenía inicialmente porque se asumió que todo el dinero se gasta (que es decir, p ji suma 1 sobre i ). La suposición es técnica, porque el dinero que no se utiliza realmente se considera simplemente que la persona j se paga a sí misma (es decir, p jj no es necesariamente cero).
Como n era arbitrario, este razonamiento es válido para cualquier n y, por lo tanto, para las cadenas de Markov reversibles, π es siempre una distribución de estado estable de Pr ( X n +1 = j | X n = i ) para cada n .
Si la cadena de Markov comienza en la distribución de estado estacionario, es decir, si , luego para todos y la ecuación de equilibrio detallada se puede escribir como
Los lados izquierdo y derecho de esta última ecuación son idénticos excepto por una inversión de los índices de tiempo n y n + 1.
El criterio de Kolmogorov da una condición necesaria y suficiente para que una cadena de Markov sea reversible directamente de las probabilidades de la matriz de transición. El criterio requiere que los productos de probabilidades alrededor de cada ciclo cerrado sean los mismos en ambas direcciones alrededor del ciclo.
Las cadenas de Markov reversibles son comunes en los enfoques de Monte Carlo de cadenas de Markov (MCMC) porque la ecuación de equilibrio detallada para una distribución deseada π implica necesariamente que la cadena de Markov se ha construido de modo que π es una distribución de estado estacionario. Incluso con cadenas de Markov no homogéneas en el tiempo, donde se utilizan múltiples matrices de transición, si cada una de estas matrices de transición muestra un equilibrio detallado con la distribución π deseada , esto implica necesariamente que π es una distribución de estado estable de la cadena de Markov.
Distribuciones estacionarias
Una distribución es una distribución estacionaria de la cadena de Markov con matriz estocástica si y solo si . Esto se puede escribir como: [1]
Esta condición implica que y por tanto si la cadena de Markov tiene distribución inicial luego (en distribución) para cualquier . [1]
Si una cadena de Markov es irreducible, entonces tiene una distribución estacionaria si y solo si es positiva recurrente, [5] en cuyo caso la única distribución está dada por dónde es el tiempo medio de recurrencia de i . [1]
Si una cadena tiene más de una clase de comunicación cerrada, sus distribuciones estacionarias no serán únicas (considere cualquier clase de comunicación cerrada en la cadena; cada uno tendrá su propia distribución estacionaria única. Al extender estas distribuciones a la cadena general, poniendo todos los valores a cero fuera de la clase de comunicación, se obtiene que el conjunto de medidas invariantes de la cadena original es el conjunto de todas las combinaciones convexas de la's). Sin embargo, si un estado j es aperiódico, entoncesy para cualquier otro estado i , sea f ij la probabilidad de que la cadena alguna vez visite el estado j si comienza en i ,
Si un estado i es periódico con un período k > 1, entonces el límite no existe, aunque el limite existe para cada entero r .
Análisis de estado estacionario y cadena de Markov no homogénea en el tiempo
Una cadena de Markov no tiene por qué ser necesariamente homogénea en el tiempo para tener una distribución de equilibrio. Si hay una distribución de probabilidad entre estados tal que
para cada estado j y cada vez n entonceses una distribución de equilibrio de la cadena de Markov. Esto puede ocurrir en los métodos de Markov Chain Monte Carlo (MCMC) en situaciones en las que se utilizan varias matrices de transición diferentes, porque cada una es eficiente para un tipo particular de mezcla, pero cada matriz respeta una distribución de equilibrio compartida.
Tiempos de golpe
El tiempo de golpe es el tiempo que comienza en un conjunto de estados dado hasta que la cadena llega a un estado o conjunto de estados dado. La distribución de dicho período de tiempo tiene una distribución de tipo de fase. La distribución más simple de este tipo es la de una sola transición distribuida exponencialmente. [ cita requerida ]
Tiempos de golpe esperados
Para un subconjunto de estados A ⊆ S , el vector k A de tiempos de golpe (donde el elementorepresenta el valor esperado , comenzando en el estado i en el que la cadena entra en uno de los estados del conjunto A ) es la solución mínima no negativa de [6]
Teorema ergódico
Un ejemplo de teoría ergódica , el teorema ergódico para los estados que para una cadena de Markov aperiódica irreducible, con dos estados cualesquiera i y j , [1]
- como
Notas
- ^ a b c d e f g h i j k l m n o p Grimmett, GR ; Stirzaker, DR (1992). "6". Probabilidad y procesos aleatorios (segunda ed.). Prensa de la Universidad de Oxford. ISBN 0198572220.
- ^ Asher Levin, David (2009). Cadenas de Markov y tiempos de mezcla . pag. 16 . ISBN 978-0-8218-4739-8.
- ^ a b Gagniuc, Paul A. (2017). Cadenas de Markov: de la teoría a la implementación y experimentación . Estados Unidos, Nueva Jersey: John Wiley & Sons. págs. 1–235. ISBN 978-1-119-38755-8.
- ^ Richard Durrett (19 de mayo de 2012). Fundamentos de los procesos estocásticos . Springer Science & Business Media. pag. 37. ISBN 978-1-4614-3615-7. Archivado desde el original el 6 de febrero de 2017.
- ^ Serfozo, Richard (2009), "Conceptos básicos de procesos estocásticos aplicados" , Probabilidad y sus aplicaciones : 35, doi : 10.1007 / 978-3-540-89332-5 , ISBN 978-3-540-89331-8, MR 2484222 , archivado desde el original el 19 de marzo de 2015
- ^ Norris, JR (1997). "Cadenas de Markov en tiempo continuo II". Cadenas de Markov . págs. 108-127. doi : 10.1017 / CBO9780511810633.005 . ISBN 9780511810633.
Referencias
- AA Markov (1971). "Extensión de los teoremas límite de la teoría de la probabilidad a una suma de variables conectadas en una cadena". reimpreso en el Apéndice B de: R. Howard. Sistemas probabilísticos dinámicos, volumen 1: Cadenas de Markov . John Wiley e hijos.
- Markov, AA (2006). Traducido por Link, David. "Un ejemplo de investigación estadística del texto Eugene Onegin sobre la conexión de muestras en cadenas" . Ciencia en contexto . 19 (4): 591–600. doi : 10.1017 / s0269889706001074 .
- Leo Breiman (1992) [1968] Probabilidad . Edición original publicada por Addison-Wesley; reimpreso por Society for Industrial and Applied MathematicsISBN 0-89871-296-3 . (Ver Capítulo 7)
- JL Doob (1953) Procesos estocásticos . Nueva York: John Wiley and Sons ISBN 0-471-52369-0 .
- SP Meyn y RL Tweedie (1993) Cadenas de Markov y estabilidad estocástica . Londres: Springer-Verlag ISBN 0-387-19832-6 . en línea: MCSS . Segunda edición publicada, Cambridge University Press, 2009.
- Kemeny, John G .; Hazleton Mirkil; J. Laurie Snell; Gerald L. Thompson (1959). Estructuras matemáticas finitas (1ª ed.). Englewood Cliffs, NJ: Prentice-Hall, Inc. Número de catálogo de la tarjeta de la Biblioteca del Congreso 59-12841.Texto clásico. cf Capítulo 6 Cadenas de Markov finitas págs. 384ss.
- John G. Kemeny y J. Laurie Snell (1960) Cadenas finitas de Markov , D. van Nostrand Company ISBN 0-442-04328-7
- E. Nummelin. "Cadenas de Markov irreductibles generales y operadores no negativos". Cambridge University Press, 1984, 2004. ISBN 0-521-60494-X
- Seneta, E. Matrices no negativas y cadenas de Markov . 2da rev. ed., 1981, XVI, 288 p., Softcover Springer Series in Statistics. (Publicado originalmente por Allen & Unwin Ltd., Londres, 1973) ISBN 978-0-387-29765-1