Markovketting

Een Markovketting, ook wel een Markov-keten genoemd, is een stochastisch proces waarbij de toekomstige toestand alleen afhankelijk is van de huidige toestand en niet van het verleden. Dit wordt de Markov-eigenschap genoemd. Een Markovketting evolueert in discrete tijdstappen (DTMC) of continu in tijd (CTMC).

De ketting heeft een toestandruimte S, die eindig of voor telbaar oneindig kan zijn. Voor DTMC bepaalt een overgangsverdeling P de kans dat de ketting in één stap van toestand i naar toestand j gaat, oftewel P_ij. Voor CTMC wordt gewerkt met een generatormatrix Q, waarin q_ij de snelheid van i naar j aangeeft en q_ii = -sum_{j≠i} q_ij.

Belangrijke concepten zijn onder meer de Chapman-Kolmogorov-vergelijkingen, die multi-stapovergangen beschrijven, en de stationaire verdeling. Een ketting heeft een stationaire verdeling pi als pi = pi P (DTMC) of als Q^T pi = 0 (CTMC) met de voorwaarde sum pi_i = 1. Irreducibiliteit en aperiodiciteit zorgen samen voor convergentie naar een unieke stationaire verdeling in veel gevallen. Absorberende kettingen bevatten toestanden waaraan men vast komt te zitten.

Toepassingen van Markovkettingen zijn onder meer wind- en weersmodellering, wachtrijtheorie, modellering van gebruikersgedrag, taalmodellering en n-grammen, en algoritmes zoals PageRank. Ze worden ook gebruikt in financiën, biologie en genetica, waar waarschijnlijkheidsveranderingen tussen toestanden centraal staan.

Berekeningen omvatten het oplossen van de lineaire vergelijkingen voor de stationaire verdeling en, in CTMC, het oplossen van Q^T pi = 0 met sommatie π_i = 1. Soms worden Markovkettingen ook gesimuleerd, bijvoorbeeld via Markov-keten Monte Carlo methoden.