Cadena de Markov

Parte de una serie sobre estadísticas
Teoría de la probabilidad
Probabilidad Axiomas Determinismo Sistema Indeterminismo Aleatoriedad
Espacio de probabilidad Espacio muestral Evento Eventos colectivamente exhaustivos Evento elemental Exclusividad mutua Resultado Semifallo Experimento El proceso de Bernoulli Distribución de probabilidad Distribución de Bernoulli Distribución binomial Distribución exponencial Distribución normal Distribución de Pareto Distribución de Poisson Medida de probabilidad Variable aleatoria Proceso de Bernoulli Continuo o discreto Valor esperado Diferencia Cadena de Markov Valor observado Paseo aleatorio Proceso estocástico
Evento complementario Probabilidad conjunta Probabilidad marginal Probabilidad condicional
Independencia Independencia condicional Ley de probabilidad total Ley de los grandes números Teorema de Bayes Desigualdad de Boole
Diagrama de Venn Diagrama de árbol
en a mi

Una cadena de Markov o proceso de Markov es un proceso estocástico que describe una secuencia de eventos posibles en la que la probabilidad de cada evento depende únicamente del estado alcanzado en el evento anterior. De manera informal, esto puede considerarse como "Lo que sucede a continuación depende únicamente del estado actual de las cosas ". Una secuencia infinitamente contable , 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 generales de simulación estocástica conocidos como Monte Carlo de cadenas de Markov , que se utilizan para simular el muestreo 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 , teoría de la información , física , procesamiento de señales y procesamiento de voz . ^{[1] [2] [3]}

