Una cadena de Markov o proceso de Markov es un modelo estocástico que describe una secuencia de posibles eventos en la que la probabilidad de cada evento depende únicamente del estado alcanzado en el evento anterior. Informalmente, esto puede considerarse como: "Lo que suceda a continuación depende sólo del estado actual de las cosas ". Una secuencia infinitamente numerable , en la que la cadena se mueve de estado en pasos de tiempo discretos, da una cadena de Markov de tiempo discreto (DTMC). Un proceso de tiempo continuo se denomina cadena de Markov de tiempo continuo (CTMC). Los procesos de Markov reciben su nombre en honor al matemático ruso Andrey Markov .
Las cadenas de Markov tienen muchas aplicaciones como modelos estadísticos de procesos del mundo real. [1] Proporcionan la base para los métodos de simulación estocástica general conocidos como cadena de Markov Monte Carlo , que se utilizan para simular muestreos a partir de distribuciones de probabilidad complejas y han encontrado aplicación en áreas que incluyen estadística bayesiana , biología , química , economía , finanzas y teoría de la información. , física , procesamiento de señales y procesamiento del habla . [1] [2] [3]
Los adjetivos markovianos y markovianos se utilizan para describir algo relacionado con un proceso de Markov. [4]
Un proceso de Markov es un proceso estocástico que satisface la propiedad de Markov (a veces caracterizada como " falta de memoria "). En términos más simples, es un proceso para el cual se pueden hacer predicciones sobre resultados futuros basándose únicamente en su estado actual y, lo más importante, tales predicciones son tan buenas como las que podrían hacerse conociendo la historia completa del proceso. [5] En otras palabras, condicionado al estado presente del sistema, sus estados futuro y pasado son independientes .
Una cadena de Markov es un tipo de proceso de Markov que tiene un espacio de estados discreto o un conjunto de índices discretos (que a menudo representa el tiempo), pero la definición precisa de una cadena de Markov varía. [6] Por ejemplo, es común definir una cadena de Markov como un proceso de Markov en tiempo discreto o continuo con un espacio de estados contable (por lo tanto, independientemente de la naturaleza del tiempo), [7] [8] [9] [10 ] pero también es común definir una cadena de Markov como si tuviera tiempo discreto en un espacio de estados contable o continuo (por lo tanto, independientemente del espacio de estados). [6]
Es necesario especificar el índice de parámetros de tiempo y espacio de estado del sistema . La siguiente tabla ofrece una descripción general de las diferentes instancias de procesos de Markov para diferentes niveles de generalidad del espacio de estados y para tiempo discreto versus tiempo continuo:
Tenga en cuenta que no existe un acuerdo definitivo en la literatura sobre el uso de algunos de los términos que indican casos especiales de procesos de Markov. Generalmente el término "cadena de Markov" se reserva para un proceso con un conjunto discreto de tiempos, es decir, una cadena de Markov de tiempo discreto (DTMC) , [11] pero algunos autores utilizan el término "proceso de Markov" para referirse a un cadena de Markov de tiempo continuo (CTMC) sin mención explícita. [12] [13] [14] Además, existen otras extensiones de los procesos de Markov a las que se hace referencia como tales pero que no necesariamente caen dentro de ninguna de estas cuatro categorías (ver modelo de Markov ). Además, el índice de tiempo no tiene por qué tener necesariamente un valor real; Al igual que con el espacio de estados, existen procesos concebibles que se mueven a través de conjuntos de índices con otras construcciones matemáticas. Observe que la cadena de Markov de tiempo continuo del espacio de estados general es general hasta tal punto que no tiene un término designado.
Si bien el parámetro de tiempo suele ser discreto, el espacio de estados de una cadena de Markov no tiene restricciones generalmente acordadas: el término puede referirse a un proceso en un espacio de estados arbitrario. [15] Sin embargo, muchas aplicaciones de las cadenas de Markov emplean espacios de estados finitos o contablemente infinitos , que tienen un análisis estadístico más sencillo. Además de los parámetros de índice de tiempo y espacio de estados, existen muchas otras variaciones, extensiones y generalizaciones (ver Variaciones). Para simplificar, la mayor parte de este artículo se concentra en el caso de tiempo discreto y espacio de estados discreto, a menos que se indique lo contrario.
Los cambios de estado del sistema se denominan transiciones. Las probabilidades asociadas con varios cambios de estado se denominan probabilidades de transición. El proceso se caracteriza por un espacio de estados, una matriz de transición que describe las probabilidades de transiciones particulares y un estado inicial (o distribución inicial) en todo el espacio de estados. Por convención, asumimos que todos los estados y transiciones posibles se han incluido en la definición del proceso, por lo que siempre hay un estado siguiente y el proceso no termina.
Un proceso aleatorio de tiempo discreto involucra un sistema que se encuentra en un cierto estado en cada paso, y el estado cambia aleatoriamente entre pasos. Los pasos a menudo se consideran momentos en el tiempo, pero también pueden referirse a una distancia física o cualquier otra medida discreta. Formalmente, los pasos son los números enteros o naturales , y el proceso aleatorio es un mapeo de estos a estados. La propiedad de Markov establece que la distribución de probabilidad condicional del sistema en el siguiente paso (y de hecho en todos los pasos futuros) depende sólo del estado actual del sistema y no adicionalmente del estado del sistema en los pasos anteriores.
Dado que el sistema cambia aleatoriamente, generalmente es imposible predecir con certeza el estado de una cadena de Markov en un momento dado en el futuro. Sin embargo, se pueden predecir las propiedades estadísticas del futuro del sistema. En muchas aplicaciones, son estas propiedades estadísticas las que son importantes.
Andrey Markov estudió los procesos de Markov a principios del siglo XX y publicó su primer artículo sobre el tema en 1906. [16] [17] [18] Los procesos de Markov en tiempo continuo se descubrieron mucho antes de su trabajo a principios del siglo XX en forma de El proceso de Poisson . [19] [20] [21] Markov estaba interesado en estudiar una extensión de secuencias aleatorias independientes, motivado por un desacuerdo con Pavel Nekrasov , quien afirmaba que la independencia era necesaria para que se cumpliera la ley débil de los grandes números . [22] En su primer artículo sobre las cadenas de Markov, publicado en 1906, Markov demostró que bajo ciertas condiciones los resultados promedio de la cadena de Markov convergerían a un vector fijo de valores, demostrando así una ley débil de grandes números sin el supuesto de independencia. [16] [17] [18] que se había considerado comúnmente como un requisito para que se cumplieran tales leyes matemáticas. [18] Más tarde, Markov utilizó cadenas de Markov para estudiar la distribución de vocales en Eugene Onegin , escrito por Alexander Pushkin , y demostró un teorema de límite central para tales cadenas. [dieciséis]
En 1912, Henri Poincaré estudió las cadenas de Markov en grupos finitos con el objetivo de estudiar el barajado de cartas. Otros usos tempranos de las cadenas de Markov incluyen un modelo de difusión, introducido por Paul y Tatyana Ehrenfest en 1907, y un proceso de ramificación, introducido por Francis Galton y Henry William Watson en 1873, que precede al trabajo de Markov. [16] [17] Después del trabajo de Galton y Watson, más tarde se reveló que su proceso de ramificación había sido descubierto y estudiado de forma independiente unas tres décadas antes por Irénée-Jules Bienaymé . [23] A partir de 1928, Maurice Fréchet se interesó por las cadenas de Markov, lo que finalmente le llevó a publicar en 1938 un estudio detallado sobre las cadenas de Markov. [16] [24]
Andrey Kolmogorov desarrolló en un artículo de 1931 gran parte de la teoría inicial de los procesos de Markov en tiempo continuo. [25] [26] Kolmogorov se inspiró en parte en el trabajo de Louis Bachelier de 1900 sobre las fluctuaciones en el mercado de valores, así como en el trabajo de Norbert Wiener sobre el modelo de movimiento browniano de Einstein. [25] [27] Introdujo y estudió un conjunto particular de procesos de Markov conocidos como procesos de difusión, donde derivó un conjunto de ecuaciones diferenciales que describen los procesos. [25] [28] Independientemente del trabajo de Kolmogorov, Sydney Chapman derivó en un artículo de 1928 una ecuación, ahora llamada ecuación de Chapman-Kolmogorov , de una manera matemáticamente menos rigurosa que Kolmogorov, mientras estudiaba el movimiento browniano. [29] Las ecuaciones diferenciales ahora se denominan ecuaciones de Kolmogorov [30] o ecuaciones de Kolmogorov-Chapman. [31] Otros matemáticos que contribuyeron significativamente a los fundamentos de los procesos de Markov incluyen a William Feller , a partir de la década de 1930, y luego a Eugene Dynkin , a partir de la década de 1950. [26]
Supongamos que hay un monedero que contiene cinco monedas de veinticinco centavos (cada una con un valor de 25 centavos), cinco monedas de diez centavos (cada una con un valor de 10 centavos) y cinco monedas de cinco centavos (cada una con un valor de 5 centavos), y una por una, las monedas se extraen al azar del monedero y se puesto sobre una mesa. Si representa el valor total de las monedas colocadas en la mesa después de n sorteos, con , entonces la secuencia no es un proceso de Markov.
Para ver por qué es así, supongamos que en los primeros seis sorteos, se extraen las cinco monedas de cinco y veinticinco centavos. De este modo . Si conocemos no sólo , sino también los valores anteriores, entonces podemos determinar qué monedas se han extraído y sabemos que la siguiente moneda no será una moneda de cinco centavos; entonces podemos determinar eso con probabilidad 1. Pero si no conocemos los valores anteriores, basándonos únicamente en el valor podríamos suponer que habíamos sacado cuatro monedas de diez centavos y dos monedas de cinco centavos, en cuyo caso ciertamente sería posible sacar otra moneda de cinco centavos. próximo. Por lo tanto, nuestras conjeturas sobre se ven afectadas por nuestro conocimiento de los valores antes de .
Sin embargo, es posible modelar este escenario como un proceso de Markov. En lugar de definir representar el valor total de las monedas en la mesa, podríamos definir representar el recuento de los distintos tipos de monedas en la mesa. Por ejemplo, podría definirse para representar el estado en el que hay una moneda de veinticinco centavos, cero monedas de diez centavos y cinco monedas de cinco centavos en la mesa después de 6 sorteos uno por uno. Este nuevo modelo podría estar representado por posibles estados, donde cada estado representa la cantidad de monedas de cada tipo (de 0 a 5) que hay sobre la mesa. (No se puede acceder a todos estos estados en 6 sorteos). Supongamos que el primer sorteo da como resultado el estado . La probabilidad de lograrlo ahora depende de ; por ejemplo, el Estado no es posible. Después del segundo sorteo, el tercer sorteo depende de qué monedas se han extraído hasta ahora, pero ya no sólo de las monedas extraídas para el primer estado (ya que desde entonces se ha añadido al escenario información probabilísticamente importante). De esta manera, la probabilidad del Estado depende exclusivamente del resultado del Estado.
Una cadena de Markov en tiempo discreto es una secuencia de variables aleatorias X 1 , X 2 , X 3 , ... con la propiedad de Markov , es decir, que la probabilidad de pasar al siguiente estado depende sólo del estado actual y no del anterior. estados:
Los posibles valores de X i forman un conjunto contable S llamado espacio de estados de la cadena.
Una cadena de Markov de tiempo continuo ( X t ) t ≥ 0 se define por un espacio de estados finito o contable S , una matriz de tasa de transición Q con dimensiones iguales a las del espacio de estados y una distribución de probabilidad inicial definida en el espacio de estados. Para i ≠ j , los elementos q ij no son negativos y describen la velocidad del proceso de transición del estado i al estado j . Los elementos q ii se eligen de manera que cada fila de la matriz de tasas de transición sume cero, mientras que las sumas de filas de una matriz de transición de probabilidad en una cadena de Markov (discreta) sean todas iguales a uno.
Hay tres definiciones equivalentes del proceso. [39]
Sea la variable aleatoria que describe el estado del proceso en el momento t , y supongamos que el proceso está en un estado i en el momento t . Entonces, sabiendo , es independiente de los valores anteriores , y como h → 0 para todo j y para todo t , donde está el delta de Kronecker , usando la notación o pequeña . Se puede considerar que mide qué tan rápido ocurre la transición de i a j .
Defina una cadena de Markov de tiempo discreto Y n para describir el enésimo salto del proceso y las variables S 1 , S 2 , S 3 , ... para describir los tiempos de retención en cada uno de los estados donde Si sigue la distribución exponencial con tasa parámetro - q Y yo Y yo .
Para cualquier valor n = 0, 1, 2, 3, ... y tiempos indexados hasta este valor de n : t 0 , t 1 , t 2 , ... y todos los estados registrados en esos momentos i 0 , i 1 , i 2 , i 3 , ... se cumple que
donde p ij es la solución de la ecuación directa (una ecuación diferencial de primer orden )
con condición inicial P(0) es la matriz identidad .
Si el espacio de estados es finito , la distribución de probabilidad de transición se puede representar mediante una matriz , llamada matriz de transición, con el ( i , j )ésimo elemento de P igual a
Dado que cada fila de P suma uno y todos los elementos no son negativos, P es una matriz estocástica derecha .
Una distribución estacionaria π es un vector (fila), cuyas entradas no son negativas y suman 1, no se modifica mediante la operación de la matriz de transición P sobre él y, por lo tanto, se define por
Al comparar esta definición con la de un vector propio vemos que los dos conceptos están relacionados y que
es un múltiplo normalizado ( ) de un vector propio izquierdo e de la matriz de transición P con un valor propio de 1. Si hay más de un vector propio unitario, entonces una suma ponderada de los estados estacionarios correspondientes también es un estado estacionario. Pero para una cadena de Markov uno suele estar más interesado en un estado estacionario que es el límite de la secuencia de distribuciones para alguna distribución inicial.
Los valores de una distribución estacionaria están asociados con el espacio de estados de P y sus vectores propios mantienen sus proporciones relativas preservadas. Dado que los componentes de π son positivos y la restricción de que su suma es la unidad se puede reescribir, vemos que el producto escalar de π con un vector cuyos componentes son todos 1 es la unidad y que π se encuentra en un simplex .
Si la cadena de Markov es homogénea en el tiempo, entonces la matriz de transición P es la misma después de cada paso, por lo que la probabilidad de transición de k pasos se puede calcular como la k -ésima potencia de la matriz de transición, P k .
Si la cadena de Markov es irreducible y aperiódica, entonces existe una distribución estacionaria única π . [40] Además, en este caso P k converge a una matriz de rango uno en la que cada fila es la distribución estacionaria π :
donde 1 es el vector columna con todas las entradas iguales a 1. Esto lo establece el teorema de Perron-Frobenius . Si, por cualquier medio, se encuentra, entonces la distribución estacionaria de la cadena de Markov en cuestión se puede determinar fácilmente para cualquier distribución inicial, como se explicará a continuación.
Para algunas matrices estocásticas P , el límite no existe mientras que la distribución estacionaria sí, como se muestra en este ejemplo:
(Este ejemplo ilustra una cadena periódica de Markov).
Debido a que hay varios casos especiales diferentes a considerar, el proceso de encontrar este límite, si existe, puede ser una tarea larga. Sin embargo, existen muchas técnicas que pueden ayudar a encontrar este límite. Sea P una matriz n × n y defina
Siempre es cierto que
Restando Q de ambos lados y factorizando se obtiene
donde In es la matriz identidad de tamaño n , y 0 n , n es la matriz cero de tamaño n × n . Al multiplicar matrices estocásticas siempre se obtiene otra matriz estocástica, por lo que Q debe ser una matriz estocástica (consulte la definición anterior). A veces es suficiente usar la ecuación matricial anterior y el hecho de que Q es una matriz estocástica para resolver Q. Incluyendo el hecho de que la suma de cada una de las filas en P es 1, hay n+1 ecuaciones para determinar n incógnitas, por lo que es computacionalmente más fácil si por un lado se selecciona una fila en Q y se sustituye cada uno de sus elementos por uno , y por el otro sustituye el elemento correspondiente (el de la misma columna) en el vector 0 , y luego multiplica a la izquierda este último vector por la inversa de la matriz anterior transformada para encontrar Q .
Aquí hay un método para hacerlo: primero, defina la función f ( A ) para devolver la matriz A con su columna más a la derecha reemplazada con todos unos. Si [ f ( P − I n )] −1 existe entonces [41] [40]
Una cosa a tener en cuenta es que si P tiene un elemento Pi , i en su diagonal principal que es igual a 1 y la i- ésima fila o columna está llena de ceros, entonces esa fila o columna permanecerá sin cambios en todas las subsiguientes. potencias P k . Por lo tanto, la i- ésima fila o columna de Q tendrá los 1 y los 0 en las mismas posiciones que en P.
Como se indicó anteriormente, de la ecuación (si existe) la distribución estacionaria (o de estado estable) π es un vector propio izquierdo de la matriz estocástica de filas P. Luego, suponiendo que P es diagonalizable o equivalentemente que P tiene n vectores propios linealmente independientes, la velocidad de convergencia se elabora de la siguiente manera. (Para matrices no diagonalizables, es decir, defectuosas , se puede comenzar con la forma normal de Jordan de P y proceder con un conjunto de argumentos un poco más complicado de manera similar. [42]
Sea U la matriz de vectores propios (cada uno normalizado para tener una norma L2 igual a 1) donde cada columna es un vector propio izquierdo de P y sea Σ la matriz diagonal de valores propios izquierdos de P , es decir, Σ = diag( λ 1 , λ 2 , λ 3 ,..., λ norte ). Luego por descomposición propia
Enumeremos los valores propios de manera que:
Dado que P es una matriz estocástica de filas, su valor propio izquierdo más grande es 1. Si hay una distribución estacionaria única, entonces el valor propio más grande y el vector propio correspondiente también son únicos (porque no hay otro π que resuelva la ecuación de distribución estacionaria anterior). Sea u i la i -ésima columna de la matriz U , es decir, u i es el vector propio izquierdo de P correspondiente a λ i . Sea también x un vector de filas de longitud n que representa una distribución de probabilidad válida; ya que los vectores propios u i abarcan podemos escribir
Si multiplicamos x por P desde la derecha y continuamos esta operación con los resultados, al final obtenemos la distribución estacionaria π . En otras palabras, π = a 1 u 1 ← xPP ... P = xP k como k → ∞. Eso significa
Dado que π es paralelo a u 1 (normalizado por la norma L2) y π ( k ) es un vector de probabilidad, π ( k ) se aproxima a a 1 u 1 = π cuando k → ∞ con una velocidad del orden de λ 2 / λ 1 exponencialmente. Esto se debe a que , por tanto, λ 2 / λ 1 es el término dominante. Cuanto menor es la relación, más rápida es la convergencia. [43] El ruido aleatorio en la distribución de estado π también puede acelerar esta convergencia a la distribución estacionaria. [44]
Muchos resultados para cadenas de Markov con espacio de estados finito se pueden generalizar a cadenas con espacio de estados incontable a través de cadenas de Harris .
El uso de cadenas de Markov en los métodos Monte Carlo de cadenas de Markov cubre casos en los que el proceso sigue un espacio de estados continuo.
Considerar una colección de cadenas de Markov cuya evolución tiene en cuenta el estado de otras cadenas de Markov, está relacionado con la noción de cadenas de Markov que interactúan localmente. Esto corresponde a la situación en la que el espacio de estados tiene una forma de producto (cartesiano). Véase sistema de partículas interactuantes y autómatas celulares estocásticos (autómatas celulares probabilísticos). Véase, por ejemplo, Interacción de los procesos de Markov [45] o. [46]
Se dice que dos estados se comunican entre sí si ambos son accesibles entre sí mediante una secuencia de transiciones que tienen probabilidad positiva. Ésta es una relación de equivalencia que produce un conjunto de clases comunicantes. Una clase está cerrada si la probabilidad de abandonar la clase es cero. Una cadena de Markov es irreductible si hay una clase comunicante, el espacio de estados.
Un estado i tiene período k si k es el máximo común divisor del número de transiciones por las cuales se puede alcanzar i , a partir de i . Eso es:
El estado es periódico si ; de lo contrario y el estado es aperiódico .
Se dice que un estado i es transitorio si, a partir de i , existe una probabilidad distinta de cero de que la cadena nunca regrese a i . De lo contrario , se llama recurrente (o persistente ). [47] Para un estado recurrente i , el tiempo medio de acierto se define como:
El estado i es recurrente positivo si es finito y recurrente nulo en caso contrario. La periodicidad, la transitoriedad, la recurrencia y la recurrencia positiva y nula son propiedades de clase; es decir, si un estado tiene la propiedad, entonces todos los estados de su clase comunicante tienen la propiedad. [48]
Un estado i se llama absorbente si no hay transiciones salientes desde el estado.
Dado que la periodicidad es una propiedad de clase, si una cadena de Markov es irreducible, entonces todos sus estados tienen el mismo período. En particular, si un estado es aperiódico, entonces toda la cadena de Markov es aperiódica. [49]
Si una cadena de Markov finita es irreducible, entonces todos los estados son recurrentes positivos y tiene una distribución estacionaria única dada por .
Un estado i se dice ergódico si es aperiódico y recurrente positivo. En otras palabras, un estado i es ergódico si es recurrente, tiene un período de 1 y un tiempo de recurrencia medio finito.
Si todos los estados de una cadena de Markov irreducible son ergódicos, entonces se dice que la cadena es ergódica. De manera equivalente, existe algún número entero tal que todas las entradas de sean positivas.
Se puede demostrar que una cadena de Markov irreducible de estado finito es ergódica si tiene un estado aperiódico. De manera más general, una cadena de Markov es ergódica si hay un número N tal que se puede alcanzar cualquier estado desde cualquier otro estado en cualquier número de pasos menor o igual a un número N. En el caso de una matriz de transición completamente conectada, donde todas las transiciones tienen una probabilidad distinta de cero, esta condición se cumple con N = 1.
Una cadena de Markov con más de un estado y sólo una transición saliente por estado no es irreducible o no es aperiódica, por lo que no puede ser ergódica.
Algunos autores llaman ergódicas, incluso periódicas, a cualquier cadena de Markov recurrente positiva e irreducible. [50] De hecho, las cadenas de Markov meramente irreducibles corresponden a procesos ergódicos , definidos según la teoría ergódica . [51]
Algunos autores llaman primitiva a una matriz si existe algún número entero tal que todas las entradas de sean positivas. [52] Algunos autores lo llaman regular . [53]
El índice de primitividad , o exponente , de una matriz regular, es el más pequeño tal que todas las entradas de sean positivas. El exponente es una propiedad puramente teórica de grafos, ya que depende sólo de si cada entrada de es cero o positiva y, por lo tanto, se puede encontrar en un gráfico dirigido con su matriz de adyacencia.
Hay varios resultados combinatorios sobre el exponente cuando hay un número finito de estados. Sea el número de estados, entonces [54]
Si una cadena de Markov tiene una distribución estacionaria, entonces se puede convertir en un sistema dinámico que preserva la medida : Sea el espacio de probabilidad , donde está el conjunto de todos los estados de la cadena de Markov. Dejemos que el álgebra sigma en el espacio de probabilidad sea generada por los conjuntos de cilindros. Dejemos que la medida de probabilidad sea generada por la distribución estacionaria y la transición de la cadena de Markov. Sea el operador de turno: . De manera similar, podemos construir un sistema dinámico con en su lugar. [56]
Dado que las cadenas de Markov irreducibles con espacios de estados finitos tienen una distribución estacionaria única, la construcción anterior es inequívoca para las cadenas de Markov irreducibles.
En teoría ergódica , un sistema dinámico que preserva la medida se llama "ergódico" si es cualquier subconjunto medible que implique o (hasta un conjunto nulo).
La terminología es inconsistente. Dada una cadena de Markov con una distribución estacionaria que es estrictamente positiva en todos los estados, la cadena de Markov es irreducible si y solo si su correspondiente sistema dinámico que preserva la medida es ergódico . [51]
En algunos casos, procesos aparentemente no markovianos pueden tener todavía representaciones markovianas, construidas ampliando el concepto de estados "actuales" y "futuros". Por ejemplo, sea X un proceso no markoviano. Luego defina un proceso Y , tal que cada estado de Y represente un intervalo de tiempo de estados de X . Matemáticamente esto toma la forma:
Si Y tiene la propiedad de Markov, entonces es una representación markoviana de X.
Un ejemplo de un proceso no markoviano con representación markoviana es una serie temporal autorregresiva de orden mayor que uno. [57]
El tiempo de acierto es el tiempo que comienza en un conjunto determinado de estados hasta que la cadena llega a un estado o conjunto de estados determinado. La distribución de dicho período de tiempo tiene una distribución de tipo fase. La distribución más simple es la de una única transición distribuida exponencialmente.
Para un subconjunto de estados A ⊆ S , el vector k A de tiempos de acierto (donde elemento representa el valor esperado , comenzando en el estado i en el que la cadena ingresa a uno de los estados en el conjunto A ) es la solución mínima no negativa para [ 58]
Para un CTMC Xt , el proceso inverso en el tiempo se define como . Según el lema de Kelly, este proceso tiene la misma distribución estacionaria que el proceso directo.
Se dice que una cadena es reversible si el proceso inverso es el mismo que el proceso directo. El criterio de Kolmogorov establece que la condición necesaria y suficiente para que un proceso sea reversible es que el producto de las velocidades de transición alrededor de un circuito cerrado debe ser el mismo en ambas direcciones.
Un método para encontrar la distribución de probabilidad estacionaria , π , de una cadena de Markov ergódica de tiempo continuo, Q , es encontrar primero su cadena de Markov incorporada (EMC) . Estrictamente hablando, la EMC es una cadena de Markov regular de tiempo discreto, a veces denominada proceso de salto . Cada elemento de la matriz de probabilidad de transición de un paso del EMC, S , se denota por s ij y representa la probabilidad condicional de transición del estado i al estado j . Estas probabilidades condicionales se pueden encontrar mediante
A partir de esto, S puede escribirse como
donde I es la matriz identidad y diag( Q ) es la matriz diagonal formada seleccionando la diagonal principal de la matriz Q y estableciendo todos los demás elementos en cero.
Para encontrar el vector de distribución de probabilidad estacionaria, a continuación debemos encontrar tal que
siendo un vector fila, tal que todos los elementos son mayores que 0 y = 1. A partir de esto, π se puede encontrar como
( S puede ser periódico, incluso si Q no lo es. Una vez que se encuentra π , se debe normalizar a un vector unitario ).
Otro proceso de tiempo discreto que puede derivarse de una cadena de Markov de tiempo continuo es un esqueleto δ: la cadena de Markov (de tiempo discreto) formada al observar X ( t ) a intervalos de δ unidades de tiempo. Las variables aleatorias X (0), X (δ), X (2δ), ... dan la secuencia de estados visitados por el δ-esqueleto.
Los modelos de Markov se utilizan para modelar sistemas cambiantes. Hay 4 tipos principales de modelos que generalizan las cadenas de Markov dependiendo de si cada estado secuencial es observable o no, y de si el sistema debe ajustarse en función de las observaciones realizadas:
Un esquema de Bernoulli es un caso especial de una cadena de Markov donde la matriz de probabilidad de transición tiene filas idénticas, lo que significa que el siguiente estado es independiente incluso del estado actual (además de ser independiente de los estados pasados). Un esquema de Bernoulli con sólo dos estados posibles se conoce como proceso de Bernoulli .
Tenga en cuenta, sin embargo, según el teorema del isomorfismo de Ornstein , que toda cadena de Markov aperiódica e irreducible es isomorfa a un esquema de Bernoulli; [59] por lo tanto, uno podría igualmente afirmar que las cadenas de Markov son un "caso especial" de los esquemas de Bernoulli. El isomorfismo generalmente requiere una recodificación complicada. El teorema del isomorfismo es incluso un poco más fuerte: establece que cualquier proceso estocástico estacionario es isomorfo a un esquema de Bernoulli; la cadena de Markov es sólo un ejemplo de ello.
Cuando la matriz de Markov se reemplaza por la matriz de adyacencia de un gráfico finito , el desplazamiento resultante se denomina cadena de Markov topológica o subdesplazamiento de tipo finito . [59] Una matriz de Markov que sea compatible con la matriz de adyacencia puede proporcionar una medida del subdesplazamiento. Muchos sistemas dinámicos caóticos son isomórficos a las cadenas topológicas de Markov; los ejemplos incluyen difeomorfismos de variedades cerradas , el sistema Prouhet-Thue-Morse , el sistema Chacón, los sistemas sóficos , los sistemas libres de contexto y los sistemas de codificación por bloques. [59]
Las cadenas de Markov se han empleado en una amplia gama de temas en las ciencias naturales y sociales, y en aplicaciones tecnológicas.
Los sistemas markovianos aparecen ampliamente en termodinámica y mecánica estadística , siempre que se utilizan probabilidades para representar detalles desconocidos o no modelados del sistema, si se puede suponer que la dinámica es invariante en el tiempo y que no es necesario considerar una historia relevante que no esté ya incluida. en la descripción del estado. [60] [61] Por ejemplo, un estado termodinámico opera bajo una distribución de probabilidad que es difícil o costosa de adquirir. Por lo tanto, el método Markov Chain Monte Carlo se puede utilizar para extraer muestras aleatoriamente de una caja negra para aproximar la distribución de probabilidad de atributos en una variedad de objetos. [61]
Las cadenas de Markov se utilizan en simulaciones QCD de celosía . [62]
Una red de reacción es un sistema químico que involucra múltiples reacciones y especies químicas. Los modelos estocásticos más simples de tales redes tratan el sistema como una cadena de Markov de tiempo continuo, siendo el estado el número de moléculas de cada especie y con reacciones modeladas como posibles transiciones de la cadena. [63] Las cadenas de Markov y los procesos de Markov de tiempo continuo son útiles en química cuando los sistemas físicos se aproximan mucho a la propiedad de Markov. Por ejemplo, imagine un gran número n de moléculas en solución en el estado A, cada una de las cuales puede sufrir una reacción química al estado B con una determinada velocidad promedio. Quizás la molécula sea una enzima y los estados se refieran a cómo está plegada. El estado de cualquier enzima sigue una cadena de Markov y, dado que las moléculas son esencialmente independientes entre sí, el número de moléculas en el estado A o B a la vez es n veces la probabilidad de que una molécula determinada se encuentre en ese estado.
El modelo clásico de actividad enzimática, la cinética de Michaelis-Menten , puede verse como una cadena de Markov, donde en cada paso la reacción avanza en alguna dirección. Si bien Michaelis-Menten es bastante sencillo, también se pueden modelar redes de reacción mucho más complicadas con cadenas de Markov. [64]
También se utilizó un algoritmo basado en una cadena de Markov para centrar el crecimiento basado en fragmentos de sustancias químicas in silico hacia una clase deseada de compuestos, como fármacos o productos naturales. [65] A medida que una molécula crece, se selecciona un fragmento de la molécula naciente como el estado "actual". No es consciente de su pasado (es decir, no es consciente de lo que ya está ligado a él). Luego pasa al siguiente estado cuando se le adjunta un fragmento. Las probabilidades de transición se basan en bases de datos de clases auténticas de compuestos. [66]
Además, el crecimiento (y la composición) de los copolímeros se puede modelar utilizando cadenas de Markov. Con base en las relaciones de reactividad de los monómeros que forman la cadena polimérica en crecimiento, se puede calcular la composición de la cadena (por ejemplo, si los monómeros tienden a agregarse de manera alterna o en series largas del mismo monómero). Debido a los efectos estéricos , los efectos de Markov de segundo orden también pueden desempeñar un papel en el crecimiento de algunas cadenas poliméricas.
De manera similar, se ha sugerido que las cadenas de Markov pueden describir con precisión la cristalización y el crecimiento de algunos materiales de óxido superreticular epitaxial. [67]
Las cadenas de Markov se utilizan en diversas áreas de la biología. Ejemplos notables incluyen:
Varios teóricos han propuesto la idea de la prueba estadística de la cadena de Markov (MCST), un método para unir cadenas de Markov para formar una " manta de Markov ", disponiendo estas cadenas en varias capas recursivas ("obleas") y produciendo conjuntos de pruebas más eficientes: muestras. —como reemplazo de pruebas exhaustivas. [ cita necesaria ]
Las evaluaciones de la variabilidad de la irradiancia solar son útiles para aplicaciones de energía solar . La variabilidad de la irradiancia solar en cualquier lugar a lo largo del tiempo es principalmente una consecuencia de la variabilidad determinista de la trayectoria del sol a través de la cúpula celeste y la variabilidad de la nubosidad. La variabilidad de la irradiancia solar accesible en la superficie de la Tierra se ha modelado utilizando cadenas de Markov, [70] [71] [72] [73] incluyendo también el modelado de los dos estados de claridad y nubosidad como una cadena de Markov de dos estados. [74] [75]
Los modelos ocultos de Markov se han utilizado en sistemas automáticos de reconocimiento de voz . [76]
Las cadenas de Markov se utilizan en todo el procesamiento de información. El famoso artículo de Claude Shannon de 1948 , Una teoría matemática de la comunicación , que en un solo paso creó el campo de la teoría de la información , comienza introduciendo el concepto de entropía a través del modelado de Markov del idioma inglés. Estos modelos idealizados pueden capturar muchas de las regularidades estadísticas de los sistemas. Incluso sin describir perfectamente la estructura completa del sistema, dichos modelos de señales pueden hacer posible una compresión de datos muy eficaz mediante técnicas de codificación entrópica como la codificación aritmética . También permiten una estimación eficaz del estado y el reconocimiento de patrones . Las cadenas de Markov también juegan un papel importante en el aprendizaje por refuerzo .
Las cadenas de Markov también son la base de los modelos ocultos de Markov, que son una herramienta importante en campos tan diversos como las redes telefónicas (que utilizan el algoritmo de Viterbi para la corrección de errores), el reconocimiento de voz y la bioinformática (como la detección de reordenamientos [77] ).
El algoritmo de compresión de datos sin pérdidas LZMA combina cadenas de Markov con compresión Lempel-Ziv para lograr relaciones de compresión muy altas.
Las cadenas de Markov son la base para el tratamiento analítico de las colas ( teoría de las colas ). Agner Krarup Erlang inició el tema en 1917. [78] Esto los hace críticos para optimizar el rendimiento de las redes de telecomunicaciones, donde los mensajes a menudo deben competir por recursos limitados (como el ancho de banda). [79]
Numerosos modelos de colas utilizan cadenas de Markov de tiempo continuo. Por ejemplo, una cola M/M/1 es una CTMC en números enteros no negativos donde las transiciones ascendentes de i a i + 1 ocurren a una velocidad λ según un proceso de Poisson y describen la llegada de empleos, mientras que las transiciones de i a i – 1 (para i > 1) ocurren a una velocidad μ (los tiempos de servicio del trabajo se distribuyen exponencialmente) y describen los servicios completados (salidas) de la cola.
El PageRank de una página web tal como lo utiliza Google está definido por una cadena de Markov. [80] [81] [82] Es la probabilidad de estar en la página en la distribución estacionaria en la siguiente cadena de Markov en todas las páginas web (conocidas). Si es el número de páginas web conocidas y una página tiene enlaces a ella, entonces tiene probabilidad de transición para todas las páginas que están enlazadas y para todas las páginas que no están enlazadas. Se considera que el parámetro es aproximadamente 0,15. [83]
Los modelos de Markov también se han utilizado para analizar el comportamiento de navegación web de los usuarios. La transición de un enlace web de un usuario en un sitio web en particular se puede modelar utilizando modelos de Markov de primer o segundo orden y se puede utilizar para hacer predicciones sobre la navegación futura y personalizar la página web para un usuario individual.
Los métodos de cadena de Markov también se han vuelto muy importantes para generar secuencias de números aleatorios para reflejar con precisión distribuciones de probabilidad deseadas muy complicadas, a través de un proceso llamado cadena de Markov Monte Carlo (MCMC). En los últimos años, esto ha revolucionado la viabilidad de los métodos de inferencia bayesianos , permitiendo simular una amplia gama de distribuciones posteriores y encontrar numéricamente sus parámetros. [ cita necesaria ]
Las cadenas de Markov se utilizan en finanzas y economía para modelar una variedad de fenómenos diferentes, incluida la distribución del ingreso, la distribución del tamaño de las empresas, los precios de los activos y las caídas del mercado. DG Champernowne construyó un modelo de cadena de Markov para la distribución del ingreso en 1953. [84] Herbert A. Simon y el coautor Charles Bonini utilizaron un modelo de cadena de Markov para derivar una distribución estacionaria de Yule del tamaño de las empresas. [85] Louis Bachelier fue el primero en observar que los precios de las acciones seguían un camino aleatorio. [86] El paseo aleatorio se consideró más tarde como evidencia a favor de la hipótesis del mercado eficiente y los modelos de paseo aleatorio fueron populares en la literatura de la década de 1960. [87] Los modelos de ciclos económicos de cambio de régimen fueron popularizados por James D. Hamilton (1989), quien utilizó una cadena de Markov para modelar cambios entre períodos de alto y bajo crecimiento del PIB (o, alternativamente, expansiones y recesiones económicas). [88] Un ejemplo más reciente es el modelo multifractal de cambio de Markov de Laurent E. Calvet y Adlai J. Fisher, que se basa en la conveniencia de modelos anteriores de cambio de régimen. [89] [90] Utiliza una cadena de Markov arbitrariamente grande para impulsar el nivel de volatilidad de los rendimientos de los activos.
La macroeconomía dinámica hace un uso intensivo de las cadenas de Markov. Un ejemplo es el uso de cadenas de Markov para modelar exógenamente los precios de las acciones en un entorno de equilibrio general . [91]
Las agencias de calificación crediticia elaboran tablas anuales de probabilidades de transición para bonos de diferentes calificaciones crediticias. [92]
Las cadenas de Markov se utilizan generalmente para describir argumentos dependientes de la ruta , donde las configuraciones estructurales actuales condicionan resultados futuros. Un ejemplo es la reformulación de la idea, originalmente debida a Das Kapital de Karl Marx , que vincula el desarrollo económico con el surgimiento del capitalismo . En la investigación actual, es común utilizar una cadena de Markov para modelar cómo una vez que un país alcanza un nivel específico de desarrollo económico, la configuración de factores estructurales, como el tamaño de la clase media , la proporción de residencia urbana y rural, la tasa de movilización política , etc., generarán una mayor probabilidad de transición de un régimen autoritario a un régimen democrático . [93]
Las cadenas de Markov se pueden utilizar para modelar muchos juegos de azar. Los juegos infantiles Serpientes y escaleras y " Hi Ho! Cherry-O ", por ejemplo, están representados exactamente por cadenas de Markov. En cada turno, el jugador comienza en un estado determinado (en un cuadrado determinado) y desde allí tiene probabilidades fijas de pasar a otros estados (cuadrados).
Las cadenas de Markov se emplean en la composición musical algorítmica , particularmente en software como Csound , Max y SuperCollider . En una cadena de primer orden, los estados del sistema se convierten en valores de nota o tono, y se construye un vector de probabilidad para cada nota, completando una matriz de probabilidad de transición (ver más abajo). Se construye un algoritmo para producir valores de notas de salida basados en las ponderaciones de la matriz de transición, que podrían ser valores de notas MIDI , frecuencia ( Hz ) o cualquier otra métrica deseable. [94]
Se puede introducir una cadena de Markov de segundo orden considerando el estado actual y también el estado anterior, como se indica en la segunda tabla. Las cadenas superiores de orden n tienden a "agrupar" notas particulares, mientras que ocasionalmente se "dividen" en otros patrones y secuencias. Estas cadenas de orden superior tienden a generar resultados con un sentido de estructura fraseal , en lugar del "deambular sin objetivo" producido por un sistema de primer orden. [95]
Las cadenas de Markov se pueden utilizar estructuralmente, como en Analogique A y B de Xenakis. [96] Las cadenas de Markov también se utilizan en sistemas que utilizan un modelo de Markov para reaccionar interactivamente a la entrada de música. [97]
Por lo general, los sistemas musicales necesitan imponer restricciones de control específicas sobre las secuencias de longitud finita que generan, pero las restricciones de control no son compatibles con los modelos de Markov, ya que inducen dependencias de largo alcance que violan la hipótesis de Markov de memoria limitada. Para superar esta limitación, se ha propuesto un nuevo enfoque. [98]
Los modelos de cadenas de Markov se han utilizado en el análisis avanzado del béisbol desde 1960, aunque su uso aún es poco común. Cada media entrada de un juego de béisbol se ajusta al estado de la cadena de Markov cuando se considera el número de corredores y outs. Durante cualquier turno al bate, hay 24 combinaciones posibles de número de outs y posición de los corredores. Mark Pankin muestra que los modelos de cadena de Markov se pueden utilizar para evaluar carreras creadas tanto para jugadores individuales como para un equipo. [99] También analiza varios tipos de estrategias y condiciones de juego: cómo se han utilizado los modelos de cadena de Markov para analizar estadísticas de situaciones de juego como toques y robo de bases y diferencias entre jugar sobre césped y AstroTurf . [100]
Los procesos de Markov también se pueden utilizar para generar texto superficialmente de apariencia real a partir de un documento de muestra. Los procesos de Markov se utilizan en una variedad de software recreativo " generador de parodias " (ver prensa disociada , Jeff Harrison, [101] Mark V. Shaney , [102] [103] y Academias Neutronium). Existen varias bibliotecas de generación de texto de código abierto que utilizan cadenas de Markov.
Las cadenas de Markov se han utilizado para pronosticar en varias áreas: por ejemplo, tendencias de precios, [104] energía eólica, [105] terrorismo estocástico , [106] [107] e irradiancia solar . [108] Los modelos de pronóstico de la cadena de Markov utilizan una variedad de configuraciones, desde discretizar las series de tiempo, [105] hasta modelos ocultos de Markov combinados con wavelets, [104] y el modelo de distribución mixta de la cadena de Markov (MCM). [108]