Cadena de Márkov

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Una cadena de Markov o proceso de Markov es un modelo estocástico que describe una secuencia de posibles eventos en los que la probabilidad de cada evento depende únicamente del estado alcanzado en el evento anterior. Una secuencia infinita numerable, en la que la cadena cambia de estado en pasos de tiempo discretos, da una cadena de Markov de tiempo discreto (DTMC). Un proceso de tiempo continuo se llama cadena de Markov de tiempo continuo (CTMC). Lleva el nombre del matemático ruso Andrey Markov.

Las cadenas de Markov tienen muchas aplicaciones como modelos estadísticos de procesos del mundo real, como el estudio de sistemas de control de crucero en vehículos motorizados, colas o filas de clientes que llegan a un aeropuerto, tasas de cambio de divisas y dinámica de población animal.

Los procesos de Markov son la base de los métodos de simulación estocástica general conocidos como cadena de Markov Monte Carlo, que se utilizan para simular muestras de distribuciones de probabilidad complejas y han encontrado aplicación en estadística bayesiana, termodinámica, mecánica estadística, física, química, economía, finanzas, señales procesamiento, teoría de la información y procesamiento del habla.

Los adjetivos Markoviano y Markov se utilizan para describir algo que está relacionado con un proceso de Markov.

Introducción

Definición

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 los resultados futuros basándose únicamente en su estado actual y, lo que es más importante, tales predicciones son tan buenas como las que se podrían hacer conociendo la historia completa del proceso. En otras palabras, condicionado al estado presente del sistema, sus estados futuro y pasado son independientes.

Una cadena de Markov es un tipo de proceso de Markov que tiene un espacio de estado 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. Por ejemplo, es común definir una cadena de Markov como un proceso de Markov en tiempo discreto o continuo con un espacio de estado contable (por lo tanto, independientemente de la naturaleza del tiempo), pero también es común definir una cadena de Markov como un proceso de tiempo discreto. en un espacio de estado contable o continuo (por lo tanto, independientemente del espacio de estado).

Tipos de cadenas de Markov

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

	Espacio de estado contable	Espacio de estado continuo o general
Tiempo discreto	(tiempo discreto) Cadena de Markov en un espacio de estado contable o finito	Cadena de Markov en un espacio de estado medible (por ejemplo, cadena de Harris)
Tiempo continuo	Proceso de Markov en tiempo continuo o proceso de salto de Markov	Cualquier proceso estocástico continuo con la propiedad de Markov (por ejemplo, el proceso de Wiener)

Tenga en cuenta que no existe un acuerdo definitivo en la literatura sobre el uso de algunos de los términos que significan casos especiales de procesos de Markov. Por lo general, 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), pero algunos autores usan el término "proceso de Markov" para referirse a un proceso de tiempo continuo. Cadena de Markov (CTMC) sin mención explícita.Además, existen otras extensiones de los procesos de Markov a las que se hace referencia como tales, pero que no necesariamente se incluyen en ninguna de estas cuatro categorías (consulte el modelo de Markov). Además, el índice de tiempo no tiene por qué ser necesariamente de valor real; Al igual que con el espacio de estado, existen procesos concebibles que se mueven a través de conjuntos de índices con otras construcciones matemáticas. Observe que la cadena de Markov de tiempo continuo en el espacio de estado general es general hasta tal punto que no tiene un término designado.

Si bien el parámetro de tiempo suele ser discreto, el espacio de estado de una cadena de Markov no tiene restricciones generalmente acordadas: el término puede referirse a un proceso en un espacio de estado arbitrario. Sin embargo, muchas aplicaciones de las cadenas de Markov emplean espacios de estado finitos o contablemente infinitos, que tienen un análisis estadístico más sencillo. Además de los parámetros de índice de tiempo y espacio de estado, hay 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 estado 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 estado, una matriz de transición que describe las probabilidades de transiciones particulares y un estado inicial (o distribución inicial) a través del espacio de estado. 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 cierto estado en cada paso, y el estado cambia aleatoriamente entre los pasos. Los pasos a menudo se consideran momentos en el tiempo, pero también pueden referirse a la distancia física o cualquier otra medida discreta. Formalmente, los pasos son los números enteros o naturales, y el proceso aleatorio es un mapeo de estos a los 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 adicionalmente del estado del sistema en los pasos anteriores.

Dado que el sistema cambia aleatoriamente, generalmente es imposible predecir con certeza el estado de una cadena de Markov en un punto dado en el futuro. Sin embargo, se pueden predecir las propiedades estadísticas del futuro del sistema. En muchas aplicaciones, son estas propiedades estadísticas las que son importantes.

Historia

