Overgangsmatrices

Overgangsmatrices zijn vierkante matrices die de overgangs- of sprongkansen tussen toestanden in een stochastisch proces vastleggen. In de context van discrete-time Markov-ketens (DTMC) geven zij aan hoe waarschijnlijk het is dat de keten na één stap in een bepaalde toestand terechtkomt, afhankelijk van de huidige toestand. Een overgangsmatrix wordt meestal aangeduid met P.

De i-de rij van P geeft de kansen om in één stap van toestand i naar elke mogelijke volgende toestand te gaan. Alle entries zijn niet-negatief en de rij som van elke i-th rij is gelijk aan 1, waardoor P een rij-stochastische matrix is. In veel bronnen wordt gewerkt met de evolutie van een verdeling p_t als p_{t+1} = p_t P (waar p_t een 1×n rij-vector is). Een alternatieve conventie gebruikt kolomvormige verdelingen met X_{t+1} = P^T X_t, waarin kolom-sommen 1 zijn.

Een stationaire verdeling π is een vector met π = π P, met ∑ π_i = 1 en π_i ≥ 0. Indien de keten irreducibel en aperiodiek is, bestaat er een unieke stationaire verdeling en convergeert P^n naar een matrix waarvan elke rij gelijk is aan π, waardoor de langetermijnverdeling onafhankelijk is van de starttoestand. Voor een voorbeeld, laat P = [[0.7, 0.3], [0.4, 0.6]]. Dan is π = [4/7, 3/7] ≈ [0.571, 0.429], en de lange termijn verdelingen volgen deze verdeling.

Voor continue-time Markov-ketens (CTMC) geldt een generatormatrix Q: off-diagonale entries q_ij ≥ 0, diagonaal q_ii = −∑_{j≠i} q_ij, zodanig dat rijen van Q optellen tot 0. De overgangsprobabiliteiten over tijd t worden gegeven door P(t) = exp(t Q).

Overgangsmatrices worden toegepast in tal van domeinen zoals wachtrijmodellen, genetica, economie en informatiezoekalgoritmen (bijv. PageRank). Ze bieden een wiskundig raamwerk voor het analyseren van systemen die evolueren over tijd door geheugenloze toestandsveranderingen.

---