Markovketen

Een markovketen, genoemd naar de Russische wiskundige Andrej Markov, beschrijft een systeem dat zich door een aantal toestanden beweegt en stapsgewijs overgangen vertoont van de ene naar een andere (of dezelfde) toestand. De specifieke markov-eigenschap houdt daarbij in dat populair uitgedrukt: "de toekomst gegeven het heden niet afhangt van het verleden". Dat betekent dat als het systeem zich in een bepaalde toestand bevindt, het toekomstige gedrag van het systeem, dus de komende overgangen, slechts afhangen van de huidige toestand en niet van de weg waarlangs deze toestand tot stand is gekomen. De toestanden van het systeem worden beschreven door een rij stochastische variabelen $X_{0},X_{1},X_{2},\ldots$ met kansverdelingen $\pi _{0},\pi _{1},\pi _{2},\ldots$, waarin $X_{n}$ de toestand van het systeem is na $n$ stappen. De markov-eigenschap wordt uitgedrukt in een eigenschap van de overgangskansen.

Een markovketen kan met een stochastische matrix worden weergegeven.

Definitie

Een markovketen van een systeem met $k$ mogelijke toestanden $E=\{1,2,\ldots ,k\}$ is een discreet stochastisch proces $(X_{n}),n=0,1,2,\ldots$ met waarden in $E$ dat voldoet aan de markov-eigenschap.

De kansverdeling van $X_{n}$ wordt gegeven door de kansfunctie $\pi _{n}$ over $E$ waarvoor geldt:

$\pi _{n}(j)=\pi _{n,j}=P(X_{n}=j)$

De begintoestand $X_{0}$ van het systeem wordt gegeven door de beginverdeling $\pi _{0}$. Tussen de kansverdelingen bestaat de relatie

$\pi _{n}=\pi _{n-1}P_{n}$

waarin de kansverdelingen beschouwd worden als rijvector en $P_{n}$ de matrix van overgangskansen op $n$ is met elementen

$p_{ij}(n)=P(X_{n}=j|X_{n-1}=i)$

Het getal $p_{ij}(n)$ is de kans dat het systeem op $n$ overgaat van toestand $i$ naar toestand $j$. Anders gezegd: dit is de voorwaardelijke kans dat het systeem op zeker tijdstip $n$ zich bevindt in toestand $j$, gegeven dat het systeem zich op tijdstip $n-1$ in toestand $i$ bevond. Hiervoor geldt de markov-eigenschap, die zegt dat deze kans alleen afhangt van de toestand op tijdstip $n-1$ en niet van de daaraan voorafgaande toestanden:

$P(X_{n}=j|X_{0}=i_{0},X_{1}=i_{1},\ldots ,X_{n-1}=i)=P(X_{n}=j|X_{n-1}=i)$

Het systeem heeft met andere woorden geen 'geheugen'. Men noemt dit een markovketen van de eerste orde in discrete tijd: het systeem kan alleen van toestand veranderen op regelmatige tijdstippen.

Eigenschappen

• Er geldt altijd dat $\sum _{i}p_{ij}(n)=1$, maar $\sum _{j}p_{ij}(n)$ kan van 1 verschillen. De figuren illustreren dat.
• $\sum _{i,n}p_{ij}(n)=\sum _{j,n}p_{ij}(n)=k$

Generalisaties

De definitie van markovketen kan op verschillende manieren gegeneraliseerd worden:

• Het systeem kan een oneindig aantal discrete toestanden aannemen of een continue toestandsruimte bezitten, zoals bij de brownse beweging. Als de toestandsruimte continu is, spreekt men van een markovproces en niet van een markovketen; maar de termen worden vaak door elkaar gebruikt.
• De eenstapsovergangskansen kunnen afhankelijk zijn van het tijdstip $n$. Als de overgangskansen niet variëren in de tijd noemt men de markovketen homogeen;
• Men kan een markovketen van orde $m$ beschouwen waarvan de eenstapsovergangskansen niet alleen afhangen van de vorige toestand, maar van $m$ vorige toestanden ($m>1$):

