Cadenas de Markov y tiempos de mezcla

Markov Chains and Mixing Times es un libro sobre tiempos de mezcla de cadenas de Markov . La segunda edición fue escrita por David A. Levin y Yuval Peres . Elizabeth Wilmer fue coautora de la primera edición y figura como colaboradora en la segunda. La primera edición fue publicada en 2009 por la American Mathematical Society , ^{[ 1 ] [ 2 ]} con una segunda edición ampliada en 2017. ^{[ 3 ] [ 4 ] [ 5 ] [ 6 ]}

Una cadena de Markov es un proceso estocástico definido por un conjunto de estados y, para cada estado, una distribución de probabilidad sobre los estados. Partiendo de un estado inicial, sigue una secuencia de estados donde cada estado en la secuencia se elige aleatoriamente de la distribución asociada al estado anterior. En ese sentido, es "sin memoria": cada elección aleatoria depende solo del estado actual, y no del historial de estados pasados. Bajo ciertas restricciones, una cadena de Markov con un conjunto finito de estados tendrá una distribución estacionaria a la que converge, lo que significa que, después de un número suficientemente grande de pasos, la probabilidad de estar en cada estado se aproximará a la de la distribución estacionaria, independientemente del estado inicial o del número exacto de pasos. El tiempo de mezcla de una cadena de Markov es el número de pasos necesarios para que se produzca esta convergencia, con un grado de precisión adecuado. Se dice que una familia de cadenas de Markov se mezcla rápidamente si el tiempo de mezcla es una función polinómica de algún parámetro de tamaño de la cadena de Markov, y se mezcla lentamente en caso contrario. Este libro trata sobre cadenas de Markov finitas, sus distribuciones estacionarias y tiempos de mezcla, y métodos para determinar si las cadenas de Markov se mezclan rápida o lentamente. ^{[ 1 ] [ 4 ]}

Un ejemplo clásico y familiar de este fenómeno consiste en barajar barajas de cartas: partiendo de una baraja inicial no aleatoria, ¿cuántas barajadas se necesitan para alcanzar una permutación casi aleatoria ? Esto puede modelarse como una cadena de Markov cuyos estados son ordenaciones de la baraja y cuyas probabilidades de transición entre estados vienen dadas por algún modelo matemático de barajado aleatorio, como el modelo de Gilbert-Shannon-Reeds . En esta situación, la rápida mezcla de la cadena de Markov implica que no es necesario realizar un gran número de barajadas para alcanzar un estado suficientemente aleatorio. Más allá de los juegos de cartas, surgen consideraciones similares en el comportamiento de los sistemas físicos estudiados en mecánica estadística y en ciertos algoritmos aleatorios . ^{[ 1 ] [ 4 ]}

El libro se divide en dos partes, la primera más introductoria y la segunda más avanzada. ^{[ 2 ] [ 6 ]} Después de tres capítulos de material introductorio sobre cadenas de Markov, el capítulo cuatro define las formas de medir la distancia de una cadena de Markov a su distribución estacionaria y el tiempo que tarda en alcanzar esa distancia. El capítulo cinco describe el acoplamiento , una de las técnicas estándar para acotar los tiempos de mezcla. En esta técnica, se establecen dos cadenas de Markov, una que parte del estado inicial dado y la otra de la distribución estacionaria, con transiciones que tienen las probabilidades correctas dentro de cada cadena pero no son independientes entre cadenas, de tal manera que las dos cadenas tienen probabilidades de moverse a los mismos estados. De esta forma, el tiempo de mezcla puede acotarse por el tiempo que tardan las dos cadenas acopladas en sincronizarse. El capítulo seis analiza una técnica llamada "tiempos estacionarios fuertes" con la que, para algunas cadenas de Markov, se puede demostrar que elegir un tiempo de parada aleatoriamente de una cierta distribución dará como resultado un estado extraído de la distribución estacionaria. ^{[ 6 ]}

