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

 Definition

Eine exponentielle obere Schranke für Randwahrscheinlichkeiten von zufälligen Summen oder Aggregaten, gewonnen durch Anwendung der Markov-Ungleichung auf die momentenerzeugende Funktion (MGF) und Optimierung der exponentiellen Neigung: für S eine Summe gilt P(S ≥ t) ≤ inf_{s>0} e^{-s t} E[e^{s S}].

 

 

 

 

 

 





## Prinzip

Prinzip

Man wendet Markov auf die Exponentialtransformation der Zufallsvariable (MGF) an und wählt den Kipp-Parameter, der die Schranke minimiert; Unabhängigkeit oder subexponentielle Kontrolle der Summanden führt oft zu exponentiell kleinen Schranken in der Stichprobengröße.

 

 

 

 

 





## Demonstration

Demonstration

Für unabhängige Bernoulli-Versuche mit Erwartungswert p liefert die Chernoff-Schranke P(S ≥ (1+δ)np) ≤ exp(−n D((1+δ)p || p)), wobei D(·||·) die relative Entropie ist; dies gibt exponentiell fallende Randwahrscheinlichkeiten, die in zufallsbasierten Algorithmen und kombinatorischer Konzentration verwendet werden.

 

 

 

 

## Fehlanwendung

Fehlanwendung

Die Standardformeln von Chernoff auf abhängige Variablen anzuwenden, auf Variablen ohne endliche MGF in einer Umgebung von null oder das Kippen nicht zu optimieren; dies kann zu leeren oder irreführenden Schranken führen.

 

 

 

 

 





## Konsequenz

Konsequenz

Liefert scharfe, exponentiell abklingende Schranken, die hochwahrscheinliche Garantien in probabilistischen Algorithmen, der Lerntheorie und bei Großabweichungsschätzungen ermöglichen; oft zusammen mit Vereinigungsschranken verwendet, um viele Ereignisse gleichzeitig zu kontrollieren.

 

 

 

 

## Umkehrung

Umkehrung

Wird die Chernoff-Technik durch schwächere Ungleichungen (z. B. Chebyshev) ersetzt, ergibt sich nur polynomielle oder deutlich langsamere Abklingung der Randwahrscheinlichkeiten; bei schwergewichtigen Verteilungen sind Chernoff-Schranken oft nicht anwendbar oder aussagekräftig.

 

 

 

 

 





## Abgrenzung

Abgrenzung

Setzt die Existenz einer MGF in einer Umgebung von null oder Kontrolle exponentieller Momente voraus; klassische Formen gehen von Unabhängigkeit oder begrenzter Abhängigkeit und beschränkten/subexponentiellen Schwänzen aus — außerhalb dieser Bereiche sind Modifikationen oder andere Techniken nötig.

 

 

 

 

 





## Semantische Spannung

Semantische Spannung

Steht im Wettbewerb mit Hoeffding-, Bernstein- und Bennett-Ungleichungen; Chernoff ist oft schärfer für Summen unabhängiger Indikator- oder subgauss'scher Variablen, kann aber bei schwergewichtigen oder stark abhängigen Daten unpassend sein.

 

 

 

 

 





## Synthese

Synthese

Chernoff-Schranken formen Markov auf MGFs und optimieren den exponentiellen Kipp-Parameter, um exponentielle Randabschätzungen für Summen geeigneter Zufallsvariablen zu erhalten; mächtig bei existierenden MGFs und (annähernder) Unabhängigkeit, aber beschränkt durch Momentsexistenz und Abhängigkeitsstruktur.