Markovketjuissa

Markovketju on stokastinen prosessi, jossa seuraava tila riippuu vain nykyisestä tilasta eikä aiemmista tiloista. Tämä “memoriattomuus” tarkoittaa, että ketjun kehitys voidaan kuvata tilojen välisillä siirtymillä. Ketjut jaetaan diskreetin aikavälin Markovketjuihin (DTMC) ja jatkuvan ajan Markovketjuihin (CTMC). Diskreetti aikainen ketju käyttää siirtymämatriisia P, jossa Pij on todennäköisyys siirtyä tilasta i tilaan j seuraavalla askeleella; jokaisen rivin summa on 1. Jatkuvan ajan ketjut kuvataan usein rate-matriisilla Q, jolloin tilan todennäköisyydet seuraavat Kolmogorov'n eteenpäin-yhtälöitä.

Keskeisiä käsitteitä ovat tilojen joukko S, tilojen ominaisuudet sekä siirtymätodennäköisyyksiä määrittävät rakenteet. Irreducibiliteetti tarkoittaa, että jokaisesta tilasta voi päästä mihin tahansa toiseen tilaan ketjun evoluution aikana. Aperiodisuus ja palaavaisuus (positive recurrent) vaikuttavat siihen, lähteekö ketju lopulta oikeudenmukaisen tasaisuun osajakaumaan, eli stationary distributioniin pi. Jos ketju on irreducible ja aperiodinen, se lähestyy pi riippumatta alkutilasta. Absorboivat tilat ovat tiloja, joista ei voi poistua.

Analyysi ja sovellukset hyödyntävät usein eigenarvoja, kovarians- ja sekoamisnopeutta sekä pitkän aikavälin jakaumaa. Sijoitettu stationary distribution pi antaa pitkän aikavälin todennäköisyyksiä tiloihin. Käytännössä Markovketjuja sovelletaan luonnollisessa kielessä ja tekstin mallinnuksessa, geneettisissä malleissa, rahoitus- ja riskimalleissa sekä jonotusteoriana; lisäksi PageRank perustuu Markovketjun vakiojakaumaan.

Esimerkkinä kaksitilan ketju A ja B, jossa P = [[0.9, 0.1], [0.4, 0.6]] ja tilasarja pi = (0.8, 0.2). Tämä osoittaa, miten pitkäaikainen jakauma voidaan laskea siirtymäsäännöistä.