$P(X_{n}=i_{n}|X_{n-1}=i_{n-1},X_{n-2}=i_{n-2},\ldots ,X_{0}=i_{0})=P(X_{n}=i_{n}|X_{n-1}=i_{n-1},\ldots ,X_{n-m}=i_{n-m})$

• In plaats van een systeem dat alleen op regelmatige, discrete tijdstippen verandert, kan men ook een systeem beschouwen in continue tijd, dat op onregelmatige tijdstippen van toestand verandert.

Voorbeelden

Voorbeeld 1

Een muis beweegt zich door een huis met op de bovenverdieping de vertrekken 1, ..., 5 en op de benedenverdieping de vertrekken 6, 7 en 8. Hij kan zich vrij op de bovenverdieping door de vertrekken bewegen, maar mocht hij in de slaapkamer 5 door het gat in de vloer vallen, dan is er geen weg terug en is hij gedwongen beneden te blijven. In de keuken, kamer nummer 8, staat een val, waar de muis, mocht hij zich in de keuken wagen, beslist in terechtkomt. Op zoek naar eten loopt de muis rond en weet zich echt niet te herinneren of hij al in een vertrek is geweest. Hij kiest daarom steeds met gelijke kansen naar een van de aangrenzende vertrekken te gaan.

De weg die de muis aflegt laat zich met een gewogen, gerichte graaf beschrijven:

Muis in het huis

Een verloop kan zijn dat de muis zich aan het begin in kamer 5 bevindt en van daaruit naar een van de vertrekken 2, 3, 4 en 7 gaat, met voor alle vier een kans van 1/4. De weg van de muis kan er zo uitzien: 5 4 1 4 1 2 5 7 6 7 8 of met meer geluk: 5 4 1 2 5 4 1 2 3 2 1 4 1 4 1 4 1 4 1 2 3 5 7 6 7 6 7 6 7 8.

Voor de bovenstaande graaf is dit de overgangs- of transitiematrix:

$P={\begin{bmatrix}0&{\frac {1}{2}}&0&{\frac {1}{2}}&0&0&0&0\\{\frac {1}{3}}&0&{\frac {1}{3}}&0&{\frac {1}{3}}&0&0&0\\0&{\frac {1}{2}}&0&0&{\frac {1}{2}}&0&0&0\\{\frac {1}{2}}&0&0&0&{\frac {1}{2}}&0&0&0\\0&{\frac {1}{4}}&{\frac {1}{4}}&{\frac {1}{4}}&0&0&{\frac {1}{4}}&0\\0&0&0&0&0&0&1&0\\0&0&0&0&0&{\frac {1}{2}}&0&{\frac {1}{2}}\\0&0&0&0&0&0&0&1\end{bmatrix}}$

Zoals hierboven gezegd is in $P$ het getal op rij $i$ en kolom $j$ de kans dat het systeem van toestand $i$ naar toestand $j$ overgaat, hier dus de kans dat de muis van kamer $i$ naar kamer $j$ gaat. Dit zijn de getallen bij de pijlen in de gegeven graaf. $P$ is een stochastische matrix: iedere rij van de matrix bestaat uit getallen tussen 0 en 1 en de som van elke rij is gelijk aan 1.

De kans dat de muis vanuit kamer 5 precies het pad 5 4 1 4 1 2 5 7 6 7 8 volgt kan aan de hand van deze matrix worden berekend, het is de combinatie van de overgangskansen 5→4, 4→1, 1→4, 4→1 enzovoort. Deze kans is het product van de overgangskansen:

$P('54141257678')=p_{54}\ p_{41}\ p_{14}\ p_{41}\ p_{12}\ p_{25}\ p_{57}\ p_{76}\ p_{67}\ p_{78}=$

$={\tfrac {1}{4}}\times {\tfrac {1}{2}}\times {\tfrac {1}{2}}\times {\tfrac {1}{2}}\times {\tfrac {1}{2}}\times {\tfrac {1}{3}}\times {\tfrac {1}{4}}\times {\tfrac {1}{2}}\times 1\times {\tfrac {1}{2}}=3{,}225\times 10^{-4}$

