Cadenas de Markov

Introducción #

La respuesta a preguntas aparentemente diversas como cuántas veces hay que barajar una baraja para que sea verdaderamente aleatoria, cuánto uranio se necesita para una bomba nuclear, cómo se predice la siguiente palabra en una frase o cómo Google sabe qué página buscas, se encuentra en una peculiar y acalorada disputa matemática que tuvo lugar en Rusia hace más de 100 años. En 1905, el levantamiento de grupos socialistas contra el Zar dividió profundamente a la nación, y esta división social y política se extendió incluso al ámbito académico, afectando a los matemáticos.

En un lado de la contienda intelectual, defendiendo al Zar y el status quo, se encontraba Pavel Nekrasov, conocido extraoficialmente como el “Zar de la Probabilidad”. Nekrasov era un hombre profundamente religioso y poderoso que usaba su posición para argumentar que las matemáticas podían ser utilizadas para explicar el libre albedrío y la voluntad de Dios. En el lado opuesto, con una postura socialista, estaba su némesis intelectual, Andrey Markov, también conocido como “Andrey el Furioso”. Markov, un ateo, no toleraba lo que consideraba una falta de rigor, especialmente cuando se vinculaba la matemática con el libre albedrío o la religión. Él criticó públicamente el trabajo de Nekrasov, incluyéndolo entre los “abusos de las matemáticas”.

La Ley de los grandes números y la independencia #

La disputa central entre Markov y Nekrasov giraba en torno a la Ley de los Grandes Números, una idea fundamental que había dominado la probabilidad durante 200 años. Esta ley, probada por primera vez por Jacob Bernoulli en 1713, establece que el comportamiento promedio de un resultado se acerca cada vez más a su valor esperado a medida que se realizan más y más pruebas independientes. Por ejemplo, al lanzar una moneda un gran número de veces, la proporción de caras y cruces tiende a estabilizarse alrededor del 50/50.

Bernoulli, sin embargo, había probado que esta ley solo funcionaba para eventos independientes, como el lanzamiento de una moneda justa, donde un evento no influye en los demás. Nekrasov aceptaba esta condición, pero la llevó un paso más allá: argumentó que si se observaba la Ley de los Grandes Números en un conjunto de datos, se podía inferir que los eventos subyacentes debían ser independientes. Nekrasov observó esta pauta en estadísticas sociales como las tasas de matrimonio, delincuencia y natalidad en Bélgica entre 1841 y 1845; vio que los promedios anuales de matrimonios convergían alrededor de 29.000. Razonó que, dado que estas estadísticas seguían la Ley de los Grandes Números, las decisiones individuales que las causaban (casarse, cometer crímenes, tener hijos) debían ser actos independientes de libre albedrío. Para Nekrasov, el libre albedrío no era solo filosófico, sino algo medible y científico.

Para Markov, la postura de Nekrasov era “delirante” y absurda por vincular la independencia matemática con el libre albedrío. Markov se propuso refutarlo, buscando demostrar que los eventos dependientes también podían seguir la Ley de los Grandes Números, y que era perfectamente posible hacer cálculos de probabilidad con ellos.

Poemas y cadenas #

Para llevar a cabo su demostración, Markov necesitaba un sistema donde un evento claramente dependiera de lo que había ocurrido antes. Tuvo la idea de que esto sucede en el texto: la probabilidad de que la siguiente letra sea una consonante o una vocal depende en gran medida de la letra actual. Para probar esto, Markov se basó en el poema “Eugenio Oneguin” de Alexander Pushkin, una obra central de la literatura rusa.

Tomó los primeros 20.000 caracteres del poema, eliminó la puntuación y los espacios, y los unió en una larga cadena. Contó que el 43% de los caracteres eran vocales y el 57% consonantes. Luego, dividió la cadena en pares de letras superpuestas para analizar las combinaciones: vocal-vocal, consonante-consonante, vocal-consonante y consonante-vocal. Si las letras fueran independientes, la probabilidad de un par vocal-vocal sería el producto de la probabilidad de una vocal consigo misma (aproximadamente $0.43 \times 0.43 = 0.18$, o un 18%). Sin embargo, Markov encontró que los pares vocal-vocal solo aparecían el 6% de las veces, lo que era significativamente menor que la predicción de independencia. Las frecuencias de todos los demás pares también diferían notablemente de lo que se esperaría si fueran independientes, confirmando que las letras eran dependientes.

