Ejemplos de cadenas de Markov

Un juego de serpientes y escaleras o cualquier otro juego cuyos movimientos se determinen completamente por los dados es una cadena de Markov, de hecho, una cadena de Markov absorbente . Esto contrasta con los juegos de cartas como el blackjack , donde las cartas representan una «memoria» de los movimientos anteriores. Para ver la diferencia, consideremos la probabilidad de un evento determinado en el juego. En los juegos de dados mencionados, lo único que importa es el estado actual del tablero. El siguiente estado del tablero depende del estado actual y de la siguiente tirada de dados. No depende de cómo se llegó a ese estado. En un juego como el blackjack, un jugador puede obtener ventaja recordando qué cartas ya se han mostrado (y, por lo tanto, qué cartas ya no están en la baraja), por lo que el siguiente estado (o mano) del juego no es independiente de los estados anteriores.

Este ejemplo provino del propio Markov. ^{[ 2 ]} Markov eligió 20 000 letras de Eugenio Oneguin de Pushkin , las clasificó en vocales y consonantes, y contó las probabilidades de transición.$${\displaystyle {\begin{array}{lll}&{\text{vocal}}&{\text{consonante}}\\{\text{vocal}}&.128&.872\\{\text{consonante}}&.663&.337\end{array}}}$$La distribución estacionaria es de 43,2 por ciento vocales y 56,8 por ciento consonantes, lo cual se acerca al recuento real del libro. ^{[ 3 ]}

Las probabilidades de las condiciones meteorológicas (modeladas como lluviosas o soleadas), dado el clima del día anterior, pueden representarse mediante una matriz de transición :

${\displaystyle P={\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}}$

La matriz P representa el modelo meteorológico en el que un día soleado tiene un 90 % de probabilidad de ser seguido por otro día soleado, y un día lluvioso tiene un 50 % de probabilidad de ser seguido por otro día lluvioso. Las columnas se pueden etiquetar como "soleado" y "lluvioso", y las filas se pueden etiquetar en el mismo orden.

( P ) _ij es la probabilidad de que, si un día determinado es de tipo i , le siga un día de tipo j .

Observe que la suma de las filas de P es igual a 1: esto se debe a que P es una matriz estocástica .

En la figura de la derecha se muestra un diagrama de estados para un ejemplo sencillo, utilizando un grafo dirigido para representar las transiciones de estado . Los estados representan si un mercado bursátil hipotético presenta una tendencia alcista , bajista o estancada durante una semana determinada. Según la figura, una semana alcista va seguida de otra semana alcista el 90% de las veces, una semana bajista el 7,5% de las veces y una semana estancada el 2,5% restante. Etiquetando el espacio de estados {1  =  alcista, 2  =  bajista, 3  =  estancado}, la matriz de transición para este ejemplo es:

${\displaystyle P={\begin{bmatrix}0.9&0.075&0.025\\0.15&0.8&0.05\\0.25&0.25&0.5\end{bmatrix}}.}$

La distribución sobre los estados se puede escribir como un vector fila estocástico x con la relación x ^{( n  +  1)}  = x ^{( n )} P  . Entonces, si en el tiempo n el sistema está en el estado x ^{( n )} , entonces tres períodos de tiempo después, en el tiempo n  +  3 la distribución es

${\displaystyle {\begin{aligned}x^{(n+3)}&=x^{(n+2)}P=\left(x^{(n+1)}P\right)P\\\\&=x^{(n+1)}P^{2}=\left(x^{(n)}P\right)P^{2}\\&=x^{(n)}P^{3}\\\end{aligned}}}$

En particular, si en el instante n el sistema está en el estado 2  (oso), entonces en el instante n  +  3 la distribución es

${\displaystyle {\begin{aligned}x^{(n+3)}&={\begin{bmatrix}0&1&0\end{bmatrix}}{\begin{bmatrix}0.9&0.075&0.025\\0.15&0.8&0.05\\0.25&0.25&0.5\end{bmatrix}}^{3}\\[5pt]&={\begin{bmatrix}0&1&0\end{bmatrix}}{\begin{bmatrix}0.7745&0.17875&0.04675\\0.3575&0.56825&0.07425\\0.4675&0.37125&0.16125\\\end{bmatrix}}\\[5pt]&={\begin{bmatrix}0.3575&0.56825&0.07425\end{bmatrix}}.\end{aligned}}}$

