Chernoff-Ungleichung

In der Wahrscheinlichkeitstheorie ermöglicht die Ungleichung von Chernoff die Begrenzung des Endes eines Wahrscheinlichkeitsgesetzes , dh es gibt einen Maximalwert für die Wahrscheinlichkeit, dass eine Zufallsvariable einen festen Wert überschreitet. Wir sprechen auch von Chernoff gebunden .

Es ist vergleichbar mit der Markov-Ungleichung , gibt jedoch eine exponentielle Grenze. Es ist nach Herman Chernoff benannt .

Aussagen

Es gibt viele Aussagen und viele Sonderfälle.

Allgemeiner Fall

Sei eine echte Zufallsvariable, deren funktionserzeugende Momente so sind, dass: X.{\ displaystyle X}

ϕ((t)=E.[etX.]]<+∞,{\ displaystyle \ phi (t) = \ mathbb {E} [e ^ {tX}] <+ \ infty,}

Also für alles , beim≥0{\ displaystyle \ scriptstyle a \ geq 0}

P.((X.≥beim)≤e- -tbeimE.[etX.]]{\ displaystyle \ mathbb {P} \ left (X \ geq a \ right) \ leq e ^ {- ta} \ mathbb {E} [e ^ {tX}]} und P.((X.≤- -beim)≤e- -tbeimE.[etX.]]{\ displaystyle \ mathbb {P} \ left (X \ leq -a \ right) \ leq e ^ {- ta} \ mathbb {E} [e ^ {tX}]}

Mit symmetrischen Variablen und Nullerwartung

Lassen Sie die Zufallsvariablen so unabhängig sein , dass und für jedes i . Wir bitten und wir nennen σ 2 die Varianz von X . X.1,X.2,...,X.nicht{\ displaystyle X_ {1}, X_ {2}, \ dots, X_ {n}} E.[X.ich]]=0{\ displaystyle \ mathbb {E} [X_ {i}] = 0}|X.ich|≤1{\ displaystyle \ left | X_ {i} \ right | \ leq 1 \,}X.=∑ich=1nichtX.ich{\ displaystyle X = \ sum _ {i = 1} ^ {n} X_ {i}}

Wir haben also für alles : 0≤k≤2σ{\ displaystyle 0 \ leq k \ leq 2 \ sigma \,}

