Eindige Markov-keten met discrete tijd-parameter

Bij een eindige Markov-keten bestaat de toestandsruimte uit, zeg, n mogelijke toestanden, die we hier, overeenkomstig de notatie in de vorige paragraaf, van 1 tot n nummeren (soms ligt het ook voor de hand om de nummering bij 0 te beginnen). De tijd-parameter doorloopt de verzameling .

De evolutie van een eindige Markov-keten met discrete tijd-parameter wordt bepaald door zijn overgangsmatrix P. Hierin geeft het element op de i-de rij, j-de kolom de kans aan dat de toestand op tijdstip t gelijk aan j zal zijn, gegeven dat de toestand op tijdstip t-1 gelijk aan i was:

Laat de kansverdeling van zijn:

De kans om op tijdstip t in toestand j te zijn wordt berekend door uit te gaan van de kansverdeling op tijdstip t-1 en voor elke toestand i de kans op een overgang van i naar j in aanmerking te nemen.

In matrixnotatie kan dit kortweg geschreven worden als:

We kunnen, uitgaande van een gegeven kansverdeling , t maal de kansverdeling rechts vermenigvuldigen met P, om zo bij uit te komen:

We beschouwen de inhoud van een berichtenbuffer als een discrete tijd Markov-proces. is het aantal berichten in de buffer aan het eind van het t-de interval. Het t-de interval duurt van tijdstip t-1 tot tijdstip t. De binnenkomst van een bericht valt precies samen met een interval en berichten die arriveren als de buffer vol is gaan verloren. Alleen als er geen aankomst is en als de buffer niet leeg is dan wordt in een interval één bericht verwerkt. De kans op een aankomst in een interval is 0.2.

Gevraagd: De matrix van overgangskansen en de kansverdeling van het aantal berichten in de buffer op t=3, gegeven dat de buffer leeg is op t=0.

Uit bovenstaande beschrijving volgt dat als de buffer leeg dan kan er met kans 0.2 één bericht bij komen of er gebeurt niets. Als er één bericht in de buffer is dan komt er met kans 0.2 nog één bij of, met kans 0.8, gaat er één weg. Als de buffer vol is dan verdwijnt er één bericht met kans 0.8 of de buffer blijft vol. Deze drie zinnen zijn samengevat in de drie regels van de overgangsmatrix P:

Het gegeven dat de buffer leeg op t=0 laat zich vertalen in de begin verdeling waarbij alle kansmassa in het eerste element zit (met kans 1 zijn er nul berichten in de buffer):

De kansverdeling op t=3 is volgens (4.15) gelijk aan . Omdat we al eerder de producten en hebben uitgerekend, ontbinden we in die twee factoren, zodat hier nog maar één vector-matrixproduct berekend hoeft te worden.

Voor de overgangsmatrices die redelijkerwijs voorkomen geldt, dat op den duur (als ) de kansverdeling van naar een limiet V gaat die niet meer afhangt van de begin verdeling . Markov-ketens waarvoor zo'n limiet V bestaat worden regulier genoemd.

Niet-reguliere Markov-ketens hebben te maken met pathologische gevallen waarin er met kans 1 een cyclus van toestanden doorlopen wordt of waarin de toestandsruimte kan worden opgedeeld in twee of meer deelverzamelingen zodanig dat er geen overgangen tussen die deelverzamelingen voorkomen. Ook kan het zijn dat de evenwichtsverdeling niet bestaat omdat bij een oneindige Markov-keten de waarschijnlijksheidmassa zich steeds verder naar rechts verplaatst (de verwachtingswaarde van wordt steeds groter als ); dit komt bijvoorbeeld voor bij een wachtrijsysteem waar de aankomst- intensiteit groter is dan de verwerkingsintensiteit.

Voor reguliere Markov-ketens is de evenwichtsverdeling V gedefinieerd als

Bij het berekenen van achtereen volgens , , ziet men dat de verandering van deze kansverdeling steeds geringer wordt. gaat in de limiet naar de kansverdeling V waarvoor geldt dat nog eens vermenigvuldigen met P in het geheel geen verandering van de kansverdeling tot gevolg heeft. Dus de evenwichtsverdeling V voldoet aan het volgende stelsel lineaire vergelijkingen:

Men is geïnteresseerd in het berekenen van de evenwichtsverdeling omdat dit het lange termijn gedrag van een systeem kwantificeert. Bijvoorbeeld de evenwichtskans dat de buffer vol is, is op de lange termijn gelijk aan de fractie van de tijd dat de buffer vol is. Hieruit volgt dan weer hoe groot de fractie van de berichten die verloren gaat is.

