L3 Informatique, Probabilités, printemps 2018
Horaires
Les cours ont lieu le mercredi matin de 10h15 à 12h15 en amphi B.
Les TD ont lieu le mercredi après-midi de 15h45 à 17h45 (responsable : Édouard Bonnet)
et le jeudi matin de 8h à 10h (responsable : Chitchanok Chuengsatiansup).
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. Loi d'une variable aléatoire. Fonction de répartition (théorème admis : elle caractérise la loi). Lois discrètes, lois à densité. Indépendance de v.a ; lemme
de groupement par paquets. Espérance d'une v.a. (détails de la construction admis) ; linéarité, espérance d'un produit de v.a. indépendantes. Justification de l'algorithme probabiliste
pour la coupe minimale introduit au cours précédent.
3. Cours du 14 février. Exemple pour illustrer la linéarité de l'espérance : temps moyen d'exécution de Quicksort pour des données permutées aléatoirement. 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) Processus de branchement
6. Cours du 14 mars. Processus de branchement : condition pour l'extinction presque
sûre. Graphe aléatoire d'Erdos-Rényi : valeur critique pour la connexité.
Loi exponentielle.
Examen partiel le 21 mars : sujet, correction.
7. Cours du 30 mars : processus de Poisson : définition par les temps de saut exponentiels. Indépendance ed loi des accroissements. Paradoxe
de l'autobus. Chapitre 4 : théorèmes-limites. Convergence presque sûre et convergence en loi : comparatif. Lemme de Borel-Cantelli. Enoncé de la loi
forte des grands nombres.
8. Cours du 4 avril : loi forte des grands nombres : preuve sous l'hypothèse L^4. Convergence en loi (=en distribution) : définition, théorème de Lévy (admis).
Théorème central limite (preuve par les fonctions caractéristiques). Vecteurs gaussiens ; utilité pour générer la mesure uniforme sur la sphère. Lemme de Johnson-Lindenstrauss
(énoncé)
9. Cours du 11 avril : Lemme de Johnson-Lindenstrauss : preuve (incluant un lemme de concentration pour la loi du chi-2). Chapitre 5 : exemples d'applications de la méthode
probabiliste. 1) Nombres de Ramsey : borne inférieure. 2) Borne inférieure sur le nombre de formules k-SAT simultanément vérifiables. 3) Problème de partage équilibré (discrepancy) : bornes
inférieures.
10. Cours du 27 avril : Lemme local de Lovasz (cas symétrique) ; application : satisfiabilité des formules k-SAT avec peu d'occurences de chaque variable. Algorithmes probabilistes :
Monte-Carlos vs Las Vegas. Exemple : le test de primalité de Miller-Rabin. Chapitre 6 : Chaînes de Markov. Définition, représentation graphique. Exemple d'un algorithme probabiliste pour le problème
2-SAT, analyse par couplage avec la marche aléatoire simple sur {0,...,n}
11. Cours du 2 mai : Chaînes de Markov irréducibles, états récurrents vs transients, récurrents positifs vs récurrents nuls ; différentes caractérisations de ces notions. Illustration :
théorème de Polya. Ruine du joueur.
12. Cours du 16 mai. Probabilité invariante pour une chaîne de Markov. Période d'un état, chaîne apériodique. Théorème de convergence
vers la mesure invariante. Existence de la mesure invariante pour les chaînes récurrentes positives et lien avec le temps moyen de retour.
13. Cours du 18 mai. Cut-sets. Exemples : files d'attente. Marche aléatoire sur un graphe ; temps de recouvrement, borne 4*|V|*|E|.
Algorithme probabiliste pour tester l'existence de chemins. Introduction aux statistiques : notion d'estimateur.
14. Cours du 23 mai. Biais, consistance, vitesse d'un estimateur ; exemples. Intervalles de confiance. Estimateurs exhaustifs. Méthode
du maximum de vraisemblance illustrée sur plusieurs exemples. Tests d'hypothèse.
Examen
Voici le sujet de la première session ainsi que le corrigé.
Feuilles de TD
Feuille numéro 1 (anglais, français)
Feuille numéro 2 (anglais)
Feuille numéro 3 (français)
Feuille numéro 4 (anglais, français)
Feuille numéro 5 (anglais, français)
Feuille numéro 6 (anglais, français)
Feuille numéro 7 (anglais, français)
Feuille numéro 8 (anglais, français)
Feuille numéro 9 (français)
Feuille numéro 10 (français)
Feuille numéro 11 (anglais)
Feuille numéro 12 (français)
Feuille numéro 13 (anglais)
Feuille numéro 14 (anglais)
Feuille numéro 15 (anglais)
Devoirs maison
Devoir maison numéro 1, à rendre pour le 28 février. Voici la correction.
Annales
Voici les sujets posés l'année dernière (cours assuré par Omar Fawzi) : examen partiel, examen final.