De verwachte toestand van het systeem op tijdstip $n$ wordt beschreven door een rijvector $\pi _{n}$. Het aantal elementen van deze vector is in dit geval gelijk aan het aantal kamers en het $i$-de element in de vector is de kans dat de muis zich op tijdstip $n$ in kamer $i$ bevindt.

Stel dat de muis bij tijdstip 0 in kamer 5 verblijft, dan is de beginverdeling

$\pi _{0}={\begin{bmatrix}0&0&0&0&1&0&0&0\end{bmatrix}}$

Vanuit kamer 5 kan de muis gaan naar de kamers 2, 3, 4 of 7. De kans daar op is steeds gelijk aan 1/4. Dit betekent dat op tijdstip 1 de muis met een kans gelijk aan 1/4 in een van de kamers 2, 3, 4 en 7 zit en met kans 0 in de andere kamers. Dus

$\pi _{1}=\pi _{0}\cdot P={\begin{bmatrix}0&{\frac {1}{4}}&{\frac {1}{4}}&{\frac {1}{4}}&0&0&{\frac {1}{4}}&0\end{bmatrix}}$

Deze verdeling ontstaat als het matrixproduct van de rijvector $\pi _{0}$ met de stochastische matrix $P$.

De kansverdeling op tijdstip 2 ontstaat op dezelfde manier

$\pi _{2}=\pi _{1}\cdot P={\begin{bmatrix}{\frac {5}{24}}&{\frac {1}{8}}&{\frac {1}{12}}&0&{\frac {1}{3}}&{\frac {1}{8}}&0&{\frac {1}{8}}\end{bmatrix}}$

In het algemeen geldt

$\pi _{n}=\pi _{n-1}\cdot P=\pi _{0}\cdot P^{n}$

Na honderd stappen is de toestandsvector geëvolueerd tot

$\pi _{100}={\begin{bmatrix}0{,}00018&0{,}00026&0{,}00016&0{,}00017&0{,}00027&0{,}00009&0{,}00017&0{,}99871\end{bmatrix}}$.

Hoe verder in de tijd, hoe waarschijnlijker het wordt dat de muis in kamer 8 terechtkomt, vanwaar er geen uitweg is. Dit volgt uit de 1 in de hoofddiagonaal van de stochastische matrix $P$). De toestandsvector $\pi _{n}$ is voor stijgende $n$ in de limiet invariant, dus geldt er

$\pi \cdot P=\pi$

zodat

$\pi ={\begin{bmatrix}0&0&0&0&0&0&0&1\end{bmatrix}}$.

Dat betekent dat de muis in de limiet altijd in kamer 8 eindigt. Deze asymptotische verdeling is onafhankelijk van de begintoestand $\pi _{0}$: waar de muis zich ook bevond bij de aanvang, ooit komt hij in kamer 8 terecht en daar niet meer uit kunnen. Die limietkans is voor de andere kamers gelijk aan 0, wat betekent dat de muis daar na een voldoend lange tijd niet meer is. Dergelijke toestanden worden overgangstoestanden genoemd en een toestand zoals dat de muis in kamer 8 zit een absorberende toestand.

Een markovketen met de eigenschap, dat de kansverdeling in de limiet onafhankelijk is van de begintoestand, noemt men compleet ergodisch.

Stel nu dat er in een ander huis twee muizenvallen zijn, bijvoorbeeld in kamers 4 en 8. De transitiematrix zal er dan anders uitzien dan hierboven, en tweemaal een 1 hebben op de hoofddiagonaal, in rijen 4 en 8. In dat geval is de markovketen niet meer compleet ergodisch. In sommige gevallen zal de muis in de val lopen in kamer 4 en in sommige gevallen in kamer 8. De limietverdeling is hier dus niet meer onafhankelijk van de begintoestand.

De limietvector $\pi$ is een eigenvector van de overgangsmatrix, overeenkomend met de eigenwaarde 1. De stelling van Perron-Frobenius zegt dat iedere stochastische matrix minstens een zo'n vector heeft en dat 1 de grootste eigenwaarde is van de matrix. Een stochastische matrix kan meer limietvectoren hebben, zoals in het geval van een markovketen met verschillende absorberende toestanden. De voorwaarde is dat de matrix of de corresponderende markovketen irreducibel is. Daarvoor moet iedere toestand vanuit iedere andere toestand kunnen worden bereikt, er mogen geen delen van de graaf geïsoleerd zijn van andere delen.