Markov estudió los procesos de Markov a principios del siglo XX y publicó su primer artículo sobre el tema en 1906. Los procesos de Markov en tiempo continuo se descubrieron mucho antes del trabajo de Andrey Markov a principios del siglo XX en la forma del proceso de Poisson. 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. En su primer artículo sobre las cadenas de Markov, publicado en 1906, Markov demostró que, bajo ciertas condiciones, los resultados promedio de la cadena de Markov convergerían en un vector fijo de valores, demostrando así una ley débil de los grandes números sin el supuesto de independencia.que se había considerado comúnmente como un requisito para que tales leyes matemáticas se mantuvieran. Más tarde, Markov usó las cadenas de Markov para estudiar la distribución de las vocales en Eugene Onegin, escrito por Alexander Pushkin, y demostró un teorema del límite central para tales cadenas.

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, presentado por Paul y Tatyana Ehrenfest en 1907, y un proceso de ramificación, presentado por Francis Galton y Henry William Watson en 1873, que precede al trabajo de Markov. Después del trabajo de Galton y Watson, más tarde se reveló que su proceso de ramificación había sido descubierto y estudiado de forma independiente unas tres décadas antes por Irénée-Jules Bienaymé. 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.

Andrey Kolmogorov desarrolló en un artículo de 1931 una gran parte de la teoría inicial de los procesos de Markov en tiempo continuo. 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. 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. 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. Las ecuaciones diferenciales ahora se denominan ecuaciones de Kolmogorov o ecuaciones de Kolmogorov-Chapman.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 a Eugene Dynkin, a partir de la década de 1950.

Ejemplos

Los paseos aleatorios basados en números enteros y el problema de la ruina del jugador son ejemplos de procesos de Markov. Algunas variaciones de estos procesos fueron estudiadas cientos de años antes en el contexto de variables independientes. Dos ejemplos importantes de procesos de Markov son el proceso de Wiener, también conocido como proceso de movimiento browniano, y el proceso de Poisson, que se consideran los procesos estocásticos más importantes y centrales en la teoría de procesos estocásticos. 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.
Una cadena de Markov famosa es la llamada "caminata del borracho", una caminata aleatoria en la recta numérica donde, en cada paso, la posición puede cambiar en +1 o -1 con igual 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 de 0,5, y todas las demás probabilidades de transición de 5 son 0. Estas probabilidades son independientes de si el sistema estaba previamente en 4 o en 6.
Otro ejemplo son los hábitos alimentarios de un animal muy teórico que sólo come uvas, queso o lechuga, y cuyos hábitos alimentarios se ajustan a las siguientes reglas:
- Come exactamente una vez al día.
- Si hoy comió queso, mañana comerá lechuga o uvas con igual probabilidad.
- Si hoy comió uvas, mañana comerá uvas con probabilidad 1/10, queso con probabilidad 4/10 y lechuga con probabilidad 5/10.
- Si hoy comió lechuga, mañana comerá uvas con probabilidad 4/10 o queso con probabilidad 6/10. No volverá a comer lechuga mañana.

Los hábitos alimenticios de este animal se pueden modelar con una cadena de Markov, ya que su elección mañana depende únicamente de lo que comió hoy, no de lo que comió ayer o en cualquier otro momento del pasado. Una propiedad estadística que podría calcularse es el porcentaje esperado, durante un largo período, de los días en que el animal comerá uvas.

Una serie de eventos independientes (por ejemplo, una serie de lanzamientos de monedas) satisface la definición formal de una cadena de Markov. Sin embargo, la teoría generalmente se aplica solo cuando la distribución de probabilidad del siguiente paso depende de manera no trivial del estado actual.

Un ejemplo no markoviano

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

Para ver por qué este es el caso, suponga que en los primeros seis sorteos, se extraen las cinco monedas de cinco centavos y un cuarto. Por lo $X_6 = $0,50$ tanto Si conocemos no solo $X_6$ , sino también los valores anteriores, entonces podemos determinar qué monedas se han extraído y sabemos que la próxima moneda no será de cinco centavos; entonces podemos determinar eso $X_7 geq $0,60$ con una probabilidad de 1. Pero si no conocemos los valores anteriores, entonces basándonos solo en el valor $X_6$ , podríamos suponer que habíamos sacado cuatro monedas de diez centavos y dos de cinco, en cuyo caso sería posible sacar otra moneda de cinco centavos. Siguiente. Por lo tanto, nuestras conjeturas sobre $X_7$ se ven afectadas por nuestro conocimiento de los valores antes de $X_6$ .

Sin embargo, es posible modelar este escenario como un proceso de Markov. En lugar de definir $X_{n}$ para representar el valor total de las monedas en la mesa, podríamos definir $X_{n}$ para representar el conteo de los distintos tipos de monedas en la mesa. Por ejemplo, ${ estilo de visualización X_ {6} = 1,0,5}$ 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 sorteos uno por uno. Este nuevo modelo podría estar representado por ${displaystyle 6times 6times 6=216}$ estados posibles, donde cada estado representa el número de monedas de cada tipo (de 0 a 5) que hay sobre la mesa. (No todos estos estados son accesibles en 6 sorteos). Suponga que el primer sorteo da como resultado el estado ${ estilo de visualización X_ {1} = 0,1,0}$ . La probabilidad de lograr $X_{2}$ ahora depende de $X_{1}$ ; por ejemplo, el estado ${ estilo de visualización X_ {2} = 1,0,1}$ no es posible. Después del segundo sorteo, el tercer sorteo depende de las monedas que se hayan sorteado hasta ahora, pero ya no solo de las monedas que se sacaron para el primer estado (ya que desde entonces se ha agregado información probabilísticamente importante al escenario). De esta manera, la probabilidad del ${displaystyle X_{n}=i,j,k}$ estado depende exclusivamente del resultado del ${displaystyle X_{n-1}=ell,m,p}$ estado.

