Chernoffsche Ungleichung für paarweise unabhängige Zufallsvariablen

13

Chernoff-Ungleichungen werden verwendet, um zu zeigen, dass die Wahrscheinlichkeit, dass eine Summe unabhängiger Zufallsvariablen signifikant von ihrem erwarteten Wert abweicht, im erwarteten Wert und in der Abweichung exponentiell klein ist. Gibt es eine Ungleichung vom Chernoff-Typ für eine Summe von paarweise unabhängigen Zufallsvariablen? Mit anderen Worten, gibt es ein Ergebnis, das Folgendes zeigt: Die Wahrscheinlichkeit, dass eine Summe von paarweise unabhängigen Zufallsvariablen von ihrem erwarteten Wert abweicht, ist im erwarteten Wert und in der Abweichung exponentiell klein?

Rahul Tripathi
quelle

Antworten:

17

Paarweise Unabhängigkeit ist nicht genug für einen Chernoff-Typ, der an die Erwartung gebunden ist.

Dies folgt aus der Tatsache , dass es -Größe Probenräume auf n 0-1 Zufallsvariablen, wobei alle Variablen paarweise unabhängig sind, und jeweils variable einheitlich ist (es ist 1 mit einer Wahrscheinlichkeit von 1 / 2 ). Der erwartete Wert ihrer Summe ist also n / 2 . Aber weil es nur p o l y ( n ) mögliche Ereignisse in dem Probenraum, auch die Wahrscheinlichkeit , dass eine Summe ist genau ein bestimmte Wert v mindestens 1 / p opoly(n)n11/2n/2pÖly(n)v (daher kann es nicht höchstens 1 / e x p ( n ) sein ).1/pÖly(n)1/exp(n)

Eine Referenz zu dieser Beispielraumkonstruktion finden Sie auf den Seiten 11-12 in dieser Übersicht .

Ryan Williams
quelle
Ich denke, es hängt davon ab, was Sie mit einer "Tschernoff-Typ" -Grenze meinen;)
Suresh Venkat
1
Ich meine genau das, was die Frage stellt ...
Ryan Williams
13

Wenn Sie eine paarweise Unabhängigkeit haben, können Sie die Varianz der Summe begrenzen und so eine Konzentration erhalten, die unter Verwendung von Chebyshevs Ungleichung gebunden wird.

Dana Moshkovitz
quelle
4
Aber das ist kein "Chernoff-Typ", oder?
Arnab
1
Ich dachte, die Person, die die Frage gestellt hat, ist möglicherweise an den Konzentrationsgrenzen interessiert, die sie erreichen können.
Dana Moshkovitz