Utilizando la matriz de transición es posible calcular, por ejemplo, la fracción a largo plazo de semanas durante las cuales el mercado está estancado, o el número promedio de semanas que se tardará en pasar de un mercado estancado a uno alcista. Utilizando las probabilidades de transición, las probabilidades de estado estacionario indican que el 62,5% de las semanas estarán en un mercado alcista, el 31,25% en un mercado bajista y el 6,25% en un mercado estancado, ya que:

${\displaystyle \lim _{N\to \infty }\,P^{N}={\begin{bmatrix}0.625&0.3125&0.0625\\0.625&0.3125&0.0625\\0.625&0.3125&0.0625\end{bmatrix}}}$

Un desarrollo exhaustivo y muchos ejemplos se pueden encontrar en la monografía en línea Meyn & Tweedie 2005. ^{[ 6 ]}

Una máquina de estados finitos puede utilizarse como representación de una cadena de Markov. Suponiendo una secuencia de señales de entrada independientes e idénticamente distribuidas (por ejemplo, símbolos de un alfabeto binario elegidos mediante lanzamientos de moneda), si la máquina se encuentra en el estado y en el instante n , entonces la probabilidad de que pase al estado x en el instante n  +  1 depende únicamente del estado actual.

El algoritmo PageRank , utilizado originalmente por Google para clasificar sitios web en los resultados de su buscador, se basa en una cadena de Markov de tiempo discreto. El espacio de estados comprende todas las páginas web indexadas por el buscador. El modelo imagina a un usuario aleatorio que comienza en una página elegida al azar y empieza a hacer clic en los enlaces.

En cada paso de tiempo discreto, el surfista puede:

• Clics en un enlace saliente elegido aleatoriamente desde la página actual con probabilidad${\displaystyle d}$(el "factor de amortiguación", históricamente fijado en torno a 0,85).
• Teletransporta a una página completamente aleatoria en toda Internet con probabilidad${\displaystyle 1-d}$.

Dado que la siguiente página del usuario depende únicamente de los enlaces de la página actual y de la probabilidad de teletransportación fija, el proceso cumple la propiedad de Markov. El PageRank de un sitio web específico es simplemente su valor de probabilidad en el vector de estado estacionario de esta enorme cadena de Markov, que representa la proporción a largo plazo del tiempo que el usuario aleatorio pasa en esa página.

La progresión de puntuación de un solo juego de tenis se puede modelar como una cadena de Markov absorbente . El espacio de estados consiste en las combinaciones de puntuación actuales (por ejemplo, "0-0", "15-0", "30-15", "Empate", "Servidor con ventaja", "Receptor con ventaja", "Servidor de juego", "Receptor de juego").

Suponiendo que el jugador que saca gana un punto determinado con una probabilidad constante${\displaystyle p}$y el jugador receptor gana con probabilidad${\displaystyle q=1-p}$La transición de un estado a otro depende estrictamente de la puntuación actual, no de la secuencia de puntos que condujo a ella.

Por ejemplo, desde el estado "Deuce", la cadena pasa a "Advantage Server" con probabilidad${\displaystyle p}$y a "Advantage Receiver" con probabilidad${\displaystyle q}$Los estados "Servidor de juego" y "Receptor de juego" actúan como estados absorbentes; una vez alcanzados, el juego termina y la cadena permanece en ese estado con probabilidad 1. Este modelo puede utilizarse para calcular la probabilidad exacta de que un jugador gane una partida a partir de cualquier puntuación intermedia.

Las cadenas de Markov se utilizan con frecuencia en la generación algorítmica de música para crear nuevas melodías que imiten el estilo de un compositor, género o corpus de entrenamiento específico.

El espacio de estados se compone de tonos musicales, acordes o valores rítmicos. Mediante el análisis computacional de un conjunto de datos musicales existentes (por ejemplo, las melodías de Johann Sebastian Bach), se construye una matriz de transición que determina la probabilidad de que una nota específica siga a la nota actual. Si el estado actual es una negra de do, la matriz proporciona las probabilidades calculadas de que el siguiente estado sea una corchea de mi, una negra de sol, y así sucesivamente.

