Markovin ketju

Markovin ketju on stokastinen prosessi, jolla mallinnetaan tapahtumaketjuja, joissa nykyinen tila määrittelee täysin seuraavan tilan todennäköisyyden. Toisin sanoen, jos tietää nykyisen tilan, Markovin ketjuissa menneistä tiloista ei saa enempää apua tulevaisuuden ennustamiseen. Se saa nimensä matemaatikolta Andrei Markov.

Määritelmä ja merkinnät

Stokastinen prosessi $\mathbf {X} =\{X(t)\colon t\in T\}$ on kokoelma satunnaismuuttujia. Prosessin tila on $X(t)$ ajanahetkellä $t$.

Tässä artikkelissa rajoitutaan prosesseihin, joissa $X(t)$ saa arvoja äärellisestä tila-avaruudesta $\{1,2,\ldots ,n\}$ ja on diskreettiaikainen $T=\mathbb {N}$.

Stokastinen prosessi $X_{0},X_{1},X_{2},\ldots$ on Markovin ketju, jos $$\mathbb {P} (X_{t}=a_{t}\mid X_{t-1}=a_{t-1},X_{t-2}=a_{t-2},\dots ,X_{0}=a_{0})=\mathbb {P} (X_{t}=a_{t}\mid X_{t-1}=a_{t-1}).$$ Tätä kutsutaan muistinmenetysominaisuudeksi, muistittomuusominaisuudeksi, tai Markovin ominaisuudeksi. On tärkeä huomata, että muistittomuus ei tarkoita, että $X_{t}$ olisi riippumaton satunnaismuuttujista $X_{0},X_{1},\ldots ,X_{t-2}$. Koko riippuvuus vain tiivistyy muuttujaan $X_{t-1}$.

Siirtymätodennäköisyys $P_{i,j}=\mathbb {P} (X_{t}=j\mid X_{t-1}=i)$ on todennäköisyys, että prosessi siirtyy tilasta $i$ tilaan $j$. Muistinmenetysominaisuudesta seuraa, että Markovin ketjun voi yksiselitteisesti määritellä siirtymämatriisilla $$\mathbf {P} ={\begin{bmatrix}P_{1,1}&P_{1,2}&\cdots &P_{1,n}\\P_{2,1}&P_{2,2}&\cdots &P_{2,n}\\\vdots &\vdots &\ddots &\vdots \\P_{n,1}&P_{n,2}&\cdots &P_{n,n}\\\end{bmatrix}}.$$ Siirtymämatriisissa rivin $i$ ja sarakkeen $j$ arvo on siirtymätodennäköisyys $P_{i,j}$ ja siten jokaisella rivillä $i$ pätee $\sum _{j=1}^{n}P_{i,j}=1$.

Olkoon $p_{i}(t)$ todennäköisyys, että prosessi on tilassa $i$ ajanhetkellä $t$. Olkoon $\mathbf {p} (t)=(p_{0}(t),p_{1}(t),\ldots ,p_{n}(t))$. Nyt voidaan kirjoittaa $\mathbf {p} (t)=\mathbf {p} (t-1)\mathbf {P}$. Todennäköisyysjakauma on tapana esittää rivivektorina käyttäen matriisikertolaskua $\mathbf {p} \mathbf {P}$ merkinnän $\mathbf {P} \mathbf {p}$ sijasta. Tämä kuvaa tulkintaa, jolla jakaumasta $\mathbf {p} (t-1)$ siirrytään operaatiolla $\mathbf {P}$ jakaumaan $\mathbf {p} (t)$.

Jakaumasta $\mathbf {p} (t)$ saadaan millä tahansa $m\geq 0$ todennäköisyysjakauma $\mathbf {p} (t+m)=\mathbf {p} (t)P^{m}$ missä $P^{m}$ on siirtymämatriisin $m$:s potenssi.

Tilojen luokittelu

Mikäli tila $i$ johtaa tilaan $j$ positiivisella todennäköisyydellä, sanotaan tilan $i$ johtavan tilaan $j$ ja sitä merkitään $i\rightarrow j$. Toisin sanoen tila $i$ johtaan tilaan $j$, jos ja vain jos $P_{i,j}^{n}>0$ jollakin $n\geq 0$.

Jos tiloista pääsee toisiinsa, sanotaan tilojen kommunikoivan ja se merkitään $i\leftrightarrow j$. Kommunikoivuus on ekvivalenssirelaatio, eli sille pätee

• Refleksiivisyys, jokaisella tilalla $i$, pätee $i\leftrightarrow i$.
• Symmetrisyys, jos $i\leftrightarrow j$ then $j\leftrightarrow i$.
• Transitiivisuus, jos $i\leftrightarrow j$ ja $j\leftrightarrow k$, niin $i\leftrightarrow k$.

Jos kaikki tilat kuuluvat samaan kommunikaatioluokkaan, sanotaan Markovin ketjun olevan yhtenäinen. Äärellinen Markovin ketju on yhtenäinen jos ja vain jos sitä vastaava siirtymäkaavio on vahvasti yhtenäinen.

Aloittaessa tilasta $i$, olkoon $r_{i,j}^{t}$ todennäköisyys, että tasan $t$ askeleen päästä siirrytään ensimmäistä kertaan tilaan $j$. Sama voidaan kirjoittaa myös $$r_{i,j}^{t}=\mathbf {P} (X_{t}=j{\text{ ja kaikilla }}1\leq s\leq t-1{\text{ pätee }}X_{s}\not =j\mid X_{0}=i).$$ Tila $i$ on toistuva, jos $\sum _{t\geq 1}r_{i,i}^{t}=1$, ja se on tilapäinen, jos $\sum _{t\geq 1}r_{i,i}^{t}<1$.