Eén mogelijkheid om de evenwichtsverdeling te berekenen is via formule (4.20). Als we I definiëren als de eenheidsmatrix (op de diagonaal 1-en en verder overal 0), en O als de nul-vector (overal 0) dan is (4.20) ook te schrijven als:

Dit zijn n vergelijkingen met n onbekenden maar het zijn niet n onafhankelijke vergelijkingen. Dit blijkt al uit het linker lid, waarin alleen nullen staan. Dit betekent dat als V een oplossing is dan is een willekeurig veelvoud van V ook een oplossing. Om de oplossing eenduidig vast te leggen moeten we gebruik maken van het gegeven dat de som van de kansen gelijk aan 1 is. Dat geeft als extra vergelijking de normeringsvergelijking:

Als men de beschikking heeft over een routine voor matrixinversie, zoals die bijvoorbeeld als standaardfunctie in het spreadsheet programma Lotus 123 vanaf versie 2 zit, dan kan hiervan als volgt gebruik gemaakt worden om de evenwichtsverdeling te berekenen:

1. Construeer de matrix M door in de laatste kolom te vervangen door een kolom van 1-en (een willekeurige andere kolom is ook mogelijk, dit verandert de positie van de 1 in de hieronder gedefinieerde vector E).
2. Definieer de liggende vector
3. dan is de evenwichtsverdeling:

Voor het model van de berichtenbuffer van voorbeeld 4.3 willen we de fractie van de tijd dat de buffer vol is weten.

We construeren de matrix M, door in de overgangsmatrix P de diagonaal-elementen met 1 te verminderen en de rechter kolom te vervangen door 1-en:

met behulp van bijvoorbeeld Lotus 123 vinden we:

De evenwichtsverdeling van de Markov-keten, V, wordt nu gegeven door:

De evenwichtsverdeling is te interpreteren als de fractie van de tijd dat het proces in de verschillende toestanden is. Dus de buffer is vol voor een fractie 0.048 van de tijd.

Bij het definiëren van een Markov-keten is het altijd nuttig om het bijbehorende toestandsdiagram te tekenen. Voor een eindige Markov-keten met discrete tijd-parameter ziet dit er als volgt uit:

• Voor elke toestand een cirkel met in de cirkel het nummer van die toestand
• Voor elke een pijl van cirkel i naar cirkel j, met naast de pijl de waarde van

 
Figuur: Toestandsdiagram van een discrete-tijd Markov-keten. Dit is niet de meest algemene vorm, omdat hier alleen overgangen plaatsvinden naar toestanden met een nummer dat één hoger of één lager is. 

Het berekenen van de evenwichtsverdeling kan nog eenvoudiger dan volgens (4.21) en (4.22) gebeuren in het geval dat vanuit toestand i alleen maar overgangen mogelijk zijn naar toestanden i-1, i+1 en i zelf. Het bijbehorende ``n dimensionale'' toestandsdiagram is weergegeven in figuur 4.1. 

In dit geval volgt uit evenwichtsoverwegingen dat de kans op een overgang van i naar i+1 even groot moet zijn als de kans op een overgang van i+1 naar i. Er vindt een overgang plaats van i naar i+1 als de toestand gelijk is aan i (kans ) en als gegeven toestand i de bestemming i+1 gekozen wordt (kans ). Met dezelfde redenering vinden we de kans op een overgang van i+1 naar i. Het gelijkstellen van deze kansen levert:

Dit leidt tot het volgende algoritme om de evenwichtsverdeling V te berekenen.

Ga uit van een ongenormeerde verdeling W, gedefinieerd door:

Bepaal :

Dan wordt de evenwichtsverdeling V gegeven door:

Gegeven een discrete-tijd Markov-keten met het toestandsdiagram als gegeven in figuur4.2:

 
Figuur: Toestandsdiagram bij voorbeeld 4.5.  

Gevraagd: De evenwichtsverdeling van deze Markov-keten.

Merk op dat dit de Markov-keten is van het voorbeeld van de berichtenbuffer. We kunnen dus het gevraagde antwoord aflezen uit de berekening van voorbeeld 4.4. Echter, we willen hier de eenvoudige structuur van het toestandsdiagram gebruiken, om zonder matrixinversie de evenwichtsverdeling te vinden.

We passen de formules (4.28)--(4.31) toe en vinden zo:

en de gevraagde evenwichtsverdeling: