Stochastische Konzentrationsungleichungen (SS 2011)

Zeit: Fr 10:15 - 11:45
Ort: SR 711 klein (Robert-Mayer Str. 10)
Dozent: Prof. Dr. R. Neininger
Übungen: 14 tägig Do 12-14, SR 901 (Dipl. Math. H. Sulzbach):

Vorlesung nun Fr 10-12 im SR 711 klein!

Übungen zur Vorlesung

Abgabe am 13. Mai 2011: Aufgaben 2.27, 2.28, 2.29, 2.30 des (aktuellen) Skripts.
Abgabe am 27. Mai 2011: Aufgaben 2.31, 2.33, 2.34 (a), 3.35 des (aktuellen) Skripts.
Abgabe am 10. Juni 2011: Aufgaben 2.35, 3.36, 3.37, 3.38 des (aktuellen) Skripts (26. Mai 2011).
Abgabe am 24. Juni 2011: Aufgaben 4.23, 4.24, 4.25, 4.26 des (aktuellen) Skripts (9. Juni 2011).
Abgabe am 8. Juli 2011: Aufgaben 5.13, 5.14, 5.15, 5.16 des (aktuellen) Skripts (30. Juni 2011).

Thema

Bei Stochastischen Konzentrationsungleichungen wird die Wahrscheinlichkeit abgeschätzt, dass eine reelle Zufallsvariable X von ihrem Erwartungswert um mindestens t > 0 abweicht. Es werden also Ungleichungen der Form

P( |X-E[X]| ≥ t ) ≤ g(t)
gezeigt mit passenden Funktionen g . Derartige Ungleichungen sind sind u.a. wichtig bei der Analyse von Algorithmen, da sie beschreiben, inwieweit die Komplexität X eines Algorithmus nur mit geringer Wahrscheinlichkeit von der mittleren Komplexität abweicht.

In dieser Vorlesung werden klassische und moderne Techniken besprochen, mit denen Konzentrationsungleichungen für reelle Zufallsvariablen hergeleitet werden. Die Ergebnisse werden auf zahlreiche Probleme für Algorithmen und auf Probleme der kombinatorischen Optimierung angewandt werden.

Voraussetzung für diese Vorlesung ist die Vorlesung Stochastische Prozesse; Kenntnisse in Maßtheorie sind nützlich, aber nicht notwendig. Einen guten Einblick in die Thematik geben die beiden unten genannten Übersichtsarbeiten von McDiarmid und Lugosi.

Skript zur Vorlesung

Skript (Version 5.. Juli 2011)

Weitergehende Literatur

McDiarmid, C. (1998) Concentration. Probabilistic methods for algorithmic discrete mathematics, 195--248, Algorithms Combin., 16, Springer, Berlin.
Lugosi, G. (2005) Concentration-of-measure inequalities. Lecture notes.
Steele, M.J. (1997) Probability theory and combinatorial optimization. CBMS-NSF Regional Conference Series in Applied Mathematics, 69. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA.
Dubhashi, D. P., Panconesi, A. (2009) Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, Cambridge.
Massart, P. (2007) Concentration inequalities and model selection. Lecture Notes in Mathematics, 1896. Springer, Berlin.
Alon, N., Spencer, J. (2000) The probabilistic method. Second edition. With an appendix on the life and work of Paul Erdös. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience [John Wiley & Sons], New York.
Janson, S., Luczak, T., Rucinski, A. (2000) Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York.
Talagrand, M. (1995) Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes Études Sci. Publ. Math. No. 81, 73--205.
Ledoux, M. (2001) The concentration of measure phenomenon. Mathematical Surveys and Monographs, 89. American Mathematical Society, Providence, RI.