Markovs kedjeträdssats

I den matematiska teorin om Markov-kedjor är Markov- kedjeträdsatsen ett uttryck för den stationära fördelningen av en Markov-kedja med ändligt många tillstånd. Den sammanfattar termer för de rotade spännande träden i Markovkedjan, med en positiv kombination för varje träd. Markovs kedjeträdssats är nära besläktad med Kirchhoffs sats om att räkna de spännande träden i en graf, från vilken den kan härledas. Det angavs först av Hill (1966) , för vissa Markov-kedjor som uppstår inom termodynamiken , och bevisades i full allmänhet av Leighton & Rivest (1986), motiverat av en tillämpning i begränsad minnesuppskattning av sannolikheten för ett partiskt mynt .

En finit Markov-kedja består av en ändlig uppsättning tillstånd och en övergångssannolikhet $p_{i,j}$ för att byta från tillstånd $i$ till tillstånd $j$ , t.ex. att för varje tillstånd summeras sannolikheterna för utgående övergång till ett. Från ett initialt val av tillstånd (som visar sig vara irrelevant för detta problem), väljs varje successivt tillstånd slumpmässigt enligt övergångssannolikheterna från det tidigare tillståndet. En Markov-kedja sägs vara irreducerbar när varje tillstånd kan nå vartannat tillstånd genom någon sekvens av övergångar, och aperiodisk om, för varje tillstånd, det möjliga antalet steg i sekvenser som börjar och slutar i det tillståndet har största gemensamma divisor ett . En irreducerbar och aperiodisk Markov-kedja har med nödvändighet en stationär fördelning, en sannolikhetsfördelning på sina tillstånd som beskriver sannolikheten att vara i ett givet tillstånd efter många steg, oavsett det initiala valet av tillstånd.

Markovkedjans trädsats anser att spännande träd för tillstånden i Markovkedjan, definierade som träd , riktade mot en utpekad rot, där alla riktade kanter är giltiga övergångar av den givna Markovkedjan. Om en övergång från tillstånd $i$ till tillstånd $j$ har övergångssannolikhet $p_{i,j}$ , då ett träd $T$ med kantmängd $E(T)$ definieras för att ha vikt lika med produkten av dess övergångssannolikheter:

$$w(T)=\prod _{(i,j)\in E(T)}p_{i,j}.$$

Låt ${\mathcal {T}}_{i}$ beteckna mängden av alla spännande träd som har tillståndet $i$ vid sin rot. Sedan, enligt Markovs kedjeträdssats, är den stationära sannolikheten $\pi _{i}$ för tillstånd $i$ proportionell mot summan av vikterna av träden med rötter i i { $displaystyle i}$ . Det är,

$$\pi _{i}={\frac {1}{Z}}\summa _{T\in {\mathcal {T}}_ {i}}w(T),$$

där normaliseringskonstanten $Z$ är summan av $w(T)$ över alla spännande träd.