Algoritmus Metropolis-Hastings je vzorkovací algoritmus používaný hlavně pro komplexní distribuční funkce . Je to trochu podobné algoritmu vzorkování rozptylu , zde se však pomocná distribuční funkce v průběhu času mění. Algoritmus poprvé publikoval Nicholas Metropolis v roce 1953 a poté jej v roce 1970 zobecnil C. Hastings . Gibbsovo vzorkování je speciálním případem algoritmu Metropolis-Hastings a je populárnější díky své jednoduchosti a rychlosti, i když méně často použitelné.
Algoritmus Metropolis-Hastings umožňuje vzorkovat jakoukoli distribuční funkci. Je založen na vytvoření Markovova řetězce , to znamená, že v každém kroku algoritmu závisí nově zvolená hodnota pouze na předchozí . Algoritmus používá pomocnou distribuční funkci v závislosti na , pro kterou je snadné vygenerovat vzorek (například normální rozdělení ). V každém kroku je pro tuto funkci vygenerována náhodná hodnota . Pak s pravděpodobností
(nebo s pravděpodobností 1 if ), vybraná hodnota je přijata jako nová: , jinak je ponechána stará: .
Pokud například vezmeme normální distribuční funkci jako pomocnou funkci, pak
Taková funkce vytvoří novou hodnotu v závislosti na hodnotě v předchozím kroku. Zpočátku Metropolisův algoritmus vyžadoval, aby pomocná funkce byla symetrická: , ale Hastingsovo zobecnění toto omezení odstraňuje.
Předpokládejme, že jsme již vybrali náhodnou hodnotu . Chcete-li vybrat další hodnotu, nejprve získejte náhodnou hodnotu funkce . Poté najdeme produkt , kde
je poměr pravděpodobností mezi střední hodnotou a předchozí hodnotou a
je poměr mezi pravděpodobnostmi přechodu z do nebo zpět. Pokud je symetrický, pak je druhý faktor roven 1. Náhodná hodnota v novém kroku se volí podle pravidla:
Algoritmus začíná od náhodné hodnoty a nejprve „nečinně“ provede řadu kroků, aby „zapomněl“ na počáteční hodnotu.
Algoritmus funguje nejlépe, když je tvar pomocné funkce blízký tvaru účelové funkce . Toho je však často a priori nemožné dosáhnout. K vyřešení tohoto problému je pomocná funkce laděna během přípravné fáze algoritmu. Například pro normální rozdělení upravte jeho parametr tak, aby se podíl „akceptovaných“ náhodných hodnot (tedy těch, pro které ) blížil 60 %. Pokud je příliš malý, hodnoty budou příliš blízko a míra přijetí bude vysoká. Pokud je příliš velký, pak s vysokou pravděpodobností nové hodnoty vyskočí do zón nízké pravděpodobnosti , proto bude podíl přijatých hodnot nízký.