Definicion formal

Cadena de Markov en tiempo discreto

Una cadena de Markov en 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 solo del estado presente y no del anterior estados: ${displaystyle Pr(X_{n+1}=xmid X_{1}=x_{1},X_{2}=x_{2},ldots,X_{n}=x_{n})= Pr(X_{n+1}=xmid X_{n}=x_{n}),}$ si ambas probabilidades condicionales están bien definidas, es decir, si0.}">

Los posibles valores de X _i forman un conjunto contable S llamado espacio de estado de la cadena.

Variaciones

Las cadenas de Markov homogéneas en el tiempo son procesos en los que ${displaystyle Pr(X_{n+1}=xmid X_{n}=y)=Pr(X_{n}=xmid X_{n-1}=y)}$ para todo n La probabilidad de la transición es independiente de n.
Las cadenas de Markov estacionarias son procesos donde ${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})}$ para todo n y k. Se puede demostrar que toda cadena estacionaria es homogénea en el tiempo mediante la regla de Bayes.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 $X_{0}$ sea una distribución estacionaria de la cadena de Markov.
Una cadena de Markov con memoria (o una cadena de Markov de orden m) donde m es finito, es un proceso que satisfacemend{alineado}}}">En otras palabras, el estado futuro depende de los m estados pasados. Es posible construir una cadena ${ estilo de visualización (Y_ {n})}$ a partir de $(X_{n})$ la cual tenga la propiedad 'clásica' de Markov tomando como espacio de estado las m -tuplas ordenadas de valores X, es decir, ${displaystyle Y_{n}=left(X_{n},X_{n-1},ldots,X_{n-m+1}right)}$ .

Cadena de Markov en tiempo continuo

Una cadena de Markov de tiempo continuo (X _t) _{t ≥ 0} está definida por un espacio de estado finito o numerable S, una matriz de tasa de transición Q con dimensiones iguales a las del espacio de estado y distribución de probabilidad inicial definida en el espacio de estado. Para i ≠ j, los elementos q _ij no son negativos y describen la tasa de transición del proceso del estado i al estado j. Los elementos q _iise eligen de tal manera que cada fila de la matriz de tasas de transición sume cero, mientras que las sumas de las filas de una matriz de transición de probabilidad en una cadena de Markov (discreta) sean todas iguales a uno.

Hay tres definiciones equivalentes del proceso.

Definición infinitesimal

