Zeit: Do 16:15 - 18:00
Ort: 711 (groß)
Dozent: Prof. Dr. R. Neininger
Übungen: 14 tägig n.V. (Dipl. Math. H. Sulzbach):
Di 12-14, SR 711 (klein), Beginn: 15. April
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 Elementare Stochastik; Kenntnisse in Stochastischen Prozessen (Martingale) und 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 (funktioniert nun, Kapitel 3 wird noch aktualisiert)
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.
-
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.
Ralph Neininger