Voorbeeld 2

Eenvoudige markovketen met twee toestanden

De hiernaast afgebeelde graaf stelt een markovketen voor met twee toestanden, A en E. Als het systeem zich op een bepaald tijdstip in toestand A bevindt, is de kans dat het zich op het volgende tijdstip nog steeds in toestand A bevindt, gelijk aan 0,6; de kans dat het overgaat naar toestand E is gelijk aan 0,4. Als het systeem zich in toestand E bevindt, is de kans dat het overgaat naar toestand A groter: 0,7. De stochastische matrix voor dit systeem met toestanden A en E is:

$P={\begin{bmatrix}{\frac {6}{10}}&{\frac {4}{10}}\\{\frac {7}{10}}&{\frac {3}{10}}\end{bmatrix}}$

Stel dat het systeem vertrekt vanuit toestand A; dan is $\pi _{0}={\begin{bmatrix}1&0\end{bmatrix}}$. In de volgende stappen vinden we voor de toestandsvector:

• $\pi _{1}=\pi _{0}\cdot P={\begin{bmatrix}{\frac {6}{10}}&{\frac {4}{10}}\end{bmatrix}}$
• $\pi _{2}=\pi _{1}\cdot P={\begin{bmatrix}{\frac {64}{100}}&{\frac {36}{100}}\end{bmatrix}}$
• $\pi _{3}=\pi _{2}\cdot P={\begin{bmatrix}{\frac {636}{1000}}&{\frac {364}{1000}}\end{bmatrix}}$
• $\pi _{4}=\pi _{3}\cdot P={\begin{bmatrix}{\frac {6364}{10000}}&{\frac {3636}{10000}}\end{bmatrix}}$, enz.

Als het systeem vertrekt vanuit toestand E, is $\pi _{0}={\begin{bmatrix}0&1\end{bmatrix}}$. Nu vinden we in de volgende stappen:

• $\pi _{1}=\pi _{0}\cdot P={\begin{bmatrix}{\frac {7}{10}}&{\frac {3}{10}}\end{bmatrix}}$
• $\pi _{2}=\pi _{1}\cdot P={\begin{bmatrix}{\frac {63}{100}}&{\frac {37}{100}}\end{bmatrix}}$
• $\pi _{3}=\pi _{2}\cdot P={\begin{bmatrix}{\frac {637}{1000}}&{\frac {363}{1000}}\end{bmatrix}}$
• $\pi _{4}=\pi _{3}\cdot P={\begin{bmatrix}{\frac {6363}{10000}}&{\frac {3637}{10000}}\end{bmatrix}}$, enz.

Klaarblijkelijk evolueert $\pi _{n}$, voor stijgende $n$, hier ook naar een constante vector die onafhankelijk is van de begintoestand van het systeem. Wat is die vector $\pi$? Om die te vinden moeten we de vergelijking $\pi =\pi P$ oplossen. Samen met de eis dat de som van de elementen van $\pi$ gelijk is aan 1, vormt dit een stelsel van lineaire vergelijkingen. Stel

$\pi ={\begin{bmatrix}\pi _{A}&\pi _{E}\end{bmatrix}}$,

dan is dat een stelsel van drie vergelijkingen in twee onbekenden:

• $0{,}6\cdot \pi _{A}+0{,}7\cdot \pi _{E}=\pi _{A}$
• $0{,}4\cdot \pi _{A}+0{,}3\cdot \pi _{E}=\pi _{E}$
• $\pi _{A}+\pi _{E}=1$

(Een van de drie vergelijkingen is lineair afhankelijk van de andere twee). Door bijvoorbeeld $\pi _{E}$ te vervangen door $1-\pi _{A}$ in de eerste vergelijking, vinden we dat $\pi _{A}={\frac {7}{11}}$ en dus is

$\pi _{E}={\frac {4}{11}}$ en $\pi ={\begin{bmatrix}{\frac {7}{11}}&{\frac {4}{11}}\end{bmatrix}}$