P.((X.≥kσ)≤e- -k2/.4{\ displaystyle \ mathbb {P} (X \ geq k \ sigma) \ leq e ^ {- k ^ {2} / 4}}sowie ,P.((- -X.≥kσ)≤e- -k2/.4{\ displaystyle \ mathbb {P} (-X \ geq k \ sigma) \ leq e ^ {- k ^ {2} / 4}} und deshalb auch .P.((|X.|≥kσ)≤2e- -k2/.4{\ displaystyle \ mathbb {P} (\ left | X \ right | \ geq k \ sigma) \ leq 2e ^ {- k ^ {2} / 4}}

Mit booleschen symmetrischen Variablen

Lassen Sie Boolesche Zufallsvariablen (dh mit Werten in {0,1}) unabhängig ist , mit der gleichen Erwartung p , dann , X.1,X.2,...,X.nicht{\ displaystyle X_ {1}, X_ {2}, \ dots, X_ {n}}∀ϵ>0{\ displaystyle \ forall \ epsilon> 0}

P.((1nicht∑ich=1nichtX.ich>p+ε)≤e- -2ε2nicht{\ displaystyle \ mathbb {P} \ left ({\ frac {1} {n}} \ sum _ {i = 1} ^ {n} X_ {i}> p + \ varepsilon \ right) \ leq e ^ { - 2 \ varepsilon ^ {2} n}}und .P.((1nicht∑ich=1nichtX.ich<p- -ε)≤e- -2ε2nicht{\ displaystyle \ mathbb {P} \ left ({\ frac {1} {n}} \ sum _ {i = 1} ^ {n} X_ {i} <p- \ varepsilon \ right) \ leq e ^ { -2 \ varepsilon ^ {2} n}}

Beweis

Es gibt verschiedene Möglichkeiten, diese Ungleichheiten zu beweisen.

Allgemeiner Fall

Demonstration

Für die erste Ungleichheit , ∀beim≥0, ∀t≥0{\ displaystyle \ forall a \ geq 0, ~ \ forall t \ geq 0}

et((X.- -beim)≥1{X.≥beim}}⇒E.[et((X.- -beim)]]≥P.((X.≥beim)⇒E.[etX.]]e- -tbeim≥P.((X.≥beim).{\ displaystyle {\ begin {align} \ mathrm {e} ^ {t (Xa)} & \ geq {1} _ {\ {X \ geq a \}} \\\ Rightarrow E \ left [\ mathrm {e } ^ {t (Xa)} \ rechts] & \ geq P (X \ geq a) \\\ Rechtspfeil E \ links [\ mathrm {e} ^ {tX} \ rechts] \ mathrm {e} ^ {- ta } & \ geq P (X \ geq a). \\\ end {align}}}

Wovon,

P.((X.≥beim)≤e- -((tbeim- -ln⁡((ϕ((t))),{\ displaystyle {\ begin {align} P (X \ geq a) & \ leq e ^ {- (ta- \ ln (\ phi (t)))}, \ end {align}}}

und wie für alles gilt , bekommen wir das t≥0{\ displaystyle t \ geq 0}

P.((X.≥beim)≤inft≥0 e- -((tbeim- -ln⁡((ϕ((t))=e- -supt≥0{tbeim- -ln⁡((ϕ((t))}}=e- -h((beim).{\ displaystyle {\ begin {align} P (X \ geq a) & \ leq \ inf _ {t \ geq 0} \ \ mathrm {e} ^ {- (ta- \ ln (\ phi (t))} \\ & = \ mathrm {e} ^ {- \ sup _ {t \ geq 0} \ {ta- \ ln (\ phi (t)) \}} \\ & = \ mathrm {e} ^ {- h (a)}. \ end {align}}}

Für die zweite Ungleichheit , ∀beim≥0, ∀t≤0{\ displaystyle \ forall a \ geq 0, ~ \ forall t \ leq 0}

et((X.+beim)≥1{X.≤- -beim}}⇒P.((X.≤- -beim)≤E.[et((X.+beim)]]≤etbeimeln⁡((ϕ((t))≤e- -((- -tbeim- -ln⁡((ϕ((t))),{\ displaystyle {\ begin {align} \ mathrm {e} ^ {t (X + a)} \ geq {1} _ {\ {X \ leq -a \}} \\\ Rightarrow P (X \ leq - a) & \ leq E \ left [\ mathrm {e} ^ {t (X + a)} \ right] \\ & \ leq \ mathrm {e} ^ {ta} \ mathrm {e} ^ {\ ln ( \ phi (t))} \\ & \ leq \ mathrm {e} ^ {- (- ta- \ ln (\ phi (t)))}, \ end {align}}}

so wie zuvor:

P.((X.≤- -beim)≤e- -h((- -beim).{\ displaystyle P (X \ leq -a) \ leq \ mathrm {e} ^ {- h (-a)}.}

Mit booleschen symmetrischen Variablen

Demonstration

Für die erste Ungleichung setzen wir und wobei X einem Bernoulli-Gesetz mit dem Parameter p folgt. Durch die Chernoff-Ungleichung angewendet auf , Z.=X.- -p{\ displaystyle Z = Xp}Z.¯nicht=1nicht∑ich=1nichtZ.ich{\ displaystyle {\ overline {Z}} _ {n} = {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} Z_ {i}}Z.¯nicht{\ displaystyle {\ overline {Z}} _ {n}}

P.((1nicht∑ich=1nichtX.ich≥p+ϵ)=P.((Z.¯nicht≥ϵ)≤e- -hZ.¯nicht((ϵ).{\ displaystyle {\ begin {align} P ({\ frac {1} {n}} \ sum _ {i = 1} ^ {n} X_ {i} \ geq p + \ epsilon) & = P ({\ overline {Z}} _ {n} \ geq \ epsilon) \\ & \ leq \ mathrm {e} ^ {- h _ {{\ overline {Z}} _ {n}} (\ epsilon)}. \ End {ausgerichtet}}}

Gold . In der Tat, wie iid und daher iid sind, hZ.¯nicht((ϵ)=supt≥0{ϵt- -ln⁡((E.[etZ.¯nicht]])}}=nichthZ.((ϵ){\ displaystyle h _ {{\ overline {Z}} _ {n}} (\ epsilon) = \ sup _ {t \ geq 0} \ {\ epsilon t- \ ln (E [\ mathrm {e} ^ { t {\ overline {Z}} _ {n}}]) \} = nh_ {Z} (\ epsilon)}{X.ich}}ich∈[1,nicht]]{\ displaystyle \ {X_ {i} \} _ {i \ in [\! 1, n \!]}}{Z.ich}}ich∈[1,nicht]]{\ displaystyle \ {Z_ {i} \} _ {i \ in [\! 1, n \!]}}

E.[etZ.¯nicht]]=∏ich=1nichtE.[etnichtZ.ich]]=E.[etnichtZ.]]nicht.{\ displaystyle {\ begin {align} E [\ mathrm {e} ^ {t {\ overline {Z}} _ {n}}] & = \ prod _ {i = 1} ^ {n} E [\ mathrm {e} ^ {{\ frac {t} {n}} Z_ {i}}] \\ & = E [\ mathrm {e} ^ {{\ frac {t} {n}} Z}] ^ {n }. \ end {align}}}

Wovon,

hZ.¯nicht((ϵ)=supt≥0{ϵt- -ln⁡((E.[etZ.¯nicht]])}}=supt≥0{ϵt- -nichtln⁡((E.[etnichtZ.]])}}=nichtsupt≥0{ϵtnicht- -ln⁡((E.[etnichtZ.]])}}=nichthZ.((ϵ).{\ displaystyle {\ begin {align} h _ {{\ overline {Z}} _ {n}} (\ epsilon) & = \ sup _ {t \ geq 0} \ {\ epsilon t- \ ln (E [ \ mathrm {e} ^ {t {\ overline {Z}} _ {n}}]) \} \\ & = \ sup _ {t \ geq 0} \ {\ epsilon tn \ ln (E [\ mathrm { e} ^ {{\ frac {t} {n}} Z}]) \} \\ & = n \ sup _ {t \ geq 0} \ {\ epsilon {\ frac {t} {n}} - \ ln (E [\ mathrm {e} ^ {{\ frac {t} {n}} Z}]) \} \\ & = nh_ {Z} (\ epsilon). \ End {align}}}

Deshalb,

P.((1nicht∑ich=1nichtX.ich≥p+ϵ)≤e- -nichtsupt≥0{ϵt- -ln⁡((E.[etZ.]])}}≤enichtinft≥0{ln⁡((E.[etZ.]])- -ϵt}}≤enicht((ln⁡((E.[etZ.]])- -ϵt)((zum t≥0).{\ displaystyle {\ begin {align} P ({\ frac {1} {n}} \ sum _ {i = 1} ^ {n} X_ {i} \ geq p + \ epsilon) & \ leq \ mathrm { e} ^ {- n \ sup _ {t \ geq 0} \ {\ epsilon t- \ ln (E [\ mathrm {e} ^ {tZ}]) \}} \\ & \ leq \ mathrm {e} ^ {n \ inf _ {t \ geq 0} \ {\ ln (E [\ mathrm {e} ^ {tZ}]) - \ epsilon t \}} \\ & \ leq \ mathrm {e} ^ {n (\ ln (E [\ mathrm {e} ^ {tZ}]) - \ epsilon t)} ({\ text {pour}} t \ geq 0). \ end {align}}}

Das merken wir . DeshalbE.[etZ.]]=e- -ptE.[etX.]]=e- -pt((1- -p+et){\ displaystyle E [\ mathrm {e} ^ {tZ}] = \ mathrm {e} ^ {- pt} E [\ mathrm {e} ^ {tX}] = \ mathrm {e} ^ {- pt} ( 1-p + \ mathrm {e} ^ {t})}
∀t≥0,{\ displaystyle \ forall t \ geq 0,}

ln⁡((E.[etZ.]])- -ϵt=ln⁡((1- -p+et)- -((ϵ+p)t=Ψ((t)- -ϵt,{\ displaystyle {\ begin {align} \ ln (E [\ mathrm {e} ^ {tZ}]) - \ epsilon t & = \ ln (1-p + \ mathrm {e} ^ {t}) - ( \ epsilon + p) t \\ & = \ Psi (t) - \ epsilon t, \ end {align}}}

mit . Um die Taylor Lagrange-Formel in Ordnung 2 zu verwenden, berechnen wir die erste und die zweite Ableitung . ∀t∈R., Ψ((t)=- -pt+ln⁡((1- -p+et){\ displaystyle \ forall t \ in \ mathbb {R}, ~ \ Psi (t) = - pt + \ ln (1-p + \ mathrm {e} ^ {t})}
Ψ{\ displaystyle \ Psi}

∀t∈R., Ψ'((t)=- -p+pet1- -p+petΨ″((t)=((1- -p)pet((1- -p+pet)2=αβ((α+β)2≤14,{\ displaystyle {\ begin {align} \ forall t \ in \ mathbb {R}, ~ \ Psi ^ {'} (t) & = - p + {\ frac {p \ mathrm {e} ^ {t}} {1-p + p \ mathrm {e} ^ {t}}} \\\ Psi ^ {''} (t) & = {\ frac {(1-p) p \ mathrm {e} ^ {t} } {(1-p + p \ mathrm {e} ^ {t}) ^ {2}}} \\ & = {\ frac {\ alpha \ beta} {(\ alpha + \ beta) ^ {2}} } \\ & \ leq {\ frac {1} {4}}, \ end {align}}}

mit . Wir können erhöhen durch . In der Tat . α=1- -p, β=pet{\ displaystyle \ alpha = 1-p, ~ \ beta = p \ mathrm {e} ^ {t}}Ψ″((t){\ displaystyle \ Psi ^ {''} (t)}14{\ displaystyle {\ frac {1} {4}}}
((α+β)2=α2+β2+2αβ und ((α- -β)2=α2+β2- -2αβ≥0⇒2αβ≤α2+β2⇒((α+β)2≥4αβ{\ displaystyle (\ alpha + \ beta) ^ {2} = \ alpha ^ {2} + \ beta ^ {2} +2 \ alpha \ beta {\ text {und}} (\ alpha - \ beta) ^ { 2} = \ alpha ^ {2} + \ beta ^ {2} -2 \ alpha \ beta \ geq 0 \ Rightarrow 2 \ alpha \ beta \ leq \ alpha ^ {2} + \ beta ^ {2} \ Rightarrow ( \ alpha + \ beta) ^ {2} \ geq 4 \ alpha \ beta}

So, wie nach Taylors Formel Lagrange , , Ψ((0)=Ψ'((0)=0{\ displaystyle \ Psi (0) = \ Psi ^ {'} (0) = 0}∀t∈R.{\ displaystyle \ forall t \ in \ mathbb {R}}

Ψ((t)=Ψ((0)+tΨ'((0)+t22Ψ″((θt)≤t28,{\ displaystyle {\ begin {align} \ Psi (t) & = \ Psi (0) + t \ Psi ^ {'} (0) + {\ frac {t ^ {2}} {2}} \ Psi ^ {''} (\ theta t) \\ & \ leq {\ frac {t ^ {2}} {8}}, \ end {align}}}

mit . Also , θ∈[0,1]]{\ displaystyle \ theta \ in [0,1]}
∀t≥0{\ displaystyle \ forall t \ geq 0}

P.((1nicht∑ich=1nichtX.ich≥p+ϵ)≤enicht((ln⁡((E.[etZ.]])- -ϵt)≤enicht((t28- -ϵt).{\ displaystyle {\ begin {align} P ({\ frac {1} {n}} \ sum _ {i = 1} ^ {n} X_ {i} \ geq p + \ epsilon) & \ leq \ mathrm { e} ^ {n (\ ln (E [\ mathrm {e} ^ {tZ}]) - \ epsilon t)} \\ & \ leq \ mathrm {e} ^ {n ({\ frac {t ^ {2 }} {8}} - \ epsilon t)}. \ End {align}}}

Entweder . Wir bemerken . Also gibt g ein Minimum in zu . Somit ist ∀t≥0, G((t)=t28- -ϵt{\ displaystyle \ forall t \ geq 0, ~ g (t) = {\ frac {t ^ {2}} {8}} - \ epsilon t}∀t≥0, G'((t)=t4- -ϵ{\ displaystyle \ forall t \ geq 0, ~ g ^ {'} (t) = {\ frac {t} {4}} - \ epsilon}
t=4ϵ{\ displaystyle t = 4 \ epsilon}
∀ϵ>0{\ displaystyle \ forall \ epsilon> 0}

P.((1nicht∑ich=1nichtX.ich≥p+ϵ)≤enicht((16ϵ28- -4ϵ2)≤e- -2nichtϵ2.{\ displaystyle {\ begin {align} P ({\ frac {1} {n}} \ sum _ {i = 1} ^ {n} X_ {i} \ geq p + \ epsilon) & \ leq \ mathrm { e} ^ {n ({\ frac {16 \ epsilon ^ {2}} {8}} - 4 \ epsilon ^ {2})} \\ & \ leq \ mathrm {e} ^ {- 2n \ epsilon ^ { 2}}. \ End {align}}}

Für die zweite Ungleichung , , ∀ϵ>0{\ displaystyle \ forall \ epsilon> 0}

P.((1nicht∑ich=1nichtX.ich≤p- -ϵ)=P.((Z.¯nicht≤- -ϵ)=P.((- -Z.¯nicht≥ϵ)≤e- -h- -Z.¯nicht((t) von Chernoffs Ungleichung≤e- -nichth- -Z.((t)≤enichtinft≥0{ln⁡((E.[e- -tZ.]])- -ϵt}}≤enicht((ln⁡((E.[e- -tZ.]])- -ϵt)((zum t≥0).{\ displaystyle {\ begin {align} P ({\ frac {1} {n}} \ sum _ {i = 1} ^ {n} X_ {i} \ leq p- \ epsilon) & = P ({\ overline {Z}} _ {n} \ leq - \ epsilon) \\ & = P (- {\ overline {Z}} _ {n} \ geq \ epsilon) \\ & \ leq \ mathrm {e} ^ { -h _ {- {\ overline {Z}} _ {n}} (t)} {\ text {gemäß der Chernoff-Ungleichung}} \\ & \ leq \ mathrm {e} ^ {- nh _ {- Z. } (t)} \\ & \ leq \ mathrm {e} ^ {n \ inf _ {t \ geq 0} \ {\ ln (E [\ mathrm {e} ^ {- tZ}]) - \ epsilon t \}} \\ & \ leq \ mathrm {e} ^ {n (\ ln (E [\ mathrm {e} ^ {- tZ}]) - \ epsilon t)} ({\ text {for}} t \ geq 0). \ end {align}}}

Beachten Sie, dass: , ∀t≥0{\ displaystyle \ forall t \ geq 0}

E.[e- -tZ.]]=eptE.[e- -tX.]]=ept((1- -p+pe- -t)⇒ln⁡((E.[e- -tZ.]])=pt+ln⁡((1- -p+pe- -t)=Ψ((- -t)≤t28.{\ displaystyle {\ begin {align} E [\ mathrm {e} ^ {- tZ}] & = \ mathrm {e} ^ {pt} E [\ mathrm {e} ^ {- tX}] \\ & = \ mathrm {e} ^ {pt} (1-p + p \ mathrm {e} ^ {- t}) \\\ Rightarrow \ ln (E [\ mathrm {e} ^ {- tZ}]) & = pt + \ ln (1-p + p \ mathrm {e} ^ {- t}) \\ & = \ Psi (-t) \\ & \ leq {\ frac {t ^ {2}} {8}}. \ end {align}}}

Also , ∀ϵ>0, ∀t≥0{\ displaystyle \ forall \ epsilon> 0, ~ \ forall t \ geq 0}

P.((1nicht∑ich=1nichtX.ich≤p- -ϵ)≤enicht((t28- -ϵt)≤e- -2nichtϵ2,{\ displaystyle {\ begin {align} P ({\ frac {1} {n}} \ sum _ {i = 1} ^ {n} X_ {i} \ leq p- \ epsilon) & \ leq \ mathrm { e} ^ {n ({\ frac {t ^ {2}} {8}} - \ epsilon t)} \\ & \ leq \ mathrm {e} ^ {- 2n \ epsilon ^ {2}}, \ end {ausgerichtet}}}

durch ein ähnliches Argument, das dazu diente, die erste Ungleichung zu demonstrieren.

Anwendungen

Diese Ungleichungen sind in der theoretischen Informatik weit verbreitet , insbesondere in der Komplexitätstheorie und in Algorithmen , wo sie es ermöglichen, Ergebnisse mit probabilistischen Algorithmen nachzuweisen .

Siehe auch Theorie großer Abweichungen .

Erweiterungen

Wir können interessante Verallgemeinerungen für Zufallsmatrizen schreiben , die in der englischen Matrix Chernoff bound  (en) genannt werden .

Verweise

1. Brémaud 2009 , p.  184
2. Wolfgang Mulzer "  Fünf Proofs von Chernoff der Bound with Applications  ", Bulletin der EATCS , n o  124, Februar 2018( online lesen ).
3. Joel A Tropp, „  Benutzerfreundliche Schwanzgrenzen für Summen zufälliger Matrizen  “, Foundations of Computational Mathematics , vol.  12, n o  4, 2012, p.  389-434

Siehe auch

Literaturverzeichnis

• (fr) Dieser Artikel stammt teilweise oder vollständig aus dem englischen Wikipedia- Artikel "  Chernoffs Ungleichung  " ( siehe Autorenliste ) .
• (en) Kirill Levchenko ( UCSD ), Chernoff gebunden

• Pierre Brémaud , Einführung in die Wahrscheinlichkeitsrechnung: und Markov Chains , Springer Science & Business Media,2009311  p. ( ISBN  978-3-540-31421-9 , online lesen )