Enseignements 2011/2012

Année 2011/2012

• Eléments de mathématiques des décisions collectives (M2 EDPMAD,TSI,MASEF)

• Processus discrets (M1 MMD)

• Contrôle des chaînes de Markov (M1 MMD)

• Processus de Poisson et méthodes actuariels (M1 MMD)

Eléments de mathématiques des décisions collectives (M2 EDPMAD,TSI,MASEF)

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

Bibliographie et liens (en anglais)

• Le cours de l'année dernière “Analyse des fonctions booléennes” (link)

• Paradoxe de Condorcet (wp), Théorème de Arrow (wp), Théorie du choix sociale (wp)

• Le cours of O'Donnell sur l'analyse des fonctions booléennes (link)

• Le cours de Kalai sur la théorie du choix sociale (link)

• Le cours de E. Friedgut sur les méthodes analytiques en combinatoire et informatique (link)

• Le cours de N. Linian sur l'analyse harmonique et ses applications combinatoires (link)

• Page web de Gil Kalai (link)

• G. Kalai and S. Safra. Threshold Phenomena and Influence, in: Computational Complexity and Statistical Physics, A.G. Percus, G. Istrate and C. Moore, eds. (Oxford University Press, New York, 2006), pp. 25-60. (PDF)

• G. Kalai, A Fourier-Theoretic Perspective for the Condorcet Paradox and Arrow's theorem, Adv. in Appl. Math. 29(2002), 412-426. (PDF)

• G. Kalai, Social Indeterminacy, Econometrica, 72 (2004), 1565-1581. (PDF)

• G. Kalai, Noise sensitivity and chaos in social choice theory. Discussion Paper Series dp399, Center for Rationality and Interactive Decision Theory, Hebrew University, Jerusalem. (PDF)

• O'Donnell, R. 2008. Some topics in analysis of boolean functions. In Proceedings of the 40th Annual ACM Symposium on theory of Computing (Victoria, British Columbia, Canada, May 17 - 20, 2008). STOC '08. ACM, New York, NY, 569-578. (doi) (PDF)

• E. Friedgut, G. Kalai, N. Nisan, Elections Can be Manipulated Often (PDF)

• “Hypercontractivity and its applications”, a survey by Punya Biswal (PDF)

• TCS math blog (link)

• The program “Metric geometry, algoritms and groups” at IHP (Jan-April 2011) (link)

Journal

1. [13/1, 3 h] Introduction à la théorie du choix social.

2. [19/1, 3 h] Formalisation mathématiques de quelques problemes en theorie du choix social. Théoreme de Arrow quantitatif.

3. [20/1, 3 h] Fonctions booléennes et transformée de Fourier. Test BLR. Théoreme de Friedgut-Kalai-Naor.

4. [17/2, 3 h] Hypercontractivité et preuve de la version quantitative du théoreme de Arrow.

5. [10/4, 10h15 – 13h30]

6. [17/4, 10h15 – 13h30]

7. [13/1, 13h45 – 17h]

Course material (in english)

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

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

3. Exam questions. (PDF)

Journal

• The oral exam will be held the 12/6.

Processus discrets (M1 MMD)

• Cours de l'année dernière (Lien)

• Chargés de TD: Joseph Lehec et François Simenhaus.

Programme

1. Espérance conditionnelle.

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

3. Chaînes de Markov.

Bibliographie conseillée

• D. Williams, Probability with martingales , Cambridge.

• P.Bremaud, Introduction aux probabilités. Modélisation des phénomènes aléatoires, Springer-verlag, New-York, 1984.

• M. Benaïm, N. El Karoui. Promenade aleéatoire, Editions Ecole Polytechnique, 2005.

• J.R.Norris. Markov chains, Cambridge University Press, 1997

• P. Baldi, L. Mazliak, P. Priouret, Martingales et chaînes de Markov (Exercices corrigés) , Hermann

• J.Neveu. Martingales à temps discret, Masson, Paris, 1972

• R.Durrett. Probability: Theory and Examples, Wadsworth and Brooks, Pacific Grove, 1991

• M.Cottrel, Ch.Duhamel, V.Genon-Catalot. Exercices de Probabilités, Berlin, Paris, 1980

• Le cours de Lalley (link)

Journal

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

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

3. [3/10, 10h15, Amphi 6] Autres propriétés de l'espérance conditionnelle. Quelques exemples. Filtrations. Processus adaptés. Stratégies dans les jeux d'hasard. Introduction aux martingales.

4. [10/10, 10h15, Amphi 6] Martingales et stratégies.

5. [17/10, 10h15, Amphi 6] Définition de martingale. Premières propriétés.

6. [24/10, 10h15, Amphi 6] Transformation de martingales. Théorème d'arret optionnel de Doob. Convergence des martingales.

7. [31/10, 10h15, Amphi 6] Théorème de convergence des martingales. Martingales bornées dans L².

8. [7/11, 10h15, Amphi 6] Châines de Markov. Definition et quelques exemples.

9. [21/11, 10h15, Amphi 6] Recurrences aléatoires. Matrice de transition. Equation de Chapman-Kolmogorov. Loi de la chaîne de Markov.

