Inegalitatea Chernoff
În teoria probabilității , inegalitatea lui Chernoff permite limitarea cozii unei legi a probabilității , adică dă o valoare maximă a probabilității ca o variabilă aleatorie să depășească o valoare fixă. Vorbim și despre Chernoff .
Este comparabilă cu inegalitatea lui Markov, dar oferă o legătură exponențială. Acesta poartă numele lui Herman Chernoff .
Declarații
Există multe afirmații și multe cazuri speciale.
Caz general
Fie o variabilă reală aleatorie a cărei funcție generează momente astfel încât:
X{\ displaystyle X}
ϕ(t)=E[etX]<+∞,{\ displaystyle \ phi (t) = \ mathbb {E} [e ^ {tX}] <+ \ infty,}Deci, pentru orice ,
la≥0{\ displaystyle \ scriptstyle a \ geq 0}
P(X≥la)≤e-tlaE[etX]{\ displaystyle \ mathbb {P} \ left (X \ geq a \ right) \ leq e ^ {- ta} \ mathbb {E} [e ^ {tX}]} și
P(X≤-la)≤e-tlaE[etX]{\ displaystyle \ mathbb {P} \ left (X \ leq -a \ right) \ leq e ^ {- ta} \ mathbb {E} [e ^ {tX}]}
Cu variabile simetrice și așteptare zero
Lăsați de variabile aleatoare independente , astfel încât și pentru orice i . Cerem si noi numim σ 2 variația lui X .
X1,X2,...,Xnu{\ displaystyle X_ {1}, X_ {2}, \ dots, X_ {n}} E[Xeu]=0{\ displaystyle \ mathbb {E} [X_ {i}] = 0}|Xeu|≤1{\ displaystyle \ left | X_ {i} \ right | \ leq 1 \,}X=∑eu=1nuXeu{\ displaystyle X = \ sum _ {i = 1} ^ {n} X_ {i}}
Deci, avem pentru toate :
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}}precum și ,
P(-X≥kσ)≤e-k2/4{\ displaystyle \ mathbb {P} (-X \ geq k \ sigma) \ leq e ^ {- k ^ {2} / 4}}
și deci și .
P(|X|≥kσ)≤2e-k2/4{\ displaystyle \ mathbb {P} (\ left | X \ right | \ geq k \ sigma) \ leq 2e ^ {- k ^ {2} / 4}}
Cu variabile simetrice booleene
Fie variabile aleatorii booleene (adică cu valori în {0,1}) să fie independente, cu aceeași așteptare p , atunci ,
X1,X2,...,Xnu{\ displaystyle X_ {1}, X_ {2}, \ dots, X_ {n}}∀ϵ>0{\ displaystyle \ forall \ epsilon> 0}
P(1nu∑eu=1nuXeu>p+ε)≤e-2ε2nu{\ displaystyle \ mathbb {P} \ left ({\ frac {1} {n}} \ sum _ {i = 1} ^ {n} X_ {i}> p + \ varepsilon \ right) \ leq e ^ { - 2 \ varepsilon ^ {2} n}}, și .
P(1nu∑eu=1nuXeu<p-ε)≤e-2ε2nu{\ displaystyle \ mathbb {P} \ left ({\ frac {1} {n}} \ sum _ {i = 1} ^ {n} X_ {i} <p- \ varepsilon \ right) \ leq e ^ { -2 \ varepsilon ^ {2} n}}Dovadă
Există mai multe modalități de a demonstra aceste inegalități.
Caz general
Demonstrație
Pentru prima inegalitate ,
∀la≥0, ∀t≥0{\ displaystyle \ forall a \ geq 0, ~ \ forall t \ geq 0}
et(X-la)≥1{X≥la}⇒E[et(X-la)]≥P(X≥la)⇒E[etX]e-tla≥P(X≥la).{\ displaystyle {\ begin {align} \ mathrm {e} ^ {t (Xa)} & \ geq {1} _ {\ {X \ geq a \}} \\\ Rightarrow E \ left [\ mathrm {e } ^ {t (Xa)} \ right] & \ geq P (X \ geq a) \\\ Rightarrow E \ left [\ mathrm {e} ^ {tX} \ right] \ mathrm {e} ^ {- ta } & \ geq P (X \ geq a). \\\ end {align}}}De unde,
P(X≥la)≤e-(tla-ln(ϕ(t))),{\ displaystyle {\ begin {align} P (X \ geq a) & \ leq e ^ {- (ta- \ ln (\ phi (t)))}, \ end {align}}}și, așa cum este adevărat pentru toate , obținem acest lucru
t≥0{\ displaystyle t \ geq 0}
P(X≥la)≤inft≥0 e-(tla-ln(ϕ(t))=e-cinat≥0{tla-ln(ϕ(t))}=e-h(la).{\ 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}}}
Pentru a doua inegalitate ,
∀la≥0, ∀t≤0{\ displaystyle \ forall a \ geq 0, ~ \ forall t \ leq 0}
et(X+la)≥1{X≤-la}⇒P(X≤-la)≤E[et(X+la)]≤etlaeln(ϕ(t))≤e-(-tla-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}}}la fel ca înainte:
P(X≤-la)≤e-h(-la).{\ displaystyle P (X \ leq -a) \ leq \ mathrm {e} ^ {- h (-a)}.}
Cu variabile simetrice booleene
Demonstrație
Pentru prima inegalitate , stabilim și unde X urmează o lege Bernoulli cu parametrul p. Prin inegalitatea Chernoff aplicată ,
Z=X-p{\ displaystyle Z = Xp}Z¯nu=1nu∑eu=1nuZeu{\ displaystyle {\ overline {Z}} _ {n} = {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} Z_ {i}}Z¯nu{\ displaystyle {\ overline {Z}} _ {n}}
P(1nu∑eu=1nuXeu≥p+ϵ)=P(Z¯nu≥ϵ)≤e-hZ¯nu(ϵ).{\ 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 {aliniat}}}Aur . Într-adevăr, așa cum sunt iid și, prin urmare, sunt iid,
hZ¯nu(ϵ)=cinat≥0{ϵt-ln(E[etZ¯nu])}=nuhZ(ϵ){\ displaystyle h _ {{\ overline {Z}} _ {n}} (\ epsilon) = \ sup _ {t \ geq 0} \ {\ epsilon t- \ ln (E [\ mathrm {e} ^ { t {\ overline {Z}} _ {n}}]) \} = nh_ {Z} (\ epsilon)}{Xeu}eu∈[1,nu]{\ displaystyle \ {X_ {i} \} _ {i \ în [\! 1, n \!]}}{Zeu}eu∈[1,nu]{\ displaystyle \ {Z_ {i} \} _ {i \ în [\! 1, n \!]}}
E[etZ¯nu]=∏eu=1nuE[etnuZeu]=E[etnuZ]nu.{\ 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}}}De unde,
hZ¯nu(ϵ)=cinat≥0{ϵt-ln(E[etZ¯nu])}=cinat≥0{ϵt-nuln(E[etnuZ])}=nucinat≥0{ϵtnu-ln(E[etnuZ])}=nuhZ(ϵ).{\ 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}}}Prin urmare,
P(1nu∑eu=1nuXeu≥p+ϵ)≤e-nucinat≥0{ϵt-ln(E[etZ])}≤enuinft≥0{ln(E[etZ])-ϵt}≤enu(ln(E[etZ])-ϵt)(pentru 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}}}Observăm că .
Prin urmareE[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}}}cu .
Pentru a utiliza formula lui Taylor Lagrange la ordinea 2, calculăm prima și a doua derivate ,
∀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}}}cu . Putem crește cu .
Într-adevăr ,.
α=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αβ și (α-β)2=α2+β2-2αβ≥0⇒2αβ≤α2+β2⇒(α+β)2≥4αβ{\ displaystyle (\ alpha + \ beta) ^ {2} = \ alpha ^ {2} + \ beta ^ {2} +2 \ alpha \ beta {\ text {și}} (\ 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}
Deci, ca , în conformitate cu Taylor formula 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}}}cu .
Deci ,
θ∈[0,1]{\ displaystyle \ theta \ in [0,1]}
∀t≥0{\ displaystyle \ forall t \ geq 0}
P(1nu∑eu=1nuXeu≥p+ϵ)≤enu(ln(E[etZ])-ϵt)≤enu(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 {aliniat}}}Fie . Observăm .
Deci, g admite un minim în .
Astfel ,
∀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(1nu∑eu=1nuXeu≥p+ϵ)≤enu(16ϵ28-4ϵ2)≤e-2nuϵ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}}}Pentru a doua inegalitate , ,
∀ϵ>0{\ displaystyle \ forall \ epsilon> 0}
P(1nu∑eu=1nuXeu≤p-ϵ)=P(Z¯nu≤-ϵ)=P(-Z¯nu≥ϵ)≤e-h-Z¯nu(t) din inegalitatea lui Chernoff≤e-nuh-Z(t)≤enuinft≥0{ln(E[e-tZ])-ϵt}≤enu(ln(E[e-tZ])-ϵt)(pentru 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 {conform inegalității Chernoff}} \\ & \ 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}}}Rețineți că: ,
∀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}}}Deci ,
∀ϵ>0, ∀t≥0{\ displaystyle \ forall \ epsilon> 0, ~ \ forall t \ geq 0}
P(1nu∑eu=1nuXeu≤p-ϵ)≤enu(t28-ϵt)≤e-2nuϵ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 {aliniat}}}printr-un argument similar care a servit pentru a demonstra prima inegalitate.
Aplicații
Aceste inegalități sunt utilizate pe scară largă în informatica teoretică , în special în teoria complexității și în algoritmi , unde fac posibilă demonstrarea rezultatelor pe algoritmi probabilistici .
A se vedea, de asemenea, teoria abaterilor mari .
Extensii
Putem scrie generalizări interesante pentru matricele aleatorii , numite în limba engleză matricea Chernoff bound (en) .
Referințe
-
Brémaud 2009 , p. 184
-
Wolfgang Mulzer, „ Cinci dovezi ale legăturii lui Chernoff cu aplicații ”, Buletinul EATCS , nr . 124,
februarie 2018( citește online ).
-
Joel A Tropp, „ Limitele cozii ușor de utilizat pentru sume de matrice aleatorii ” , Foundations of Computational Mathematics , vol. 12, n o 4,
2012, p. 389-434
Vezi și tu
Bibliografie
-
Pierre Brémaud , Introduction to Probability: and Markov Chains , Springer Science & Business Media,2009, 311 p. ( ISBN 978-3-540-31421-9 , citit online )