Después de un capítulo sobre límites inferiores del tiempo de mezcla basados ​​en la " relación de cuello de botella " y el número isoperimétrico , ^{[ 5 ]} los dos capítulos siguientes de la primera parte cubren dos ejemplos importantes: barajar cartas y paseos aleatorios en grafos . Los capítulos 10 y 11 consideran dos parámetros más estrechamente relacionados con el tiempo de mezcla, el tiempo de llegada en el que la cadena de Markov alcanza por primera vez un estado específico, y el tiempo de cobertura en el que ha alcanzado por primera vez todos los estados. ^{[ 6 ]} También analizan las cadenas de Markov reversibles en el tiempo y su conexión con las redes eléctricas. ^{[ 5 ]} El capítulo final de esta parte analiza la conexión entre la brecha espectral de una cadena de Markov y su tiempo de mezcla. ^{[ 6 ]}

La segunda parte del libro incluye muchos más ejemplos en los que se ha aplicado esta teoría, incluyendo la dinámica de Glauber en el modelo de Ising , los modelos de Markov de reordenamiento cromosómico , el proceso de exclusión simple asimétrico en el que las partículas saltan aleatoriamente a espacios adyacentes desocupados y los paseos aleatorios en el grupo del farolero . ^{[ 6 ]} Los temas cubiertos en la segunda parte del libro incluyen más sobre gráficos espectrales y gráficos expansores , ^{[ 5 ]} acoplamiento de trayectorias (en el que una secuencia de más de dos cadenas de Markov se acopla en pares), ^{[ 6 ]} conexiones entre el acoplamiento y la distancia del transportador de tierra , martingalas , ^{[ 5 ]} temperaturas críticas , ^{[ 2 ]} el "efecto de corte" en el que la distribución de probabilidad de la cadena transita rápidamente entre no mezclada y mezclada, ^{[ 1 ] [ 2 ] [ 6 ]} el proceso de conjunto evolutivo (una cadena de Markov derivada en conjuntos de estados de la cadena dada), ^{[ 2 ]} cadenas de Markov con infinitos estados, y cadenas de Markov que operan en tiempo continuo en lugar de mediante una secuencia discreta de pasos. Un capítulo invitado de Jim Propp y David B. Wilson describe el acoplamiento desde el pasado , un método para obtener muestras extraídas exactamente de la distribución estacionaria en lugar de (como se obtiene de los métodos de Monte Carlo de cadenas de Markov ) aproximaciones a esta distribución. ^{[ 1 ] [ 2 ]} El capítulo final recopila problemas abiertos en esta área. ^{[ 5 ]}

Este libro puede utilizarse como referencia por investigadores en áreas que emplean estos métodos, o como base para un curso de posgrado, ^{[ 1 ]} particularmente uno limitado al material más introductorio de la primera parte del libro ^{[ 6 ]} donde solo se requiere un conocimiento de nivel de pregrado de teoría de la probabilidad y álgebra lineal . ^{[ 1 ] [ 2 ]} Sin embargo, el revisor Rick Durrett sugiere que el contenido del libro sería demasiado avanzado para cursos de pregrado, incluso en universidades de investigación, ^{[ 6 ]} y el revisor Takis Konstantopoulos sugiere que el contenido del libro sería mejor apreciado por un lector que ya tenga cierta familiaridad con el material que abarca. ^{[ 5 ]}

El crítico Olle Häggström califica el libro de «autorizado y de fácil lectura». ^{[ 1 ]} El crítico HM Mai escribe que sus explicaciones son cuidadosas y «bien fundamentadas», y que la escritura es «lúcida y clara». ^{[ 2 ]} El crítico László Lakatos lo considera «una guía brillante para la teoría moderna de las cadenas de Markov». Y el crítico David Aldous predice que «seguirá siendo durante mucho tiempo la lectura obligatoria definitiva» en este campo.

• Página web del autor con erratas y una copia descargable del libro.