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 on kokoelma satunnaismuuttujia. Prosessin tila on ajanahetkellä .
Tässä artikkelissa rajoitutaan prosesseihin, joissa saa arvoja äärellisestä tila-avaruudesta ja on diskreettiaikainen .
Stokastinen prosessi on Markovin ketju, jos
Tätä kutsutaan muistinmenetysominaisuudeksi, muistittomuusominaisuudeksi, tai Markovin ominaisuudeksi. On tärkeä huomata, että muistittomuus ei tarkoita, että olisi riippumaton satunnaismuuttujista . Koko riippuvuus vain tiivistyy muuttujaan .
Siirtymätodennäköisyys on todennäköisyys, että prosessi siirtyy tilasta tilaan . Muistinmenetysominaisuudesta seuraa, että Markovin ketjun voi yksiselitteisesti määritellä siirtymämatriisilla
Siirtymämatriisissa rivin ja sarakkeen arvo on siirtymätodennäköisyys ja siten jokaisella rivillä pätee .<ref name=Mitzenmacher2017 />
Olkoon todennäköisyys, että prosessi on tilassa ajanhetkellä . Olkoon . Nyt voidaan kirjoittaa . Todennäköisyysjakauma on tapana esittää rivivektorina käyttäen matriisikertolaskua merkinnän sijasta. Tämä kuvaa tulkintaa, jolla jakaumasta siirrytään operaatiolla jakaumaan .
Jakaumasta saadaan millä tahansa todennäköisyysjakauma
missä on siirtymämatriisin :s potenssi.
Tilojen luokittelu
Mikäli tila johtaa tilaan positiivisella todennäköisyydellä, sanotaan tilan johtavan tilaan ja sitä merkitään . Toisin sanoen tila johtaan tilaan , jos ja vain jos jollakin .<ref name=Hopeanaula2021 />
Jos tiloista pääsee toisiinsa, sanotaan tilojen kommunikoivan ja se merkitään . Kommunikoivuus on ekvivalenssirelaatio, eli sille pätee Refleksiivisyys, jokaisella tilalla , pätee . Symmetrisyys, jos then . Transitiivisuus, jos ja , niin .
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 , olkoon todennäköisyys, että tasan askeleen päästä siirrytään ensimmäistä kertaan tilaan . Sama voidaan kirjoittaa myös
Tila on toistuva, jos , ja se on tilapäinen, jos .<ref name=Mitzenmacher2017 />
Tasapainojakauma
Tilajakaumasta ja siirtymämatriisista saadaan seuraavan ajanhetken tilajakauma . Tilajakauma on tasapainojakauma kun . 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
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ä.
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
Toinen mielenkiintoinen siirtymämatriisi on
Siirtymämatriisi kuvaa tilannetta, jossa todennäköisyydellä pysytään samassa tilassa, ja todennäköisyydellä vaihdetaan toiseen tilaan.<ref name=Mitzenmacher2017 />
Symmetrisyydestä saadaan, että tasapainojakauma on yksiselitteinen ja :n askeleen siirtymätodennäköisyys on .
Tarkastellaan vielä siirtymämatriisia
Tämä Markovin ketju ei ole yhtenäinen, ja sillä on useita tasapainojakaumia. Jokainen muotoa
oleva jakauma on ketjun tasapainojakauma, kun .
Lähteet
Kirjallisuutta Suomeksi
Englanniksi
Luokka:Stokastiset prosessit Luokka:Seulonnan keskeiset artikkelit