Markov-kedjans blandningstid

I sannolikhetsteorin är blandningstiden för en Markov-kedja tiden tills Markov-kedjan är "nära" sin steady state- distribution .

Mer exakt är ett fundamentalt resultat om Markov-kedjor att en ändligt tillstånd irreducerbar aperiodisk kedja har en unik stationär fördelning π och, oavsett initialtillståndet, konvergerar tidsfördelningen av kedjan till π eftersom t tenderar till oändlighet. Blandningstid hänvisar till någon av flera variantformaliseringar av idén: hur stor måste t vara tills tidsfördelningen är ungefär π ? En variant, variationsavståndsblandningstid , definieras som det minsta t så att det totala variationsavståndet för sannolikhetsmått är litet:

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

för alla delmängder $A$ av tillstånd och alla initiala tillstånd. Detta är den mening i vilken Dave Bayer och Persi Diaconis ( 1992 ) bevisade att antalet riffelblandningar som behövs för att blanda en vanlig kortlek med 52 kort är 7. Matematisk teori fokuserar på hur blandningstiderna förändras som en funktion av storleken på den underliggande strukturen. kedjan. För en $n$ -kort växer antalet riffle shuffles som behövs med $1,5\log _{2}n$ . Den mest utvecklade teorin gäller randomiserade algoritmer för #P-Complete algoritmiska räkneproblem som antalet graffärgningar för en given $n$ vertexgraf. Sådana problem kan, för tillräckligt stort antal färger, besvaras med Markov-kedjans Monte Carlo- metoden och visar att blandningstiden bara växer som $n\log(n)$ ( Jerrum 1995 ). Det här exemplet och blandningsexemplet har snabb blandning , att blandningstiden som mest växer polynomiskt snabbt i $\log$ (antal tillstånd i kedjan). Verktyg för att bevisa snabb blandning inkluderar argument baserade på konduktans och kopplingsmetoden . Vid bredare användningar av Markov-kedjan Monte Carlo-metoden skulle en rigorös motivering av simuleringsresultat kräva en teoretisk begränsning av blandningstid, och många intressanta praktiska fall har motstått sådan teoretisk analys.

Se även

• Blandning (matematik) för en formell definition av blandning

• Aldous, David; Fill, Jim, Reversible Markov Chains and Random Walks on Graphs , arkiverad från originalet 2004-09-21 .
• Bayer, Dave ; Diaconis, Persi (1992), "Trailing the dovetail shuffle to its lair" (PDF) , The Annals of Applied Probability , 2 (   ): 294–313, doi : 10.1214/aoap/1177005705 , JSTOR 52 , 1059   2
•   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-kedjor och blandningstider , Providence, Rhode Island: American Mathematical Society, ISBN 978-0-8218-4739-8 , MR 2466937 .
•    Sinclair, Alistair (1993), Algoritmer för slumpmässig generering och räkning: 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 .