Algoritme de Metropolis-Hastings

La distribució de proposta Q proposa el següent punt al qual es podria moure la caminada aleatòria.

En estadística i física estadística, l'algoritme de Metropolis-Hastings és un mètode de Monte Carlo de cadena de Markov (MCMC) per obtenir una seqüència de mostres aleatòries mitjançant una distribució de probabilitat a partir de la qual el mostreig directe és difícil. Aquesta seqüència es pot utilitzar per aproximar la distribució (per exemple, per generar un histograma) o per calcular una integral (per exemple, un valor esperat). Metropolis-Hastings i altres algorismes MCMC s'utilitzen generalment per al mostreig de distribucions multidimensionals, especialment quan el nombre de dimensions és elevat. Per a distribucions unidimensionals, normalment hi ha altres mètodes (per exemple, mostreig de rebuig adaptatiu) que poden retornar directament mostres independents de la distribució, i aquests estan lliures del problema de les mostres autocorrelacionades inherent als mètodes MCMC.

L'algorisme va rebre el nom de Nicholas Metropolis i WK Hastings. Metropolis va ser el primer autor a aparèixer a la llista d'autors de l'article de 1953 Equation of State Calculations by Fast Computing Machines juntament amb Arianna W. Rosenbluth, Marshall Rosenbluth, Augusta H. Teller i Edward Teller. Aquest article va proposar l'algorisme per al cas de les distribucions de propostes simètriques, i durant molts anys va ser conegut com "algorisme de Metropolis". El 1970, Hastings el va ampliar al cas més general. El mètode generalitzat finalment va rebre els dos noms, encara que el primer ús del terme "algorisme de Metropolis-Hastings" no està clar; pot haver aparegut per primera vegada en una revisió de Chib i Greenberg de 1995.

L'algorisme de Metropolis-Hastings pot extreure mostres de qualsevol distribució de probabilitat amb densitat de probabilitat $P(x)$, sempre que coneguem una funció $f(x)$ proporcional a la densitat $P$ i els valors de $f(x)$ es poden calcular. El requisit que $f(x)$ només ha de ser proporcional a la densitat, en lloc de ser exactament igual a ella, fa que l'algorisme de Metropolis-Hastings sigui especialment útil, perquè calcular el factor de normalització necessari sovint és extremadament difícil a la pràctica.

L'algorisme de Metropolis–Hastings funciona generant una seqüència de valors de mostra de manera que, a mesura que es produeixen més i més valors de mostra, la distribució de valors s'aproxima més a la distribució desitjada. Aquests valors de mostra es produeixen de manera iterativa, amb la distribució de la mostra següent depenent només del valor de la mostra actual (per tant, la seqüència de mostres es converteix en una cadena de Markov). Concretament, a cada iteració, l'algoritme tria un candidat per al següent valor de mostra en funció del valor de mostra actual. Aleshores, amb certa probabilitat, el candidat és acceptat (en aquest cas el valor candidat s'utilitza a la següent iteració) o rebutjat (en aquest cas el valor candidat es descarta i el valor actual es reutilitza a la següent iteració): la probabilitat. d'acceptació es determina comparant els valors de la funció $f(x)$ dels valors mostrals actuals i candidats respecte a la distribució desitjada.