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
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]
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]
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
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)
Convergence vers l'équilibre
Cas apériodique irréductible : [formule] quand [formule]
Vitesse de convergence : trou spectral [formule]
Temps de mélange : [formule]
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