Los adjetivos markoviano y markoviano se utilizan para describir algo que está 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 que es más importante, dichas predicciones son tan buenas como las que se podrían hacer conociendo la historia completa del proceso. ^[5] En otras palabras, dependiendo del estado actual 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 representan 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 contables (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 que tiene tiempo discreto en un espacio de estados contables o continuos (por lo tanto, independientemente del espacio de estados). ^[6]

Es necesario especificar el índice de parámetros de tiempo y espacio de estados del sistema . La siguiente tabla ofrece una descripción general de las diferentes instancias de procesos de Markov para diferentes niveles de generalidad de espacio de estados y para tiempo discreto frente a tiempo continuo:

Nótese que no hay un acuerdo definitivo en la literatura sobre el uso de algunos de los términos que significan casos especiales de procesos de Markov. Usualmente 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 usan el término "proceso de Markov" para referirse a una cadena de Markov de tiempo continuo (CTMC) sin mención explícita. ^{[12] [13] [14]} Además, hay otras extensiones de procesos de Markov que se conocen 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 necesariamente necesita ser de valor real; al igual que con el espacio de estados, hay procesos concebibles que se mueven a través de conjuntos de índices con otras construcciones matemáticas. Nótese que la cadena de Markov de tiempo continuo del espacio de estados general es general a tal grado que no tiene un término designado.

Aunque el parámetro de tiempo suele ser discreto, el espacio de estados de una cadena de Markov no tiene ninguna restricción generalmente aceptada: 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 numerablemente infinitos , que tienen un análisis estadístico más sencillo. Además de los parámetros de índice de tiempo y de 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 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 implica un sistema que se encuentra en un estado determinado en cada paso, y que cambia de estado aleatoriamente entre los pasos. Los pasos suelen considerarse momentos en el tiempo, pero también pueden referirse a distancias físicas o a cualquier otra medida discreta. Formalmente, los pasos son los números enteros o naturales y el proceso aleatorio es una aplicación de estos a estados. La propiedad de Markov establece que la distribución de probabilidad condicional para el sistema en el siguiente paso (y, de hecho, en todos los pasos futuros) depende únicamente del estado actual del sistema y no, además, 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, las propiedades estadísticas del futuro del sistema sí se pueden predecir. En muchas aplicaciones, son estas propiedades estadísticas las que son importantes.

Andrey Markov estudió los procesos de Markov a principios del siglo XX, publicando 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 la forma del 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 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, probando así una ley débil de los grandes números sin el supuesto de independencia, ^{[16] [17] [18]} que había sido considerado comúnmente como un requisito para que tales leyes matemáticas se cumplieran. ^[18] Posteriormente, 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 dichas cadenas. ^[16]

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 precedió al trabajo de Markov. ^{[16] [17]} Después del trabajo de Galton y Watson, se reveló más tarde 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ó en las cadenas de Markov, lo que finalmente lo llevó a publicar en 1938 un estudio detallado sobre las cadenas de Markov. ^{[16] [24]}

Andrey Kolmogorov desarrolló en un artículo de 1931 una gran parte de la teoría temprana de los procesos de Markov en tiempo continuo. ^{[25] [26]} Kolmogorov se inspiró en parte en el trabajo de 1900 de Louis Bachelier 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 las bases de los procesos de Markov incluyen a William Feller , a partir de la década de 1930, y luego más tarde a Eugene Dynkin , a partir de la década de 1950. ^[26]

• Los paseos aleatorios basados ​​en números enteros y el problema de la ruina del jugador son ejemplos de procesos de Markov. ^{[32] [33]} Algunas variaciones de estos procesos se estudiaron cientos de años antes en el contexto de variables independientes. ^{[34] [35]} Dos ejemplos importantes de procesos de Markov son el proceso de Wiener , también conocido como el proceso de movimiento browniano , y el proceso de Poisson , ^[19] que se consideran los procesos estocásticos más importantes y centrales en la teoría de procesos estocásticos. ^{[36] [37] [38]} Estos dos procesos son procesos de Markov en tiempo continuo, mientras que los paseos aleatorios sobre los números enteros y el problema de la ruina del jugador son ejemplos de procesos de Markov en tiempo discreto. ^{[32] [33]}
• Una famosa cadena de Markov es la llamada "caminata del borracho", un paseo aleatorio por la recta numérica en el que, en cada paso, la posición puede cambiar en +1 o -1 con la misma probabilidad. Desde cualquier posición hay dos transiciones posibles, al siguiente o al anterior entero. Las probabilidades de transición dependen únicamente de la posición actual, no de la forma en que se alcanzó la posición. Por ejemplo, las probabilidades de transición de 5 a 4 y de 5 a 6 son ambas 0,5, y todas las demás probabilidades de transición a partir de 5 son 0. Estas probabilidades son independientes de si el sistema estaba previamente en 4 o 6.
• Una serie de estados independientes (por ejemplo, una serie de lanzamientos de moneda) satisface la definición formal de una cadena de Markov. Sin embargo, la teoría suele aplicarse solo cuando la distribución de probabilidad del siguiente estado depende del actual.

Supongamos que hay un monedero que contiene cinco monedas de veinticinco centavos (cada una con un valor de 25¢), cinco de diez centavos (cada una con un valor de 10¢) y cinco de cinco centavos (cada una con un valor de 5¢), y una por una, se extraen monedas al azar del monedero y se colocan sobre una mesa. Si representa el valor total de las monedas colocadas sobre la mesa después de n extracciones, con , entonces la secuencia no es un proceso de Markov.${\displaystyle X_{n}}$${\displaystyle X_{0}=0}$${\displaystyle \{X_{n}:n\in \mathbb {N} \}}$

Para ver por qué es así, supongamos que en los primeros seis sorteos se extraen las cinco monedas de cinco centavos y una de veinticinco centavos. Por lo tanto , . Si no solo conocemos , 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; por lo tanto, podemos determinarlo con una probabilidad de 1. Pero si no conocemos los valores anteriores, entonces, basándonos solo en el valor, podríamos suponer que habíamos extraído cuatro monedas de diez centavos y dos de cinco centavos, en cuyo caso, sin duda, sería posible extraer otra moneda de cinco centavos a continuación. Por lo tanto, nuestras suposiciones sobre se ven afectadas por nuestro conocimiento de los valores anteriores a .${\displaystyle X_{6}=\$0.50}$${\displaystyle X_{6}}$${\displaystyle X_{7}\geq \$0.60}$${\displaystyle X_{6}}$${\displaystyle X_{7}}$${\displaystyle X_{6}}$

Sin embargo, es posible modelar este escenario como un proceso de Markov. En lugar de definir para representar el valor total de las monedas en la mesa, podríamos definir para representar el recuento de los diversos tipos de monedas en la mesa. Por ejemplo, podría definirse para representar el estado donde hay una moneda de veinticinco centavos, cero monedas de diez centavos y cinco monedas de cinco centavos en la mesa después de 6 extracciones una por una. Este nuevo modelo podría representarse por estados posibles, donde cada estado representa el número de monedas de cada tipo (de 0 a 5) que están en la mesa. (No todos estos estados son alcanzables dentro de 6 extracciones). Supongamos que la primera extracción da como resultado el estado . La probabilidad de lograrlo ahora depende de ; por ejemplo, el estado no es posible. Después de la segunda extracción, la tercera extracción depende de qué monedas se han extraído hasta ahora, pero ya no solo de las monedas que se extrajeron para el primer estado (ya que desde entonces se ha agregado información probabilísticamente importante al escenario). De esta manera, la probabilidad del estado depende exclusivamente del resultado del estado.${\displaystyle X_{n}}$${\displaystyle X_{n}}$${\displaystyle X_{6}=1,0,5}$${\displaystyle 6\times 6\times 6=216}$${\displaystyle X_{1}=0,1,0}$${\displaystyle X_{2}}$${\displaystyle X_{1}}$${\displaystyle X_{2}=1,0,1}$${\displaystyle X_{n}=i,j,k}$${\displaystyle X_{n-1}=\ell ,m,p}$

Una cadena de Markov de tiempo discreto es una secuencia de variables aleatorias X ₁ , X ₂ , X ₃ , ... con la propiedad de Markov , es decir, que la probabilidad de pasar al siguiente estado depende sólo del estado actual y no de los estados anteriores:

${\displaystyle \Pr(X_{n+1}=x\mid X_{1}=x_{1},X_{2}=x_{2},\ldots ,X_{n}=x_{n})=\Pr(X_{n+1}=x\mid X_{n}=x_{n}),}$si ambas probabilidades condicionales están bien definidas, es decir, si${\displaystyle \Pr(X_{1}=x_{1},\ldots ,X_{n}=x_{n})>0.}$

_{Los posibles valores} de Xi forman un conjunto contable S llamado espacio de estados de la cadena.

• Las cadenas de Markov homogéneas en el tiempo son procesos en los que para todo n , la probabilidad de la transición es independiente de n .$${\displaystyle \Pr(X_{n+1}=x\mid X_{n}=y)=\Pr(X_{n}=x\mid X_{n-1}=y)}$$
• Las cadenas de Markov estacionarias son procesos en los que, para todos los n y k , se puede demostrar que toda cadena estacionaria es homogénea en el tiempo mediante la regla de Bayes.$${\displaystyle \Pr(X_{0}=x_{0},X_{1}=x_{1},\ldots ,X_{k}=x_{k})=\Pr(X_{n}=x_{0},X_{n+1}=x_{1},\ldots ,X_{n+k}=x_{k})}$$
  Una condición necesaria y suficiente para que una cadena de Markov homogénea en el tiempo sea estacionaria es que la distribución de sea una distribución estacionaria de la cadena de Markov.${\displaystyle X_{0}}$
• 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 a partir de la cual tiene la propiedad 'clásica' de Markov tomando como espacio de estados las m -tuplas ordenadas de valores X , es decir, .$${\displaystyle {\begin{aligned}{}&\Pr(X_{n}=x_{n}\mid X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{1}=x_{1})\\=&\Pr(X_{n}=x_{n}\mid X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{n-m}=x_{n-m}){\text{ for }}n>m\end{aligned}}}$$${\displaystyle (Y_{n})}$${\displaystyle (X_{n})}$${\displaystyle Y_{n}=\left(X_{n},X_{n-1},\ldots ,X_{n-m+1}\right)}$

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 son no negativos y describen la tasa de transición del proceso del estado i al estado j . Los elementos q _ii se eligen de modo que cada fila de la matriz de tasa 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.

Existen 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 que , es independiente de los valores anteriores , y cuando h → 0 para todo j y para todo t , donde es el delta de Kronecker , utilizando la notación de o minúscula . Se puede considerar que mide la rapidez con la que ocurre la transición de i a j .${\displaystyle X_{t}}$${\displaystyle X_{t}=i}$${\displaystyle X_{t+h}=j}$${\displaystyle \left(X_{s}:s<t\right)}$$${\displaystyle \Pr(X(t+h)=j\mid X(t)=i)=\delta _{ij}+q_{ij}h+o(h),}$$${\displaystyle \delta _{ij}}$${\displaystyle q_{ij}}$

Defina una cadena de Markov de tiempo discreto Y _n para describir el n º salto del proceso y las variables S ₁ , S ₂ , S ₃ , ... para describir los tiempos de retención en cada uno de los estados donde S _i sigue la distribución exponencial con parámetro de velocidad − q _{Y i Y i} .

Para cualquier valor n = 0, 1, 2, 3, ... y tiempos indexados hasta este valor de n : t ₀ , t ₁ , t ₂ , ... y todos los estados registrados en estos tiempos i ₀ , i ₁ , i ₂ , i ₃ , ... se cumple que

${\displaystyle \Pr(X_{t_{n+1}}=i_{n+1}\mid X_{t_{0}}=i_{0},X_{t_{1}}=i_{1},\ldots ,X_{t_{n}}=i_{n})=p_{i_{n}i_{n+1}}(t_{n+1}-t_{n})}$

donde p _ij es la solución de la ecuación directa (una ecuación diferencial de primer orden )

${\displaystyle P'(t)=P(t)Q}$

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 elemento ( i , j ) de P igual a

${\displaystyle p_{ij}=\Pr(X_{n+1}=j\mid X_{n}=i).}$

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 cambia por la operación de la matriz de transición P sobre ella y por lo tanto se define por

${\displaystyle \pi \mathbf {P} =\pi .}$

Comparando esta definición con la de un vector propio vemos que los dos conceptos están relacionados y que

${\displaystyle \pi ={\frac {e}{\sum _{i}{e_{i}}}}}$

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 sea el límite de la secuencia de distribuciones para alguna distribución inicial.${\textstyle \sum _{i}\pi _{i}=1}$

Los valores de una distribución estacionaria están asociados con el espacio de estados de P y sus vectores propios conservan sus proporciones relativas. Dado que los componentes de π son positivos y la restricción de que su suma es la unidad se puede reescribir como vemos que el producto escalar de π con un vector cuyos componentes son todos 1 es la unidad y que π se encuentra en un símplex .${\displaystyle \textstyle \pi _{i}}$${\textstyle \sum _{i}1\cdot \pi _{i}=1}$

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 π :

${\displaystyle \lim _{k\to \infty }\mathbf {P} ^{k}=\mathbf {1} \pi }$

donde 1 es el vector columna con todas las entradas iguales a 1. Esto se establece mediante el teorema de Perron-Frobenius . Si se encuentra, por cualquier medio, 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.${\textstyle \lim _{k\to \infty }\mathbf {P} ^{k}}$

Para algunas matrices estocásticas P , el límite no existe mientras que la distribución estacionaria sí, como lo muestra este ejemplo:${\textstyle \lim _{k\to \infty }\mathbf {P} ^{k}}$

${\displaystyle \mathbf {P} ={\begin{pmatrix}0&1\\1&0\end{pmatrix}}\qquad \mathbf {P} ^{2k}=I\qquad \mathbf {P} ^{2k+1}=\mathbf {P} }$

${\displaystyle {\begin{pmatrix}{\frac {1}{2}}&{\frac {1}{2}}\end{pmatrix}}{\begin{pmatrix}0&1\\1&0\end{pmatrix}}={\begin{pmatrix}{\frac {1}{2}}&{\frac {1}{2}}\end{pmatrix}}}$

(Este ejemplo ilustra una cadena periódica de Markov).

Dado que hay varios casos especiales diferentes a tener en cuenta, 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${\textstyle \mathbf {Q} =\lim _{k\to \infty }\mathbf {P} ^{k}.}$

Siempre es cierto que

${\displaystyle \mathbf {QP} =\mathbf {Q} .}$

Restando Q de ambos lados y factorizando obtenemos

${\displaystyle \mathbf {Q} (\mathbf {P} -\mathbf {I} _{n})=\mathbf {0} _{n,n},}$

donde I _n es la matriz identidad de tamaño n , y 0 _{n , n} es la matriz cero de tamaño n × n . Multiplicar entre sí matrices estocásticas siempre produce otra matriz estocástica, por lo que Q debe ser una matriz estocástica (véase la definición anterior). A veces es suficiente utilizar 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 se sustituye el elemento correspondiente (el de la misma columna) en el vector 0 , y luego se multiplica por la izquierda este último vector por la inversa de la matriz anterior transformada para encontrar Q .

He aquí 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 los 1. Si [ f ( P − I _n )] ⁻¹ existe, entonces ^{[41] [40]}

${\displaystyle \mathbf {Q} =f(\mathbf {0} _{n,n})[f(\mathbf {P} -\mathbf {I} _{n})]^{-1}.}$

Explicación: La ecuación matricial original es equivalente a un sistema de n×n ecuaciones lineales en n×n variables. Y hay n ecuaciones lineales más debido a que Q es una matriz estocástica derecha cuyas filas suman 1. Por lo tanto, necesita n×n ecuaciones lineales independientes de las ecuaciones (n×n+n) para resolver las n×n variables. En este ejemplo, las n ecuaciones de “Q multiplicada por la columna más a la derecha de (P-In)” han sido reemplazadas por las n ecuaciones estocásticas.

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 fila o columna i está llena de ceros, entonces esa fila o columna permanecerá sin cambios en todas las potencias subsiguientes _P ^k . Por lo tanto, la fila o columna i de Q tendrá los 1 y los ceros 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 complejo de manera similar. ^[42] )${\displaystyle {\boldsymbol {\pi }}={\boldsymbol {\pi }}\mathbf {P} ,}$

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( λ ₁ , λ ₂ , λ ₃ ,..., λ _n ). Luego, por descomposición propia

${\displaystyle \mathbf {P} =\mathbf {U\Sigma U} ^{-1}.}$

Sean enumerados los valores propios de tal manera que:

${\displaystyle 1=|\lambda _{1}|>|\lambda _{2}|\geq |\lambda _{3}|\geq \cdots \geq |\lambda _{n}|.}$

Como P es una matriz estocástica por 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 fila de longitud n que representa una distribución de probabilidad válida; dado que los vectores propios u _i abarcan, podemos escribir${\displaystyle \mathbb {R} ^{n},}$

${\displaystyle \mathbf {x} ^{\mathsf {T}}=\sum _{i=1}^{n}a_{i}\mathbf {u} _{i},\qquad a_{i}\in \mathbb {R} .}$

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 ₁ u ₁ ← xPP ... P = xP ^k cuando k → ∞. Esto significa que

${\displaystyle {\begin{aligned}{\boldsymbol {\pi }}^{(k)}&=\mathbf {x} \left(\mathbf {U\Sigma U} ^{-1}\right)\left(\mathbf {U\Sigma U} ^{-1}\right)\cdots \left(\mathbf {U\Sigma U} ^{-1}\right)\\&=\mathbf {xU\Sigma } ^{k}\mathbf {U} ^{-1}\\&=\left(a_{1}\mathbf {u} _{1}^{\mathsf {T}}+a_{2}\mathbf {u} _{2}^{\mathsf {T}}+\cdots +a_{n}\mathbf {u} _{n}^{\mathsf {T}}\right)\mathbf {U\Sigma } ^{k}\mathbf {U} ^{-1}\\&=a_{1}\lambda _{1}^{k}\mathbf {u} _{1}^{\mathsf {T}}+a_{2}\lambda _{2}^{k}\mathbf {u} _{2}^{\mathsf {T}}+\cdots +a_{n}\lambda _{n}^{k}\mathbf {u} _{n}^{\mathsf {T}}&&u_{i}\bot u_{j}{\text{ for }}i\neq j\\&=\lambda _{1}^{k}\left\{a_{1}\mathbf {u} _{1}^{\mathsf {T}}+a_{2}\left({\frac {\lambda _{2}}{\lambda _{1}}}\right)^{k}\mathbf {u} _{2}^{\mathsf {T}}+a_{3}\left({\frac {\lambda _{3}}{\lambda _{1}}}\right)^{k}\mathbf {u} _{3}^{\mathsf {T}}+\cdots +a_{n}\left({\frac {\lambda _{n}}{\lambda _{1}}}\right)^{k}\mathbf {u} _{n}^{\mathsf {T}}\right\}\end{aligned}}}$

Como π es paralelo a u ₁ (normalizado por la norma L2) y π ^{( k )} es un vector de probabilidad, π ^{( k )} se aproxima a a ₁ u ₁ = π cuando k → ∞ con una velocidad del orden de λ ₂ / λ ₁ exponencialmente. Esto se deduce porque, por lo tanto, λ ₂ / λ ₁ es el término dominante. Cuanto menor sea la relación, más rápida será la convergencia. ^[43] El ruido aleatorio en la distribución de estados π también puede acelerar esta convergencia a la distribución estacionaria. ^[44]${\displaystyle |\lambda _{2}|\geq \cdots \geq |\lambda _{n}|,}$

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 de Monte Carlo de cadenas de Markov cubre casos en los que el proceso sigue un espacio de estados continuo.

Las "cadenas de Markov que interactúan localmente" son cadenas de Markov con una evolución que tiene en cuenta el estado de otras cadenas de Markov. 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 procesos de Markov ^[45] o ^{[46] .}

Se dice que dos estados se comunican entre sí si ambos pueden alcanzarse entre sí mediante una secuencia de transiciones que tienen una probabilidad positiva. Esta es una relación de equivalencia que produce un conjunto de clases que se comunican. Una clase está cerrada si la probabilidad de abandonar la clase es cero. Una cadena de Markov es irreducible si hay una clase que se comunica, 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 que se puede llegar a i , a partir de i . Es decir:

${\displaystyle k=\gcd\{n>0:\Pr(X_{n}=i\mid X_{0}=i)>0\}}$

El estado es periódico si ; en caso contrario y el estado es aperiódico .${\displaystyle k>1}$${\displaystyle k=1}$

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 . En caso contrario, se denomina recurrente (o persistente ). ^[47] Para un estado recurrente i , el tiempo medio de impacto se define como:

${\displaystyle M_{i}=E[T_{i}]=\sum _{n=1}^{\infty }n\cdot f_{ii}^{(n)}.}$

El estado i es recurrente positivo si es finito y 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 en su clase comunicante tienen la propiedad. ^[48]${\displaystyle M_{i}}$

Un estado i se denomina absorbente si no hay transiciones salientes desde el estado.

Como 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 .${\displaystyle \pi _{i}=1/E[T_{i}]}$

Se dice que un estado i es 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 irreducible de Markov son ergódicos, entonces se dice que la cadena es ergódica. De manera equivalente, existe algún entero tal que todas las entradas de son positivas.${\displaystyle k}$${\displaystyle M^{k}}$

Se puede demostrar que una cadena de Markov irreducible de estados finitos es ergódica si tiene un estado aperiódico. De manera más general, una cadena de Markov es ergódica si existe un número N tal que cualquier estado puede alcanzarse 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 ni aperiódica, por lo tanto no puede ser ergódica.

Algunos autores denominan cadenas de Markov irreducibles y positivas como ergódicas, incluso las periódicas. ^[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 a una matriz primitiva si y solo si existe algún entero tal que todas las entradas de son positivas. ^[52] Algunos la llaman autora regular . ^[53]${\displaystyle k}$${\displaystyle M^{k}}$

El índice de primitividad , o exponente , de una matriz regular es el más pequeño tal que todas las entradas de son positivas. El exponente es puramente una propiedad de teoría de grafos, ya que depende únicamente de si cada entrada de es cero o positiva y, por lo tanto, se puede encontrar en un grafo dirigido con como su matriz de adyacencia. ${\displaystyle k}$${\displaystyle M^{k}}$${\displaystyle M}$${\displaystyle \mathrm {sign} (M)}$

Existen varios resultados combinatorios sobre el exponente cuando hay un número finito de estados. Sea el número de estados, entonces ^[54]${\displaystyle n}$

• El exponente es . El único caso en el que es una igualdad es cuando el gráfico de va como .${\displaystyle \leq (n-1)^{2}+1}$${\displaystyle M}$${\displaystyle 1\to 2\to \dots \to n\to 1{\text{ and }}2}$
• Si tiene entradas diagonales, entonces su exponente es .${\displaystyle M}$${\displaystyle k\geq 1}$${\displaystyle \leq 2n-k-1}$
• Si es simétrico, entonces tiene entradas diagonales positivas, lo que por la proposición anterior significa que su exponente es .${\displaystyle \mathrm {sign} (M)}$${\displaystyle M^{2}}$${\displaystyle \leq 2n-2}$
• (Teorema de Dulmage-Mendelsohn) El exponente es donde es la circunferencia del gráfico . Se puede mejorar a , donde es el diámetro del gráfico . ^[55]${\displaystyle \leq n+s(n-2)}$${\displaystyle s}$${\displaystyle \leq (d+1)+s(d+1-2)}$${\displaystyle d}$

Si una cadena de Markov tiene una distribución estacionaria, entonces puede convertirse en un sistema dinámico que preserva la medida : Sea el espacio de probabilidad , donde es el conjunto de todos los estados para la cadena de Markov. Sea el álgebra sigma en el espacio de probabilidad generado por los conjuntos de cilindros. Sea la medida de probabilidad generada por la distribución estacionaria y la transición de la cadena de Markov. Sea el operador de desplazamiento: . De manera similar, podemos construir un sistema dinámico de este tipo con en su lugar. ^[56]${\displaystyle \Omega =\Sigma ^{\mathbb {N} }}$${\displaystyle \Sigma }$${\displaystyle T:\Omega \to \Omega }$${\displaystyle T(X_{0},X_{1},\dots )=(X_{1},\dots )}$${\displaystyle \Omega =\Sigma ^{\mathbb {Z} }}$

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 la teoría ergódica , un sistema dinámico que preserva la medida se denomina "ergódico" si existe algún subconjunto medible que implique o (hasta un conjunto nulo).${\displaystyle S}$${\displaystyle T^{-1}(S)=S}$${\displaystyle S=\emptyset }$${\displaystyle \Omega }$

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, los procesos aparentemente no markovianos pueden tener representaciones markovianas, construidas mediante la expansión del concepto de los estados "actual" y "futuro". Por ejemplo, sea X un proceso no markoviano. Luego definamos un proceso Y , de modo que cada estado de Y represente un intervalo de tiempo de estados de X . Matemáticamente, esto toma la forma:

${\displaystyle Y(t)={\big \{}X(s):s\in [a(t),b(t)]\,{\big \}}.}$

Si Y tiene la propiedad de Markov, entonces es una representación markoviana de X.

Un ejemplo de un proceso no markoviano con una representación markoviana es una serie temporal autorregresiva de orden mayor que uno. ^[57]

El tiempo de impacto es el tiempo que transcurre desde que se inicia un conjunto de estados determinado 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 de este tipo es la de una única transición distribuida exponencialmente.

Para un subconjunto de estados A  ⊆  S , el vector k ^A de tiempos de impacto (donde elemento representa el valor esperado , comenzando en el estado i en que la cadena ingresa a uno de los estados del conjunto A ) es la solución mínima no negativa de ^[58]${\displaystyle k_{i}^{A}}$

${\displaystyle {\begin{aligned}k_{i}^{A}=0&{\text{ for }}i\in A\\-\sum _{j\in S}q_{ij}k_{j}^{A}=1&{\text{ for }}i\notin A.\end{aligned}}}$

Para un CTMC X _t , el proceso invertido en el tiempo se define como . Según el lema de Kelly, este proceso tiene la misma distribución estacionaria que el proceso directo.${\displaystyle {\hat {X}}_{t}=X_{T-t}}$

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 bucle 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 incrustada (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 de la 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

${\displaystyle s_{ij}={\begin{cases}{\frac {q_{ij}}{\sum _{k\neq i}q_{ik}}}&{\text{if }}i\neq j\\0&{\text{otherwise}}.\end{cases}}}$

A partir de esto, S puede escribirse como

${\displaystyle S=I-\left(\operatorname {diag} (Q)\right)^{-1}Q}$

donde I es la matriz identidad y diag( Q ) es la matriz diagonal formada al seleccionar la diagonal principal de la matriz Q y establecer todos los demás elementos en cero.

Para encontrar el vector de distribución de probabilidad estacionaria, debemos encontrar a continuación tal que${\displaystyle \varphi }$

${\displaystyle \varphi S=\varphi ,}$

siendo un vector fila, de modo que todos los elementos en son mayores que 0 y = 1. A partir de esto, π puede encontrarse como${\displaystyle \varphi }$${\displaystyle \varphi }$${\displaystyle \|\varphi \|_{1}}$

${\displaystyle \pi ={-\varphi (\operatorname {diag} (Q))^{-1} \over \left\|\varphi (\operatorname {diag} (Q))^{-1}\right\|_{1}}.}$

( S puede ser periódico, incluso si Q no lo es. Una vez que se encuentra π , debe normalizarse 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. Existen cuatro tipos principales de modelos que generalizan las cadenas de Markov en función de si cada estado secuencial es observable o no y de si el sistema se debe ajustar en función de las observaciones realizadas:

Un esquema de Bernoulli es un caso especial de una cadena de Markov en la que 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 anteriores). Un esquema de Bernoulli con solo dos estados posibles se conoce como proceso de Bernoulli .

Nótese, sin embargo, que según el teorema de isomorfismo de Ornstein , 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 esquemas de Bernoulli. El isomorfismo generalmente requiere una recodificación complicada. El teorema de 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 solo un ejemplo de ello.

Cuando la matriz de Markov se reemplaza por la matriz de adyacencia de un grafo 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 entonces proporcionar una medida del subdesplazamiento. Muchos sistemas dinámicos caóticos son isomorfos a las cadenas de Markov topológicas; los ejemplos incluyen difeomorfismos de variedades cerradas , el sistema Prouhet–Thue–Morse , el sistema Chacon, sistemas sóficos , sistemas libres de contexto y 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 utilicen 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 ninguna 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 de Monte Carlo de cadena de Markov se puede utilizar para extraer muestras aleatoriamente de una caja negra para aproximar la distribución de probabilidad de los atributos en un rango de objetos. ^[61]

Las cadenas de Markov se utilizan en simulaciones QCD de red . ^[62]

${\displaystyle {\ce {{E}+{\underset {Substrate \atop binding}{S<=>E}}{\overset {Catalytic \atop step}{S->E}}+P}}}$

Cinética de Michaelis-Menten . La enzima (E) se une a un sustrato (S) y produce un producto (P). Cada reacción es una transición de estado en una cadena de Markov.

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 donde el estado es 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 una gran cantidad n de moléculas en solución en el estado A, cada una de las cuales puede experimentar una reacción química al estado B con una cierta velocidad promedio. Quizás la molécula sea una enzima y los estados se refieren a cómo está plegada. El estado de cualquier enzima individual sigue una cadena de Markov, y dado que las moléculas son esencialmente independientes entre sí, la cantidad de moléculas en el estado A o B en un momento es n veces la probabilidad de que una molécula dada esté en ese estado.

El modelo clásico de la actividad enzimática, la cinética de Michaelis-Menten , puede verse como una cadena de Markov, donde en cada paso temporal la reacción avanza en alguna dirección. Si bien la cinética de Michaelis-Menten es bastante sencilla, 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 enfocar 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 se cultiva una molécula, 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á unido a ella). Luego pasa al siguiente estado cuando se le une un fragmento. Las probabilidades de transición se entrenan 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. En función de las proporciones de reactividad de los monómeros que forman la cadena de polímero en crecimiento, se puede calcular la composición de la cadena (por ejemplo, si los monómeros tienden a agregarse de manera alternada o en largas series 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 de polímeros.

De manera similar, se ha sugerido que la cristalización y el crecimiento de algunos materiales de óxido superred epitaxial pueden describirse con precisión mediante cadenas de Markov. ^[67]

Las cadenas de Markov se utilizan en diversas áreas de la biología. Algunos ejemplos destacados son:

• Filogenética y bioinformática , donde la mayoría de los modelos de evolución del ADN utilizan cadenas de Markov de tiempo continuo para describir el nucleótido presente en un sitio determinado del genoma .
• Dinámica de poblaciones , donde las cadenas de Markov son en particular una herramienta central en el estudio teórico de los modelos matriciales de población .
• Neurobiología , donde se han utilizado cadenas de Markov, por ejemplo, para simular el neocórtex de los mamíferos. ^[68]
• Biología de sistemas , por ejemplo con el modelado de la infección viral de células individuales. ^[69]
• Modelos compartimentados para el modelado de brotes y epidemias de enfermedades.

Varios teóricos han propuesto la idea de la prueba estadística de cadenas de Markov (MCST), un método para unir cadenas de Markov para formar una " manta de Markov ", organizando estas cadenas en varias capas recursivas ("wafering") y produciendo conjuntos de pruebas más eficientes (muestras) como reemplazo de pruebas exhaustivas. ^{[ cita requerida ]}

Las evaluaciones de la variabilidad de la irradiación solar son útiles para las aplicaciones de energía solar . La variabilidad de la irradiación solar en cualquier ubicación a lo largo del tiempo es principalmente una consecuencia de la variabilidad determinista de la trayectoria del sol a través de la bóveda celeste y la variabilidad de la nubosidad. La variabilidad de la irradiación 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 cielo despejado y nubosidad como una cadena de Markov de dos estados. ^{[74] [75]}

Los modelos ocultos de Markov se han utilizado en sistemas de reconocimiento automático 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 al modelar textos en un lenguaje natural (como el inglés) generados por un proceso ergódico de Markov, donde cada letra puede depender estadísticamente de letras anteriores. ^[77] Estos modelos idealizados pueden capturar muchas de las regularidades estadísticas de los sistemas. Incluso sin describir perfectamente la estructura completa del sistema, estos modelos de señales pueden hacer posible una compresión de datos muy efectiva a través de técnicas de codificación de entropía como la codificación aritmética . También permiten una estimación de estado efectiva y el reconocimiento de patrones . Las cadenas de Markov también juegan un papel importante en el aprendizaje de 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 en la detección de reordenamientos ^[78] ).

El algoritmo de compresión de datos sin pérdida LZMA combina cadenas de Markov con compresión Lempel-Ziv para lograr índices de compresión muy altos.

Las cadenas de Markov son la base para el tratamiento analítico de las colas ( teoría de colas ). Agner Krarup Erlang inició el tema en 1917. ^[79] Esto las hace críticas para optimizar el rendimiento de las redes de telecomunicaciones, donde los mensajes a menudo deben competir por recursos limitados (como el ancho de banda). ^[80]

Numerosos modelos de colas utilizan cadenas de Markov de tiempo continuo. Por ejemplo, una cola M/M/1 es una CTMC de números enteros no negativos donde las transiciones ascendentes de i a i  + 1 ocurren a una tasa λ según un proceso de Poisson y describen las llegadas de trabajos, mientras que las transiciones de i a i  – 1 (para i  > 1) ocurren a una tasa μ (los tiempos de servicio de los trabajos se distribuyen exponencialmente) y describen los servicios completados (salidas) de la cola.

El PageRank de una página web, tal como lo utiliza Google, se define mediante una cadena de Markov. ^{[81] [82] [83]} Es la probabilidad de estar en una página en la distribución estacionaria de 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 una probabilidad de transición para todas las páginas que tienen enlaces y para todas las páginas que no tienen enlaces. El parámetro se toma en aproximadamente 0,15. ^[84]${\displaystyle i}$${\displaystyle N}$${\displaystyle i}$${\displaystyle k_{i}}$${\displaystyle {\frac {\alpha }{k_{i}}}+{\frac {1-\alpha }{N}}}$${\displaystyle {\frac {1-\alpha }{N}}}$${\displaystyle \alpha }$

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 usuario a un enlace web 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 para personalizar la página web para un usuario individual.

Los métodos de cadena de Markov también han adquirido gran importancia para generar secuencias de números aleatorios que reflejen con precisión distribuciones de probabilidad deseadas muy complicadas, mediante un proceso llamado Markov Chain 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 determinar numéricamente sus parámetros. ^{[ cita requerida ]}

Las cadenas de Markov se utilizan en finanzas y economía para modelar una variedad de fenómenos diferentes, incluyendo 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 de la distribución del ingreso en 1953. ^[85] Herbert A. Simon y el coautor Charles Bonini utilizaron un modelo de cadena de Markov para derivar una distribución estacionaria de Yule de tamaños de empresas. ^[86] Louis Bachelier fue el primero en observar que los precios de las acciones seguían un paseo aleatorio. ^[87] El paseo aleatorio fue visto 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. ^[88] Los modelos de cambio de régimen de los ciclos económicos 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 económicas y recesiones). ^[89] Un ejemplo más reciente es el modelo multifractal de cambio de régimen de Markov de Laurent E. Calvet y Adlai J. Fisher, que se basa en la conveniencia de los modelos de cambio de régimen anteriores. ^{[90] [91]} Utiliza una cadena de Markov arbitrariamente grande para determinar 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 contexto de equilibrio general . ^[92]

Las agencias de calificación crediticia elaboran anualmente tablas de las probabilidades de transición para bonos de diferentes calificaciones crediticias. ^[93]

Las cadenas de Markov se utilizan generalmente para describir argumentos dependientes de la trayectoria , donde las configuraciones estructurales actuales condicionan los resultados futuros. Un ejemplo es la reformulación de la idea, originalmente debido a El capital de Karl Marx , que vincula el desarrollo económico al auge 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 relación entre la residencia urbana y rural, la tasa de movilización política , etc., generará una mayor probabilidad de transición de un régimen autoritario a uno democrático . ^[94]

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, se representan exactamente mediante cadenas de Markov. En cada turno, el jugador comienza en un estado determinado (en una casilla determinada) y a partir de ahí tiene probabilidades fijas de pasar a otros estados (casillas) determinados.

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 nota de salida basados ​​en las ponderaciones de la matriz de transición, que podrían ser valores de nota MIDI , frecuencia ( Hz ) o cualquier otra métrica deseada. ^[95]

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 de orden n -ésimo más altas 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 una sensación de estructura de frase , en lugar del "vagabundeo sin rumbo" producido por un sistema de primer orden. ^[96]

Las cadenas de Markov se pueden utilizar estructuralmente, como en Analogique A y B de Xenakis. ^[97] Las cadenas de Markov también se utilizan en sistemas que utilizan un modelo de Markov para reaccionar de forma interactiva a la entrada de música. ^[98]

Por lo general, los sistemas musicales necesitan imponer restricciones de control específicas a 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. ^[99]

Los modelos de cadena de Markov se han utilizado en el análisis avanzado del béisbol desde 1960, aunque su uso todavía es poco frecuente. 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 demuestra que los modelos de cadena de Markov se pueden utilizar para evaluar las carreras creadas tanto para jugadores individuales como para un equipo. ^[100] 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 para situaciones de juego como el toque de bola y el robo de bases y las diferencias entre jugar en césped y césped artificial . ^[101]

Los procesos de Markov también se pueden utilizar para generar texto que parezca real a primera vista a partir de un documento de muestra. Los procesos de Markov se utilizan en una variedad de software recreativo " generador de parodias " (consulte Dissociated Press , Jeff Harrison, ^[102] Mark V. Shaney , ^{[103] [104]} 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 realizar pronósticos en varias áreas: por ejemplo, tendencias de precios, ^[105] energía eólica, ^[106] terrorismo estocástico , ^{[107] [108]} e irradiancia solar . ^[109] Los modelos de pronóstico de cadenas de Markov utilizan una variedad de configuraciones, desde la discretización de las series temporales, ^[106] hasta modelos ocultos de Markov combinados con wavelets, ^[105] y el modelo de distribución de mezcla de cadenas de Markov (MCM). ^[109]