Cadenas de Markov y tiempos de mezcla 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 se le acredita como colaboradora de la segunda edición. 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 de los estados. A partir de un estado inicial, sigue una secuencia de estados donde cada estado de la secuencia se elige aleatoriamente de la distribución asociada con el estado anterior. En ese sentido, es "sin memoria": cada elección aleatoria depende sólo del estado actual y no de la historia pasada de los estados. Bajo restricciones leves, 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 acercará 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 adecuado de precisión. 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 que se mezcla lentamente en caso contrario. Este libro trata sobre cadenas finitas de Markov, 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 implica barajar barajas de cartas: partiendo de una baraja inicial no aleatoria, ¿cuántas barajas se necesitan para llegar a una permutación casi aleatoria ? Esto se puede modelar como una cadena de Markov cuyos estados son ordenamientos del mazo de cartas y cuyas probabilidades de transición de estado a estado están 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 significa que no es necesario realizar una gran cantidad de mezclas 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 la mecánica estadística , y de 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 las 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 lleva alcanzar esa distancia. El capítulo cinco describe el acoplamiento , una de las técnicas estándar para limitar los tiempos de mezcla. En esta técnica, se configuran dos cadenas de Markov, una a partir del estado inicial dado y la otra a partir de la distribución estacionaria, con transiciones que tienen las probabilidades correctas dentro de cada cadena pero que no son independientes de cadena a cadena, de tal manera que manera que sea probable que las dos cadenas se muevan a los mismos estados entre sí. De esta manera, el tiempo de mezcla puede estar limitado por el tiempo para que las dos cadenas acopladas se sincronicen. El capítulo seis analiza una técnica llamada "tiempos estacionarios fuertes" con la cual, para algunas cadenas de Markov, se puede demostrar que elegir un tiempo de parada aleatoriamente de una determinada distribución dará como resultado un estado extraído de la distribución estacionaria. [6]
Después de un capítulo sobre los límites inferiores del tiempo de mezcla basado en la " relación de cuello de botella " y el número isoperimétrico , [5] los siguientes dos capítulos de la primera parte cubren dos ejemplos importantes: barajado de cartas y paseos aleatorios en gráficos . Los capítulos 10 y 11 consideran dos parámetros más estrechamente relacionados con el tiempo de mezcla, el tiempo de impacto en el que la cadena de Markov alcanza por primera vez un estado específico y el tiempo de cobertura en el que alcanza por primera vez todos los estados. [6] También analizan las cadenas de Markov reversibles en el tiempo y su conexión a redes eléctricas. [5] El último capítulo 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, incluida la dinámica de Glauber en el modelo de Ising , los modelos de reordenamiento cromosómico de Markov , el proceso de exclusión simple asimétrico en el que las partículas saltan aleatoriamente a espacios adyacentes desocupados y el proceso aleatorio de exclusión. camina en el grupo de faroleros . [6] Los temas cubiertos en la segunda parte del libro incluyen más sobre gráficos espectrales y gráficos de expansión , [5] acoplamiento de ruta (en el que una secuencia de más de dos cadenas de Markov se acopla en pares), [6] conexiones entre acoplamiento y la distancia del motor de tierra , martingalas , [5] temperaturas críticas , [2] el "efecto de corte" en el que la distribución de probabilidad de la cadena cambia rápidamente entre no mezclado y mixto, [1] [2] [6] el proceso de conjunto en evolución ( 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 del pasado , un método para obtener muestras extraídas exactamente de la distribución estacionaria en lugar de (como se obtiene con los métodos de Monte Carlo de la cadena de Markov ) aproximaciones a esta distribución. [1] [2] El capítulo final recoge los problemas abiertos en este ámbito. [5]
Este libro puede ser utilizado como referencia por investigadores en áreas que utilizan 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 sólo se requiere un conocimiento de nivel universitario de teoría de la probabilidad y álgebra lineal . [1] [2] Sin embargo, el crítico Rick Durrett sugiere que el contenido del libro sería demasiado avanzado para cursos universitarios, incluso en universidades de nivel de investigación, [6] y el crítico Takis Konstantopoulos sugiere que el lector apreciaría mejor el contenido del libro. que ya haya tenido alguna exposición al material que cubre. [5]
El crítico Olle Häggström califica el libro de "autorizado y muy legible". [1] El crítico HM Mai escribe que sus explicaciones son cuidadosas y "bien motivadas", y que la escritura es "lúcida y clara". [2] El crítico László Lakatos lo llama "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 definitiva obligatoria" en esta área.