Cadenas de Markov y tiempos de mezcla
Markov Chains and Mixing Times es un libro sobre los tiempos de mezcla de las 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 en los estados. Partiendo 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 solo 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 estacionariaa 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 ocurra 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 polinomial 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: a partir de una baraja de cartas 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 órdenes de la baraja 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 mezcla rápida de la cadena de Markov significa que uno no tiene que realizar una gran cantidad de mezclas para alcanzar un estado suficientemente aleatorio. Más allá de los juegos de cartas, consideraciones similares surgen en el comportamiento de los sistemas físicos estudiados en 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 establecen 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 forma en que es probable que las dos cadenas se muevan a los mismos estados entre sí. De esta forma, el tiempo de mezcla puede estar limitado por el tiempo de sincronización de las dos cadenas acopladas. 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 al azar de una determinada distribución dará como resultado un estado extraído de la distribución estacionaria. [6]
