Introducción a las cadenas de Markov

Las cadenas de Markov son una forma bastante común, y relativamente sencilla, de modelar estadísticamente procesos aleatorios. Se han utilizado en muchos ámbitos diferentes, desde la generación de textos hasta la modelización financiera. Un ejemplo popular es r/SubredditSimulator, que utiliza cadenas de Markov para automatizar la creación de contenido para todo un subreddit. En general, las cadenas de Markov son conceptualmente bastante intuitivas, y son muy accesibles en el sentido de que pueden implementarse sin el uso de ningún concepto estadístico o matemático avanzado. Son una gran manera de empezar a aprender sobre el modelado probabilístico y las técnicas de ciencia de datos.

Escenario

Para empezar, las describiré con un ejemplo muy común:

Imagine that there were two possible states for weather: sunny or cloudy. You can always directly observe the current weather state, and it is guaranteed to always be one of the two aforementioned states.Now, you decide you want to be able to predict what the weather will be like tomorrow. Intuitively, you assume that there is an inherent transition in this process, in that the current weather has some bearing on what the next day's weather will be. So, being the dedicated person that you are, you collect weather data over several years, and calculate that the chance of a sunny day occurring after a cloudy day is 0.25. You also note that, by extension, the chance of a cloudy day occurring after a cloudy day must be 0.75, since there are only two possible states.You can now use this distribution to predict weather for days to come, based on what the current weather state is at the time.

Este ejemplo ilustra muchos de los conceptos clave de una cadena de Markov. Una cadena de Markov consiste esencialmente en un conjunto de transiciones, que están determinadas por alguna distribución de probabilidad, que satisfacen la propiedad de Markov.

Observe cómo en el ejemplo, la distribución de probabilidad se obtiene únicamente observando las transiciones del día actual al siguiente. Esto ilustra la propiedad de Markov, la característica única de los procesos de Markov que los hace sin memoria. Por ello, suelen ser incapaces de producir con éxito secuencias en las que se espera que se produzca alguna tendencia subyacente. Por ejemplo, aunque una cadena de Markov pueda imitar el estilo de escritura de un autor basándose en las frecuencias de las palabras, sería incapaz de producir un texto que contenga un significado profundo o una significación temática, ya que éstos se desarrollan en secuencias de texto mucho más largas. Por lo tanto, carecen de la capacidad de producir contenido dependiente del contexto, ya que no pueden tener en cuenta la cadena completa de estados previos.

El modelo

Formalmente, una cadena de Markov es un autómata probabilístico. La distribución de probabilidad de las transiciones de estado se representa típicamente como la matriz de transición de la cadena de Markov. Si la cadena de Markov tiene N estados posibles, la matriz será una matriz N x N, tal que la entrada (I, J) es la probabilidad de transición del estado I al estado J. Además, la matriz de transición debe ser una matriz estocástica, una matriz cuyas entradas en cada fila deben sumar exactamente 1. Esto tiene pleno sentido, ya que cada fila representa su propia distribución de probabilidad.

Además, una cadena de Markov también tiene un vector de estado inicial, representado como una matriz N x 1 (un vector), que describe la distribución de probabilidad de comenzar en cada uno de los N estados posibles. La entrada I del vector describe la probabilidad de que la cadena comience en el estado I.

Estas dos entidades son típicamente todo lo que se necesita para representar una cadena de Markov.

Ahora sabemos cómo obtener la probabilidad de transición de un estado a otro, pero ¿qué tal si encontramos la probabilidad de que esa transición ocurra en múltiples pasos? Para formalizar esto, ahora queremos determinar la probabilidad de pasar del estado I al estado J a lo largo de M pasos. Resulta que esto es muy sencillo de averiguar. Dada una matriz de transición P, se puede determinar calculando el valor de la entrada (I, J) de la matriz que se obtiene elevando P a la potencia de M. Para valores pequeños de M, esto se puede hacer fácilmente a mano con multiplicaciones repetidas. Sin embargo, para valores grandes de M, si está familiarizado con el Álgebra Lineal simple, una forma más eficiente de elevar una matriz a una potencia es primero diagonalizar la matriz.

Conclusión

Ahora que conoce los fundamentos de las cadenas de Markov, debería ser capaz de implementarlas fácilmente en un lenguaje de su elección. Si la codificación no es tu fuerte, también hay muchas propiedades más avanzadas de las cadenas de Markov y los procesos de Markov en las que puedes sumergirte. En mi opinión, la progresión natural en la ruta de la teoría sería hacia los procesos de Markov ocultos o MCMC. Las cadenas de Markov simples son los bloques de construcción de otras técnicas de modelado más sofisticadas, así que con este conocimiento, ahora puede pasar a varias técnicas dentro de temas como el modelado de creencias y el muestreo.