Ein Flussdiagramm für Konzentrationsgrenzen

21

Wenn ich Schwanzgrenzen unterrichte, benutze ich die übliche Progression:

  • Wenn Ihr rv positiv ist, können Sie Markovs Ungleichung anwenden
  • Wenn Sie Unabhängigkeit und auch begrenzte Varianz haben, können Sie die Ungleichung von Chebyshev anwenden
  • Wenn für jedes unabhängige RV auch alle Momente begrenzt sind, können Sie eine Chernoff-Grenze verwenden.

Danach werden die Dinge etwas weniger sauber. Beispielsweise

  • Wenn Ihre Variablen den Mittelwert Null haben, ist eine Bernstein-Ungleichung praktischer
  • Wenn Sie nur wissen, dass die Kombinationsfunktion Lipschitz ist, dann gibt es eine generalisierte McDiarmid-Ungleichung
  • Wenn Sie eine schwache Abhängigkeit haben, gibt es Grenzen nach Siegel (und wenn Sie eine negative Abhängigkeit haben, ist Janssons Ungleichung möglicherweise Ihr Freund).

Gibt es irgendwo einen Verweis auf ein praktisches Flussdiagramm oder einen Entscheidungsbaum, in dem beschrieben wird, wie man den "richtigen" Schwanz wählt (oder sogar, wenn man in ein Meer von Talagrand eintauchen muss)?

Ich frage zum Teil, ob ich eine Referenz habe, zum Teil, um sie meinen Schülern zu zeigen, und zum Teil, weil ich versuchen könnte, selbst eine zu erstellen, wenn ich mich ausreichend ärgere und es keine gibt.

reference-request pr.probability randomized-algorithms Suresh Venkat
quelle
Ich denke, die einfache Antwort ist nein und ja, bitte an jeden, der eine macht.
Lembik

Antworten:

11

Fan Chung und Linyuan Lu. Konzentrations- und Martingal-Ungleichungen: Eine Umfrage unter http://projecteuclid.org/euclid.im/1175266369 oder auf der Website von Fan Chung Graham.

Chandra Chekuri
quelle
Ja ! das ist ausgezeichnet ! Ich habe diese Umfrage bereits gelesen, aber völlig vergessen.
Suresh Venkat
6
Es ist eine sehr schöne Umfrage, aber ich sehe nichts Vergleichbares wie das, was im ursprünglichen Beitrag gefordert wird: "Ein praktisches Flussdiagramm oder ein Entscheidungsbaum, der beschreibt, wie Sie die 'richtige' Schwanzgrenze für Ihre Zufallsvariablen auswählen."
Usul
Es ist nicht genau richtig, aber es gibt Flussdiagramme, die zeigen, wie die verschiedenen Sätze sich gegenseitig implizieren, was ein Anfang ist.
Suresh Venkat