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 successievelijke toestanden van het systeem worden beschreven door een rij stochastische variabelen ${\displaystyle X_{0},X_{1},X_{2},\ldots }$ met respectievelijke kansverdelingen ${\displaystyle \pi _{0},\pi _{1},\pi _{2},\ldots }$, waarin ${\displaystyle X_{n))$ de toestand van het systeem is na ${\displaystyle n}$ stappen. De markov-eigenschap wordt uitgedrukt in een eigenschap van de overgangskansen.

Definitie

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

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

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

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

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

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

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

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

${\displaystyle 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 enkel van toestand veranderen op regelmatige tijdstippen.

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 ${\displaystyle n}$. Als de overgangskansen niet variëren in de tijd noemt men de markovketen homogeen;
• Men kan een markovketen van orde ${\displaystyle m}$ beschouwen waarvan de eenstapsovergangskansen niet slechts afhangen van de vorige toestand, maar van ${\displaystyle m}$ vorige toestanden (${\displaystyle m>1}$):

${\displaystyle 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 enkel 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 (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 geweest is. Hij kiest daarom met gelijke kansen naar een van de aangrenzende vertrekken te gaan.

Het systeem laat zich mooi beschrijven met een gewogen, gerichte graaf:

Een typisch verloop kan zijn dat de muis zich aanvankelijk in vertrek 5 bevindt. Van daaruit kan hij, met voor elk kans 1/4, naar een van de vertrekken 2, 3, 4 en 7. Het leven van de muis, dat we een realisatie van het proces noemen, kan er schematisch zo uitzien: 5 4 1 4 1 2 5 7 6 7 8(bam!). Met meer geluk zou het kunnen zijn: 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, een aanmerkelijk langer leven.

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

${\displaystyle P={\begin{bmatrix}0&1/2&0&1/2&0&0&0&0\\1/3&0&1/3&0&1/3&0&0&0\\0&1/2&0&0&1/2&0&0&0\\1/2&0&0&0&1/2&0&0&0\\0&1/4&1/4&1/4&0&0&1/4&0\\0&0&0&0&0&0&1&0\\0&0&0&0&0&1/2&0&1/2\\0&0&0&0&0&0&0&1\end{bmatrix))}$

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

Aan de hand van deze matrix kan men de kans berekenen dat de muis vanuit kamer 5 precies het pad 5 4 1 4 1 2 5 7 6 7 8 volgt; het is de combinatie van de overgangskansen 5→4, 4→1, 1→4, 4→1 enz. Omwille van de markov-eigenschap is deze combinatie gewoon het product van deze overgangskansen:

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

${\displaystyle ={\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 ${\displaystyle n}$ wordt beschreven door een rijvector ${\displaystyle \pi _{n))$. Het aantal elementen van deze vector is gelijk aan het aantal mogelijke toestanden van het systeem (het aantal kamers in het huis in dit voorbeeld) en het ${\displaystyle i}$-de element in de vector is de kans dat het systeem zich in toestand ${\displaystyle i}$ bevindt op tijdstip ${\displaystyle n}$; dus de kans dat de muis in kamer ${\displaystyle i}$ is na ${\displaystyle n}$ tijdstippen.

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

${\displaystyle \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 voor elke overgang is gelijk aan 1/4. Dit betekent dat op tijdstip 1 de muis met een kans gelijk aan 1/4 aangetroffen wordt in de kamers 2, 3, 4 en 7, en met kans 0 in de andere kamers. Dus

${\displaystyle \pi _{1}={\begin{bmatrix}0&1/4&1/4&1/4&0&0&1/4&0\end{bmatrix))}$

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

De kansverdeling op tijdstip 2 ontstaat op dezelfde manier

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

In het algemeen geldt

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

Na honderd stappen is de toestandsvector geëvolueerd tot

${\displaystyle \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 ${\displaystyle P}$). De toestandsvector ${\displaystyle \pi _{n))$ is in de limiet, voor stijgende ${\displaystyle n}$, invariant, dus er geldt

${\displaystyle \pi \cdot P=\pi }$

zodat

${\displaystyle \pi ={\begin{bmatrix}0&0&0&0&0&0&0&1\end{bmatrix))}$,

wat betekent: het staat vast dat de muis ooit in kamer 8 terechtkomt. Deze asymptotische verdeling is onafhankelijk van de begintoestand ${\displaystyle \pi _{0))$: waar de muis zich ook bevond bij de aanvang, ooit zal ze in toestand/kamer 8 terechtkomen en er blijven. De toestanden/kamers 1 tot en met 7 hebben een limietkans gelijk aan 0, wat betekent dat ze nooit meer zullen bezet worden na een voldoend lange tijd. Dergelijke toestanden noemt men overgangstoestanden (transient states); een toestand zoals toestand 8 in het voorbeeld is een absorberende toestand (absorbing state of trapping state).

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 limiet-verdeling is hier dus niet meer onafhankelijk van de begintoestand.

De limietvector ${\displaystyle \pi }$ is een eigenvector van de overgangsmatrix, overeenkomend met de eigenwaarde 1. De stelling van Perron-Frobenius zegt dat elke stochastische matrix minstens een zo'n vector heeft (er kunnen er meerdere zijn, zoals in het geval van een markovketen met meerdere absorberende toestanden) en dat 1 de grootste eigenwaarde is van de matrix. De voorwaarde is dat de matrix of de corresponderende markovketen, irreducibel is. Daarvoor moet elke toestand van het systeem bereikbaar zijn vanuit elke andere toestand (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:

${\displaystyle P={\begin{bmatrix}6/10&4/10\\7/10&3/10\end{bmatrix))}$

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

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

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

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

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

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

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

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

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

${\displaystyle \pi _{E}=4/11}$ en ${\displaystyle \pi ={\begin{bmatrix}7/11&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 ${\displaystyle 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 ${\displaystyle i}$ bevindt en exact ${\displaystyle n}$ tijdstippen in dezelfde toestand blijft; dus dat het de volgorde ${\displaystyle \{i,i,\ldots ,i,j\))$ doorloopt waarin er ${\displaystyle n-1}$ maal een "overgang" van ${\displaystyle i}$ naar ${\displaystyle i}$ gebeurt gevolgd door een overgang van ${\displaystyle i}$ naar ${\displaystyle j}$, waarin ${\displaystyle j}$ verschilt van ${\displaystyle i}$. Die kans is:

${\displaystyle 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:

${\displaystyle \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

Een binaire boom

Een toevalsbeweging ("random walk") 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:

${\displaystyle P={\begin{bmatrix}0&1/2&1/2&0&0&0&0&0&0\\1/3&0&0&1/3&1/3&0&0&0&0\\1/2&0&0&0&0&1/2&0&0&0\\0&1&0&0&0&0&0&0&0\\0&1/3&0&0&0&0&1/3&1/3&0\\0&0&1/2&0&0&0&0&0&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 ${\displaystyle \pi }$ voor dit systeem laat zich eenvoudig berekenen; het is

${\displaystyle \pi ={\begin{bmatrix}1/8&3/16&1/8&1/16&3/16&1/8&1/16&1/16&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 ${\displaystyle \pi _{n))$ (${\displaystyle 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:

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

${\displaystyle {\begin{bmatrix}0&3/8&1/4&0&0&0&1/8&1/8&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 chemie kan het klassieke model van de kinetiek van enzym-gekatalyseerde reacties, beschreven door de Michaelis-Menten-vergelijking, 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 ${\displaystyle 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, zie promotie-onderzoek van Jesse Dorrestijn van het Centrum Wiskunde & Informatica (CWI).
• In taalmodellen met kunstmatige intelligentie wordt gebruik gemaakt van de markov-eigenschap.