- Algorithme de Metropolis-Hastings
-
L'algorithme de Métropolis-Hasting est une méthode MCMC. Étant donnée une distribution de probabilité π sur un univers Ω, cet algorithme définit une chaîne de Markov dont la distribution stationnaire est π. Il permet ainsi de tirer aléatoirement un élément de Ω selon la loi π (on parle d'échantillonnage).
Un point essentiel de l'algorithme de Métropolis-Hasting est qu'il ne nécessite que la connaissance de π à constante multiplicative près. En particulier, il n'est pas nécessaire de calculer la fonction de partition de π, tâche souvent difficile.
Pour cette raison, cette méthode est très utilisée en physique statistique.
Sommaire
Historique
La première version de l'algorithme est décrite dans un article de 1953 par Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, et Edward Teller[1]. Cette première version considérait le cas particulier de la distribution de Boltzmann, une des distributions les plus utilisées en physique statistique. En 1970, W. Keith Hastings a étendu l'algorithme au cas de n'importe quelle distribution[2].
Cas général
L'algorithme est une marche aléatoire sur Ω. Cette marche utilise une loi de probabilité Q pour choisir, étant en position xt à l'instant t, une nouvelle position potentielle x (appelée proposition) avec probabilité Q(xt,x). La probabilité P(xt + 1 = x | xt) que la marche se déplace en x à l'instant t + 1 (i.e., xt + 1 = x) est alors définie par
La probabilité restante est la probabilité que la marche reste en xt, c'est-à-dire P(xt + 1 = xt | xt) = 1 − P(xt + 1 = x | xt).
Cas symétrique
Un cas particulier courant de l'algorithme est celui où Q est symétrique (i.e., Q(x,y) = Q(y,x)). Dans ce cas, l'algorithme se déplace de xt en x
- avec probabilité 1 si
; - avec probabilité
sinon (et reste en xt avec la probabilité restante).
Voir aussi
- Chaîne de Markov
- Recuit simulé
- Optimisation combinatoire
- Markov chain Monte Carlo
- Méthode de Monte-Carlo
- Échantillonnage
Notes et références
- Metropolis, N.; Rosenbluth, A.W.; Rosenbluth, M.N.; Teller, A.H.; Teller, E. (1953). "Equations of State Calculations by Fast Computing Machines". Journal of Chemical Physics 21 (6): 1087–1092.
- Hastings, W.K. (1970). "Monte Carlo Sampling Methods Using Markov Chains and Their Applications". Biometrika 57 (1): 97–109.
Portail des probabilités et des statistiques
Portail de la physique
Portail de l’algorithmique
Wikimedia Foundation. 2010.