Sea $X_{t}$ la variable aleatoria que describe el estado del proceso en el tiempo t, y suponga que el proceso está en un estado i en el tiempo t. Entonces, conociendo ${ estilo de visualización X_ {t} = i}$ , ${ estilo de visualización X_ {t + h} = j}$ es independiente de los valores anteriores <img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7a95f5c63111a32db00d348f62f2e0732ce4b515" alt="{ estilo de visualización izquierda (X_ {s}: s , y como h → 0 para todo j y para todo t,

{displaystyle Pr(X(t+h)=jmid X(t)=i)=delta _{ij}+q_{ij}h+o(h),}

donde $delta _{ij}$ está el delta de Kronecker, usando la notación de o pequeña. Se $q_{ij}$ puede considerar que mide la rapidez con la que ocurre la transición de i a j.

Definición de cadena de salto/tiempo de espera

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

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 estado finito

Si el espacio de estados es finito, la distribución de probabilidad de transición se puede representar mediante una matriz, llamada matriz de transición, con el (i, j)-ésimo elemento de P igual a ${displaystyle p_{ij}=Pr(X_{n+1}=jmid X_{n}=i).}$

Como 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 simples

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 en él y, por lo tanto, se define por ${displaystyle pi mathbf {P} =pi.}$

Al comparar esta definición con la de un vector propio vemos que los dos conceptos están relacionados y que $pi ={frac {e}{sum _{i}{e_{i}}}}$

es un múltiplo normalizado ( ${estilo de texto sum _{i}pi _{i}=1}$ ) de un vector propio izquierdo e de la matriz de transición P con un valor propio de 1. Si hay más de un vector propio unitario, entonces una suma ponderada de los estados estacionarios correspondientes también es un estado estacionario. Pero para una cadena de Markov uno suele estar más interesado en un estado estacionario que es el límite de la secuencia de distribuciones para alguna distribución inicial.

Los valores de una distribución estacionaria $estilo de texto pi _{i}$ están asociados con el espacio de estado 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 ${estilo de texto sum _{i}1cdot pi _{i}=1}$ vemos que el producto escalar de π con un vector cuyas componentes son todos 1 es la unidad y que π se encuentra en un símplex.

Cadena de Markov homogénea en el tiempo con un espacio de estado 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.

Si la cadena de Markov es irreducible y aperiódica, entonces hay una distribución estacionaria única π. Además, en este caso P converge a una matriz de rango uno en la que cada fila es la distribución estacionaria π: ${displaystyle lim _{kto infty }mathbf {P} ^{k}=mathbf {1} pi }$

donde 1 es el vector columna con todas las entradas iguales a 1. Esto lo establece el teorema de Perron-Frobenius. Si, por cualquier medio, ${textstyle lim _{kto infty}mathbf {P} ^{k}}$ se encuentra, entonces la distribución estacionaria de la cadena de Markov en cuestión se puede determinar fácilmente para cualquier distribución inicial, como se explicará a continuación.

Para algunas matrices estocásticas P, el límite ${textstyle lim _{kto infty}mathbf {P} ^{k}}$ no existe mientras que la distribución estacionaria sí, como lo muestra este ejemplo: ${displaystyle mathbf {P} ={begin{pmatrix}0&1\1&0end{pmatrix}}qquad mathbf {P} ^{2k}=Iqquad mathbf {P} ^{2k+1 }=mathbf {P} }$ ${begin{pmatrix}{frac {1}{2}}&{frac {1}{2}}end{pmatrix}}{begin{pmatrix}0&1\1&0end{pmatrix}}= {begin{pmatrix}{frac {1}{2}}&{frac {1}{2}}end{pmatrix}}$

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

Debido a que hay varios casos especiales diferentes a considerar, el proceso de encontrar este límite, si existe, puede ser una tarea larga. Sin embargo, existen muchas técnicas que pueden ayudar a encontrar este límite. Sea P una matriz n × n, y defina ${textstyle mathbf {Q} =lim _{kto infty }mathbf {P} ^{k}.}$

Siempre es cierto que $mathbf{QP} =mathbf{Q}.$

Restar Q de ambos lados y factorizar luego produce $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 matrices estocásticas siempre produce otra matriz estocástica, por lo que Q debe ser una matriz estocástica (ver la definición anterior). A veces es suficiente usar la ecuación matricial anterior y el hecho de que Q es una matriz estocástica para resolver Q. Incluyendo el hecho de que la suma de cada fila en P es 1, hay n+1 ecuaciones para determinar nincógnitas, por lo que computacionalmente es 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 otro se sustituye el elemento correspondiente (el de la misma columna) en el vector 0, y next multiplica a la izquierda este último vector por el inverso de la matriz anterior transformada para encontrar Q.

Aquí hay un método para hacerlo: primero, defina la función f (A) para devolver la matriz A con su columna más a la derecha reemplazada con todos los 1. Si [ f (P − I _n)] existe entonces $mathbf {Q} =f(mathbf {0} _{n,n})[f(mathbf {P} -mathbf {I} _{n})]^{-1}.$ Explique: 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 por el hecho de 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 el n × n variables. En este ejemplo, las n ecuaciones de “Q multiplicado por la columna más a la derecha de (P-In)” han sido reemplazadas por las n 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 se rellena con ceros, entonces esa fila o columna permanecerá sin cambios en todos los subsiguientes. potencias P. _ Por lo tanto, la i -ésima fila o columna de Q tendrá los 1 y los 0 en las mismas posiciones que en P.

Velocidad de convergencia a la distribución estacionaria

Como se indicó anteriormente, a partir de la ecuación ${displaystyle {boldsymbol {pi }}={boldsymbol {pi }}mathbf {P},}$ (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, de manera equivalente, 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, uno puede comenzar con la forma normal de Jordan de P y proceder con un conjunto de argumentos un poco más complicado de manera similar.

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). Entonces por autodescomposición $mathbf {P} =mathbf {USigma U} ^{-1}.$

Se enumeran los valores propios de tal manera que:|lambda _{2}|geq |lambda _{3}|geq cdots geq |lambda _{n}|.}">

Dado que P es una matriz estocástica de filas, su valor propio izquierdo más grande es 1. Si hay una distribución estacionaria única, entonces el valor propio más grande y el vector propio correspondiente también son únicos (porque no hay otro π que resuelva la ecuación de distribución estacionaria anterior). Sea u _i la i -ésima columna de la matriz U, es decir, u _i es el vector propio izquierdo de P correspondiente a λ _i. También sea x un vector de longitud n fila que representa una distribución de probabilidad válida; ya que los vectores propios u _i abarcan ${ estilo de visualización mathbb {R} ^ {n},}$ podemos escribir ${displaystyle mathbf {x} ^{mathsf {T}}=sum _{i=1}^{n}a_{i}mathbf {u} _{i},qquad a_{i} en 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, π = u _i ← xPP... P = xP cuando k → ∞. Eso significa ${displaystyle {begin{alineado}{boldsymbol {pi }}^{(k)}&=mathbf {x} left(mathbf {USigma U} ^{-1}right) izquierda(mathbf {USigma U} ^{-1}right)cdots left(mathbf {USigma U} ^{-1}right)\&=mathbf {xUSigma } ^{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 {USigma } ^ {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{ para }}ineq 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} fin{alineado}}}$

Como π = u ₁, π se aproxima a π cuando k → ∞ con una velocidad del orden de λ ₂ / λ ₁ exponencialmente. Esto se debe a que, por ${ estilo de visualización | lambda _ {2} | geq cdots geq | lambda _ {n} |,}$ lo tanto, λ ₂ / λ ₁ es el término dominante. Cuanto menor es la relación, más rápida es la convergencia. El ruido aleatorio en la distribución de estado π también puede acelerar esta convergencia a la distribución estacionaria.

Espacio de estado general

Cadenas harris

Muchos resultados para cadenas de Markov con espacio de estado finito se pueden generalizar a cadenas con espacio de estado incontable a través de cadenas de Harris.

El uso de cadenas de Markov en métodos Monte Carlo de cadenas de Markov cubre casos en los que el proceso sigue un espacio de estado continuo.

Cadenas de Markov que interactúan localmente

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 cuando el espacio de estado tiene una forma de producto (cartesiano). Ver sistema de partículas que interactúan y autómatas celulares estocásticos (autómatas celulares probabilísticos). Véase, por ejemplo, Interacción de procesos de Markov o

Propiedades

Dos estados se comunican entre sí si ambos son alcanzables entre sí mediante una secuencia de transiciones que tienen probabilidad positiva. Esta es una relación de equivalencia que produce un conjunto de clases comunicantes. Una clase se cierra si la probabilidad de abandonar la clase es cero. Una cadena de Markov es irreducible si hay una clase comunicante, el espacio de estado.

Un estado i tiene un 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:0:Pr(X_{n}=imid X_{0}=i)>0}">

Se dice que un estado i es transitorio si, a partir de i, existe una probabilidad distinta de cero de que la cadena nunca vuelva a i. Es recurrente en caso contrario. Para un estado recurrente i, el tiempo medio de acierto se define como: ${displaystyle M_{i}=E[T_{i}]=sum _{n=1}^{infty}ncdot f_{ii}^{(n)}.}$

El estado i es recurrente positivo si $Mi}$ 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, todos los estados en su clase de comunicación tienen la propiedad.

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

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 tiene un tiempo de recurrencia medio finito. Si todos los estados de una cadena de Markov irreducible son ergódicos, se dice que la cadena es ergódica.