Op lange termijn is de kans het grootst (namelijk 7/11) dat we het systeem aantreffen in toestand A. We hebben hier dus ook te maken met een compleet ergodisch proces, maar dan een zonder overgangstoestanden. De toestanden A en E zijn recurrente toestanden, die met zekerheid een oneindig aantal malen zullen voorkomen als $n$ naar oneindig gaat. Een markovketen zoals deze, waarin elke toestand recurrent is, noemt men een recurrente keten.

We kunnen hier ook de kans berekenen dat het systeem zich in een toestand $i$ bevindt en exact $n$ tijdstippen in dezelfde toestand blijft; dus dat het de volgorde $\{i,i,\ldots ,i,j\}$ doorloopt waarin er $n-1$ maal een "overgang" van $i$ naar $i$ gebeurt gevolgd door een overgang van $i$ naar $j$, waarin $j$ verschilt van $i$. Die kans is:

$p_{i}(n)=(P_{ii})^{n-1}\cdot (1-P_{ii})$

De kans dat het systeem zich in toestand A bevindt en daar gedurende vijf opeenvolgende tijdstippen blijft en dan naar toestand E overgaat is dus gelijk aan 0,6⁴.(1−0,6) = 0,05184.

Het verwachte aantal opeenvolgende gelijke toestanden, dus de verwachte duur dat het systeem in eenzelfde toestand blijft, is dan gelijk aan:

$\sum _{n=1}^{\infty }n\cdot p_{i}(n)=\sum _{n=1}^{\infty }n\cdot (P_{ii})^{n-1}\cdot (1-P_{ii})={\frac {1}{1-P_{ii}}}$

In dit geval is dit voor toestand A : 1/(1−0,6) = 2,5 en voor toestand E: 1/(1−0,3) = 1,4286. Over een (oneindig) lange periode verwachten we dat het systeem gemiddeld 2,5 tijdsperioden in toestand A blijft en 1,4286 tijdsperioden in toestand E.

Voorbeeld 3: toevalsbeweging

Binaire boom

Een toevalsbeweging in een netwerk of een rooster is een typische markovketen. Stel dat het netwerk een binaire boom is zoals hiernaast afgebeeld, waarin een vlo voortdurend verspringt van een knooppunt naar een willekeurig aangrenzend knooppunt; zowel omhoog als omlaag (met de richting van de pijlen houden we geen rekening). De overgangsmatrix voor dit systeem met negen mogelijke toestanden, is:

$P={\begin{bmatrix}0&{\frac {1}{2}}&{\frac {1}{2}}&0&0&0&0&0&0\\{\frac {1}{3}}&0&0&{\frac {1}{3}}&{\frac {1}{3}}&0&0&0&0\\{\frac {1}{2}}&0&0&0&0&{\frac {1}{2}}&0&0&0\\0&1&0&0&0&0&0&0&0\\0&{\frac {1}{3}}&0&0&0&0&{\frac {1}{3}}&{\frac {1}{3}}&0\\0&0&{\frac {1}{2}}&0&0&0&0&0&{\frac {1}{2}}\\0&0&0&0&1&0&0&0&0\\0&0&0&0&1&0&0&0&0\\0&0&0&0&0&1&0&0&0\end{bmatrix}}$

De limietvector $\pi$ voor dit systeem laat zich eenvoudig berekenen; het is

$\pi ={\begin{bmatrix}{\frac {1}{8}}&{\frac {3}{16}}&{\frac {1}{8}}&{\frac {1}{16}}&{\frac {3}{16}}&{\frac {1}{8}}&{\frac {1}{16}}&{\frac {1}{16}}&{\frac {1}{16}}\end{bmatrix}}$

Deze waarden zijn evenredig met het aantal verbindingen van en naar de knooppunten in de boom.

Maar als we de kansvector $\pi _{n}$ ($n=1,2,\ldots$) berekenen voor het geval de vlo start vanuit knooppunt 1, vinden we dat die na verloop van tijd niet naar die waarde gaat maar blijft oscilleren tussen de twee waarden:

${\begin{bmatrix}{\frac {1}{4}}&0&0&{\frac {1}{8}}&{\frac {3}{8}}&{\frac {1}{4}}&0&0&0\end{bmatrix}}$ in de even stappen, en

