Chaînes et algorithmes de Markov

Cette séance de cours couvre le concept des chaînes de Markov et leurs applications dans les algorithmes, en se concentrant sur des sujets tels que la simulation exacte par couplage du passé et la cartographie aléatoire. L'instructeur explique la théorie derrière les chaînes de Markov et démontre comment elles peuvent être utilisées dans la conception d'algorithmes. La séance de cours se penche également sur les algorithmes et théorèmes de Propp-Wilson liés aux chaînes de Markov. Divers théorèmes sont présentés, y compris ceux de Propp et Wilson en 1986, discutant du comportement des chaînes avec des états initiaux et de leur convergence dans le temps.