Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 1. Oktober 2016 um 00:01 Uhr durch NikelsenH(Diskussion | Beiträge)(kat). Sie kann sich erheblich von der aktuellen Version unterscheiden.
Sei eine Sequenz von unabhängigen Bernoulli-Experimenten mit und . Demnach beschreibt die erwartete Anzahl an Erfolgen () des Experiments.
1. Dann gilt für jedes
2. Für jedes gilt:
Beweis der ersten Chernoff-Schranke
Sei eine zunächst beliebige Konstante.
Bezeichne im Folgenden zur Vereinfachung der Schreibweise eine neue Zufallsvariable vermöge . Auf Grund der Monotonie der Abbildung folgt dann
,
wobei als definiert ist und die letzte Abschätzung mittels Markow-Ungleichung folgt.
Nun gilt
Der Beweis der zweiten Schranke folgt technisch analog zur ersten Schranke.
Varianten
Eine allgemeine Variante der Chernoff-Ungleichung lässt sich mittels der Standardabweichung formulieren. Seien diskrete, unabhängige Zufallsvariablen mit und . Bezeichne die Varianz von . Dann gilt für jedes :
Der Beweis ist technisch analog zu dem oben gezeigten.
Beispiele
Betrachte die folgende Frage: Wie wahrscheinlich ist es, beim zehnmaligen Wurf einer fairen Münze wenigstens siebenmal das Ergebnis "Zahl" zu erhalten? Die Münzwürfe stellen Bernoulli-Experimente mit dar. Somit folgt nach der ersten Chernoff-Ungleichung:
Man formuliere das obige Beispiel nur leicht um und frage stattdessen: Wie wahrscheinlich ist es, bei hundertmaligem fairen Münzwurf wenigstens siebzigmal das Ergebnis "Zahl" zu erhalten? Sofort erweist sich die erste Chernoff-Schranke als deutlich stärker:
↑Herman Chernoff: Past, Present, and Future of Statistics. Hrsg.: Xihong Lin, Christian Genest, David L. Banks. CRC Press, 2014, ISBN 978-1-4822-0496-4, A career in statistics, S.35 (crcpress.com).Fehler bei Vorlage * Parametername unbekannt (Vorlage:Cite book): "editor-last5; editor-last6; editor-first4; editor-last4; editor-first5; editor-first6"
↑John Bather: A Conversation with Herman Chernoff. In: Statistical Science. 11. Jahrgang, Nr.4, November 1996, S.335–350, doi:10.1214/ss/1032280306.