Cadena de Markov

Random process independent of past history

Diagrama que representa un proceso de Markov de dos estados. Los números representan la probabilidad de cambiar de un estado a otro.

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 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 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]

Principios

El matemático ruso Andrei Markov

Definición

Un proceso de Markov es un proceso estocástico que satisface la propiedad de Markov (a veces caracterizada como " falta de memoria "): 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 podrían hacerse conociendo la historia completa del proceso. ^[5] Esto significa que, condicionado al 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]

Tipos de cadenas de Markov

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.

Transiciones

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.

Historia

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]

Ejemplos

• 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 entero siguiente o al anterior. 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.

Un ejemplo no markoviano

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}$

Definición formal

Cadena de Markov de tiempo discreto

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.

Variaciones

• 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)}$

Cadena de Markov de tiempo continuo

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]

Definición infinitesimal

La cadena de Markov de tiempo continuo se caracteriza por las tasas de transición, las derivadas con respecto al tiempo de las probabilidades de transición entre los estados i y j.

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}}$

Definición de cadena de salto/tiempo de retención

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} .

Definición de probabilidad de transición

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 .

Espacio de estados finitos

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 .

Relación de distribución estacionaria con vectores propios y símplices

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}$

Cadena de Markov homogénea en el tiempo con un espacio de estados finito

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 _i - ésima fila o columna está llena de ceros, entonces esa fila o columna permanecerá sin cambios en todas las potencias subsiguientes P ^k . Por lo tanto, la i - ésima fila o columna de Q tendrá los 1 y los ceros en las mismas posiciones que en P.

Velocidad de convergencia a la distribución estacionaria

Como se dijo 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}|,}$

Espacio de estados generales

Cadenas de Harris

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.

Cadenas de Markov que interactúan localmente

El hecho de 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 procesos de Markov ^[45] o ^{[46] .}

Propiedades

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 periodo 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.

Irreducibilidad

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}]}$

Ergodicidad

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 de Markov irreducible 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.

Terminología

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 autores la llaman regular . ^[53] ${\displaystyle k}$ ${\displaystyle M^{k}}$

Índice de primitividad

El índice de primitividad , o exponente , de una matriz regular es el más pequeño de modo que todas las entradas de sean positivas. El exponente es una propiedad puramente 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}$

Sistema dinámico que preserva la medida

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]

Representaciones markovianas

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]

Tiempos de bateo

El tiempo de impacto es el tiempo que transcurre desde 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.

Tiempos de impacto esperados

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}}}$

Inversión del tiempo

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.

Cadena de Markov incorporada

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, π se puede encontrar 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.

Tipos especiales de cadenas de Markov

Modelo de Markov

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:

Esquema de Bernoulli

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.

Subdesplazamiento de tipo finito

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]

Aplicaciones

Las cadenas de Markov se han empleado en una amplia gama de temas en las ciencias naturales y sociales y en aplicaciones tecnológicas.

Física

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]

Química

${\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 tasa 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]

Biología

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.

Pruebas

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 ]}

Variabilidad de la irradiación solar

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]}

Reconocimiento de voz

Los modelos ocultos de Markov se han utilizado en sistemas de reconocimiento automático de voz . ^[76]

Teoría de la información

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.

Teoría de colas

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.

Aplicaciones de Internet

Un diagrama de estados que representa el algoritmo PageRank con una probabilidad de transición de M, o . ${\displaystyle {\frac {\alpha }{k_{i}}}+{\frac {1-\alpha }{N}}}$

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.

Estadística

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 ]}

Economía y finanzas

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]

Ciencias sociales

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]

Juegos

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.

Música

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 a continuación). 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]

Béisbol

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]

Generadores de texto de Markov

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.

Pronóstico probabilístico

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]

Véase también

• Dinámica de las partículas markovianas
• Proceso de Gauss-Markov
• Método de aproximación de cadena de Markov
• Geoestadística de cadenas de Markov
• Tiempo de mezcla de la cadena de Markov
• Teorema del árbol de cadenas de Markov
• Proceso de decisión de Markov
• Fuente de información de Markov
• Odómetro de Markov
• Operador de Markov
• Campo aleatorio de Markov
• Ecuación maestra
• Cadena cuántica de Markov
• Proceso semi-Markoviano
• Autómata celular estocástico
• Cadena telescópica de Markov
• Modelo de Markov de orden variable