Con la dependencia demostrada, el siguiente paso de Markov era mostrar que estas letras aún seguían la Ley de los Grandes Números. Para ello, creó una especie de “máquina de predicción”. Dibujó dos círculos, uno para “vocal” y otro para “consonante”, que representaban sus estados. Luego calculó las probabilidades de transición entre estos estados. Sabiendo que los pares vocal-vocal ocurrían el 6% de las veces y las vocales el 43%, calculó la probabilidad de ir de una vocal a otra vocal como la razón entre ambos:

$$ P(\text{vocal} \to \text{vocal}) = \frac{P(\text{vocal-vocal})}{P(\text{vocal})} = \frac{0.06}{0.43} \approx 0.13 $$

Esto significaba una probabilidad del 13% de transición de vocal a vocal. Como la suma de las probabilidades de todas las transiciones desde un estado dado debe ser 1 (100%), la probabilidad de ir de una vocal a una consonante era $1 - 0.13 = 0.87$ (87%). Repitió el proceso para las consonantes, completando su máquina predictiva.

Simulando secuencias de letras con esta máquina, generando números aleatorios para decidir la siguiente transición, Markov observó que, aunque la proporción de vocales a consonantes fluctuaba al principio, con el tiempo convergía a los valores exactos que había contado a mano en el poema: 43% vocales y 57% consonantes. Así, Markov construyó un sistema dependiente, una “cadena literal de eventos”, y demostró que aún así seguía la Ley de los Grandes Números. Esto significaba que la convergencia observada en las estadísticas sociales no probaba la independencia de las decisiones subyacentes, y por lo tanto, no probaba el libre albedrío. Markov sabía que había destrozado el argumento de Nekrasov, y culminó su trabajo con una última burla: “Así, el libre albedrío no es necesario para hacer probabilidad”. De hecho, ni siquiera la independencia es necesaria para hacer probabilidad.

Esta nueva forma de teoría de la probabilidad, que permitía modelar eventos dependientes, pasó a conocerse como la Cadena de Markov. Aunque era un avance significativo —ya que en el mundo real casi todo depende de algo más, como el clima de mañana del de hoy, o la propagación de una enfermedad de quién está infectado— Markov mismo no le dio mucha importancia a sus aplicaciones prácticas, declarando estar “preocupado solo con cuestiones de puro análisis”.

Aplicaciones en cadena #

La aparente indiferencia de Markov sobre la aplicabilidad de su teoría contrastaría drásticamente con el papel fundamental que las Cadenas de Markov jugarían en desarrollos cruciales del siglo XX.

1. El Método Monte Carlo y la Simulación de Bombas Nucleares En 1945, se detonó la primera bomba nuclear. Incluso después de la guerra, el matemático Stanislaw Ulam, parte del Proyecto Manhattan, continuó investigando el comportamiento de los neutrones dentro de una bomba. Una bomba nuclear funciona mediante una reacción en cadena: un neutrón golpea un núcleo de uranio-235, este se divide liberando energía y dos o tres neutrones más. Si, en promedio, estos nuevos neutrones logran golpear y dividir más de un núcleo, se produce una reacción en cadena descontrolada, es decir, una bomba. Una pregunta clave era la cantidad mínima de uranio-235 necesaria, lo que requería comprender el comportamiento de los neutrones.

En enero de 1946, Ulam fue afectado por una encefalitis casi fatal. Durante su larga recuperación, pasaba el tiempo jugando al solitario. La pregunta de cuáles eran las probabilidades de ganar una partida aleatoriamente barajada de solitario le obsesionaba. Resolver esto analíticamente era inviable debido al número inmenso de posibles arreglos de las cartas ($52! \approx 8 \times 10^{67}$). Ulam tuvo una revelación: ¿y si simplemente jugaba cientos de partidas y contaba cuántas ganaba para obtener una aproximación estadística?.

Al regresar a Los Álamos, Ulam aplicó esta idea a la simulación de neutrones en un núcleo nuclear, donde trillones de neutrones interactúan y el número de posibles resultados es inmenso. Su colega John von Neumann reconoció el poder de la idea, pero notó una diferencia crucial: a diferencia del solitario, donde cada juego es independiente, el comportamiento de un neutrón depende de su ubicación y de lo que ha hecho antes. Por lo tanto, no se podían simplemente tomar muestras aleatorias, sino que se necesitaba modelar una cadena completa de eventos donde cada paso influyera en el siguiente.

