Markovketen

Uit Wikipedia, de vrije encyclopedie
(Doorverwezen vanaf Markov-keten)
Ga naar: navigatie, zoeken

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 de 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 \pi_0, \pi_1, \pi_2,\ldots\,, waarin πn de verwachte toestand van het systeem is na n stappen. De Markov-eigenschap wordt uitgedrukt in een eigenschap van de overgangskansen.

Definitie[bewerken]

Een Markovketen van een systeem met k mogelijke toestanden E = \{1, 2, ... k \}, beschrijft de mogelijke evolutie van het systeem doorheen de tijd, op regelmatige tijdstippen 0, 1, 2, ..., middels een reeks (\pi_0, \pi_1, \pi_2, \ldots)\, van stochastische variabelen over E die berekend worden met:

\pi_n = \pi_{n-1} \cdot P \!

\pi_0 is de begintoestand van het systeem. Het is een vector met k elementen, nl. een waarschijnlijkheidsverdeling over E . Als de begintoestand is vastgelegd, bijvoorbeeld toestand 1, is het eerste element van deze vector 1 en de andere elementen 0. Algemeen geldt dat de elementen van de vector liggen tussen 0 en 1 en dat hun som gelijk is aan 1.

De k-bij-k-matrix P = (p_{ij}) is de (eenstaps)overgangsmatrix. p_{ij} is de waarschijnlijkheid dat het systeem overgaat van toestand i naar toestand j. Anders gezegd: dit is de conditionele waarschijnlijkheid dat het systeem op 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 waarschijnlijkheid enkel afhangt van de toestand op tijdstip n-1 en niet van de voorafgaande toestanden:

P(\pi_n= j| \pi_0=i_0, \pi_1=i_1, \ldots , \pi_{n-1}=i) = P(\pi_n=j|\pi_{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.

Veralgemeningen[bewerken]

De definitie van Markovketen kan op verschillende manieren veralgemeend 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 slechts afhangen van de vorige toestand maar van m vorige toestanden (m is groter dan 1):
P(\pi_n=i_n|\pi_{n-1}=i_{n-1},\pi_{n-2}=i_{n-2},...,\pi_0=i_0) = P(\pi_n=i_n|\pi_{n-1}=i_{n-1}, \ldots \pi_{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[bewerken]

Voorbeeld 1[bewerken]

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 terecht komt. 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.

NyMarkovMuis.png

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

"Gewogen, gerichte graaf van toestanden muis"

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:

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 P het getal op rij i en kolom j de waarschijnlijkheid dat het systeem van toestand i naar toestand j overgaat; hier dus de waarschijnlijkheid dat de muis van kamer i naar kamer j gaat. Dit zijn de getallen bij de pijlen in de bovenstaande graaf. 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 waarschijnlijkheid 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 overgangswaarschijnlijkheden 5-4, 4-1, 1-4, 4-1 enz. Omwille van de Markov-eigenschap, is deze combinatie gewoon het product van deze overgangswaarschijnlijkheden:

kans(54141257678)=P54. P41.P14.P41.P12.P25.P57.P76.P67.P78 =1/4 x 1/2 x 1/2 x 1/2 x 1/2 x 1/3 x 1/4 x 1/2 x 1 x 1/2 = 3,225 x 10-4


De verwachte toestand van het systeem op tijdstip n wordt beschreven door een rijvector \pi_n. Het aantal rijen in de vector is gelijk aan het aantal mogelijke toestanden van het systeem (het aantal kamers in het huis in dit voorbeeld) en het i-de element in de vector is de waarschijnlijkheid dat het systeem zich in toestand i bevindt op tijdstip n; dus de waarschijnlijkheid dat de muis in kamer i is na n tijdstippen.

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 kamer 2, 3, 4 of 7; de kans voor elke overgang is gelijk aan 1/4. Dit betekent dat we op tijdstip 1 de muis met een waarschijnlijkheid gelijk aan 1/4 kunnen aantreffen in kamer 2, 3, 4 en 7 en met waarschijnlijkheid 0 in de andere kamers. Dus

\pi_1 = \begin{bmatrix} 0 & 1/4 & 1/4 & 1/4 & 0 & 0 & 1/4 & 0 \end{bmatrix}.

Deze verdeling bekomen we door het matrixproduct te maken van de rijvector \pi_0 met de stochastische matrix P.

De waarschijnlijkheidsverdeling op tijdstip 2 vinden we op dezelfde manier

\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

\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}.

We zien dat, hoe verder we in de tijd vooruit kijken, 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 in de limiet, voor stijgende n, invariant (er geldt

\pi \cdot P = \pi) en gelijk aan \pi =\begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} ,

wat we kunnen uitdrukken als: het staat vast dat de muis ooit in kamer 8 terechtkomt. Deze asymptotische verdeling is onafhankelijk van de begintoestand \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 limietwaarschijnlijkheid 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 waarschijnlijkheidsverdeling 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 \pi is een eigenvector van de overgangsmatrix, overeenkomend met de eigenwaarde 1. De stelling van Perron-Frobenius zegt dat elke stochastische matrix minstens één 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[bewerken]

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 waarschijnlijkheid dat het zich op het volgende tijdstip nog steeds in toestand A bevindt, gelijk aan 0,6; de waarschijnlijkheid dat het overgaat naar toestand E is gelijk aan 0,4. Als het systeem zich in toestand E bevindt, is de waarschijnlijkheid dat het overgaat naar toestand A groter: 0,7. De stochastische matrix voor dit systeem met toestanden A,E is:

P = \begin{bmatrix} 6/10 & 4/10 \\
7/10 & 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} 6/10 & 4/10 \end{bmatrix}
  • \pi_2 = \pi_1 \cdot P = \begin{bmatrix} 64/100 & 36/100 \end{bmatrix}
  • \pi_3 = \pi_2 \cdot P = \begin{bmatrix} 636/1000 & 364/1000 \end{bmatrix}
  • \pi_4 = \pi_3 \cdot P = \begin{bmatrix} 6364/10000 & 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} 7/10 & 3/10 \end{bmatrix}
  • \pi_2 = \pi_1 \cdot P = \begin{bmatrix} 63/100 & 37/100 \end{bmatrix}
  • \pi_3 = \pi_2 \cdot P = \begin{bmatrix} 637/1000 & 363/1000 \end{bmatrix}
  • \pi_4 = \pi_3 \cdot P = \begin{bmatrix} 6363/10000 & 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 \cdot 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 = 7/11 en dus is

\pi_E = 4/11 en \pi = \begin{bmatrix} 7/11 & 4/11 \end{bmatrix}.

Op lange termijn is de waarschijnlijkheid 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 waarschijnlijkheid 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, ... , 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 waarschijnlijkheid is:

 p_i(n) = (P_{ii})^{n-1} \cdot (1-P_{ii})

De waarschijnlijkheid 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,64.(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[bewerken]

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 pijlen houden we geen rekening). De transitiematrix voor dit systeem met negen mogelijke toestanden, is:

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 \pi voor dit systeem laat zich eenvoudig berekenen; het is

\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 waarschijnlijkheidsvector \pi_n (n=0,1,2,...) 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} 1/4 & 0 & 0 & 1/8 & 3/8 & 1/4 & 0 & 0 & 0 \end{bmatrix} in de even stappen, en
 \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 waarschijnlijkheid dat ze zich op een knooppunt van een oneven niveau bevindt noodzakelijkerwijs nul. De limietvector die hierboven berekend is, kunnen we beschouwen als de waarschijnlijkheid 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[bewerken]

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 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.

Zie ook[bewerken]