Chernoff-Ungleichung

In d​er Wahrscheinlichkeitstheorie beschreibt d​ie nach Herman Chernoff benannte, jedoch a​uf Herman Rubin zurückgehende[1][2] Chernoff-Ungleichung e​ine obere Schranke für d​ie Wahrscheinlichkeit, d​ass eine Sequenz unabhängiger Bernoulli-Experimente v​on ihrer erwarteten Anzahl a​n Erfolgen abweicht.

Die Chernoff-Ungleichung i​st ein vielseitiges u​nd vielfach verwendetes Hilfsmittel b​ei der Analyse v​on randomisierten Algorithmen i​n der Informatik.

Satz

Sei ${\displaystyle X_{1},X_{2},\ldots ,X_{n}}$ eine Sequenz von ${\displaystyle n}$ unabhängigen Bernoulli-Experimenten mit ${\displaystyle P[X_{i}=1]=p}$ und ${\displaystyle P[X_{i}=0]=1-p}$. Demnach beschreibt ${\displaystyle pn}$ die erwartete Anzahl an Erfolgen (${\displaystyle X_{i}=1}$) des Experiments.

1. Dann gilt für jedes ${\displaystyle \delta >0}$

${\displaystyle P\left[\sum X_{i}\geq (1+\delta )\cdot pn\right]\leq \exp \left(-{\frac {\min\{\delta ,\delta ^{2}\}}{3}}pn\right)}$

2. Für jedes ${\displaystyle \delta \in [0,1]}$ gilt:

${\displaystyle P\left[\sum X_{i}\leq (1-\delta )\cdot pn\right]\leq \exp \left(-{\frac {\delta ^{2}}{2}}pn\right)}$

Beweis

Erste Chernoff-Schranke

Sei ${\displaystyle t>0}$ eine zunächst beliebige Konstante. Bezeichne ${\displaystyle Y}$ im Folgenden zur Vereinfachung der Schreibweise eine neue Zufallsvariable vermöge ${\displaystyle \textstyle Y=\exp \left(t\sum X_{i}\right)}$. Auf Grund der Monotonie der Abbildung ${\displaystyle x\mapsto \exp(tx)}$ folgt dann

${\displaystyle P\left[\sum X_{i}\geq (1+\delta )\cdot pn\right]=P\left[Y\geq \exp \left(t(1+\delta )\cdot pn\right)\right]=P\left[Y\geq k{\textrm {E}}\left[Y\right]\right]\leq {\frac {1}{k}}}$,

wobei ${\displaystyle k}$ als ${\displaystyle k={\tfrac {\exp(t(1+\delta )pn)}{{\textrm {E}}[Y]}}}$ definiert ist und die letzte Abschätzung mittels Markow-Ungleichung folgt. Nun gilt

${\displaystyle {\textrm {E}}\left[\exp(tX_{i})\right]=(1-p)e^{0}+pe^{t}=1+(e^{t}-1)p}$

und somit

${\displaystyle {\textrm {E}}\left[Y\right]={\textrm {E}}\left[\exp(t\sum X_{i})\right]={\textrm {E}}\left[\prod \exp(tX_{i})\right]=\prod {\textrm {E}}\left[\exp(tX_{i})\right]=\left(1+(e^{t}-1)p\right)^{n}}$.

Damit folgt

${\displaystyle {\frac {1}{k}}=e^{-t(1+\delta )pn}\left(1+(e^{t}-1)p\right)^{n}\leq e^{-t(1+\delta )pn}\cdot e^{(e^{t}-1)pn}=e^{-t(1+\delta )pn+(e^{t}-1)pn}}$.

Betrachte nun ${\displaystyle t=\log(1+\delta )}$. Dann gilt

${\displaystyle {\frac {1}{k}}\leq e^{-(\log(1+\delta ))(1+\delta )pn+\delta pn}=e^{(\delta -(1+\delta )\log(1+\delta ))pn}}$.

