Markovketjuihin

Markovketjuihin (engl. Markov chains) ovat stokastisia prosesseja, joissa järjestyksen seuraava tila riippuu vain nykyisestä tilasta eikä aiemmista tiloista. Tämä Markovin ominaisuus tarkoittaa, että X_{n+1} riippuu X_n:stä ainoastaan, ei siitä, miten tilaan on päädytty. Ketjut koostuvat tilojen joukosta S ja siirtymistä niiden välillä, joita kuvaavat todennäköisyydet.

Ketjuja on monenlaisia. Diskreetin ajan Markovketjut (DTMC) muuttuvat askel askeleelta, ja siirtymät määritellään siirtomatriisilla P, jossa p_{ij} on todennäköisyys siirtyä tilasta i tilaan j seuraavalla askeleella. Jatkuvan ajan Markovketjut (CTMC) kuvaavat tapahtumia, jotka tapahtuvat jatkuvassa ajassa generatorilla Q, jossa q_{ij} (i ≠ j) on siirtymisen tahti tilasta i tilaan j ja q_{ii} = -∑_{j≠i} q_{ij}.

Keskeisiä käsitteitä ovat tilat ja niiden yhteydet, pysyvä jakauma π, sekä ominaisuudet kuten irreducibiliteetti ja aperiodisuus. Kun ketju on irreducible ja aperiodinen, se convergoituu loppuun riippumatta alkuperäisestä tilasta, ja tilastoja voidaan kuvata pysyvällä jakaumalla. Pysyvän jakauman löytäminen on usein tavoiteltavaa käytännössä; DTMC:ssä se täyttää πP = π ja ∑_i π_i = 1, CTMC:ssä π Q = 0.

Esimerkki: kaksitasinen DTMC, jossa tilat A ja B. A→A 0,7, A→B 0,3, B→A 0,4, B→B 0,6. Tämänkaltaiset mallit soveltuvat esimerkiksi puhe- ja kielimallinnukseen, genomitutkimukseen, taloustieteeseen, queueing-theoryyn sekä Monte Carlo -menetelmiin (Markov-ketjut Monte Carlo -menetelmät). Markovketjuja käytetään laajasti tilastollisissa malleissa ja laskennassa, joissa muistia ei tarvita pitkäaikaisesti.