Stochastische Konzentrationsungleichungen (WS 2005/06)
Dozent: PD Dr. R. Neininger
Zeit: Mo 12:30 - 14:00
Ort: 711 (groß)
Thema
Mit 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 . Damit soll festgestellt werden, in welchen Bereich um den Erwartungswert die Zufallsvariable mit hoher Wahrscheinlichkeit fällt.
In dieser Vorlesung werden klassische und moderne Techniken besprochen, mit denen
Konzentrationsungleichungen für reelle Zufallsvariablen hergeleitet werden: Chernoff Schranken, Efron-Stein Ungleichung, Azuma-Hoeffding-Ungleichung und Ungleichungen bei beschränkten Differenzen (Martingaldifferenzmethoden), Talagrands Induktionsmethode, Entropiemethode und logarithmische Sobolev-Ungleichungen. Zudem sollen zahlreiche Anwendungen auf zufällige, diskrete Probleme besprochen werden, insbesondere auf Probleme mit algorithmischem Hintergrund.
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
Empfohlene 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.
- 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