Se puede demostrar que una cadena de Markov irreducible de estado finito es ergódica si tiene un estado aperiódico. De manera más general, una cadena de Markov es ergódica si hay un número N tal que se puede alcanzar cualquier estado desde cualquier otro estado en cualquier número de pasos menor o igual a un número N. En el caso de una matriz de transición completamente conectada, donde todas las transiciones tienen una probabilidad distinta de cero, esta condición se cumple con N = 1.

Una cadena de Markov con más de un estado y solo una transición saliente por estado no es irreducible ni aperiódica, por lo que no puede ser ergódica.

Representaciones markovianas

En algunos casos, los procesos aparentemente no markovianos aún pueden tener representaciones markovianas, construidas mediante la expansión del concepto de estados "actuales" y "futuros". Por ejemplo, sea X un proceso no markoviano. Luego defina un proceso Y, tal que cada estado de Y represente un intervalo de tiempo de estados de X. Matemáticamente, esto toma la forma: $Y(t) = grande{ X(s): s in [a(t), b(t)] , grande}.$

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 de tiempo autorregresiva de orden mayor que uno.

Tiempos de golpe

El tiempo de acierto es el tiempo que comienza en un conjunto dado de estados hasta que la cadena llega a un estado o conjunto de estados dado. La distribución de tal período de tiempo tiene una distribución de tipo de fase. La distribución más simple es la de una única transición distribuida exponencialmente.

Tiempos de golpe esperados

Para un subconjunto de estados A ⊆ S, el vector k de tiempos de acierto (donde el elemento ${displaystyle k_{i}^{A}}$ representa el valor esperado, comenzando en el estado i en el que la cadena ingresa a uno de los estados del conjunto A) es la solución mínima no negativa de ${displaystyle begin{align} k_i^A = 0 & text{ para } yo in A\ -sum_{j in S} q_{ij} k_j^A = 1&text{ para } yo no en A. end{align}}$

Inversión del tiempo

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

Se dice que una cadena es reversible si el proceso inverso es el mismo que el proceso directo. El criterio de Kolmogorov establece que la condición necesaria y suficiente para que un proceso sea reversible es que el producto de las tasas de transición alrededor de un circuito cerrado debe ser el mismo en ambas direcciones.

Cadena de Markov incrustada

Un método para encontrar la distribución de probabilidad estacionaria, π, de una cadena de Markov de tiempo continuo ergódica, Q, es encontrar primero su cadena de Markov incrustada (EMC). Estrictamente hablando, el 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 pueden ser encontradas por ${displaystyle s_{ij} = begin{cases} frac{q_{ij}}{sum_{k neq i} q_{ik}} & text{if } i neq j \ 0 & texto {de lo contrario}. end{casos} }$