Debido a que la elección de la siguiente nota depende únicamente de la nota actual, el proceso de generación es un paseo aleatorio a través de la matriz de transición. Las cadenas de Markov de orden superior también se utilizan comúnmente en este campo, donde el siguiente estado depende de una secuencia de los anteriores.${\displaystyle k}$notas, logradas al redefinir el espacio de estados para que consista en tuplas de secuencia de longitud${\displaystyle k}$.

El proceso de Poisson es uno de los ejemplos más simples y fundamentales de una cadena de Markov de tiempo continuo. Modela una secuencia de eventos que ocurren aleatoriamente en el tiempo, como la desintegración radiactiva, la llegada de correos electrónicos a una bandeja de entrada o los clics en un sitio web. Si${\displaystyle X_{t}}$representa el número total de eventos que han ocurrido hasta el momento${\displaystyle t}$El proceso tiene un espacio de estados de enteros no negativos.${\displaystyle \{0,1,2,\dots \}}$. La cadena solo se mueve hacia arriba (un proceso de "nacimiento puro"), pasando del estado${\displaystyle i}$a${\displaystyle i+1}$a una velocidad constante${\displaystyle \lambda }$El tiempo transcurrido en cada estado es una variable aleatoria independiente con distribución exponencial y parámetro${\displaystyle \lambda }$.

Si se hacen cien palomitas de maíz en un horno, y cada palomita explota en un tiempo independiente con distribución exponencial , entonces esto sería un proceso de Markov de tiempo continuo .${\displaystyle X_{t}}$denota el número de núcleos que han aparecido hasta el momento${\displaystyle t}$El problema se puede definir como encontrar el número de núcleos que explotarán en algún momento posterior. Lo único que se necesita saber es el número de núcleos que han explotado antes de ese momento.${\displaystyle t}$No es necesario saber cuándo surgieron, por lo que conocer la secuencia histórica exacta de${\displaystyle X_{t}}$Los datos de épocas pasadas no son relevantes para predecir el futuro.

Matemáticamente, se trata de un proceso de nacimiento puro con un espacio de estados finito.${\displaystyle \{0,1,\dots ,100\}}$A diferencia del proceso de Poisson estándar, la tasa de aparición de elementos cambia dependiendo del estado actual. Si${\displaystyle i}$Los núcleos ya han explotado, hay${\displaystyle 100-i}$granos sin explotar restantes. Si cada grano explota a una velocidad${\displaystyle \lambda }$, la tasa de transición general del estado${\displaystyle i}$para declarar${\displaystyle i+1}$es${\displaystyle (100-i)\lambda }$.

Una de las cadenas de Markov de tiempo continuo más prácticas es el modelo de dos estados, que se utiliza a menudo en ingeniería de confiabilidad para modelar una máquina que alterna entre estar operativa y estar averiada. El espacio de estados es${\displaystyle \{0,1\}}$donde 0 representa "funcionando" y 1 representa "fallido".

• Cuando la máquina está funcionando, falla después de un tiempo distribuido exponencialmente con una tasa de falla.${\displaystyle \lambda }$.
• Cuando la máquina falla, se necesita un tiempo distribuido exponencialmente para repararla con una tasa de reparación${\displaystyle \mu }$.

Este sistema carece por completo de memoria: la probabilidad de que la máquina se averíe en el próximo minuto depende únicamente del hecho de que esté funcionando en ese momento, no del tiempo que haya transcurrido desde su última reparación. La matriz de tasas de transición (o matriz generadora)${\displaystyle Q}$para este sistema es:

${\displaystyle Q={\begin{pmatrix}-\lambda &\lambda \\\mu &-\mu \end{pmatrix}}}$

Un ejemplo clásico de un proceso de nacimiento y muerte es la cola M/M/1, que modela un único servidor que atiende a una fila de clientes, como un cajero en un supermercado o un enrutador que procesa paquetes de datos.

