Metropolisin ja Hastingsin algoritmi
Metropolisin ja Hastingsin algoritmi on Markovin ketjuun perustuva Monte Carlo -algoritmi. Se on näytteistysalgoritmi, eli sen avulla voidaan generoida likimäärin tietyn todennäköisyysjakauman mukaisesti jakautunut luku- tai vektorijoukko. Generoitua joukkoa voidaan käyttää esimerkiksi Monte Carlo -integroinnissa.
Metropolisin ja Hastingsin algoritmilla voidaan periaatteessa generoida näytteitä mistä tahansa jakaumasta, kunhan jakauman tiheysfunktion arvot voidaan laskea missä tahansa tila-avaruuden pisteessä. Tiheysfunktio saa myös olla normalisoimaton eli sen integraalin (jatkuvan tila-avaruuden tapauksessa) tai summan (diskreetin tila-avaruuden tapauksessa) koko tila-avaruuden yli ei tarvitse olla yksi. Algoritmi on erityisen hyödyllinen bayesläisessä tilastotieteessä, jossa esiintyy usein analyyttiseltä muodoltaan hyvin monimutkaisia todennäköisyysjakaumia.
Hyvin tunnettu Gibbsin näytteistysalgoritmi on erikoistapaus Metropolisin ja Hastingsin algoritmista. Se on laskennallisesti tehokas mutta vaatii jakaumalta tiettyjä lisäominaisuuksia.
Simuloitavaa jakaumaa kutsutaan kohdejakaumaksi ja merkitään formula_1. Se saa siis olla normalisoimaton. Algoritmi tuottaa realisoituman sellaiselle Markovin ketjulle, jonka invariantti jakauma kohdejakauma on. Ketjun generoimiseksi on generoitava toinen Markovin ketju, ja sen siirtymätodennäköisyyttä pisteestä formula_2 pisteeseen formula_3 merkitään tässä formula_4. Funktio formula_4 on tiheysfunktio muuttujan formula_3 suhteen, ja sitä kutsutaan ehdokasjakaumaksi. Tämän ketjun määrittelevä ehdokasjakauma voidaan valita mielivaltaisesti, kunhan siitä voidaan (jollakin tähän algoritmiin liittymättömällä tavalla) generoida näytteitä kaikilla nykyisen tilan formula_2 arvoilla ja kunhan ehdokasjakauman kantaja sisältää kohdejakauman kantajan. Ehdokasjakauman valinta tosin vaikuttaa huomattavasti algoritmin laskennalliseen tehokkuuteen.
Metropolisin ja Hastingsin algoritmi tarvittavan Markovin ketjun generoimiseen on seuraava: Jos ollaan ketjun alussa, ketjulle on määrättävä alkuarvo sellaiseen pisteeseen, että simuloitava tiheys on siinä nollasta poikkeava. Näin ollen ketjulla on olemassa jokin tila. Olkoon nyt formula_2 ketjun nykyinen tila. Generoidaan ehdokasjakaumasta formula_9 satunnaisluku, jota kutsutaan ehdokasarvoksi ja merkitään formula_3. Kutsutaan nyt Metropolisin ja Hastingsin suhteeksi lukua
Seuraavaksi generoidaan satunnaisluku formula_12 tasajakaumasta formula_13. Jos pätee formula_14, niin sanotaan, että ehdokasarvo hyväksytään, ja asetetaan ketjun seuraavaksi tilaksi ehdokasarvo formula_3. Muutoin ehdokasarvo hylätään ja asetetaan ketjun seuraavaksi tilaksi nykyisen tilan arvo formula_2. Ehdokasarvon hyväksymisen todennäköisyys on siis
Koska ketjun alkupää saattaa riippua voimakkaasti ketjun alkuarvosta, alusta on yleensä syytä poistaa joitakin arvoja. Alkuosan poikkeamista muun ketjun jakaumasta kutsutaan burn in -ilmiöksi. Näin muodostetun ketjun tiloista muodostuu vaaditut ehdot täyttävän Markovin ketjun realisoituma.
Vaikka ehdokasjakaumalla ei teoriassa juuri ole rajoitteita, algoritmin suorituskyvyn kannalta ehdokasjakauman valinta voi olla hyvin kriittinen. Tavallisia ovat esimerkiksi riippumattomaan satunnaisjonoon sekä satunnaiskulkuun perustuvat Metropolisin ja Hastingsin algoritmit.
Satunnaiskulkuun perustuvassa Metropolisin ja Hastingsin algoritmissa ehdokasarvo generoidaan lausekkeella
missä formula_19 on generoitu jostakin ketjun tilasta riippumattomasta jakaumasta. Tavallisin on normaali satunnaiskulku, jossa luvut formula_19 generoidaan nollakeskisestä normaalijakaumasta. Tällöin ehdokasketju on symmetrinen ehdon formula_21 mielessä, joten Metropolisin ja Hastingsin suhde on
Käytännössä ei koskaan voida varmasti todeta, että jokin Metropolisin ja Hastingsin algoritmin tuottama Markovin ketju simuloi hyvin kohdejakaumaa. Usein luotettavin keino on näytehistorioitten silmämääräinen tarkastelu. Näytehistoria on kuvaaja ketjun tilan arvoista tilan indeksien ("ajanhetkien") funktiona.
Satunnaiskulun tapauksessa keskeinen algoritmin tehokkuutta säätelevä parametri on ehdokasjakauman varianssi formula_23. Jos varianssi on liian suuri, algoritmi on tehoton, koska hyväksymistodennäköisyys on alhainen. Jos taas varianssi on liian pieni, ehdokasarvot ovat usein lähellä nykyisiä harvoja. Tällöin ketjusta tulee voimakkaasti autokorreloitunut eli ketjuun on generoitava hyvin monta arvoa, jotta se simuloisi hyvin koko jakaumaa.
Yleisesti näytteistysalgoritmin toimimisen takaavat lauseet ovat suurten lukujen laki je keskeinen raja-arvolause.
Metropolisin ja Hastingsin algoritmin tuottamat Markovin ketjun tilat eivät yleisesti ole toisistaan riippumattomia, joten tavallisesti esitetyt versiot suurten lukujen laista ja keskeisestä raja-arvolauseesta eivät riitä.
Artikkelissa todistetaan Metropolisin ja Hastingsin algoritmille oma suurten lukujen lause. Sen mukaan jos ehdokasjakauman kantaja sisältää kohdejakauman kantajan, niin algoritmin tuottaman otoksen keskiarvo lähestyy kohdejakauman odotusarvoa, kun otoskoko lähestyy ääretöntä. Sama koskee kaikkia muitakin jakauman momentteja, siis esimerkiksi varianssia.
Samoin artikkelissa todistetaan keskeinen raja-arvolause Metropolisin ja Hastingsin algoritmille. Siinä otoskeskiarvon poikkeama odotusarvosta riippuu otoskoon lisäksi esimerkiksi ketjun autokorrelaatiofunktiosta, joten se ei tarjoa yhtä käytännöllistä virhearviota kuin riippumattomien jonojen keskeinen raja-arvolause. Se kuitenkin osoittaa, että otoskesarvo on suurilla otosko'oilla likimain normaalijakautunut ja että sen poikkeama jakauman odotusarvosta eli odotusarvoestimaatin virhe on formula_24-riippuvainen, missä formula_25 on ketjun pituus.