[main] [teaching]mg|pages

Enseignements 2010/2011

Lectures delivered at Paris Dauphine, academic year 2010–2011.

Année 2010/2011

Analysis of Boolean functions [Analyse des fonctions booléennes] (M2 EDPMAD/TSI)

Descriptive du cours

Une fonction booléenne est une fonction \(f : \{- 1, 1\}^n \rightarrow \{- 1, 1\}\). Les fonction booléennes apparaissent souvent dans des situations variées: en mathématiques (théorie des graphes, percolation), en informatique théorique (algorithmes de classification, théorie de la complexité algorithmique, optimisation combinatoire), sciences sociales et économie (choix sociale, systèmes de vote). Ce cours est une introduction à l'analyse de ce type de fonctions et aux résultats (parfois étonnants) qui en résultent. On donnera des applications à la théorie du choix sociale: quelles sont les propriétés des systèmes de vote, le paradoxe de Condorcet, le théorème de Arrow, le théorème de Kahn-Kalai-Linial, la sensibilité au bruit et les phénomènes de “chaos".

Mots clefs: analyse de Fourier des fonctions booléennes, sensibilité aux bruit, phénomènes de seuil, influence, hypercontractivité, criticalité auto-organisée, paradoxe de Condorcet, théorème de Arrow, agrégation de l'information.

Bibliographie et liens (en anglais)

Journal

  1. [6/1, 10h00-13h15, A301] Not held.

  2. [13/1, 10h00-13h15, B212] Not held.

  3. [20/1, 10h00-13h15, B104 bis] Introduction. Social choice theory motivations. Fourier analysis.

  4. [27/1, 10h00-13h15, B104 bis] BLR test, Friedgut-Kalai-Naor theorem and Kalai's robust version of Arrow's theorem.

  5. [3/2, 13h45-17h00, B203] A first look at hypercontractivity. Some properties of the majority function. The noise operator and stability of the majority function.

  6. [10/2, 13h45-17h00, B203] A proof of the general hypercontractivity inequality. Influences. The Tribes function and the KKL theorem.

  7. [5/4, 13h45-17h00, A305] Proof of the KKL theorem and Friedgut theorem.

  8. [6/4, 9h00-12h00, A305] Influences of coalitions. Noise sensitivity and Social chaos.

Course material (in english)

  1. Lecture 1. Introduction. Social choice theory. Fourier analysis. BLR ad FKN theorems. (PDF)

  2. Lecture 2. Hypercontractivity. A first look to majority. Influences. KKL and Friedgut theorems. Influential coalitions. (PDF)

  3. Lecture 3. Noise sensitivity and social chaos. (PDF)

Processus discrets (M1 MMD)

Programme

  1. Espérance conditionnelle.

  2. Martingales. Stratégies. Convergence des martingales. Arrêt optionnel.

  3. Chaînes de Markov.

Bibliographie conseillée

Journal

  1. [21/9, 8h30, Amphi 6] Introduction du cours. Pré-requis. Sous-tribus. Motivation et définition générale de l'espérance conditionnelle.

  2. [28/9, 8h30, Amphi 6] Preuve de l'unicité p.s. de l'espérance conditionnelle. Quelques propriétés des l'espérance conditionnelle.

  3. [5/10, 8h30, Amphi 6] Martingales et leur lien avec les stratégies dans les jeux d'hasard.

  4. [12/10, 8h30, Amphi 6] Définition et caractérisation des martingales, premières propriétés, transformation de martingale, processus prévisibles, stabilité de la notion de martingale par rapport aux transformation avec les processus prévisibles.

  5. [19/10, 8h30, Amphi 6] Processus arrêté. Théorème d'arrêt optionnel de Doob. Introduction aux phénomènes de convergence des martingales.

  6. [26/10, 8h30, Amphi 6] Traversées montantes, théorème de convergence des martingales.

  7. [2/11, 8h30, Amphi 6] Convergence en moyenne quadratique des martingales bornées en L².

  8. [9/11, 8h30, Amphi 6] Chaînes de Markov. Matrice de transition. Equation de Chapman-Kolmogorov.

  9. [23/11, 8h30, Amphi 6] Construction d'une chaîne avec matrice de transition donnée.

  10. [30/11, 8h30, Amphi 6] Classification des états. Récurrence.

  11. [7/12, 8h30, Amphi 6] Critères pour la récurrence et la transience.

  12. [14/12, 8h30, Amphi 6] Probabilités invariantes. Existence.

  13. [4/1, 8h30, Amphi 6] Unicité dans le cas irréductible. Excursions. Récurrence positive. Lien entre probabilité invariante et temps moyens de retour. Théorème ergodique et convergence à l'équilibre.

