L3 Informatique, Probabilités, printemps 2019
Enseignants
Responsable du cours : Guillaume AUBRUN.
Responsables du TD : Alice PELLET--MARY et Tien-Nam LE
Références
Avancement du cours
1. Cours du 31 janvier. Warm-up : deux exemples d'algorithmes probabilistes 1) vérifier la multiplication de matrices
et 2) trouver la coupe minimale dans un graphe (on reviendra sur ce dernier). Chapitre 1 (formalisme) : espaces de probabilités, tribus,
événements. Propriétés élémentaires. Définition de l'indépendance d'événements. Théorème admis : il existe une infinité de bits aléatoires, lien avec la mesure de Lebesgue.
Exemple de partie non mesurable. Définition d'une variable aléatoire.
2. Cours du 7 février. Exemples des v.a. discrètes et des v.a.
admettant une densité, espérance d'une variable aléatoire, indépendance
(linéarité, espérance d'un produit de va indépendantes). Lemme des
groupement par paquets. Théorème d'existence d'une suite de va
indépendantes de loi prescrite. Exemples : calcul de la complexité moyenne de randomized Quicksort ;
retour sur l'algorithme probabiliste pour trouver la coupe minimale.
3. Cours du 14 février. Loi géométrique, absence de mémoire. Problème du collectionneur de vignettes. Chapitre 2 (déviations) : inégalité de Markov. Moments, norme L^p, variance, covariance.
Inégalité de Tchebychev, convergence en probabilité, loi faible des grands nombres.
4. Cours du 28 février. Fonction génératrice des moments. Inégalité de Chernoff
(version Bernoulli(1/2), version Bernoulli générale). Loi de Poisson, loi
gaussienne introduites comme lois limites.
5. Cours du 7 mars. Application des bornes de Chernoff : estimation de paramètres,
partage équilibré. Inégalité de Hoeffding. Chapitre 3 (quelques modèles probabilistes). Exemple d'un modèle probabiliste : processus de branchement
6. Cours du 14 mars. Graphe aléatoire d'Erdos-Rényi : valeur critique pour la connexité. Processus de Poisson : définition par les temps de saut exponentiels. Indépendance et loi des
accroissements. Paradoxe de l'autobus
7. Cours du 21 mars. Chapitre 4 (Convergence des variables aléatoires) : convergence en probabilité, presque sûrement, en loi(=en distribution). Lemme de Borel-Cantelli, loi forte des grands
nombres (preuve sous hypothèse L^4). Théorème de Lévy (admis).
8. Cours du 28 mars. Théorème central limite (preuve comme conséquence du théorème de Lévy). Vecteurs aléatoires gaussiens. Lemme de Johnson-Lindenstrauss : preuve (incluant un lemme de
concentration pour la loi du chi-2). Chapitre 5 (La méthode probabiliste). Exemple 1 : bornes inférieures pour les nombres de Ramsey. Exemple 2 : satisfiabilité de formules k-SAT
9. Cours du 5 avril. Exemple 3 : borne inférieure pour le problème de partage équilibré. Exemple 4 : lemme local de Lovasz (énoncé + preuve), application aux formules k-SAT, k>>1. Algorithmes
probabilistes : exemple de l'algorithme de factorisation de Miller-Rabin
10. Cours du 12 avril. Chapitre 6 (Chaînes de Markov). Définition d'une chaîne de Markov, représentation graphique. Exemple : algorithme probabiliste pour tester si une formule 2-SAT peut
être satisfiable. Classification des états : notions de chaîne irréductible, d'état transient vs récurrent, récurrent positif vs récurrent nul.
11. Partiel le 23 avril : sujet, corrigé
12. Cours du 2 mai. Lemme : deux états qui communiquent ont même nature. Tous les états d'une chaîne irréductible finie sont récurrents positifs. Exemple : ruine du joueur.
Mesure de probabilité invariante. Notion de période d'un état, d'apériodicité.
13. Cours du 16 mai. Théorème de convergence pour les chaînes irréductibles apériodiques récurrentes positives. Lien entre probabilité invariante et espérance du temps de retour. Méthode
des cut-sets. Exemple : files d'attente. Marche aléatoire sur un graphe, mesure invariante. Temps de recouvrement d'un graphe, borne en fonction du nombre de sommets et d'arêtes.
14. Cours du 21 mai. Méthode de Monte-Carlo : exemple du problème DNF counting. Exemple : chaîne de Markov sur l'ensemble des stables d'un graphe. Variation totale entre 2 mesures de
probabilités, reformulation en termes de couplage. Temps de mélange.
15. Cours du 24 mai. Couplage et temps de mélange : exemple du jeu de cartes, de la marche aléatoire paresseuse sur l'hypercube. Convergence géométrique vers la mesure invariante.
Application : algorithme probabiliste pour compter (via l'échantillonnage) les coloriages d'un graphe (quand nb couleurs> 4*degré maximal).
Examen final : sujet, corrigé.
Feuilles de TD
Vous les trouverez, ainsi que des corrigés, sur la page web de Alice PELLET--MARY
Devoir maison
Voici le sujet et le corrigé du devoir maison.
Annales
La page de l'an dernier avec sujets d'examen et corrections.