Ejemplo de cadena de Markov y aplicaciones

¿Qué es la Cadena de Markov?

Theresa diseña la apariencia del menú mensual para la cafetería de una escuela. Se da cuenta de que hay tendencias entre el plato principal de un día y el plato principal del día anterior. Por ejemplo, es más probable que los nuggets de pollo sean seguidos por carne, pero los espaguetis nunca vienen después de los palitos de pescado. Por lo general, Theresa debe esperar a que llegue el horario del servicio de catering antes de poder comenzar a diseñar el menú del mes. Sin embargo, después de ver que hay tendencias entre las opciones de almuerzo, Theresa se pregunta si podría crear un algoritmo para predecir futuros menús mensuales.

Theresa debería considerar usar una cadena de Markov. Desarrollado por Andrei Andreevich Markov, una cadena de Markov es un modelo que simula los resultados de múltiples eventos en una serie. Las cadenas de Markov dependen de probabilidades conocidas entre estados. Un estado es cualquier resultado potencial de un evento, y la probabilidad de que un estado pase a otro estado se basa en el conocimiento previo. Por ejemplo, Theresa necesitaría incluir menús anteriores en su modelo para generar la probabilidad de que una opción de menú lleve a otra. Sin este conocimiento previo, su modelo no sabría que la transición de nuggets de pollo a pastel de carne es más probable que la transición de nuggets de pollo a espaguetis.

Si bien las cadenas de Markov pueden ser herramientas de modelado útiles, tienen limitaciones. Por ejemplo, los sistemas que tienen muchos estados potenciales pueden ser demasiado complejos para calcularlos de manera realista. Además, si bien el modelo se basa en conocimientos previos, es posible que no refleje con precisión lo que realmente sucede porque pueden existir estados intermedios u ocultos que carecen de los datos apropiados.

Explicación de la cadena de Markov

Las cadenas de Markov enfatizan la probabilidad de transiciones entre un estado y otro. En una cadena de Markov, el resultado de cada evento depende solo del resultado del evento directamente anterior. En el caso del menú de Theresa, el almuerzo del miércoles dependería del almuerzo del martes, no del lunes. Debido a que solo se enfocan en una transición a la vez, no tienen memoria. Esto significa que no consideran ninguna probabilidad transitoria previa para determinar el resultado de un solo evento.

Tipos de cadena de Markov

Las cadenas de Markov se pueden clasificar de muchas maneras. Dos categorías comunes para clasificar las cadenas de Markov incluyen:

• Cadenas de Markov en tiempo discreto (DTMC)
• Cadenas de Markov de tiempo continuo (CTMC)

Los DTMC consideran que todos los estados dentro de un sistema permanecen dentro de su estado durante una sola unidad de tiempo. En el ejemplo de Theresa, los elementos del menú cambian diariamente. Los DTMC son más fáciles de conceptualizar porque se mueven en un patrón de pasos.

Los CTMC no restringen a los estados a permanecer en su forma actual durante un período de tiempo determinado. Si este fuera el caso del menú escolar, los nuggets de pollo podrían seguir siendo el plato principal durante un tiempo indefinido antes de pasar a otra cosa.

Fórmula de la cadena de Markov

Las cadenas de Markov generan matrices de transición . Estas matrices tienen el mismo número de filas y columnas que representan el número de estados dentro de un sistema. Los valores representan la probabilidad de pasar de un estado de fila dado a un estado de columna. Por ejemplo, las filas en la siguiente matriz representan los estados iniciales de nuggets de pollo, carne, espagueti y palitos de pescado de arriba a abajo y los estados de transición del mismo orden de izquierda a derecha:

{eq}P=\begin{bmatrix} 0 & 0.6 & 0.4 & 0\\ 0.5 & 0 & 0.5 & 0\\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix} {/equ}

En la matriz dada, la probabilidad de pasar de nuggets de pollo a espagueti es 0,4. Los vectores de estado son vectores de probabilidad generados para las cadenas de Markov después de un número dado de pasos ({eq}v_{n} {/eq}). Si la cadena de Markov comienza en un día en el que se sirven nuggets de pollo, entonces el vector de estado inicial ({eq}v_{0} {/eq}) es el siguiente:

{eq}v_{0}=\begin{bmatriz} 1\\ 0\\ 0\\ 0 \end{bmatriz} {/eq}

Usando vectores de estado y la siguiente fórmula, es posible generar la probabilidad de que un sistema se encuentre en un estado dado después de {eq}n {/eq} pasos:

{eq}V_{n}=v_{0}P^{n} {/eq}

En esta fórmula, P representa la matriz de transición. Para 5 pasos, la fórmula aparecería como tal para las 4 opciones de almuerzo:

{eq}V_{5}=\begin{bmatrix} 1\\ 0\\ 0\\ 0 \end{bmatrix} \begin{bmatrix} 0 & 0.6 & 0.4 & 0\\ 0.5 & 0 & 0.5 & 0\ \ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatriz}^{5} {/eq}

Aplicaciones de la cadena de Markov

El uso de una Cadena de Markov es beneficioso para múltiples campos de estudio. Por ejemplo, las cadenas de Markov tienen aplicaciones importantes en:

• Ciencias
• Teoría de la información
• Teoría de colas
• Estadísticas
• Deportes y Música

A continuación, estos ejemplos se explican con más detalle para ilustrar cómo las cadenas de Markov son herramientas de modelado interdisciplinario.

Cadena de Markov en la ciencia