Notes de cours et TDs

  1. Poly 1. Espérance conditionnelle (PDF)

  2. Poly 2. Martingales, stratégies et arrêt optionnel (PDF)

  3. Poly 3. Comportement asymptotique des martingales (PDF)

  4. Poly 4. Chaînes de Markov (PDF)

  5. TD1. Espérance conditionnelle. (PDF)

  6. TD2. Martingales, stratégies et arrêt optionnel (PDF)

  7. TD3. Comportement asymptotique des martingales (PDF)

  8. TD4. Chaînes de Markov (PDF)

  9. TD5. Chaînes de Markov (II) (PDF)

  10. Partiel (PDF)

  11. Corrigé Partiel (PDF)

Sujets des années précédentes

  1. 2004/2004. Examen (PDF). Rattrapage (PDF).

  2. 2005/2006. Examen (PDF). Rattrapage (PDF).

  3. 2006/2007. Partiel (PDF). Examen (PDF). Rattrapage (PDF).

  4. 2007/2008. Partiel (PDF). Examen (PDF). Rattrapage (PDF).

  5. 2008/2009. Examen (PDF).

  6. 2009/2010. Partiel (PDF). Corrigé Partiel (PDF). Examen (PDF). Rattrapage (PDF).

Contrôle des chaines de Markov (M1 MMD - parcours MAMD)

Programme

  1. Compléments sur l'espérance conditionnelle.

  2. Chaînes de Markov contrôlées.

  3. Compléments sur les temps d'arrêt et sur les martingales. Arrêt optimal en horizon fini. Enveloppe de Snell

  4. Arrêt optimale en horizon infini. Principe d'optimalité. Exemples et applications.

Bibliographie conseillée (en anglais)

Journal

  1. [23/9, 15h30, A307] Rappels sur l'espace L² et compléments sur l'espérance conditionnelle.

  2. [30/9, 15h30, A307]Existence de l'espérance conditionnelle. Preuve de quelques propriétés.

  3. [7/10, 15h30, A307] Arrêt optimal en horizon fini. Lien avec les martingales. Enveloppe de Snell.

  4. [14/10, 15h30, A307] Preuve du théorème d'arrêt optimal et compléments.

  5. [21/10, 15h30, A307] Etude des temps d'arrêt optimaux.

  6. [28/10, 17h00, A307] Integrabilité uniforme.

  7. [4/11, 15h30, A307] Martingales uniformément intégrables.

  8. [11/11, 15h30, A307] Martingales rétrogrades. Loi du 0-1 de Lévy, de Kolmogorov et démonstration de la loi forte des grandes nombres.

  9. [25/11, 15h30, A307] Chaînes de Markov contrôlées.

  10. [2/12, 15h30, A307] Récurrence aléatoires contrôlées. Cas homogène en temps. Equation de Bellman.

  11. [9/12, 15h30, A307] Contrôle en horizon fini.

  12. [16/12, 15h30, A307] Contrôle en horizon infini. Cas de gains positifs.

  13. [6/1, 15h30, A307]

  14. [16/1, 15h30, A307]

Notes de cours et TDs

  1. Poly 1. Compléments sur l'espérance conditionnelle (PDF)

  2. Poly 2. Arrêt optimal en horizon fini. (PDF)

  3. Poly 4. Chaînes de Markov contrôlées. (PDF)

  4. TD1. Compléments sur l'espérance conditionnelle. (PDF)

  5. TD2. Arrêt optimal en horizon fini. (PDF)

  6. TD3. Integrabilité uniforme. (PDF)

  7. TD4. Chaînes de Markov contrôlées. (PDF)

Sujets des années précédentes

  1. 2008/2009. Examen (PDF). Rattrapage (PDF).

  2. 2009/2010. Partiel (PDF). Corrigé Partiel (PDF). Examen (PDF). Rattrapage (PDF).