Von Neumann se dio cuenta de que lo que necesitaban era una Cadena de Markov. Crearon un modelo simplificado donde el estado inicial es un neutrón viajando por el núcleo. Tres cosas podían suceder: dispersarse (permanecer en el mismo estado), salir del sistema o ser absorbido (terminar la cadena), o golpear otro átomo de uranio-235, causando fisión y liberando más neutrones que iniciarían sus propias cadenas. Las probabilidades de transición no eran fijas, sino que dependían de factores como la posición, velocidad y energía del neutrón, así como la configuración y masa del uranio.

Esta cadena se simuló en el ENIAC, la primera computadora electrónica. La computadora generaba condiciones iniciales aleatorias para un neutrón y seguía la cadena, registrando el factor de multiplicación k, que es el número promedio de neutrones producidos por cada neutrón. Si $k < 1$, la reacción se extingue; si $k = 1$, es autosostenible; y si $k > 1$, la reacción crece exponencialmente y se tiene una bomba. Repitiendo este proceso cientos de veces, obtuvieron una distribución estadística de los resultados, lo que les permitió aproximar ecuaciones diferenciales que eran demasiado difíciles de resolver analíticamente. Ulam, recordando a su tío jugador, nombró el método “Monte Carlo” en honor al famoso casino de Mónaco. El método fue tan exitoso que se extendió rápidamente.

2. Google PageRank y la Búsqueda en Internet En 1993, el acceso público a Internet provocó una explosión de información, con miles de páginas nuevas apareciendo cada día. Encontrar algo en este “mar en expansión de información” se convirtió en un problema. Los primeros motores de búsqueda, como Yahoo (fundado en 1994), clasificaban las páginas simplemente por la frecuencia con la que un término de búsqueda aparecía en ellas. Esto era fácilmente manipulable por sitios web que repetían palabras clave cientos de veces, a menudo ocultas con texto blanco sobre un fondo blanco, lo que significaba que la noción de “calidad” de los resultados era inexistente.

Sergey Brin y Larry Page, también estudiantes de doctorado en Stanford, abordaron este problema. Su idea se inspiró en las bibliotecas: un libro con muchas fechas de préstamo estampadas en su tarjeta (lo que indicaba que había sido sacado muchas veces) se percibía como un buen libro. Brin y Page aplicaron esta idea a la web: cada enlace a una página podía considerarse un “aval”. Además, la importancia de un aval dependía de la “calidad” de la página que lo emitía, y cuantos más enlaces enviaba una página, menos valioso se volvía cada “voto”.

Se dieron cuenta de que podían modelar la web como una Cadena de Markov. Las páginas web eran los estados (por ejemplo, Amy, Ben, Chris, Dan), y los enlaces entre ellas eran las transiciones. La probabilidad de transición de una página a otra dependía de cómo se distribuían los enlaces. Por ejemplo, si la página Amy solo enlazaba a Ben, la probabilidad de ir de Amy a Ben era del 100%. Si Ben enlazaba a Amy, Chris y Dan, la probabilidad de ir a cualquiera de ellos desde Ben era del 33%.

Al simular un “surfista” aleatorio que se movía por esta web de juguete, se hacía un seguimiento del porcentaje de tiempo que el surfista pasaba en cada página. Con el tiempo, esta proporción se estabilizaba, y las puntuaciones resultantes daban una medida de la importancia relativa de estas páginas. Este sistema era más robusto contra la manipulación: crear muchas páginas de baja calidad que enlazaran a tu sitio no funcionaba, ya que los enlaces de estas páginas no eran “enlaces de calidad” y no afectaban significativamente el algoritmo.

Sin embargo, existía un problema: no todas las páginas están conectadas, y un “surfista aleatorio” podría quedar atrapado en un bucle, sin alcanzar el resto de la web. Para solucionar esto, Brin y Page introdujeron un factor de amortiguación: el 85% de las veces, el surfista seguía un enlace normal, pero el 15% de las veces, saltaba a una página completamente al azar. Este factor de amortiguación garantizaba que se exploraran todas las partes posibles de la web sin quedarse atascado. Utilizando Cadenas de Markov, Page y Brin construyeron un motor de búsqueda superior, al que llamaron PageRank. En 1998, lanzaron su nuevo motor de búsqueda, inicialmente llamado BackRub, y luego renombrado Google (por el término “googol”, $10^{100}$, simbolizando su ambición de indexar todas las páginas de Internet). Google rápidamente superó a Yahoo y se convirtió en el motor de búsqueda más utilizado. Hoy en día, una Cadena de Markov sigue siendo el corazón de su algoritmo de billones de dólares.

