Méthode de Monte-Carlo par chaînes de Markov

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Les méthodes de Monte-Carlo par chaînes de Markov, ou méthodes MCMC pour Markov chain Monte Carlo, sont une classe de méthodes d'échantillonnage à partir de distributions de probabilité. Ces méthodes de Monte-Carlo se basent sur le parcours de chaînes de Markov qui ont pour lois stationnaires les distributions à échantillonner.

Certaines méthodes utilisent des marches aléatoires sur les chaînes de Markov (Algorithme de Metropolis-Hastings, Échantillonnage de Gibbs), alors que d'autres algorithmes, plus complexes, introduisent des contraintes sur les parcours pour essayer d'accélérer la convergence (Monte Carlo Hybride, Surrelaxation successive)

Ces méthodes sont notamment appliquées dans le cadre de l'inférence bayésienne.

Principe[modifier | modifier le code]

Cet article fait référence à un vocabulaire spécialisé. Pour plus d'informations, voir : Chaîne de Markov.

On veut simuler une loi π sur un espace d'états général (Ω ; Ɛ). Une transition sur (Ω ; Ɛ) est une application P : (Ω ; Ɛ) → [0 ; 1] telle que P(·,A) pour tout AƐ est mesurable et P(x,·) pour tout xΩ est une probabilité sur (Ω ; Ɛ). Soit X = (Xk,k∈ℕ) une chaîne de Markov homogène de transition P et de loi initiale X0 ~ v, on note Pv la loi de la chaîne X.

Pour simuler π, on veut savoir construire une transition P telle que ∀ v, vPk → π, avec convergence en norme en variation totale μ∥ = supAƐ μ(A) − infAƐ μ(A). La chaîne de transition P est ergodique.

Convergence d'une chaîne de Markov — Si une transition P est π-réductible, π-invariante, apériodique, Harris-récurrente, alors x, Pk(x,·) →k→∞π.

La dernière condition, délicate, est satisfaite dans les cas de l'échantillonnage de Gibbs et de l'algorithme de Metropolis-Hastings.

Voir aussi[modifier | modifier le code]

D'autres échantillonnages de distribution[modifier | modifier le code]

Bibliographie[modifier | modifier le code]