Tiempo de mezcla de la cadena de Markov

En teoría de la 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 estacionario .

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, independientemente del estado inicial, la distribución temporal t de la cadena converge a π cuando t tiende a infinito. El tiempo de mezcla se refiere a cualquiera de las varias formalizaciones variantes de la idea: ¿qué tamaño debe ser t hasta que la distribución tiempo- t sea aproximadamente π ? Una variante, el tiempo de mezcla de la distancia de variación total , se define como la t más pequeña tal que la distancia de variación total de las medidas de probabilidad es pequeña:

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

Elegir un diferente , siempre y cuando , solo pueda cambiar el tiempo de mezcla hasta un factor constante (dependiendo de ), por lo que a menudo uno arregla y simplemente escribe . ${\displaystyle \epsilon }$ ${\displaystyle \epsilon <1/2}$ ${\displaystyle \epsilon }$ ${\displaystyle \epsilon =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 mezclas necesarias para mezclar una baraja ordinaria de 52 cartas es 7. La teoría matemática se centra en cómo los tiempos de mezcla cambian en función del tamaño de la estructura subyacente. La cadena. Para una baraja de cartas, el número de barajas necesarias crece a medida que . La teoría más desarrollada se refiere a algoritmos aleatorios para problemas de conteo algorítmico #P-Complete, como el número de colores de gráficos de un gráfico de vértice determinado. Estos problemas se pueden responder, para un número suficientemente grande de colores, utilizando el método Monte Carlo de la cadena de Markov y demostrando que el tiempo de mezcla crece sólo a medida que aumenta (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 una mezcla rápida incluyen argumentos basados ​​en la conductancia y el método de acoplamiento . En usos más amplios del método Monte Carlo de la cadena 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 se han resistido a dicho análisis teórico. ${\displaystyle n}$ ${\displaystyle 1.5\log _{2}n}$ ${\displaystyle n}$ ${\displaystyle n\log(n)}$ ${\displaystyle \log }$

Ver también

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

Referencias

• Aldous, David; Fill, Jim, Cadenas de Markov reversibles y paseos aleatorios en gráficos, archivado desde el original el 21 de septiembre de 2004.
• Bayer, Dave ; Diaconis, Persi (1992), "Siguiendo 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, Señor  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, señor  2466937.
• Sinclair, Alistair (1993), Algoritmos para generación y conteo aleatorios: un enfoque de cadena de Markov , Progreso en informática teórica, Birkhäuser Boston, Inc., Boston, MA, doi :10.1007/978-1-4612-0323-0, ISBN 0-8176-3658-7, SEÑOR  1201590.