Statistique (DU2 Eco IGD Math/Eco Mat/Info)

Programme

  1. Rappels sûr les intégrales multiples et le distributions des vecteurs aléatoires.

  2. Vecteurs aléatoires gaussiens. Lois Gamma, Beta, Khi-deux, Student.

  3. Convergence et théorèmes limites. Inégalités de Tchebichev et Hölder. Convergence en loi. Convergence en probabilité. loi faible des grands nombres. Convergence presque sûre. Loi forte des grands nombres. Convergence en moyenne p-eme. Théorème Central Limite. La delta-méthode.

  4. Estimation ponctuelle. Modèle paramétrique. Estimateurs ponctuels. Exhaustivité des statistiques. Méthodes d'estimation: moments, maximum de vraisemblance.

  5. Estimation par intervalles de confiance.

  6. Test d'hypothèses. Test du rapport de vraisemblances. Test du Khi-deux. Test d'indépendance.

Journal

  1. [4/2, 8h30, Amphi 1] Introduction au cours. Vecteurs aléatoires avec densité. Densités marginales et densité conditionnelle.

  2. [11/2, 8h30, Amphi 1] Indépendance des vecteurs aléatoires. Espérance. Espérance conditionnelle et ses propriétés. Covariance et coefficient de corrélation.

  3. [16/2, 12h00, Amphi 1] Propriétés de la covariance. Variance conditionnelle. Formule de la variance conditionnelle. Matrice de covariance d'un vecteur aléatoire et ses propriétés.

  4. [18/2, 8h30, Amphi 1] Fonction caractéristique pour une v.a. et un vecteur aléatoire. Exemples. Vecteurs aléatoires gaussiens. Premières propriétés.

  5. [2/3, 12h00, Amphi 1] Caractérisation des vecteurs gaussiens. Vecteurs gaussiens avec moyenne et variance données.

  6. [4/3, 8h30, Amphi 1] Fonction caractéristique d'un vecteur gaussien. Définition de la loi gaussienne multidimensionnelle avec moyenne et variance donnée. Densité d'un vecteur avec matrice de covariance inversible.

  7. [9/3, 12h00, Amphi 1] Lien entre covariance et indépendance pour les vecteurs gaussiens. Introduction à la convergence des variables aléatoires. Exemple de convergence (en loi) d'une suite de v.a. vers une v.a. uniforme. Théorème sur la convergence jointe des fonction caractéristiques, des moyennes et des fonctions de répartitions. Définition de convergence en loi.

  8. [18/3, 8h30, Amphi 1] Convergence en probabilité. Inégalité de Markov et Tchebychev. Loi faible des grandes nombres. Convergence presque sûre. Loi forte des grandes nombres. Théorème Centrale Limite.

  9. [27/4, 12h00, Amphi 1] Convergence en moyenne r-éme. Inégalité de Jensen. Convergence de la moyenne. Lien entre les modes de convergence. Théorème de continuité. Lemme de Slusky.

  10. [3/5, 17h15, Amphi 4]

  11. [11/5, 12h00, Amphi 1]

  12. [17/5, 17h15, Amphi 4?]

  13. [18/5, 12h00, Amphi 1]

Cours

  1. Poly 1. Vecteurs aléatoires, espérance conditionnelle, régression. (PDF)

  2. Poly 2. Matrice de covariance. Fonction caractéristique. Vecteurs Gaussiens. (PDF)

  3. Poly 3. Convergence des variables aléatoires. Loi des grandes nombres et théorème centrale limite. (PDF)

  4. Poly 4. Estimation ponctuelle. (PDF)

  5. Poly 5. Intervalles de confiance. (PDF)

Feuilles de TD et sujets

  1. TD1: Intégrales doubles et couples de variables aléatoires. (PDF)

  2. TD2: Vecteurs aléatoires, vecteurs Gaussiens et loi Gamma et Khi-deux. (PDF)

  3. TD3: Vecteurs Gaussiens. (PDF)

  4. TD4: Convergence en loi. (PDF)

  5. TD5: Estimation ponctuelle. (PDF)

  6. TD6: Intervalles de confiance. (PDF)