마르코프 체인 믹싱 시간

확률론에서, 마르코프 체인의 혼합 시간은 마르코프 체인이 그것의 안정된 상태 분포에 "가까이"될 때까지의 시간이다.

더 정확히 말하면, 마르코프 체인에 대한 근본적인 결과는 유한 상태 불가침 aperiodic 체인이 독특한 고정 분포 π을 가지고 있으며, 초기 상태에 관계없이 체인의 시간 t 분포는 무한대로 π으로 수렴된다는 것이다.혼합 시간은 아이디어의 몇 가지 변형 공식화 중 하나를 가리킨다: 시간-t 분포가 대략 π? 한 변종, 변동 거리 혼합 시간은 확률 측정의 총 변동 거리가 작도록 가장 작은 t로 정의된다.

${\displaystyle \Pr(X_{t}\in A)-\pi(A) \leq 1/4}$

$모든$ 하위 집합 $상태$ 및 모든 초기 상태에 대해데이브 바이어와 페르시 디아콘리스(1992)가 일반 52개 카드데크를 섞는데 필요한 리플 슈플의 수가 7개라는 것을 증명해 보인 감각이다.수학적 이론은 체인의 밑바탕에 깔려 있는 구조물의 크기 함수로서 혼합 시간이 어떻게 변하느냐에 초점을 맞춘다.$n{\displaystyle }$ ${\displaystyle n}$ -카드$$ 데크의 경우 1.5 ${\displaystyle {\mathrm{로그}}_{}}$ 2${\displaystyle {}_{}{2\mathrm{}}_{}}$ ${\displaystyle n}$ ${\displaystyle$ 1.$5\log _{2}n$에 따라 필요한 리플 슈플의 수가 증가한다.가장 발전된 이론은 $주어진{\displaystyle }$ n ${\displaystyle n}$ 꼭지점$$ 그래프의 그래프 색상 수와 같은 #P-완전한 알고리즘 계산 문제에 대한 무작위화된 알고리즘에 관한 것이다.그러한 문제들은, 충분히 많은 색상에 대해, 마코프 체인 몬테카를로 방법을 사용하여, 그리고 혼합 시간이 n log ${\displaystyle \log }$ (n$){\displaystyle$ n\$log(n)}$ (Jerrum 1995)$$에 의해서만 증가한다는 것을 보여줄 수 있다.이 예와 섞기 예는 빠른 혼합 특성을 가지고 있는데, 혼합 시간은 ${\displaystyle \mathrm{로그}}$ ${\displaystyle \log$ $\}($체인의 상태 수)에서 최대 다항식으로 빠르게 증가한다.급속 혼합을 입증하기 위한 도구에는 전도성과 결합 방법에 기초한 주장이 포함된다.마르코프 체인 몬테 카를로 방법의 광범위한 사용에서, 시뮬레이션 결과의 엄격한 정당성은 혼합 시간에 대한 이론적 구속을 필요로 할 것이며, 많은 흥미로운 실제 사례들이 그러한 이론 분석에 저항해왔다.

참고 항목

• 혼합의 공식 정의를 위한 혼합(수학)

참조

• Aldous, David; Fill, Jim, Reversible Markov Chains and Random Walks on Graphs, archived from the original on 2004-09-21.
• Bayer, Dave; Diaconis, Persi (1992), "Trailing the dovetail shuffle to its lair" (PDF), The Annals of Applied Probability, 2 (2): 294–313, doi:10.1214/aoap/1177005705, JSTOR 2959752, MR 1161056.
• Jerrum, Mark (1995), "A very simple algorithm for estimating the number of k-colorings of a low-degree graph", Random Structures & Algorithms, 7 (2): 157–165, doi:10.1002/rsa.3240070205, MR 1369061.
• Levin, David A.; Peres, Yuval; Wilmer, Elizabeth L. (2009), Markov chains and mixing times, Providence, Rhode Island: American Mathematical Society, ISBN 978-0-8218-4739-8, MR 2466937.
• Sinclair, Alistair (1993), Algorithms for random generation and counting: A Markov chain approach, Progress in Theoretical Computer Science, Birkhäuser Boston, Inc., Boston, MA, doi:10.1007/978-1-4612-0323-0, ISBN 0-8176-3658-7, MR 1201590.