• Nacimientos (Llegadas): Los clientes llegan según un proceso de Poisson con tasa${\displaystyle \lambda }$. Esto aumenta el estado (número de personas en el sistema) de${\displaystyle i}$a${\displaystyle i+1}$.
• Muertes (Salidas): El servidor procesa a los clientes uno a la vez. Los tiempos de servicio se distribuyen exponencialmente con una tasa${\displaystyle \mu }$. Un servicio terminado disminuye el estado de${\displaystyle i}$a${\displaystyle i-1}$(para${\displaystyle i>0}$).

El espacio de estados es el conjunto de enteros no negativos.${\displaystyle \{0,1,2,\dots \}}$representa el número de clientes en el sistema. Dado que tanto los tiempos de llegada como los de servicio siguen una distribución exponencial, el estado futuro del sistema depende únicamente del número actual de clientes en la cola, lo que lo califica como una cadena de Markov de tiempo continuo.

Las cadenas de Markov de tiempo continuo se utilizan ampliamente para modelar la propagación de enfermedades infecciosas. Un ejemplo clásico es el modelo estocástico SIS (Susceptible-Infectado-Susceptible), que rastrea el número de individuos infectados en una población fija y completamente mezclada de tamaño${\displaystyle N}$El espacio de estados es${\displaystyle \{0,1,\dots ,N\}}$, que representa el número actual de personas infectadas,${\displaystyle I}$.

• Infección: Un individuo susceptible entra en contacto con un individuo infectado y contrae la enfermedad. La tasa de transición del estado${\displaystyle I}$a${\displaystyle I+1}$es proporcional al número de individuos infectados y al número de individuos susceptibles:${\displaystyle \beta I(N-I)}$, dónde${\displaystyle \beta }$es la tasa de transmisión.
• Recuperación: Un individuo infectado se recupera e inmediatamente vuelve a ser susceptible. La tasa de transición del estado${\displaystyle I}$a${\displaystyle I-1}$es${\displaystyle \gamma I}$, dónde${\displaystyle \gamma }$es la tasa de recuperación.

Dado que las tasas de infección y recuperación dependen exclusivamente del número actual de personas infectadas en un momento dado, se cumple la propiedad de ausencia de memoria. Cabe destacar que el estado 0 es un estado absorbente : una vez que la infección desaparece por completo, no puede reaparecer.

En genética, el modelo de Moran describe la evolución estocástica de dos alelos en competencia (por ejemplo, el alelo A y el alelo B) en una población de tamaño estrictamente fijo.${\displaystyle N}$. El estado de la cadena de Markov es el número de individuos portadores del alelo A, que puede variar desde${\displaystyle 0}$a${\displaystyle N}$.

En tiempo continuo, los eventos de reproducción ocurren a una tasa constante. Cuando ocurre un evento:

• Se elige un individuo al azar para reproducirse (creando una copia de su alelo).
• Se elige a un individuo al azar para que muera (dejando espacio para que la nueva copia mantenga el tamaño de la población).

Las tasas de transición del estado${\displaystyle i}$(donde hay${\displaystyle i}$individuos con alelo A y${\displaystyle N-i}$con el alelo B) a${\displaystyle i+1}$o${\displaystyle i-1}$dependen únicamente de las proporciones actuales de los alelos en la población. Tanto el estado 0 (el alelo A se pierde permanentemente) como el estado${\displaystyle N}$(el alelo A está fijado permanentemente) actúan como límites absorbentes.

En química física y biología de sistemas, las interacciones de las moléculas en un volumen microscópico bien mezclado se modelan como una cadena de Markov de tiempo continuo. El estado del sistema es un vector que representa la cantidad exacta de cada tipo de molécula presente.

Las reacciones se tratan como saltos aleatorios entre estos estados discretos. Por ejemplo, una reacción en la que la molécula A y la molécula B chocan para formar la molécula C (${\displaystyle A+B\to C}$La transición ocurre a una velocidad proporcional al número de moléculas A multiplicado por el número de moléculas B. La propiedad de ausencia de memoria se mantiene porque la probabilidad de que una colisión dé lugar a una reacción exitosa en el siguiente intervalo de tiempo infinitesimalmente pequeño depende únicamente de la concentración instantánea de los reactivos, no del tiempo que hayan estado rebotando en el recipiente.