Markovkedja
From Wikipedia, the free encyclopedia
En Markovkedja är inom matematiken en tidsdiskret stokastisk process med Markovegenskapen, det vill säga att processens förlopp kan bestämmas utifrån dess befintliga tillstånd utan kännedom om det förflutna. En Markovkedja som är tidskontinuerlig kallas en Markovprocess.
En markovkedja är en modell som beskriver ett system som alltid befinner sig i ett visst tillstånd. Det kan finnas mer än ett möjligt tillstånd och systemet "hoppar" mellan tillstånden med en viss sannolikhet för varje möjligt hopp. Ett möjligt hopp beskrivs av fråntillstånd, till-tillstånd och sannolikhet. Markovkedjans historia blir en kedja (sekvens) av de tillstånd som den har befunnit sig i. När systemet "hoppar" bestäms nästa tillstånd endast av vilket tillstånd det befinner sig i och det beror inte alls på historien före systemet hoppade till det tillståndet. Detta kallas för "minneslöshet".
En Markovkedja som antar ändligt många värden kan representeras av en övergångsmatris. Givet en sannolikhetsvektor, erhålles sannolikhetsvektorn för nästa steg i kedjan av multiplikation med övergångsmatrisen. Flera steg kan beräknas genom exponentiering av övergångsmatrisen. Det är även möjligt att beräkna processens stationära fördelning, det vill säga vad som händer då processen fortsätter i oändligheten, med hjälp av egenvektorer.
Markovkedjor har många tillämpningsområden, bland annat för att beskriva befolkningsprocesser och inom bioinformatik. Resultaten som ligger till grund för teorin om Markovkedjor framlades 1906 av Andrej Markov.