Markovkjede

En markovkjede er en stokastisk prosess som beveger seg mellom tilstander i et målbart tilstandsrom bestemt av en sannsynlighetsstruktur. I en diskret tidsmarkovkjede (DTMC) avhenger neste tilstand utelukkende av dagens tilstand, ikke av historien. Den kontinuerlige tidsvarianten (CTMC) utvikler seg i kontinuerlige tidstrinn og beskrives ofte med en generator.

En markovkjede består av tre viktige komponenter: tilstandsrommet S, en overgangsmatrise P (for DTMC) der Pij er sannsynligheten for å gå fra tilstand i til tilstand j i neste tidssteg, og en startfordeling som beskriver sannsynligheten for hver tilstand ved tid t=0. For CTMC brukes i stedet en oppsett med en generator Q som beskriver avgangshastigheter mellom tilstander.

Viktige egenskaper inkluderer Markov-egenskapen og Chapman–Kolmogorov-likningen, som knytter sannsynligheter over flere tidssteg sammen (for DTMC: P^{(n+m)} = P^{(n)} P^{(m)}). For langtidsskikk bruker man ofte en stasjonær fordeling pi, som oppfyller pi P = pi og sum(pi)=1. Hvis kjeden er irreducibel og aperiodisk, konvergerer den mot en unik stasjonær fordeling fra enhver startfordeling.

Vanlige anvendelser spenner bredt: språkmodellering og tekstgenerering (n-grammer), nettsøk og PageRank, køteori og serviceoptimalisering i telekommunikasjon og logistikk, finansielle modeller og genetiske prosesser. Beregningene gjøres ofte ved matriseeksponering, eigenverdianalyse og simulering.