Für e​inen Teil d​es Exponenten d​es rechten Terms

${\displaystyle L(\delta )=(1+\delta )\log(1+\delta )}$

kann man mittels Kurvendiskussion und Taylor-Reihenentwicklung zeigen, dass stets ${\displaystyle L(\delta )\geq \delta +{\tfrac {1}{3}}\min\{\delta ,\delta ^{2}\}}$ gilt. Auf Grund der Monotonie der Exponentialfunktion gilt

${\displaystyle {\frac {1}{k}}\leq e^{(\delta -(\delta +{\frac {1}{3}}\min\{\delta ,\delta ^{2}\}))pn}=\exp \left(-{\frac {\min\{\delta ,\delta ^{2}\}}{3}}pn\right)}$.

Zusammen m​it der ersten Abschätzung f​olgt die Behauptung.

Zweite Chernoff-Schranke

Der Beweis d​er zweiten Schranke f​olgt technisch analog z​ur ersten Schranke.

Varianten

Eine allgemeine Variante der Chernoff-Ungleichung lässt sich mittels der Standardabweichung formulieren. Seien ${\displaystyle X_{1},X_{2},\ldots ,X_{n}}$ diskrete, unabhängige Zufallsvariablen mit ${\displaystyle {\textrm {E}}[X_{i}]=0}$ und ${\displaystyle |X_{i}|\leq 1}$. Bezeichne ${\displaystyle \sigma ^{2}}$ die Varianz von ${\displaystyle \textstyle X=\sum X_{i}}$. Dann gilt für jedes ${\displaystyle 0<\lambda \leq 2\sigma }$:

${\displaystyle P\left[\left|\sum X_{i}\right|\geq \lambda \sigma \right]\leq 2\exp \left(-{\frac {\lambda ^{2}}{4}}\right)}$

Der Beweis i​st technisch analog z​u dem o​ben 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 ${\displaystyle X_{1},X_{2},\ldots ,X_{10}}$ mit ${\displaystyle pn={\tfrac {1}{2}}\cdot 10=5}$ dar. Somit folgt nach der ersten Chernoff-Ungleichung:

${\displaystyle P\left[\sum X_{i}\geq 7\right]=P\left[\sum X_{i}\geq \left(1+{\frac {4}{10}}\right)\cdot 5\right]}$

${\displaystyle \leq \exp \left(-{\frac {\min\{{\frac {4}{10}},{\frac {16}{100}}\}}{3}}\cdot 5\right)=\exp \left(-{\frac {4}{15}}\right)\approx 0{,}766\ldots }$

• 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:

${\displaystyle P\left[\sum X_{i}\geq 70\right]=P\left[\sum X_{i}\geq \left(1+{\frac {4}{10}}\right)\cdot 50\right]}$

${\displaystyle \leq \exp \left(-{\frac {\min\{{\frac {4}{10}},{\frac {16}{100}}\}}{3}}\cdot 50\right)=\exp \left(-{\frac {8}{3}}\right)\approx 0{,}069\ldots }$

Literatur

• Christian Schindelhauer, Algorithmen für Peer-to-Peer Netzwerke (Vorlesungsmaterialien), http://wwwcs.upb.de/cs/ag-madh/WWW/Teaching/2004SS/AlgoP2P/skript.html, Universität Paderborn, 2004.
• Kirill Levchenko, Notizen, http://www.cs.ucsd.edu/~klevchen/techniques/chernoff.pdf

Einzelnachweise

1. Herman Chernoff: A career in statistics. In: Xihong Lin, Christian Genest, David L. Banks, Geert Molenberghs, David W. Scott, Jane-Ling Wang (Hrsg.): Past, Present, and Future of Statistics. CRC Press, 2014, ISBN 978-1-4822-0496-4, S. 35 (crcpress.com).
2. John Bather: A Conversation with Herman Chernoff. In: Statistical Science. 11, Nr. 4, November 1996, S. 335–350. doi:10.1214/ss/1032280306.