Notas

1. Sean Meyn; Richard L. Tweedie (2 de abril de 2009). Cadenas de Markov y estabilidad estocástica. Cambridge University Press. p. 3. ISBN 978-0-521-73182-9.
2. Reuven Y. Rubinstein; Dirk P. Kroese (20 de septiembre de 2011). Simulación y el método de Monte Carlo. John Wiley & Sons. pág. 225. ISBN 978-1-118-21052-9.
3. Dani Gamerman; Hedibert F. Lopes (10 de mayo de 2006). Cadena de Markov Monte Carlo: simulación estocástica para inferencia bayesiana, segunda edición. CRC Press. ISBN 978-1-58488-587-0.
4. "Markoviano" . Oxford English Dictionary (edición en línea). Oxford University Press . (Se requiere suscripción o membresía a una institución participante).
5. Øksendal, BK (Bernt Karsten) (2003). Ecuaciones diferenciales estocásticas: una introducción con aplicaciones (6.ª ed.). Berlín: Springer. ISBN 3540047581.OCLC 52203046  .
6. Søren Asmussen (15 de mayo de 2003). Probabilidad Aplicada y Colas. Medios de ciencia y negocios de Springer. pag. 7.ISBN​ 978-0-387-00211-8.
7. Emanuel Parzen (17 de junio de 2015). Procesos estocásticos. Courier Dover Publications. pág. 188. ISBN 978-0-486-79688-8.
8. Samuel Karlin; Howard E. Taylor (2 de diciembre de 2012). Un primer curso sobre procesos estocásticos. Academic Press. pp. 29 y 30. ISBN 978-0-08-057041-9.
9. John Lamperti (1977). Procesos estocásticos: un estudio de la teoría matemática. Springer-Verlag. pp. 106-121. ISBN 978-3-540-90275-1.
10. Sheldon M. Ross (1996). Procesos estocásticos. Wiley. Págs. 174 y 231. ISBN. 978-0-471-12062-9.
11. Everitt, BS (2002) Diccionario de Estadística de Cambridge . ISBN 0-521-81099-X 
12. Parzen, E. (1962) Procesos estocásticos , Holden-Day. ISBN 0-8162-6664-6 (Tabla 6.1) 
13. Dodge, Y. (2003) The Oxford Dictionary of Statistical Terms , OUP. ISBN 0-19-920613-9 (entrada para "Cadena de Markov") 
14. Dodge, Y. Diccionario Oxford de términos estadísticos , OUP. ISBN 0-19-920613-9 
15. Meyn, S. Sean P. y Richard L. Tweedie. (2009) Cadenas de Markov y estabilidad estocástica . Cambridge University Press. (Prefacio, pág. iii)
16. Charles Miller Grinstead; James Laurie Snell (1997). Introducción a la probabilidad. American Mathematical Soc., págs. 464-466. ISBN 978-0-8218-0749-1.
17. Pierre Bremaud (9 de marzo de 2013). Cadenas de Markov: campos de Gibbs, simulación de Monte Carlo y colas. Springer Science & Business Media. p. ix. ISBN 978-1-4757-3124-8.
18. Hayes, Brian (2013). "Primeros eslabones de la cadena de Markov". American Scientist . 101 (2): 92–96. doi :10.1511/2013.101.92.
19. Sheldon M. Ross (1996). Procesos estocásticos. Wiley. págs. 235 y 358. ISBN 978-0-471-12062-9.
20. Jarrow, Robert; Protter, Philip (2004). "A short history of stochastic integration and mathematical finance: The early years, 1880–1970". A Festschrift for Herman Rubin. pp. 75–91. CiteSeerX 10.1.1.114.632. doi:10.1214/lnms/1196285381. ISBN 978-0-940600-61-4.
21. Guttorp, Peter; Thorarinsdottir, Thordis L. (2012). "What Happened to Discrete Chaos, the Quenouille Process, and the Sharp Markov Property? Some History of Stochastic Point Processes". International Statistical Review. 80 (2): 253–268. doi:10.1111/j.1751-5823.2012.00181.x.
22. Seneta, E. (1996). "Markov and the Birth of Chain Dependence Theory". International Statistical Review. 64 (3): 255–257. doi:10.2307/1403785. JSTOR 1403785.
23. Seneta, E. (1998). "I.J. Bienaymé [1796–1878]: Criticality, Inequality, and Internationalization". International Statistical Review. 66 (3): 291–292. doi:10.2307/1403518. JSTOR 1403518.
24. Bru B, Hertz S (2001). "Maurice Fréchet". In Heyde CC, Seneta E, Crépel P, Fienberg SE, Gani J (eds.). Statisticians of the Centuries. New York, NY: Springer. pp. 331–334. doi:10.1007/978-1-4613-0179-0_71. ISBN 978-0-387-95283-3.
25. Kendall, D. G.; Batchelor, G. K.; Bingham, N. H.; Hayman, W. K.; Hyland, J. M. E.; Lorentz, G. G.; Moffatt, H. K.; Parry, W.; Razborov, A. A.; Robinson, C. A.; Whittle, P. (1990). "Andrei Nikolaevich Kolmogorov (1903–1987)". Bulletin of the London Mathematical Society. 22 (1): 33. doi:10.1112/blms/22.1.31.
26. Cramér, Harald (1976). "Half a Century with Probability Theory: Some Personal Recollections". The Annals of Probability. 4 (4): 509–546. doi:10.1214/aop/1176996025.
27. Marc Barbut; Bernard Locker; Laurent Mazliak (23 August 2016). Paul Lévy and Maurice Fréchet: 50 Years of Correspondence in 107 Letters. Springer London. p. 5. ISBN 978-1-4471-7262-8.
28. Valeriy Skorokhod (5 December 2005). Basic Principles and Applications of Probability Theory. Springer Science & Business Media. p. 146. ISBN 978-3-540-26312-8.
29. Bernstein, Jeremy (2005). "Bachelier". American Journal of Physics. 73 (5): 395–398. Bibcode:2005AmJPh..73..395B. doi:10.1119/1.1848117.
30. William J. Anderson (6 December 2012). Continuous-Time Markov Chains: An Applications-Oriented Approach. Springer Science & Business Media. p. vii. ISBN 978-1-4612-3038-0.
31. Kendall, D. G.; Batchelor, G. K.; Bingham, N. H.; Hayman, W. K.; Hyland, J. M. E.; Lorentz, G. G.; Moffatt, H. K.; Parry, W.; Razborov, A. A.; Robinson, C. A.; Whittle, P. (1990). "Andrei Nikolaevich Kolmogorov (1903–1987)". Bulletin of the London Mathematical Society. 22 (1): 57. doi:10.1112/blms/22.1.31.
32. Ionut Florescu (7 November 2014). Probability and Stochastic Processes. John Wiley & Sons. pp. 373 and 374. ISBN 978-1-118-59320-2.
33. Samuel Karlin; Howard E. Taylor (2 December 2012). A First Course in Stochastic Processes. Academic Press. p. 49. ISBN 978-0-08-057041-9.
34. Weiss, George H. (2006). "Random Walks". Encyclopedia of Statistical Sciences. p. 1. doi:10.1002/0471667196.ess2180.pub2. ISBN 978-0471667193.
35. Michael F. Shlesinger (1985). The Wonderful world of stochastics: a tribute to Elliott W. Montroll. North-Holland. pp. 8–10. ISBN 978-0-444-86937-1.
36. Emanuel Parzen (17 June 2015). Stochastic Processes. Courier Dover Publications. p. 7, 8. ISBN 978-0-486-79688-8.
37. Joseph L. Doob (1990). Stochastipoic processes. Wiley. p. 46, 47.
38. Donald L. Snyder; Michael I. Miller (6 December 2012). Random Point Processes in Time and Space. Springer Science & Business Media. p. 32. ISBN 978-1-4612-3166-0.
39. Norris, J. R. (1997). "Continuous-time Markov chains I". Markov Chains. pp. 60–107. doi:10.1017/CBO9780511810633.004. ISBN 9780511810633.
40. Serfozo, Richard (2009). Basics of Applied Stochastic Processes. Berlin: Springer. doi:10.1007/978-3-540-89332-5. ISBN 978-3-540-89331-8.
41. "Chapter 11 "Markov Chains"" (PDF). Retrieved 2017-06-02.
42. Schmitt, Florian; Rothlauf, Franz (2001). "On the Importance of the Second Largest Eigenvalue on the Convergence Rate of Genetic Algorithms". Proceedings of the 14th Symposium on Reliable Distributed Systems. CiteSeerX 10.1.1.28.6191.
43. Rosenthal, Jeffrey S. (1995). "Convergence Rates for Markov Chains". SIAM Review. 37 (3): 387–405. doi:10.1137/1037083. JSTOR 2132659. Retrieved 2021-05-31.
44. Franzke, Brandon; Kosko, Bart (1 October 2011). "Noise can speed convergence in Markov chains". Physical Review E. 84 (4): 041112. Bibcode:2011PhRvE..84d1112F. doi:10.1103/PhysRevE.84.041112. PMID 22181092.
45. Spitzer, Frank (1970). "Interaction of Markov Processes". Advances in Mathematics. 5 (2): 246–290. doi:10.1016/0001-8708(70)90034-4.
46. Dobrushin, R. L.; Kryukov, V. I.; Toom, A. L. (1978). Stochastic Cellular Systems: Ergodicity, Memory, Morphogenesis. Manchester University Press. ISBN 9780719022067. Retrieved 2016-03-04.
47. Heyman, Daniel P.; Sobel, Mathew J. (1982). Stochastic Models in Operations Research, Volume 1. New York: McGraw-Hill. p. 230. ISBN 0-07-028631-0.
48. Peres, Yuval. "Show that positive recurrence is a class property". Mathematics Stack Exchange. Retrieved 2024-02-01.
49. Lalley, Steve (2016). "Markov Chains: Basic Theory" (PDF). Retrieved 22 June 2024.
50. Parzen, Emanuel (1962). Stochastic Processes. San Francisco: Holden-Day. p. 145. ISBN 0-8162-6664-6.
51. Shalizi, Cosma (1 Dec 2023). "Ergodic Theory". bactra.org. Retrieved 2024-02-01.
52. Seneta, E. (Eugene) (1973). Non-negative matrices; an introduction to theory and applications. Internet Archive. New York, Wiley. ISBN 978-0-470-77605-6.
53. "10.3: Regular Markov Chains". Mathematics LibreTexts. 2020-03-22. Retrieved 2024-02-01.
54. Seneta, E. (Eugene) (1973). "2.4. Combinatorial properties". Non-negative matrices; an introduction to theory and applications. Internet Archive. New York, Wiley. ISBN 978-0-470-77605-6.
55. Shen, Jian (1996-10-15). "An improvement of the Dulmage-Mendelsohn theorem". Discrete Mathematics. 158 (1): 295–297. doi:10.1016/0012-365X(95)00060-A.
56. Kallenberg, Olav (2002). Fundamentos de la probabilidad moderna . Probabilidad y sus aplicaciones (2. ed., [Nachdr.] ed.). Nueva York, NY Berlin Heidelberg: Springer. Proposición 8.6 (página 145). ISBN 978-0-387-95313-7.
57. Doblinger, G. (septiembre de 1998). "Suavizado de señales AR ruidosas utilizando un filtro Kalman adaptativo" (PDF) . 9.ª Conferencia Europea de Procesamiento de Señales (EUSIPCO 1998) : 781–784.
58. Norris, JR (1997). "Cadenas de Markov en tiempo continuo II". Cadenas de Markov . págs. 108-127. doi :10.1017/CBO9780511810633.005. ISBN . 9780511810633.
59. Matthew Nicol y Karl Petersen, (2009) "Teoría ergódica: ejemplos básicos y construcciones", Enciclopedia de complejidad y ciencia de sistemas , Springer https://doi.org/10.1007/978-0-387-30440-3_177
60. Fitzpatrick, Richard. "Termodinámica y mecánica estadística" (PDF) . Consultado el 2 de junio de 2017 .
61. van Ravenzwaaij, Don; Cassey, Pete; Brown, Scott D. (11 de marzo de 2016). "Una introducción sencilla al muestreo de Montecarlo con cadenas de Markov". Psychonomic Bulletin & Review . 25 (1): 143–154. doi :10.3758/s13423-016-1015-8. PMC 5862921 . PMID  26968853. 
62. Gattringer, Christof; Lang, Christian B (2010). Cromodinámica cuántica en la red. Apuntes de clases de física. Vol. 788. Springer-Verlag Berlin Heidelberg. doi :10.1007/978-3-642-01850-3. ISBN . 978-3-642-01849-7.
63. Anderson, David F.; Kurtz, Thomas G. (2011), "Modelos de cadena de Markov de tiempo continuo para redes de reacciones químicas", Diseño y análisis de circuitos biomoleculares , Springer Nueva York, págs. 3–42, doi :10.1007/978-1-4419-6766-4_1, ISBN 9781441967657
64. Du, Chao; Kou, SC (septiembre de 2012). "Análisis de correlación de la reacción enzimática de una sola molécula de proteína". Anales de estadística aplicada . 6 (3): 950–976. arXiv : 1209.6210 . Bibcode :2012arXiv1209.6210D. doi :10.1214/12-aoas541. PMC 3568780 . PMID  23408514. 
65. Kutchukian, Peter; Lou, David; Shakhnovich, Eugene (2009). "FOG: Algoritmo de crecimiento optimizado de fragmentos para la generación de novo de moléculas que ocupan sustancias químicas similares a fármacos". Revista de información y modelado químico . 49 (7): 1630–1642. doi :10.1021/ci9000458. PMID  19527020.
66. Kutchukian, Peter S.; Lou, David; Shakhnovich, Eugene I. (15 de junio de 2009). "FOG: Algoritmo de crecimiento optimizado de fragmentos para la generación de novo de moléculas que ocupan un espacio químico similar al de los fármacos". Revista de información y modelado químico . 49 (7): 1630–1642. doi :10.1021/ci9000458. PMID  19527020.
67. Kopp, VS; Kaganer, VM; Schwarzkopf, J.; Waidick, F.; Remmele, T.; Kwasniewski, A.; Schmidbauer, M. (2011). "Difracción de rayos X a partir de estructuras en capas no periódicas con correlaciones: cálculo analítico y experimento en películas mixtas de Aurivillius". Acta Crystallographica Sección A . 68 (Pt 1): 148–155. Bibcode :2012AcCrA..68..148K. doi :10.1107/S0108767311044874. PMID  22186291.
68. George, Dileep; Hawkins, Jeff (2009). Friston, Karl J. (ed.). "Hacia una teoría matemática de los microcircuitos corticales". PLOS Comput Biol . 5 (10): e1000532. Bibcode :2009PLSCB...5E0532G. doi : 10.1371/journal.pcbi.1000532 . PMC 2749218 . PMID  19816557. 
69. Gupta, Ankur; Rawlings, James B. (abril de 2014). "Comparación de métodos de estimación de parámetros en modelos cinéticos químicos estocásticos: ejemplos en biología de sistemas". AIChE Journal . 60 (4): 1253–1268. Bibcode :2014AIChE..60.1253G. doi :10.1002/aic.14409. PMC 4946376 . PMID  27429455. 
70. Aguiar, RJ; Collares-Pereira, M.; Conde, JP (1988). "Procedimiento simple para generar secuencias de valores de radiación diaria utilizando una biblioteca de matrices de transición de Markov". Energía Solar . 40 (3): 269–279. Bibcode :1988SoEn...40..269A. doi :10.1016/0038-092X(88)90049-7.
71. Ngoko, BO; Sugihara, H.; Funaki, T. (2014). "Generación sintética de datos de radiación solar de alta resolución temporal utilizando modelos de Markov". Energía solar . 103 : 160–170. Código Bibliográfico :2014SoEn..103..160N. doi :10.1016/j.solener.2014.02.026.
72. Bright, J. M.; Smith, C. I.; Taylor, P. G.; Crook, R. (2015). "Stochastic generation of synthetic minutely irradiance time series derived from mean hourly weather observation data". Solar Energy. 115: 229–242. Bibcode:2015SoEn..115..229B. doi:10.1016/j.solener.2015.02.032.
73. Munkhammar, J.; Widén, J. (2018). "An N-state Markov-chain mixture distribution model of the clear-sky index". Solar Energy. 173: 487–495. Bibcode:2018SoEn..173..487M. doi:10.1016/j.solener.2018.07.056.
74. Morf, H. (1998). "The stochastic two-state solar irradiance model (STSIM)". Solar Energy. 62 (2): 101–112. Bibcode:1998SoEn...62..101M. doi:10.1016/S0038-092X(98)00004-8.
75. Munkhammar, J.; Widén, J. (2018). "A Markov-chain probability distribution mixture approach to the clear-sky index". Solar Energy. 170: 174–183. Bibcode:2018SoEn..170..174M. doi:10.1016/j.solener.2018.05.055.
76. Mor, Bhavya; Garhwal, Sunita; Kumar, Ajay (May 2021). "A Systematic Review of Hidden Markov Models and Their Applications". Archives of Computational Methods in Engineering. 28 (3): 1429–1448. doi:10.1007/s11831-020-09422-4. ISSN 1134-3060.
77. Thomsen, Samuel W. (2009), "Some evidence concerning the genesis of Shannon's information theory", Studies in History and Philosophy of Science, 40: 81–91, doi:10.1016/j.shpsa.2008.12.011
78. Pratas, D; Silva, R; Pinho, A; Ferreira, P (May 18, 2015). "An alignment-free method to find and visualise rearrangements between pairs of DNA sequences". Scientific Reports. 5 (10203): 10203. Bibcode:2015NatSR...510203P. doi:10.1038/srep10203. PMC 4434998. PMID 25984837.
79. O'Connor, John J.; Robertson, Edmund F., "Markov chain", MacTutor History of Mathematics Archive, University of St Andrews
80. S. P. Meyn, 2007. Control Techniques for Complex Networks Archived 2015-05-13 at the Wayback Machine, Cambridge University Press, 2007.
81. U.S. patent 6,285,999
82. Gupta, Brij; Agrawal, Dharma P.; Yamaguchi, Shingo (16 May 2016). Handbook of Research on Modern Cryptographic Solutions for Computer and Cyber Security. IGI Global. pp. 448–. ISBN 978-1-5225-0106-0.
83. Langville, Amy N.; Meyer, Carl D. (2006). "A Reordering for the PageRank Problem" (PDF). SIAM Journal on Scientific Computing. 27 (6): 2112–2113. Bibcode:2006SJSC...27.2112L. CiteSeerX 10.1.1.58.8652. doi:10.1137/040607551.
84. Page, Lawrence; Brin, Sergey; Motwani, Rajeev; Winograd, Terry (1999). The PageRank Citation Ranking: Bringing Order to the Web (Technical report). CiteSeerX 10.1.1.31.1768.
85. Champernowne, D (1953). "A model of income distribution". The Economic Journal. 63 (250): 318–51. doi:10.2307/2227127. JSTOR 2227127.
86. Simon, Herbert; C Bonini (1958). "The size distribution of business firms". Am. Econ. Rev. 42: 425–40.
87. Bachelier, Louis (1900). "Théorie de la spéculation". Annales Scientifiques de l'École Normale Supérieure. 3: 21–86. doi:10.24033/asens.476. hdl:2027/coo.31924001082803.
88. e.g.Fama, E (1965). "The behavior of stock market prices". Journal of Business. 38.
89. Hamilton, James (1989). "A new approach to the economic analysis of nonstationary time series and the business cycle". Econometrica. 57 (2): 357–84. CiteSeerX 10.1.1.397.3582. doi:10.2307/1912559. JSTOR 1912559.
90. Calvet, Laurent E.; Fisher, Adlai J. (2001). "Forecasting Multifractal Volatility". Journal of Econometrics. 105 (1): 27–58. doi:10.1016/S0304-4076(01)00069-0.
91. Calvet, Laurent; Adlai Fisher (2004). "How to Forecast long-run volatility: regime-switching and the estimation of multifractal processes". Journal of Financial Econometrics. 2: 49–83. CiteSeerX 10.1.1.536.8334. doi:10.1093/jjfinec/nbh003.
92. Brennan, Michael; Xiab, Yihong. "Stock Price Volatility and the Equity Premium" (PDF). Department of Finance, the Anderson School of Management, UCLA. Archived from the original (PDF) on 2008-12-28.
93. "A Markov Chain Example in Credit Risk Modelling" (PDF). Columbia University. Archived from the original (PDF) on March 24, 2016.
94. Acemoglu, Daron; Georgy Egorov; Konstantin Sonin (2011). "Political model of social evolution". Proceedings of the National Academy of Sciences. 108 (Suppl 4): 21292–21296. Bibcode:2011PNAS..10821292A. CiteSeerX 10.1.1.225.6090. doi:10.1073/pnas.1019454108. PMC 3271566. PMID 22198760.
95. K McAlpine; E Miranda; S Hoggar (1999). "Making Music with Algorithms: A Case-Study System". Computer Music Journal. 23 (2): 19–30. doi:10.1162/014892699559733.
96. Curtis Roads, ed. (1996). The Computer Music Tutorial. MIT Press. ISBN 978-0-262-18158-7.
97. Xenakis, Iannis; Kanach, Sharon (1992) Formalized Music: Mathematics and Thought in Composition, Pendragon Press. ISBN 1576470792
98. "Continuator". Archived from the original on July 13, 2012.
99. Pachet, F.; Roy, P.; Barbieri, G. (2011) "Finite-Length Markov Processes with Constraints" Archived 2012-04-14 at the Wayback Machine, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI, pages 635–642, Barcelona, Spain, July 2011
100. Pankin, Mark D. "MARKOV CHAIN MODELS: THEORETICAL BACKGROUND". Archived from the original on 2007-12-09. Retrieved 2007-11-26.
101. Pankin, Mark D. "BASEBALL AS A MARKOV CHAIN". Retrieved 2009-04-24.
102. "Poet's Corner – Fieralingue". Archived from the original on December 6, 2010.
103. Kenner, Hugh; O'Rourke, Joseph (November 1984). "A Travesty Generator for Micros". BYTE. 9 (12): 129–131, 449–469.
104. Hartman, Charles (1996). Virtual Muse: Experiments in Computer Poetry. Hanover, NH: Wesleyan University Press. ISBN 978-0-8195-2239-9.
105. de Souza e Silva, E.G.; Legey, L.F.L.; de Souza e Silva, E.A. (2010). "Forecasting oil price trends using wavelets and hidden Markov models". Energy Economics. 32.
106. Carpinone, A; Giorgio, M; Langella, R.; Testa, A. (2015). "Markov chain modeling for very-short-term wind power forecasting". Electric Power Systems Research. 122: 152–158. doi:10.1016/j.epsr.2014.12.025.
107. Woo, Gordon (2002-04-01). "Quantitative Terrorism Risk Assessment". The Journal of Risk Finance. 4 (1): 7–14. doi:10.1108/eb022949. Retrieved 5 October 2023.
108. Woo, Gordon (December 2003). "Insuring Against Al-Quaeda" (PDF). Cambridge: National Bureau of Economic Research. Retrieved 26 March 2024.
109. Munkhammar, J.; van der Meer, D.W.; Widén, J. (2019). "Probabilistic forecasting of high-resolution clear-sky index time-series using a Markov-chain mixture distribution model". Solar Energy. 184: 688–695. Bibcode:2019SoEn..184..688M. doi:10.1016/j.solener.2019.04.014.

