Structures et Algorithmes Aléatoires

Horaires

Intervenants

Si vous avez des questions, n'hésitez pas à leur envoyer un mail : prenom.nom@ens.fr

Résumé du cours

Ce cours vise à donner aux étudiants les bases de probabilités qui sont utilisées dans divers domaines de l'informatique (algorithmique, algorithmes stochastiques, réseaux de communication,...). Il est divisé en deux parties :
  1. Probabilités discrètes et applications
  2. Modèles markoviens

Plan du cours

Cours du 24 septembre : événements et probabilités

  1. Introduction : égalité de deux polynômes, file d'attente
  2. Événements, axiomes des probabilités
  3. Indépendance, probabilité conditionnelle, lois de Bayes

Cours du 1er octobre : variables aléatoires

  1. Variables aléatoires et lois de probabilité. Exemples : Lois Bernoulli, binomiales, géométriques
  2. Espérance et variance. Linéarité de l'espérance, collectionneur de coupons
  3. Inégalités de Markov et de Tchebychev

Cours du 8 octobre : fonctions génératrices et applications

  1. Fonctions génératrices : définition, lien avec les moments, caractérisation d'une loi, égalité de Wald
  2. Processes de branchement de Galson-Watson, probabilité d'extinction
  3. Bornes de Chernoff, application au tri rapide.

Cours du 15 octobre : urnes et balles

  1. Modèle d'urnes et de balles, charge maximale d'une urne
  2. Limite de la loi binomiale : distribution de Poisson; approximation poissonnienne : borne inférieure de la charge maximalde d'une urne
  3. Puissance de deux choix, amélioration de la charge maximale

Cours du 22 octobre : la méthode probabiliste

  1. Argument de comptage : nombre de Ramsey
  2. Méthode du premier moment : MAXSAT et ensemblees indépendants
  3. Méthode du second moment : graphes Erdös-Rényi, fonction-seuil pour les cliques de taille 4 ; schéma de Flajolet-Martin

Cours du 24 octobre : le lemme local de Lovàsz

  1. Énoncé, application à k-SAT
  2. Preuve constructive

Cours du 12 novembre : émergence de la composante géante

  1. Énoncé, application à la propagation de virus
  2. Preuve : régime sous-critique, régime sur-critique

Cours du 19 novembre : Chaînes de Markov

  1. Définition, propriété de Markov, indépendance du passé et du futur conditionnellement au présent
  2. Représentations : matricielles, fonctionelles et graphiques (période, classes de communication, irréductibilité)
  3. Mesure invariante, distribution stationnaire, réversibilité.

Cours du 26 novembre : Classification des états , existence de mesures invariantes et probabilités stationnaires

  1. Temps d'arrêt, propriété de Markov forte
  2. Classification des états : états transitoires, récurrents nuls et récurrents positifs, critère de la matrice du potentiel
  3. Existence et unicité à un facteur multiplicatif près de la mesure invariante pour les chaînes irréductibles et récurrentes
  4. Existence et unicité de la distribution stationnaire pour les chaînes irréductibles et récurrentes positives

Cours du 3 décembre : théorème ergodique et simulation

  1. Théorème ergodique, théorème de Kolmogorov
  2. Génération de variables aléatoires discrètes, méthode de l'alias

Cours du 10 décembre : simulation de chaînes de Markov

  1. Echantillonneur de Gibbs et simulation MCMC
  2. Temps de mélange, couplage de chaînes de Markov

Cours du 17 décembre : simulation parfaite des chaînes de Markov

  1. Algorithme de Propp et Wilson
  2. Chaînes monotones, chaînes bornantes

Notes de cours

Notes jusqu'au 12 novembre. Il y a certainement des erreurs, merci de m'en faire part.

Feuilles de TDs

Devoirs maison

Chaque devoir maison comptera entre 10% et 15% de la note finale.

Références

  1. Markov chains: Gibbs fields, Monte Carlo simulation and queues, P. Brémaud, Springer, New York, 2nd printing, 2001.
  2. Probability and Computing. Randomized Algorithms and Probabilistic Analysis. M. Mitzenmacher and E. Upfal.
  3. The Probabilistic Method. N. Alon and J.H. Spencer.

Examens des années précédentes

Pages des années précédentes