${\begin{bmatrix}0&{\frac {3}{8}}&{\frac {1}{4}}&0&0&0&{\frac {1}{8}}&{\frac {1}{8}}&{\frac {1}{8}}\end{bmatrix}}$ in de oneven stappen.

Als de vlo vertrekt vanuit knooppunt 2 of 3 is de volgorde van deze twee vectoren omgekeerd. Dit is uiteraard het gevolg van het feit dat de vlo op elk tijdstip van niveau verandert in de boom. Als ze op tijdstip 0 op een "even" niveau begint zal ze op elk volgend even tijdstip ook op een even niveau zijn, en is de kans dat ze zich op een knooppunt van een oneven niveau bevindt noodzakelijkerwijs nul. De limietvector die hierboven berekend is, kunnen we beschouwen als de kans dat de vlo zich op een bepaald knooppunt bevindt op een willekeurig tijdstip in de toekomst.

Als we toelaten dat de vlo mag "rusten" op sommige punten, valt deze oscillatie weg en zal de toestandsvector evolueren naar een vaste limietwaarde. Na een groot aantal sprongen kan de vlo dan immers op elk knooppunt van de boom zitten. In dat geval zullen sommige waarden op de hoofddiagonaal van de overgangsmatrix verschillend van nul zijn.

Toepassingen

Markovketens en markovprocessen worden in velerlei domeinen gebruikt voor het simuleren en analyseren van (computer)modellen van systemen waarvan de toestand geheel of gedeeltelijk van het toeval afhangt. Afhankelijk van de aard van het probleem wordt daarbij het transiënt gedrag van de keten dan wel de limiettoestand onderzocht.

• In de scheikunde kan het klassieke model van de kinetiek van enzym-gekatalyseerde reacties, beschreven door de Michaelis-Mentenvergelijking, voorgesteld worden als een markovketen. Ook de groei en samenstelling van copolymeerketens kan met markovketens geanalayseerd worden.
• In de wachtrijtheorie kan men markovketens inzetten voor het analyseren van wachtrijproblemen en het optimaliseren van telecommunicatienetwerken.
• In de economische en financiële wereld komen markovketens veelvuldig voor bij het modelleren van allerlei fenomenen, zoals bij Leontiefs input-outputanalyse. Het economische aspect komt bijvoorbeeld aan bod als aan een overgang van het systeem een bepaalde opbrengst (positief of negatief, winst of verlies) verbonden is. Men kan dan bepalen wat de verwachte opbrengst is in de volgende $n$ stappen, in functie van de huidige toestand van het systeem (transiënt gedrag), of wat de verwachte opbrengst per stap is op lange termijn.
• De statistiek combineert markovketens met Monte-Carlosimulaties in de zogenaamde MCMC-methode (Markov Chain Monte Carlo). Hierbij onderzoekt men steekproefsgewijs hoeveel stappen er nodig zijn om een vooraf bepaalde, stationaire verdeling van een markovketen te bereiken of te benaderen binnen een bepaalde foutenmarge. De methode wordt o.m. toegepast om meerdimensionale integralen numeriek te berekenen.
• In kwaliteitsmanagement voor het bepalen van de betrouwbaarheid en beschikbaarheid van systemen, bijvoorbeeld van procescontrole- of regelsystemen.
• Veel spellen waarin het toeval een rol speelt kunnen als een markovketen gemodelleerd worden.
• In de muziek kunnen markovketens dienen als basis voor stochastische muziek, zoals bij Iannis Xenakis.
• Bij het berekenen van kans op wolkenvorming worden markovketens toegepast.
• In taalmodellen met kunstmatige intelligentie wordt gebruik gemaakt van de markov-eigenschap.
• Een hidden Markov model is een markovproces met onwaarneembare toestanden. De uitkomsten van het proces hangen op bekende wijze af van een waarneembaar proces en wel zo dat op een bepaald tijdstip de toestand van dit waarneembare proces alleen afhangt van de toestand van de onwaarneembare toestand van het verborgen markovproces. Het doel is kennis over het verborgen proces te verkrijgen op basis van het waarneembare proces.

Voetnoten