3. Modelos de Lenguaje Grandes (LLMs) y Predicción de Texto La idea original de Markov de predecir texto fue retomada en la década de 1940 por Claude Shannon, el padre de la teoría de la información. Shannon fue más allá de vocales y consonantes, centrándose en letras individuales y luego en palabras completas. Se preguntó qué pasaría si, en lugar de mirar solo la última letra o palabra, se consideraran las dos o más palabras anteriores como predictores. Descubrió que al tomar en cuenta cada vez más palabras previas, se podían hacer mejores y mejores predicciones sobre cuál sería la siguiente palabra.

Esta es precisamente la base de cómo funcionan los sistemas de predicción de texto modernos, como el autocompletado de Gmail, y los algoritmos de los modelos de lenguaje grandes (LLMs) actuales. Aunque los LLMs no usan estrictamente letras individuales sino “tokens” (que pueden ser letras, palabras, marcas de puntuación, etc.), la pregunta fundamental sigue siendo: “¿Cuáles son las probabilidades de que el siguiente token sea este, o este, o este?”. Sin embargo, los LLMs actuales superan a las Cadenas de Markov simples al utilizar un mecanismo llamado “atención”, que les permite ponderar la importancia de diferentes tokens en el contexto previo para afinar sus predicciones (por ejemplo, distinguiendo “celda” en un contexto biológico de “celda” de prisión).

Contextos limitados #

A pesar de su versatilidad, las Cadenas de Markov no son adecuadas para modelar todos los sistemas dependientes. En particular, los sistemas con bucles de retroalimentación positiva —donde un cambio inicial se amplifica a sí mismo, como el calentamiento global (el aumento de CO2 eleva la temperatura, que a su vez aumenta el vapor de agua, un potente gas de efecto invernadero, elevando aún más la temperatura)— son difíciles de predecir con Cadenas de Markov. En estos casos, el estado futuro no depende solo del estado actual, sino de la acumulación de efectos pasados.

Una preocupación actual con los LLMs es precisamente esta: si el texto generado por los modelos termina en Internet y se utiliza como datos de entrenamiento para futuros modelos, podría conducir a un “estado muy aburrido y estable”, donde el sistema solo “dice lo mismo una y otra vez para siempre”. Estos sistemas con bucles de retroalimentación se vuelven difíciles de modelar con Cadenas de Markov.

Sin embargo, para muchos otros sistemas dependientes, las Cadenas de Markov siguen siendo una herramienta increíblemente poderosa para la probabilidad. Su gran fortaleza radica en una propiedad clave: son “sin memoria” o “memoryless”. Aunque la historia de un sistema puede ser extremadamente larga (como todas las letras en un texto, todas las interacciones de un neutrón o el clima durante semanas), la propiedad sin memoria de las Cadenas de Markov permite ignorar casi todo ese historial y solo mirar el estado actual para hacer predicciones significativas. Es esta capacidad de simplificación la que permite tomar sistemas extremadamente complejos y reducirlos significativamente para hacer predicciones útiles. Como un artículo lo resume: “La resolución de problemas es a menudo una cuestión de idear una Cadena de Markov apropiada”.

Esta simplificación también explica por qué se sabe que siete barajados de riffle son suficientes para que una baraja de 52 cartas esté “completamente aleatoria”. El barajado de cartas puede verse como una Cadena de Markov donde cada arreglo de la baraja es un estado, y cada barajado es un paso. Después de siete barajados, cada arreglo posible de la baraja es aproximadamente igualmente probable, lo que significa que la baraja está “básicamente aleatoria”.

Es irónico y fascinante que un concepto matemático tan fundamental y con aplicaciones tan vastas y modernas haya surgido de una disputa tan personal. La determinación de Markov para refutar a Nekrasov fue, al final, lo que le llevó a desarrollar un trabajo que transformaría la probabilidad y muchos campos de la ciencia y la tecnología.