3.3 Matematička formulacija Metropolis - Hestingovog algoritma
Metropolis algoritam opisuje pravila prelaska kod Markovljevih lanaca koristeći simetričnu predloženu funkciju dok Hesting (1970) proširuje ovaj algoritam slučajem u kome T ne mora nužno biti simetrična [17]. Jedina restrikcija Hestingove metode jeste da za predloženu funkciju T mora važiti ako i samo ako je . Metropolis - Hesting algoritam se može opisati sledećim koracima:
-
odabrati iz predložene raspodele .
-
odabrati i izračunati
Hesting za funkciju predlaže:
Ukoliko je T simetrična funkcija tada je ovaj algoritam identičan Metropolis algoritmu. Još neke od predloga za funkciju su dali Barker [18]:
i Čarls Stejn (eng. Charls Stein):
(2.1)
gde je bilo koja simetrična funkcija za koju važi za svako i Ukoliko je funkcija odbacivanja oblika (2.1) i tada je verovatnoća prelaska iz u jednaka:
Kako je funkcija simetrična odatle sledi da je
, (2.2)
tj. da je Markovljev lanac reverzibilan, a invarijantna raspodela. Jednakost 2.2 se naziva i detaljna uravnoteženost (end. detailed balance), pomoću koje možemo dokazati da važi:
.
Dokaz:
.
Zbog ovoga detaljna uravnoteženost obezbeđuje invarijantrnost, a svaki Markovljev lanac koji zadovoljava ovaj uslov je reverzibilan.
Pokažimo sada da uslov detaljne uravnoteženosti važi i kod Metropolis-Hestingovog algoritma. U slučaju da je verovatnoća prelaska iz u jednaka je proizvodu predložene verovatnoće Ti verovatnoće prihvatanja koraka tj:
pa je stoga,
=
što predstavlja simetričnu funkciju po i , zbog čega je uslov detaljne uravnoteženosti zadovoljen.
Uopštenije, ako je funkcija prelaska oblika
gde je simetrična funkcija po i takva da važi onda se lako može ustanoviti da je uslov detaljne uravnoteženosti zadovoljen i da se Metropolis funkcija prelaska može zapisati kao:
Ukoliko se koristi Barkerovo pravilo prihvatanja tada je funkcija prelaska sledećeg oblika:
Prema standardnoj teoriji Markovljevih lanaca [7], ukoliko je lanac nesvodljiv3, aperiodičan4 i ima invarijantnu raspodelu nakon koraka, lanac će konvergirati ciljanoj raspodeli
Dostları ilə paylaş: |