M2 Modélisation Aléatoire

Master en statistique, probabilités et finance - Université Paris 7 - Paris Diderot

 
 
 
 
 
 
Liste des cours Cours Probabilités et Analyse Temps de mélange et phénomène de cutoff pour les chaines de Markov
 
 

Temps de mélange et phénomène de cutoff pour les chaines de Markov

Cours:  J. Salez
Période: 
Trimestre 3
Nombre de crédits: 
6
Volume horaire 3 heures de cours par semaine

Combien de fois faut-il battre un paquet de 52 cartes pour que la permutation aléatoire obtenue soit à peu près uniformément distribuée ? Ce cours est une introduction sans pré-requis à la théorie moderne des "temps de mélange" des chaînes de Markov irreductibles et apériodiques. Un interêt particulier sera porté au célèbre phénomène de "cutoff", qui est une transition de phase remarquable - et encore largement incomprise - dans la convergence de certaines chaînes vers leur distribution stationnaire. Parmi les outils abordés figurent les techniques de couplage, les martingales, l'analyse spectrale de la matrice de transition, et les inégalités fonctionnelles de type Nash ou log-Sobolev. En guise d'illustration, toutes ces méthodes fondamentales seront appliquées à divers exemples classiques issus de contextes variés: marches aléatoires sur les groupes finis, chaînes de vie et de mort, systèmes de particules en intéraction, algorithmes de Metropolis-Hastings, etc. Une place importante sera accordée aux marches sur réseaux, qui sont aujourd'hui au coeur des algorithmes d'exploration d'Internet et sont massivement utilisées pour la collecte de données et la hiérarchisation des pages par les moteurs de recherche.

BIBLIOGRAPHIE: Le cours sera basé sur les deux ouvrages suivants, qui sont disponibles gratuitement en ligne:
- Markov Chains and Mixing Times (Levin, Peres & Wilmer)
- Mathematical Aspects of Mixing Times in Markov Chains (Montenegro & Tetali)