10. [5/12, 10h15, Amphi 6] Calculs de probabilités liées à la chaînes, probabilité d'atteinte, methode à un pas.

11. [12/12, 10h15, Amphi 6] Classification des états. Ètats recurrents et transients.

12. [14/12, 10h15, Amphi 6] Mesures invariantes. Existence et unicité.

13. [2/1, 10h15, Amphi 6] Excursions. Recurrence nulle et recurrence positive.

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)

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).

7. 2010/2011. Partiel (PDF). Corrigé Partiel (PDF). Examen (PDF). Rattrapage (PDF).

8. 2011/2012. Partiel (PDF). Corrigé Partiel (PDF).

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

• Cours de l'année dernière (Lien)

• Chargé de TD: Jimmy Lamboley.

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)

• Les notes de cours de James Norris à Cambridge (url)

• Le cours de Ben Van Roy à Stanford (url)

• Bertsekas, D. P., Dynamic Programming. Prentice Hall, 1987.

• Bertsekas, D. P., Dynamic Programming and Optimal Control, Volumes I and II, Prentice Hall, 1995.

• Hocking, L. M., Optimal Control: An introduction to the theory and applications, Oxford 1991.

• Ross, S., Introduction to Stochastic Dynamic Programming. Academic Press, 1983.

Journal

1. [19/9, 17h15, B104bis] Rappels sur l'espace L² et compléments sur l'espérance conditionnelle.

2. [26/9, 17h15, B104bis] Projections dans L² et existence de l'espérance conditionnelle.

3. [3/10, 17h15, B104bis] Démonstration de quelques propriétés de l'espérance conditionnelle. Théorème de Borel-Cantelli et étude des maximum des processus stochastiques.

4. [10/10, 17h15, B104bis] Tribu d'un temps d'arrêt. Martingales et temps d'arrêt.

5. [17/10, 17h15, B104bis] Arrêt optimal. Existence de temps d'arrêt optimaux en horizon fini.

6. [24/10, 17h15, B104bis] Premier et dernier temps d'arrêt optimaux.

7. [31/10, 17h15, B104bis] Integrabilité uniforme.

8. [7/11, 17h15, B104bis] Integrabilité uniforme et convergence des martingales.

9. [21/11, 17h15, B104bis] Chaînes de Markov controlées.

10. [28/11, 17h15, B104bis] Equation de Bellman.

11. [12/12, 17h15, B104bis] Preuve de l'equation de Bellman. Chaînes homogénes, optimalité en horizon fini. Probleme d'arrêt comme probleme de contrôle.

12. [14/12, 17h15, B203] Horizon infini. Cas des gains positifs.

13. [2/1, 17h15, B104bis] Horizon infini. Cas des gains actualisés.

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 controlé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 controlé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).

Processus de Poisson et méthodes actuariels (M1 MMD)

• Chargés de TD: Joseph Lehec et François Simenhaus.

Programme

1. Processus de comptage et renouvellement. Processus de Poisson.

2. Processus de Poisson composés.

3. Processus de Renouvellement.

4. Théorie de la ruine.

Journal

1. [23/1, 10h15, A2+3] Introduction. Processus de comptage et processus de renouvellement. Processus de Poisson (PP).

2. [23/1, 12h00, A2+3] Caracterisation du PP. Intertemps exponentiels. Preuves.

3. [26/1, 10h15, A1] Quelques propriétes du PP. Loi des grandes nombres. Proprieté de Markov.

4. [16/2, 10h15, A1] Statistiques d'ordre des temps de saut du PP.

5. [20/2, 10h15, A2+3] Mélange de processus de Poisson.

6. [5/3, 10h15, A2+3] Modelisation de la charge sinistrale totale.

7. [12/3, 10h15, A2+3] Étude de la charge sinistrale totale à temps fixe. Algorithme de Panjer.

8. [19/3, 10h15, A2+3] Étude de la charge sinistrale totale à temps variable. Modéle de Cramer-Lundberg. Processus de Poisson composé.

9. [19/3, 12h00, A2+3] Caracterisation du PP composé. Loi des grandes nombres, TCL.

10. [2/4, 10h15, A2+3] Processus de renouvellement. Fonction et mesure de renouvellement. Théoreme du renouvellement elementaire.

11. [30/4, 10h15, A2+3] Théoreme de Blackwell et du renouvellement clé. Equation du renouvellement. Introduction à la théorie de la ruine.

12. [7/5, 10h15, A2+3] Probabilité de ruine. Condition de profit net. Variables à queues fines et lourdes. Inegalité de Lundberg.

13. [14/5, 10h15, A2+3] Fin de la preuve de l'inegalité de Lundberg. Eq. du renouvellement pour la probabilité de ruine.

Notes de cours et TDs

1. Poly 1. Processus de Poisson (PDF)

2. Poly 4. Théorie de la ruine (PDF)

3. TD1. Processus de Poisson (PDF)

4. TD2. Mélange de Processus de Poisson. Etude de la charge sinistrale totale à temps fixe. (PDF)

5. TD3. Processus de Poisson composés, processus de renouvellement. (PDF)

6. TD4. Théorie de la ruine (PDF)

7. Partiel 2010/2011 (PDF)

8. Examen 2010/2011 (PDF)