Monte karlo metode I primene u bioinformatici master rad

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 nesvodljiv³, aperiodičan⁴ i ima invarijantnu raspodelu nakon koraka, lanac će konvergirati ciljanoj raspodeli