APM_4PRB1_TA - Chaînes de Markov (S1-2A - 2024-25)

La théorie des chaînes de Markov fournit un cadre mathématique rigoureux pour décrire la classe d'évolutions aléatoires pour lesquelles (la loi) du futur de la chaîne ne dépend que de son état présent. 

Si on raisonne à temps discret et à espace d’état finis, une telle chaîne est caractérisée par la donnée d’une matrice stochastique, et on montre grâce aux outils de l’algèbre linéaire que, sous des conditions peu restrictives, on a existence et unicité d’une mesure invariante vers laquelle la loi de la chaîne converge en temps long.

Hormis cette notion de loi limite, on s’intéressera aussi aux probabilités et aux temps d’atteinte de sous-ensembles de l’espace d’états. Dans le cas de chaînes dites réversibles, il existe une connection riche avec la théorie des réseaux électriques, qui permet de ramener ces questions à des calculs de résistances équivalentes.

Dans un article de l'American Mathematical Monthly de 1989, Herbert Wilf a décrit sa surprise en constatant le temps (long!) mis par une marche aléatoire pour visiter chaque pixel de son écran d’ordinateur. Ce temps est le temps de couverture du tore de dimension 2, jolie application de la théorie des chaines de Markov qui sera étudiée à la fin du cours si le temps le permet.

Les pré-requis pour les étudiants sont les suivants: une bonne maîtrise du cours de probabilités de première année et de l’algèbre linéaire de classe préparatoire. 

Référence: Le cours s'appuiera sur (un sous-ensemble de) l'ouvrage Markov Chains and Mixing Times par Levin, Peres et Wilmer, seconde édition, dont plusieurs exemplaires papier sont disponibles à la bibliothèque.