##  [Chernoff-Schranke](/de/node/57991) 

 Definition

Eine exponentielle obere Schranke für die Randswahrscheinlichkeit einer Summe von Zufallsvariablen, gewonnen durch Optimierung der Markov-Ungleichung angewandt auf die Momentenerzeugende Funktion; sie quantifiziert, wie unwahrscheinlich große Abweichungen sind.

 

 

 

 

 

 





## Prinzip

Prinzip

Verwende die momentenerzeugende Funktion, um Aussagen über Randwahrscheinlichkeiten in exponentielle Schranken zu überführen, und minimiere dann über den freien Parameter, um die engste exponentielle Abklingrate zu erhalten.

 

 

 

 

 





## Demonstration

Demonstration

Für unabhängige Bernoulli-Versuche wendet man die Chernoff-Schranke an, um zu zeigen, dass die Wahrscheinlichkeit, dass der empirische Mittelwert seine Erwartung um ε übersteigt, wie exp(-Θ(nε^2)) abfällt.

 

 

 

 

## Fehlanwendung

Fehlanwendung

Anwendung der Standard-Chernoff-Schranke auf stark abhängige Variablen ohne Überprüfung der Unabhängigkeit oder geeigneter Konzentrationsbedingungen, was zu ungültigen oder zu optimistischen Rändern führt.

 

 

 

 

 





## Konsequenz

Konsequenz

Liefert starke, häufig exponentiell kleine Randschranken, die uniform in der Problemgröße sind und in der Analyse probabilistischer Algorithmen sowie bei endlichen Stichproben-Bewertungen von zentraler Bedeutung sind.

 

 

 

 

## Umkehrung

Umkehrung

Untere Randschranken oder Anti-Konzentrationsabschätzungen, die zeigen, dass eine Variable nicht scharf konzentriert ist; diese benötigen andere Techniken und Parameter als eine obere Chernoff-Schranke.

 

 

 

 

 





## Abgrenzung

Abgrenzung

Gültig, wenn eine geeignete momentenerzeugende Funktion existiert und Abhängigkeiten kontrolliert sind (z. B. Unabhängigkeit, Martingaldifferenzen oder abhängige Graphen mit Beschränkung); schließt schwerverteilte Verteilungen ohne endliche exponentielle Momente aus.

 

 

 

 

 





## Semantische Spannung

Semantische Spannung

Hoeffding liefert unter Beschränktheitsannahmen eine ähnliche exponentielle Randschranke, ohne momentenerzeugende Funktionen zu verlangen; die Wahl hängt von verfügbaren Momenteninformationen und gewünschter Schärfe ab.

 

 

 

 

 





## Synthese

Synthese

Die Chernoff-Schranke ist die Methode zur Herleitung exponentiell abklingender oberer Ränder durch Anwenden der Markov-Ungleichung auf die momentenerzeugende Funktion und Optimieren des Transformationsparameters, um das Verhalten großer Abweichungen zu erfassen.