A partir de esto, S puede escribirse como ${displaystyle S = yo - 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 estacionario, debemos encontrar $varphi$ tal que ${ estilo de visualización varphi S = varphi,}$

siendo $varphi$ un vector de fila, tal que todos los elementos en $varphi$ son mayores que 0 y ${ estilo de visualización | varphi |_{1}}$ = 1. A partir de esto, π se puede encontrar como ${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 markoviano

Los modelos de Markov se utilizan para modelar sistemas cambiantes. Hay 4 tipos principales de modelos, que generalizan las cadenas de Markov dependiendo de si cada estado secuencial es observable o no, y si el sistema se va a ajustar sobre la base de las observaciones realizadas:

	El estado del sistema es totalmente observable	El estado del sistema es parcialmente observable
El sistema es autónomo	cadena de Markov	Modelo oculto de Markov
El sistema es controlado	Proceso de decisión de Markov	Proceso de decisión de Markov parcialmente observable

Esquema de Bernoulli

Un esquema de Bernoulli es un caso especial de una cadena de Markov donde la matriz de probabilidad de transición tiene filas idénticas, lo que significa que el siguiente estado es independiente incluso del estado actual (además de ser independiente de los estados pasados). Un esquema de Bernoulli con solo dos estados posibles se conoce como proceso de Bernoulli.

Nótese, sin embargo, por el teorema del isomorfismo de Ornstein, que toda cadena de Markov aperiódica e irreducible es isomorfa a un esquema de Bernoulli; por lo tanto, uno podría igualmente afirmar que las cadenas de Markov son un "caso especial" de los esquemas de Bernoulli. El isomorfismo generalmente requiere una recodificación complicada. El teorema del isomorfismo es aún 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 uno de esos ejemplos.

Subshift 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. Una matriz de Markov que sea compatible con la matriz de adyacencia puede proporcionar una medida del subdesplazamiento. Muchos sistemas dinámicos caóticos son isomorfos a las cadenas topológicas de Markov; los ejemplos incluyen difeomorfismos de variedades cerradas, el sistema Prouhet-Thue-Morse, el sistema Chacon, sistemas sofic, sistemas libres de contexto y sistemas de codificación de bloques.

Aplicaciones

La investigación ha informado de la aplicación y utilidad de las cadenas de Markov en una amplia gama de temas como la física, la química, la biología, la medicina, la música, la teoría de juegos y los deportes.

Física

Los sistemas markovianos aparecen ampliamente en la termodinámica y la 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 invariable en el tiempo y que no es necesario considerar una historia relevante que no esté ya incluida. en la descripción del estado. 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 Markov Chain Monte Carlo se puede utilizar para extraer muestras al azar de una caja negra para aproximar la distribución de probabilidad de los atributos en un rango de objetos.

Los caminos, en la formulación integral de caminos de la mecánica cuántica, son cadenas de Markov.

Las cadenas de Markov se utilizan en simulaciones QCD de celosía.

Química

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 dichas redes tratan el sistema como una cadena de Markov de tiempo continuo, siendo el estado el número de moléculas de cada especie y con reacciones modeladas como posibles transiciones de la cadena. 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, imagina un gran número nde moléculas en solución en el estado A, cada una de las cuales puede sufrir una reacción química al estado B con una cierta velocidad promedio. Tal vez la molécula sea una enzima y los estados se refieran a cómo se pliega. El estado de cualquier enzima individual sigue una cadena de Markov, y dado que las moléculas son esencialmente independientes entre sí, el número de moléculas en el estado A o B a la vez es n veces la probabilidad de que una molécula dada esté en ese estado.

El modelo clásico de actividad enzimática, la cinética de Michaelis-Menten, puede verse como una cadena de Markov, donde en cada paso de tiempo la reacción procede en alguna dirección. Si bien Michaelis-Menten es bastante sencillo, también se pueden modelar redes de reacción mucho más complicadas con cadenas de Markov.

También se utilizó un algoritmo basado en una cadena de Markov para enfocar el crecimiento basado en fragmentos de productos químicos in silico hacia una clase deseada de compuestos, como medicamentos o productos naturales. A medida que crece 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á ligado a él). Luego pasa al siguiente estado cuando se le adjunta un fragmento. Las probabilidades de transición se entrenan en bases de datos de clases auténticas de compuestos.

Además, el crecimiento (y la composición) de los copolímeros se puede modelar utilizando cadenas de Markov. En función de las relaciones 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 alterna o en series largas del mismo monómero). Debido a los efectos estéricos, los efectos de Markov de segundo orden también pueden desempeñar un papel en el crecimiento de algunas cadenas de polímeros.

De manera similar, se ha sugerido que la cristalización y el crecimiento de algunos materiales de óxido de superredes epitaxiales pueden describirse con precisión mediante cadenas de Markov.

Biología

Las cadenas de Markov se utilizan en diversas áreas de la biología. Los ejemplos notables incluyen:

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 de población matriciales.
Neurobiología, donde se han utilizado cadenas de Markov, por ejemplo, para simular el neocórtex de mamíferos.
Biología de sistemas, por ejemplo con el modelado de infección viral de células individuales.
Modelos compartimentales para el modelado de brotes de enfermedades y epidemias.

Pruebas

