Doba míchání Markovova řetězce - Markov chain mixing time - Wikipedia

v teorie pravděpodobnosti, doba míchání a Markovův řetězec je čas, než je markovský řetězec „blízko“ svému ustálený stav rozdělení.

Přesněji řečeno, zásadní výsledek o Markovovy řetězy je, že nereukovatelný aperiodický řetězec konečného stavu má jedinečné stacionární rozdělení π a bez ohledu na počáteční stavt distribuce řetězce konverguje k π tak jako t inklinuje k nekonečnu. Směšovací čas se vztahuje na některou z několika variant formalizace myšlenky: jak velká musí být t být do času -t distribuce je přibližně π ? Jedna varianta, doba míchání variační vzdálenosti, je definován jako nejmenší t takové, že celková variační vzdálenost pravděpodobnostních opatření je malý:

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

pro všechny podskupiny ${ displaystyle A}$ stavů a ​​všech počátečních stavů. To je smysl, ve kterém Dave Bayer a Persi Diaconis  (1992 ) dokázal, že počet riffle zamíchá k smíchání obyčejného balíčku 52 karet je 7. Matematická teorie se zaměřuje na to, jak se časy míchání mění v závislosti na velikosti struktury pod řetězcem. Pro ${ displaystyle n}$- balíček karet, počet potřebných přeskupení riffle roste s ${ displaystyle 1,5 log _ {2} n}$. Nejrozvinutější teorie se týká randomizované algoritmy pro # P-Complete problémy s algoritmickým počítáním, jako je počet barvení grafů daného ${ displaystyle n}$ vrcholový graf. Na takové problémy lze u dostatečně velkého počtu barev odpovědět pomocí Markovský řetězec Monte Carlo metoda a ukázka, že doba míchání roste jen jako ${ displaystyle n log (n)}$ (Jerrum 1995 ). Tento příklad a zamíchaný příklad mají rychlé míchání vlastnost, že doba míchání roste nanejvýš polynomiálně rychle ${ displaystyle log}$(počet států řetězce). Mezi nástroje pro prokázání rychlého míchání patří argumenty založené na vodivost a způsob spojka. V širším použití řetězce Markov Metoda Monte Carlo, důsledné zdůvodnění výsledků simulace by vyžadovalo teoretickou vazbu na čas míchání a mnoho zajímavých praktických případů takové teoretické analýze odolalo.

Viz také

• Míchání (matematika) pro formální definici míchání

Reference

• Aldous, David; Fill, Jim, Reverzibilní Markovovy řetězce a náhodné procházky po grafech, archivovány z originál dne 2004-09-21.
• Bayer, Dave; Diaconis, Persi (1992), „Sledování rybinového shuffle do jeho doupěte“ (PDF), Annals of Applied Probability, 2 (2): 294–313, doi:10.1214 / aoap / 1177005705, JSTOR  2959752, PAN  1161056.
• Jerrum, Mark (1995), „Velmi jednoduchý algoritmus pro odhad počtu k-barvy nízkoúrovňového grafu ", Náhodné struktury a algoritmy, 7 (2): 157–165, doi:10.1002 / rsa.3240070205, PAN  1369061.
• Levin, David A .; Peres, Yuval; Wilmer, Elizabeth L. (2009), Markovovy řetězce a doby míchání, Providence, Rhode Island: American Mathematical Society, ISBN  978-0-8218-4739-8, PAN  2466937.
• Sinclair, Alistair (1993), Algoritmy pro náhodné generování a počítání: Markovův řetězový přístupPokrok v teoretické informatice, Birkhäuser Boston, Inc., Boston, MA, doi:10.1007/978-1-4612-0323-0, ISBN  0-8176-3658-7, PAN  1201590.