Tiempo de mezcla de la cadena de Markov

En teoría de probabilidad , el tiempo de mezcla de una cadena de Markov es el tiempo hasta que la cadena de Markov está "cerca" de su distribución de estado estable .

Más precisamente, un resultado fundamental sobre las cadenas de Markov es que una cadena aperiódica irreducible de estado finito tiene una distribución estacionaria única π y, sin importar el estado inicial, la distribución de tiempo- t de la cadena converge a π cuando t tiende a infinito. El tiempo de mezcla se refiere a cualquiera de varias formalizaciones variantes de la idea: ¿qué tan grande debe ser t hasta que la distribución de tiempo -t sea aproximadamente π ? Una variante, el tiempo de mezcla de distancia de variación total , se define como el t más pequeño tal que la distancia de variación total de las medidas de probabilidad sea pequeña:

${\displaystyle t_{\operatorname {mix} }(\varepsilon )=\min \left\{t\geq 0:\max _{x\in S}{\Big [}\max _{A\subseteq S}\left|\Pr(X_{t}\in A\mid X_{0}=x)-\pi (A)\right|{\Big ]}\leq \varepsilon \right\}.}$

Elegir un diferente , siempre que , solo pueda cambiar el tiempo de mezcla hasta un factor constante (dependiendo de ) y por eso a menudo se arregla y simplemente se escribe . ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon <1/2}$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon =1/4}$ ${\displaystyle t_{\mathrm {mix} }}$

Este es el sentido en el que Dave Bayer y Persi Diaconis  (1992) demostraron que el número de barajadas necesarias para mezclar una baraja ordinaria de 52 cartas es 7. La teoría matemática se centra en cómo cambian los tiempos de mezcla en función del tamaño de la estructura subyacente a la cadena. Para una baraja de , el número de barajadas necesarias crece como . La teoría más desarrollada se refiere a algoritmos aleatorios para problemas de conteo algorítmicos #P-completos , como el número de coloraciones de grafos de un grafo de vértices dado . Tales problemas pueden, para un número suficientemente grande de colores, resolverse utilizando el método de Monte Carlo de la cadena de Markov y mostrando que el tiempo de mezcla crece solo como (Jerrum 1995). Este ejemplo y el ejemplo de barajado poseen la propiedad de mezcla rápida , de que el tiempo de mezcla crece como máximo polinomialmente rápido en (número de estados de la cadena). Las herramientas para demostrar la mezcla rápida incluyen argumentos basados ​​en la conductancia y el método de acoplamiento . En usos más amplios del método de Monte Carlo de cadenas de Markov , la justificación rigurosa de los resultados de la simulación requeriría un límite teórico en el tiempo de mezcla, y muchos casos prácticos interesantes han resistido dicho análisis teórico. ${\displaystyle n}$ ${\displaystyle 1.5\log _{2}n}$ ${\displaystyle n}$ ${\displaystyle n\log(n)}$ ${\displaystyle \log }$

Véase también

• Mezcla (matemáticas) para una definición formal de mezcla

Referencias

• Aldous, David; Fill, Jim, Cadenas de Markov reversibles y recorridos aleatorios en gráficos, archivado desde el original el 21 de septiembre de 2004.
• Bayer, Dave ; Diaconis, Persi (1992), "Siguiendo el ejemplo de la cola de milano hasta su guarida" (PDF) , The Annals of Applied Probability , 2 (2): 294–313, doi : 10.1214/aoap/1177005705 , JSTOR  2959752, MR  1161056.
• Jerrum, Mark (1995), "Un algoritmo muy simple para estimar el número de k -coloraciones de un gráfico de bajo grado", Random Structures & Algorithms , 7 (2): 157–165, doi :10.1002/rsa.3240070205, MR  1369061.
• Levin, David A.; Peres, Yuval ; Wilmer, Elizabeth L. (2009), Cadenas de Markov y tiempos de mezcla , Providence, Rhode Island: American Mathematical Society, ISBN 978-0-8218-4739-8, Sr.  2466937.
• Sinclair, Alistair (1993), Algoritmos para generación y conteo aleatorios: un enfoque de cadena de Markov , Progress in Theoretical Computer Science, Birkhäuser Boston, Inc., Boston, MA, doi : 10.1007/978-1-4612-0323-0, ISBN 0-8176-3658-7, Sr.  1201590.