Markovprosesser

Markovprosesser är stokastiska processer som uppfyller Markov-egenskapen: framtida tillstånd beror endast på nuvarande tillstånd och inte på tidigare tillstånd. Tillståndsrymden S kan vara fin eller oändlig, och tiden kan vara diskret eller kontinuerlig. För varje tidpunkt finns övergångssannolikheter mellan tillstånden.

Diskreta tidens Markovkedjor (DTMC) kännetecknas av en övergångsmatris P där p_{ij} är sannolikheten att gå från i till j i nästa tidssteg. Chapman–Kolmogorov-ekvationerna gör det möjligt att beräkna sannolikheter efter flera steg: P^{(n+m)} = P^{(n)} P^{(m)}. En initialfördelning och en stationär distribution π uppfyller ofta π P = π.

Kontinuerliga Markovkedjor (CTMC) har en semigrupp P_t, där t ≥ 0, och en generator Q. För finita tillstånd är Q en kvadratisk matris med q_{ij} ≥ 0 i ≠ j och raderna summan till noll. Sannolikheter för tid t ges ofta av P_t = exp(Qt). Kedjan följs av framåt- och bakåt-ekvationer.

Viktiga egenskaper är irreducibilitet, ergodicitet och existensen av en stationär distribution. Reversibilitet uppstår när detaljerna balans uppfylls: π_i q_{ij} = π_j q_{ji}.

Vanliga exempel är en enkel slumpvandring i diskret tid, birth–death-processer och Poissonprocessen i kontinuerlig tid. Anpassningar används inom köteori, finans, biologi, datavetenskap och andra områden där man vill modellera system med minneslös stokastik.