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

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Markov chain Monte Carlo)
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.

Approche intuitive[modifier | modifier le code]

On se place dans un espace vectoriel \varepsilon de dimension finie n. On veut générer aléatoirement des vecteurs x suivant une distribution de probabilité π. On veut donc avoir une suite de N vecteurs (x_0,x_1,\dots,x_{N-1}) telle que la distribution des x_i approche π.

Les méthodes de Monte-Carlo par chaînes de Markov consistent à générer un vecteur x_i uniquement à partir de la donnée du vecteur x_{i-1} ; c'est donc un processus « sans mémoire », ce qui caractérise les chaînes de Markov. Il faut donc trouver un générateur aléatoire avec une distribution de probabilité q_{x_{i-1}} qui permette de générer x_i à partir de x_{i-1}. On remplace ainsi le problème de génération avec une distribution π par N problèmes de génération avec des distributions x_i, que l'on espère plus simples.

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]