Tasapainojakauma

Tilajakaumasta $p(t)$ ja siirtymämatriisista $\mathbf {P}$ saadaan seuraavan ajanhetken tilajakauma $p(t+1)=p(t)\mathbf {P}$. Tilajakauma $\pi$ on tasapainojakauma kun $\pi =\pi \mathbf {P}$. Jos Markovin ketju ikinä saavuttaa tasapainojakauman, se säilyttää kyseisen jakauman kaikkina tulevina ajanhetkinä. Äärellisillä yhtenäisillä Markovin ketjuilla on aina tasan yksi tasapainojakauma.

Esimerkkejä

Säätila on yleinen esimerkki, jota voidaan mallintaa Markovin ketjulla. Käytetään siirtymämatriisia $$\mathbf {P} ={\begin{bmatrix}0.9&0.1\\0.5&0.5\end{bmatrix}}.$$ Siirtymämatriisi kuvaa tilannetta, jossa aurinkoista päivää seuraa uusi aurinkoinen päivä 90% todennäköisyydellä, ja sateista päivää seuraa uusi sateinen päivä 50% todennäköisyydellä.

Säätilaesimerkkiä vastaava siirtymäkaavio. Aurinkoisen (Sunny) päivän jälkeen on todennäköisemmin aurinkoinen päivä, ja sateisen (Rainy) päivän jälkeen on yhtätodennäköisesti aurinkoinen tai sateinen päivä.

Tarkastellaan tilannetta, jossa ensimmäisenä päivänä on aurinkoista, ja seuraavina päivinä on järjestyksessä sadetta, sadetta, aurinkoista, ja aurinkoista. Tämän ketjun todennäköisyys kaikista mahdollisista neljän tilasiirtymän tapahtumaketjuista on mallin mukaan $$0.1\cdot 0.5\cdot 0.5\cdot 0.9=0.0225.$$

Toinen mielenkiintoinen siirtymämatriisi on $$\mathbf {P} ={\begin{bmatrix}p&1-p\\1-p&p\end{bmatrix}}.$$ Siirtymämatriisi kuvaa tilannetta, jossa todennäköisyydellä $p$ pysytään samassa tilassa, ja todennäköisyydellä $1-p$ vaihdetaan toiseen tilaan.

Symmetrisyydestä saadaan, että tasapainojakauma on yksiselitteinen $\pi =({\frac {1}{2}},{\frac {1}{2}})$ ja $t$:n askeleen siirtymätodennäköisyys on $\mathbf {P} _{1,1}^{t}={\frac {1}{2}}+{\frac {1}{2}}(2p-1)^{t}$.

Tarkastellaan vielä siirtymämatriisia $$\mathbf {P} ={\begin{bmatrix}{\frac {1}{2}}&{\frac {1}{2}}&0\\{\frac {1}{2}}&{\frac {1}{2}}&0\\0&0&1\end{bmatrix}}.$$ Tämä Markovin ketju ei ole yhtenäinen, ja sillä on useita tasapainojakaumia. Jokainen muotoa $$\pi =\alpha {\begin{bmatrix}{\frac {1}{2}}&{\frac {1}{2}}&0\end{bmatrix}}+(1-\alpha ){\begin{bmatrix}0&0&1\end{bmatrix}}$$ oleva jakauma on ketjun tasapainojakauma, kun $0\leq \alpha \leq 1$.

Suomeksi

• Ketokivi, Mikko: ”Muutoksen selittäminen tutkimuskysymyksenä: latentit muutoskäyrät ja Markovin ketjut”, Tilastollinen päättely ja tieteellinen argumentointi. Helsinki: Gaudeamus Helsinki University Press, 2009. ISBN 978-951-570-778-9
• Saaren-Seppälä, Kyösti: Markovin päätösprosessit. Pro gradu -tutkielma, Helsingin yliopisto, Matematiikan ja tilastotieteen laitos, 2012. Helsinki: Helsingin yliopisto. Pysyvä linkki.
• Palmu, Sanna: Markovin päätöksentekoprosesseista. Pro gradu -tutkielma, Turun yliopisto, sovellettu matematiikka, 2003. Turku: Turun yliopisto. Pysyvä linkki. Viitattu 7.5.2026.
• Peltonen, Jouni Kalervo: Markovin päätösprosessit. Pro gradu -tutkielma, Helsingin yliopisto, matemaattis-luonnontieteellinen tiedekunta, matematiikan laitos, 1989. Helsinki: Jouni Kalervo Peltonen. Pysyvä linkki. Viitattu 7.5.2026.
• Korolainen, Sakari: Epätäydellinen tieto Markovin ohjausprosessin sovellutuksissa. (School of Business) Pro gradu -tutkielma, Helsingin kauppakorkeakoulu, kansantalous, 1968. HKKK. Pysyvä linkki. Viitattu 7.5.2026.

Englanniksi

• Piunovskiy, Alexey: Counterexamples in Markov Decision Processes. Singapore: World Scientific Publishing Europe Ltd., 2025. doi:10.1142/q0494 ISBN 978-1-80061-675-2 (englanniksi)
• Boucherie, Richard J. & van Dijk, Nico M.: Markov Decision Processes in Practice. Cham: Springer International Publishing, 2017. doi:10.1007/978-3-319-47766-4 ISBN 978-3-319-47764-0 (englanniksi)
• Piunovskiy, A. B.: Examples in Markov Decision Processes. London: Imperial College Press, 2012. doi:10.1142/p809 ISBN 978-1-84816-793-3 (englanniksi)