References

• A. A. Markov (1906) "Rasprostranenie zakona bol'shih chisel na velichiny, zavisyaschie drug ot druga". Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete, 2-ya seriya, tom 15, pp. 135–156.
• A. A. Markov (1971). "Extension of the limit theorems of probability theory to a sum of variables connected in a chain". reprinted in Appendix B of: R. Howard. Dynamic Probabilistic Systems, volume 1: Markov Chains. John Wiley and Sons.
• Classical Text in Translation: Markov, A. A. (2006). "An Example of Statistical Investigation of the Text Eugene Onegin Concerning the Connection of Samples in Chains". Science in Context. 19 (4). Translated by Link, David: 591–600. doi:10.1017/s0269889706001074.
• Leo Breiman (1992) [1968] Probability. Original edition published by Addison-Wesley; reprinted by Society for Industrial and Applied Mathematics ISBN 0-89871-296-3. (See Chapter 7)
• J. L. Doob (1953) Stochastic Processes. New York: John Wiley and Sons ISBN 0-471-52369-0.
• S. P. Meyn and R. L. Tweedie (1993) Markov Chains and Stochastic Stability. London: Springer-Verlag ISBN 0-387-19832-6. online: MCSS . Second edition to appear, Cambridge University Press, 2009.
• Dynkin, Eugene Borisovich (1965). Markov Processes. Grundlehren der mathematischen Wissenschaften. Vol. I (121). Translated by Fabius, Jaap; Greenberg, Vida Lazarus; Maitra, Ashok Prasad; Majone, Giandomenico. Berlin: Springer-Verlag. doi:10.1007/978-3-662-00031-1. ISBN 978-3-662-00033-5. Title-No. 5104.; Markov Processes. Vol. II (122). 1965. doi:10.1007/978-3-662-25360-1. ISBN 978-3-662-23320-7. Title-No. 5105. (NB. This was originally published in Russian as Марковские процессы (Markovskiye protsessy) by Fizmatgiz in 1963 and translated to English with the assistance of the author.)
• S. P. Meyn. Control Techniques for Complex Networks. Cambridge University Press, 2007. ISBN 978-0-521-88441-9. Appendix contains abridged Meyn & Tweedie. online: CTCN
• Booth, Taylor L. (1967). Sequential Machines and Automata Theory (1st ed.). New York, NY: John Wiley and Sons, Inc. Library of Congress Card Catalog Number 67-25924. ] Extensive, wide-ranging book meant for specialists, written for both theoretical computer scientists as well as electrical engineers. With detailed explanations of state minimization techniques, FSMs, Turing machines, Markov processes, and undecidability. Excellent treatment of Markov processes pp. 449ff. Discusses Z-transforms, D transforms in their context.
• Kemeny, John G.; Hazleton Mirkil; J. Laurie Snell; Gerald L. Thompson (1959). Finite Mathematical Structures (1st ed.). Englewood Cliffs, NJ: Prentice-Hall, Inc. Library of Congress Card Catalog Number 59-12841. Classical text. cf Chapter 6 Finite Markov Chains pp. 384ff.
• John G. Kemeny & J. Laurie Snell (1960) Finite Markov Chains, D. van Nostrand Company ISBN 0-442-04328-7
• E. Nummelin. "General irreducible Markov chains and non-negative operators". Cambridge University Press, 1984, 2004. ISBN 0-521-60494-X
• Seneta, E. Non-negative matrices and Markov chains. 2nd rev. ed., 1981, XVI, 288 p., Softcover Springer Series in Statistics. (Originally published by Allen & Unwin Ltd., London, 1973) ISBN 978-0-387-29765-1
• Kishor S. Trivedi, Probability and Statistics with Reliability, Queueing, and Computer Science Applications, John Wiley & Sons, Inc. New York, 2002. ISBN 0-471-33341-7.
• K. S. Trivedi and R.A.Sahner, SHARPE at the age of twenty-two, vol. 36, no. 4, pp. 52–57, ACM SIGMETRICS Performance Evaluation Review, 2009.
• R. A. Sahner, K. S. Trivedi and A. Puliafito, Performance and reliability analysis of computer systems: an example-based approach using the SHARPE software package, Kluwer Academic Publishers, 1996. ISBN 0-7923-9650-2.
• G. Bolch, S. Greiner, H. de Meer and K. S. Trivedi, Queueing Networks and Markov Chains, John Wiley, 2nd edition, 2006. ISBN 978-0-7923-9650-5.

External links

• "Markov chain", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Markov Chains chapter in American Mathematical Society's introductory probability book Archived 2008-05-22 at the Wayback Machine
• Introduction to Markov Chains on YouTube
• A visual explanation of Markov Chains
• Original paper by A.A Markov (1913): An Example of Statistical Investigation of the Text Eugene Onegin Concerning the Connection of Samples in Chains (translated from Russian)