Stochastische Konzentrationsungleichungen (WS 16/17)

Zeit: Mi 10:15 - 12:00
Ort: SR 711 groß (Robert-Mayer Str. 10)
Dozent: Prof. Dr. R. Neininger
Übung: donnerstags 8:15 - 10:00 Uhr, SR 711 klein, 14 tägig (3.11., 17.11., 1.12., 15.12., 19.1., 2.2.)
Betreuung: Andrea Kuntschik

Module:
MaM-STO-k
MaM-STO-gks, d.h. Spezialisierung in Stochastik (zusammen mit passenden weiteren Veranstaltungen, vgl. Studienordnung Seite 110)

Am 11. Januar 2017 fällt die Vorlesung aus.

Übungen zur Vorlesung

Abgabe am 9. November 2016: Aufgaben 2.27, 2.29, 2.30, 2.33 des Skripts.
Abgabe am 23. November 2016: Aufgaben 2.31, 2.34, 2.35, 3.38 des Skripts.
Abgabe am 7. Dezember 2016: Aufgaben 2.36 (möglicherweise schwierig), 3.39, 3.40, 3.42 des Skripts.
Abgabe am 21. Dezember 2016: Aufgaben 3.41, 4.23, 4.25 (Satz 4.9 wird am 14.12. besprochen), 4.26 des Skripts.
Blatt 5
Blatt 6


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 oft als technisches Hlifsmittel wichtig, um Zufallsvariable approximativ durch deren Erwartung ersetzen zu können. Zudem spielen sie in der mathematischen Statistik eine grundlegende Rolle.

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

Voraussetzung für diese Vorlesung sind Kenntnisse über Martingale in diskreter Zeit etwa aus der Vorlesung 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

Es wird ein gebundenes Skript in der ersten Vorlesung kostenfrei ausgegeben.


Weitere Literatur

Impressum, Datenschutzerklärung