Varios teóricos han propuesto la idea de la prueba estadística de la cadena de Markov (MCST), un método para unir cadenas de Markov para formar una "manta de Markov", organizando estas cadenas en varias capas recursivas ("obleas") y produciendo conjuntos de prueba más eficientes: muestras —como reemplazo de pruebas exhaustivas. Los MCST también tienen usos en redes basadas en estados temporales; El artículo de Chilukuri et al. titulado "Redes de razonamiento de incertidumbre temporal para la fusión de evidencia con aplicaciones para la detección y el seguimiento de objetos" (ScienceDirect) brinda antecedentes y un estudio de caso para aplicar MCST a una gama más amplia de aplicaciones.

Variabilidad de la irradiancia solar

Las evaluaciones de la variabilidad de la irradiancia solar son útiles para las aplicaciones de energía solar. La variabilidad de la radiación solar en cualquier lugar a lo largo del tiempo es principalmente una consecuencia de la variabilidad determinista de la trayectoria del sol a través de la cúpula del cielo y la variabilidad de la nubosidad. La variabilidad de la radiación solar accesible en la superficie de la Tierra se ha modelado utilizando cadenas de Markov, que también incluyen el modelado de los dos estados de claridad y nubosidad como una cadena de Markov de dos estados.

Reconocimiento de voz

Los modelos ocultos de Markov son la base de la mayoría de los sistemas automáticos de reconocimiento de voz modernos.

Teoría de la información

Las cadenas de Markov se utilizan en todo el procesamiento de la información. El famoso artículo de 1948 de Claude Shannon A Mathematical Theory of Communication, que en un solo paso creó el campo de la teoría de la información, comienza introduciendo el concepto de entropía a través del modelado de Markov del idioma inglés. Tales modelos idealizados pueden capturar muchas de las regularidades estadísticas de los sistemas. Incluso sin describir perfectamente la estructura completa del sistema, tales 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 la estimación efectiva del estado y el reconocimiento de patrones. Las cadenas de Markov también juegan un papel importante en el aprendizaje por refuerzo.

Las cadenas de Markov también son la base de los modelos ocultos de Markov, que son una herramienta importante en campos tan diversos como las redes telefónicas (que utilizan el algoritmo de Viterbi para la corrección de errores), el reconocimiento de voz y la bioinformática (como en la detección de reordenamientos).

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

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. Esto los hace fundamentales para optimizar el rendimiento de las redes de telecomunicaciones, donde los mensajes a menudo deben competir por recursos limitados (como el ancho de banda).

Numerosos modelos de colas utilizan cadenas de Markov de tiempo continuo. Por ejemplo, una cola M/M/1 es una CTMC en los enteros no negativos donde las transiciones ascendentes de i a i + 1 ocurren a una velocidad λ de acuerdo con 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 del trabajo se distribuyen exponencialmente) y describen los servicios completados (salidas) de la cola.

Aplicaciones de internet

El PageRank de una página web tal como lo utiliza Google se define mediante una cadena de Markov. Es la probabilidad de estar en la página $i$ en la distribución estacionaria en la siguiente cadena de Markov en todas las páginas web (conocidas). Si $norte$ es el número de páginas web conocidas y una página $i$ tiene $k_{yo}$ enlaces a ella, entonces tiene probabilidad de transición ${frac {alfa }{k_{i}}}+{frac {1-alfa }{N}}$ para todas las páginas a las que se enlazan y ${frac{1-alfa}{N}}$ para todas las páginas a las que no se enlazan. El parámetro $alfa$ se toma en torno a 0,15.

Los modelos de Markov también se han utilizado para analizar el comportamiento de navegación web de los usuarios. La transición del enlace web de un usuario en un sitio web en particular se puede modelar utilizando modelos de Markov de primer o segundo orden y se puede usar para hacer predicciones sobre la navegación futura y personalizar la página web para un usuario individual.

Estadísticas

Los métodos de la cadena de Markov también se han vuelto muy importantes para generar secuencias de números aleatorios para reflejar con precisión distribuciones de probabilidad deseadas muy complicadas, a través de un proceso llamado cadena de Markov Monte Carlo (MCMC). En los últimos años, esto ha revolucionado la viabilidad de los métodos de inferencia bayesianos, lo que permite simular una amplia gama de distribuciones posteriores y encontrar sus parámetros numéricamente.

Economía y Finanzas

Las cadenas de Markov se utilizan en finanzas y economía para modelar una variedad de fenómenos diferentes, incluida la distribución del ingreso, la distribución del tamaño de las empresas, los precios de los activos y las caídas del mercado. DG Champernowne construyó un modelo de cadena de Markov de la distribución del ingreso en 1953. Herbert A. Simon y el coautor Charles Bonini utilizaron un modelo de cadena de Markov para derivar una distribución estacionaria de Yule del tamaño de las empresas. Louis Bachelier fue el primero en observar que los precios de las acciones seguían un camino aleatorio. La caminata aleatoria se vio más tarde como evidencia a favor de la hipótesis del mercado eficiente y los modelos de caminata aleatoria fueron populares en la literatura de la década de 1960.Los modelos de ciclos económicos de cambio de régimen fueron popularizados por James D. Hamilton (1989), quien usó una cadena de Markov para modelar cambios entre períodos de alto y bajo crecimiento del PIB (o, alternativamente, expansiones y recesiones económicas). Un ejemplo más reciente es el modelo multifractal de conmutación de Markov de Laurent E. Calvet y Adlai J. Fisher, que se basa en la conveniencia de modelos anteriores de conmutación de régimen. Utiliza una cadena de Markov arbitrariamente grande para impulsar el nivel de volatilidad de los rendimientos de los activos.

