Leçon 308 — Chaînes de Markov à espace d'états fini.

Points clés

• Matrice de transition et propriété de Markov
• Classification des états : transience, récurrence
• Irréductibilité et apériodicité
• Mesure stationnaire et théorème ergodique
• Convergence vers l'équilibre

Plan

1. Définition et propriété de Markov
   • Processus stochastique [formule] à valeurs dans un ensemble fini [formule]
   • Propriété de Markov : [formule]
   • Matrice de transition [formule] avec [formule]
   • Chaîne homogène : la matrice [formule] ne dépend pas de [formule]
2. Classification des états
   • Accessibilité : [formule] s'il existe [formule] tel que [formule]
   • Communication : [formule] si [formule] et [formule]. Classes de communication
   • État récurrent : [formule] ; état transient sinon
   • Période d'un état : [formule]
3. Irréductibilité et mesure invariante
   • Chaîne irréductible : tous les états communiquent
   • Mesure invariante [formule] : [formule] avec [formule]
   • Existence et unicité de [formule] pour une chaîne irréductible sur un espace fini
4. Théorème ergodique
   • Énoncé : [formule] pour tout [formule]
   • Lien avec le théorème de Perron-Frobenius
   • Convergence de [formule] vers la matrice dont chaque ligne est [formule] (cas apériodique)
5. Convergence vers l'équilibre
   • Cas apériodique irréductible : [formule] quand [formule]
   • Vitesse de convergence : trou spectral [formule]
   • Temps de mélange : [formule]
6. Applications
   • Algorithme PageRank : marche aléatoire sur le graphe du web
   • Marche aléatoire sur un graphe fini : [formule]
   • Algorithme de Metropolis-Hastings et méthodes MCMC

Théorèmes clés

• Théorème ergodique pour les chaînes de Markov : si la chaîne est irréductible sur un espace fini, [formule]
• Théorème de Perron-Frobenius : une matrice stochastique irréductible admet [formule] comme valeur propre simple dominante, de vecteur propre à gauche [formule]
• Convergence en loi : si la chaîne est irréductible apériodique, [formule] pour tout [formule]
• Tout état récurrent d'une chaîne irréductible finie est récurrent positif

Exemples importants

• Marche aléatoire symétrique sur [formule] : irréductible, apériodique si [formule] est impair
• Modèle d'Ehrenfest : [formule] particules entre deux urnes, mesure invariante binomiale
• Chaîne à deux états : [formule], [formule]

Erreurs courantes

• Confondre irréductibilité et apériodicité
• Oublier que l'existence de la mesure invariante est automatique en dimension finie (mais pas en général)
• Appliquer le théorème de convergence sans vérifier l'apériodicité

Conseils du jury

• Le théorème de Perron-Frobenius est un développement apprécié qui relie algèbre et probabilités
• Savoir traiter complètement un exemple de chaîne à [formule] ou [formule] états
• Le jury apprécie les applications modernes comme PageRank

Développements associés

• Théorème ergodique pour les chaînes de Markov
• Théorème de Perron-Frobenius
• Algorithme PageRank
• Distribution stationnaire des chaînes de Markov
• File d'attente M/M/1
• Récurrence de la marche aléatoire
• Problème de la ruine du joueur

Prérequis

algebre lineaire, espaces probabilises, matrices