Las cadenas de Markov tienen un papel particularmente importante en las ciencias físicas. En biología, las cadenas de Markov se utilizan a menudo para representar los ciclos de vida dentro de un ecosistema. Por ejemplo, en cualquier estado dado, un animal tiene la probabilidad de envejecer un año más o morir. Al comprender estas probabilidades, los biólogos pueden predecir tendencias en las fluctuaciones de la población a lo largo del tiempo.

En química, las cadenas de Markov se pueden usar para predecir el estado de una reacción en un paso particular. Los CTMC son especialmente útiles en los campos de la química, ya que la cantidad de tiempo que los reactivos permanecen en un estado dado puede no ser siempre constante. En física, las cadenas de Markov se utilizan para predecir la serie de eventos dentro de un sistema de acuerdo con las leyes de la termodinámica.

Cadena de Markov en la teoría de la información

La teoría de la información está interesada en cómo se transmiten los mensajes entre las partes. Shannon Claude descubrió que los patrones en el lenguaje a menudo siguen cadenas de Markov, donde la probabilidad de aparición de una letra depende de la letra que le precede. Usando una cadena de Markov simple y letras aleatorias, Claude pudo producir cadenas de letras que se parecían más a palabras y frases en inglés.

Cadena de Markov en la teoría de colas

La teoría de colas investiga patrones en los procesos de colas. Por ejemplo, ¿cómo se podría mover a un paciente del vestíbulo a una sala de examen, a una farmacia y, finalmente, a un mostrador de pago mientras se reduce la cantidad de tiempo de espera y se mantiene un alto nivel de satisfacción del paciente? La teoría de colas emplea cadenas de Markov para proporcionar probabilidades de la cantidad de clientes que se encuentran dentro de una cola para determinar las áreas que carecen de eficiencia.

Cadena de Markov en Estadísticas

Debido a que las cadenas de Markov se ocupan de las probabilidades, brindan información importante en estadística. Las cadenas de Markov son herramientas comunes en las estadísticas bayesianas, donde los resultados se representan en probabilidades y verosimilitudes en lugar del valor p que se usa a menudo en las estadísticas frecuentistas.

Cadena de Markov en Deportes y Música

En los deportes, las cadenas de Markov se pueden usar para hacer predicciones sobre el resultado de un juego dado un puntaje actual. Si un juego se juega a 20 puntos y un jugador tiene 15 puntos mientras que otro jugador tiene 6, aún existe la posibilidad de que cualquiera de los dos gane, ya que ninguno ha adquirido 20 puntos. Sin embargo, según el puntaje, una cadena de Markov puede producir una probabilidad de que un jugador gane a otro.

Las computadoras han podido generar música utilizando cadenas de Markov. Una canción se puede dar a una computadora como conocimiento previo. La progresión de acordes, el tono y los tiempos se utilizan para predecir las probabilidades de pasar de un estado (por ejemplo, un acorde «A») a otro (como un acorde «B»). Basándose en la pieza musical original, las cadenas de Markov pueden simular otra pieza musical con un sonido similar.

Ejemplos de cadenas de Markov

Hay varios ejemplos comunes de cadenas de Markov que se utilizan para representar cómo funcionan estos modelos. Dos de los ejemplos más utilizados son las predicciones meteorológicas y los juegos de mesa. A continuación, estos ejemplos se exploran con más detalle para ilustrar su aplicación.

Predecir el clima

Los modelos de predicción meteorológica son ejemplos simples de cómo funcionan las cadenas de Markov. Considere que el clima de un día depende del clima anterior. Si el clima es soleado, la probabilidad de tener un clima soleado al día siguiente es 0.7 y 0.3 para un clima lluvioso. Se puede construir una cadena de Markov para predecir la probabilidad de clima en un número determinado de días en el futuro dado el clima actual.

Juegos de mesa

Los juegos de mesa son otro ejemplo del mundo real de una cadena de Markov. Considere el juego Monopoly. En el juego, el espacio en el que aterrizas depende del espacio en el que te encuentres. Un jugador se mueve tirando dos dados. La probabilidad de sacar un 12 es baja, ya que el jugador debe sacar 2 seises. Sin embargo, la probabilidad de sacar un 6 es mucho mayor, ya que un jugador puede sacar un 4 y un 2, un 3 doble, un 5 y un 1, etc. Así, la probabilidad de aterrizar en un espacio depende del punto de partida original.

Resumen de la lección

Una cadena de Markov es una herramienta de modelado que se utiliza para predecir el estado (o estado o condición actual) de un sistema dado un estado inicial. En una cadena de Markov, el resultado de un estado depende del estado anterior. Sin embargo, los estados no dependen de estados anteriores al estado inmediatamente anterior. La probabilidad de que un estado haga la transición a otro estado se deriva del conocimiento previo y se puede utilizar para generar matrices de transición.. En una matriz de transición, las filas indican el estado inicial y las columnas indican el estado de transición. El valor compartido por una fila en una columna es la probabilidad de que el estado de esa fila cambie al estado de esa columna. La probabilidad de un estado en un número conocido de pasos en el futuro se puede determinar usando la siguiente ecuación, donde {eq}v_{n} {/eq} es el vector de estado (probabilidades de cualquier estado dado) en n pasos en el futuro, P es la matriz de probabilidad generada y {eq}v_{0} {/eq} es el estado original:

{eq}V_{n}=v_{0}P^{n} {/eq}

Las cadenas de Markov pueden ser cadenas de Markov de tiempo discreto (DTMC) cuando cada paso está restringido a una unidad de tiempo específica. Cuando los pasos no están restringidos a una unidad de tiempo dada o igual entre transiciones, las cadenas de Markov se consideran cadenas de Markov de tiempo continuo (CTMC) .

Rodrigo Ricardo Editor y fundador