La macroeconomía dinámica hace un uso intensivo de las cadenas de Markov. Un ejemplo es el uso de cadenas de Markov para modelar exógenamente los precios de las acciones (acciones) en un entorno de equilibrio general.

Las agencias de calificación crediticia elaboran tablas anuales de probabilidades de transición para bonos de diferentes calificaciones crediticias.

Ciencias Sociales

Las cadenas de Markov generalmente se usan para describir argumentos dependientes de la ruta, donde las configuraciones estructurales actuales condicionan los resultados futuros. Un ejemplo es la reformulación de la idea, originalmente debida a Das Kapital de Karl Marx, vinculando el desarrollo económico al surgimiento del capitalismo. En la investigación actual, es común usar una cadena de Markov para modelar cómo una vez que un país alcanza un nivel específico de desarrollo económico, la configuración de factores estructurales, como el tamaño de la clase media, la proporción de residencia urbana a rural, la tasa de movilización política, etc., generará una mayor probabilidad de transitar de un régimen autoritario a uno democrático.

Juegos

Las cadenas de Markov se pueden usar para modelar muchos juegos de azar. Los juegos infantiles Snakes and Ladders y "Hi Ho! Cherry-O", por ejemplo, están representados exactamente por cadenas de Markov. En cada turno, el jugador comienza en un estado dado (en un cuadrado dado) y desde allí tiene probabilidades fijas de moverse a otros estados (cuadrados).

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 más abajo). Se construye un algoritmo para producir valores de notas de salida basados en las ponderaciones de la matriz de transición, que podrían ser valores de notas MIDI, frecuencia (Hz) o cualquier otra métrica deseable.

Nota	UN	do ♯	mi ♭
UN	0.1	0.6	0.3
do ♯	0.25	0.05	0.7
mi ♭	0.7	0.3	0

notas	UN	D	GRAMO
Automóvil club británico	0.18	0.6	0.22
ANUNCIO	0.5	0.5	0
AG	0.15	0.75	0.1
DD	0	0	1
AD	0.25	0	0.75
director general	0.9	0.1	0
GG	0.4	0.4	0.2
Georgia	0.5	0.25	0.25
GD	1	0	0

Se puede introducir una cadena de Markov de segundo orden considerando el estado actual y también el estado anterior, como se indica en la segunda tabla. Las cadenas superiores de n -ésimo orden tienden a "agrupar" notas particulares, mientras que ocasionalmente se "descomponen" en otros patrones y secuencias. Estas cadenas de orden superior tienden a generar resultados con un sentido de estructura de frase, en lugar del "vagabundeo sin rumbo" producido por un sistema de primer orden.

Las cadenas de Markov se pueden usar estructuralmente, como en Analogique A y B de Xenakis. Las cadenas de Markov también se usan en sistemas que usan un modelo de Markov para reaccionar de forma interactiva a la entrada de música.

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

Béisbol

Los modelos de cadena de Markov se han utilizado en análisis avanzados de béisbol desde 1960, aunque su uso aún es raro. Cada media entrada de un juego de béisbol se ajusta al estado de la cadena de Markov cuando se considera el número de corredores y outs. Durante cualquier turno al bate, hay 24 combinaciones posibles de número de outs y posición de los corredores. Mark Pankin muestra que los modelos de cadena de Markov se pueden usar para evaluar carreras creadas tanto para jugadores individuales como para un equipo. También analiza varios tipos de estrategias y condiciones de juego: cómo se han utilizado los modelos de cadenas de Markov para analizar las estadísticas de situaciones de juego, como toques y robo de base, y las diferencias cuando se juega en césped frente a AstroTurf.

Generadores de texto de Markov

Los procesos de Markov también se pueden utilizar para generar texto superficialmente real a partir de un documento de muestra. Los procesos de Markov se utilizan en una variedad de software recreativo "generador de parodias" (ver prensa disociada, Jeff Harrison, Mark V. Shaney y Academias Neutronium). Existen varias bibliotecas de generación de texto de código abierto que utilizan cadenas de Markov, incluido The RiTa Toolkit.

Pronóstico probabilístico

Las cadenas de Markov se han utilizado para pronosticar en varias áreas: por ejemplo, tendencias de precios, energía eólica e irradiación solar. Los modelos de pronóstico de la cadena de Markov utilizan una variedad de configuraciones, desde la discretización de la serie temporal hasta los modelos ocultos de Markov combinados con wavelets y el modelo de distribución de mezcla de cadenas de Markov (MCM).

Contenido relacionado

Más resultados...