Chernoff eşitsizliği

In olasılık teorisi , Chernoff'un eşitsizliği verir bir olasılık kanunun kuyruk yukarı sınırlanmış olarak bir olasılığı için kullanılan bir maksimum değeri verir, yani rastgele değişken sabit bir değerini aşıyor. Ayrıca Chernoff sınırından da bahsediyoruz .

Markov eşitsizliği ile karşılaştırılabilir, ancak üstel bir sınır verir. Herman Chernoff'un adını almıştır .

İfadeler

Birçok ifade ve birçok özel durum var.

Genel dava

Izin bir gerçek rasgele değişken olan fonksiyon anları üreten şekildedir: X{\ displaystyle X}

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

Yani, her şey için , -de≥0{\ displaystyle \ scriptstyle a \ geq 0}

P(X≥-de)≤e-t-deE[etX]{\ displaystyle \ mathbb {P} \ sol (X \ geq a \ sağ) \ leq e ^ {- ta} \ mathbb {E} [e ^ {tX}]} ve P(X≤--de)≤e-t-deE[etX]{\ displaystyle \ mathbb {P} \ sol (X \ leq -a \ sağ) \ leq e ^ {- ta} \ mathbb {E} [e ^ {tX}]}

Simetrik değişkenler ve sıfır beklenti ile

Let rasgele değişkenler bağımsız şekilde ve her için i . Soruyoruz ve biz σ diyoruz 2 varyansı arasında X . X1,X2,...,Xdeğil{\ displaystyle X_ {1}, X_ {2}, \ noktalar, X_ {n}} E[Xben]=0{\ displaystyle \ mathbb {E} [X_ {i}] = 0}|Xben|≤1{\ displaystyle \ sol | X_ {i} \ sağ | \ leq 1 \,}X=∑ben=1değilXben{\ displaystyle X = \ toplam _ {i = 1} ^ {n} X_ {i}}

Yani, her şey için sahibiz : 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}}sıra sıra ,P(-X≥kσ)≤e-k2/4{\ displaystyle \ mathbb {P} (-X \ geq k \ sigma) \ leq e ^ {- k ^ {2} / 4}} ve aynı zamanda .P(|X|≥kσ)≤2e-k2/4{\ displaystyle \ mathbb {P} (\ sol | X \ sağ | \ geq k \ sigma) \ leq 2e ^ {- k ^ {2} / 4}}

Boolean simetrik değişkenlerle

Let aynı beklenen ile, bağımsız (örn {0,1} değerleri ile) Boole rastgele değişkenler p , o , X1,X2,...,Xdeğil{\ displaystyle X_ {1}, X_ {2}, \ noktalar, X_ {n}}∀ϵ>0{\ displaystyle \ forall \ epsilon> 0}

P(1değil∑ben=1değilXben>p+ε)≤e-2ε2değil{\ displaystyle \ mathbb {P} \ sol ({\ frac {1} {n}} \ toplamı _ {i = 1} ^ {n} X_ {i}> p + \ varepsilon \ sağ) \ leq e ^ { - 2 \ varepsilon ^ {2} n}}ve .P(1değil∑ben=1değilXben<p-ε)≤e-2ε2değil{\ displaystyle \ mathbb {P} \ sol ({\ frac {1} {n}} \ toplamı _ {i = 1} ^ {n} X_ {i} <p- \ varepsilon \ sağ) \ leq e ^ { -2 \ varepsilon ^ {2} n}}

Kanıt

Bu eşitsizlikleri kanıtlamanın birkaç yolu var.

Genel dava

Gösteri

İlk eşitsizlik için , ∀-de≥0, ∀t≥0{\ displaystyle \ forall a \ geq 0, ~ \ forall t \ geq 0}

et(X--de)≥1{X≥-de}⇒E[et(X--de)]≥P(X≥-de)⇒E[etX]e-t-de≥P(X≥-de).{\ displaystyle {\ begin {align} \ mathrm {e} ^ {t (Xa)} & \ geq {1} _ {\ {X \ geq a \}} \\\ Rightarrow E \ sol [\ 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). \\\ uç {hizalı}}}

Nereden,

P(X≥-de)≤e-(t-de-ln⁡(ϕ(t))),{\ displaystyle {\ başlar {hizalı} P (X \ geq a) & \ leq e ^ {- (ta- \ ln (\ phi (t)))}, \ uç {hizalı}}}

ve her şey için doğru olduğu gibi , bunu anlıyoruz t≥0{\ displaystyle t \ geq 0}

P(X≥-de)≤inft≥0 e-(t-de-ln⁡(ϕ(t))=e-supt≥0{t-de-ln⁡(ϕ(t))}=e-h(-de).{\ displaystyle {\ başlar {hizalı} 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 {hizalı}}}

İkinci eşitsizlik için , ∀-de≥0, ∀t≤0{\ displaystyle \ forall a \ geq 0, ~ \ forall t \ leq 0}

et(X+-de)≥1{X≤--de}⇒P(X≤--de)≤E[et(X+-de)]≤et-deeln⁡(ϕ(t))≤e-(-t-de-ln⁡(ϕ(t))),{\ displaystyle {\ başlar {hizalı} \ mathrm {e} ^ {t (X + a)} \ geq {1} _ {\ {X \ leq -a \}} \\\ Sağa doğru 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 {hizalı}}}

eskisi gibi:

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

Boolean simetrik değişkenlerle

Gösteri

İçin ilk eşitsizlik , biz ayarlamak ve X parametresi p ile bir Bernoulli kanununa göre hareket eder nerede. Uygulanan Chernoff eşitsizliğine göre , Z=X-p{\ displaystyle Z = Xp}Z¯değil=1değil∑ben=1değilZben{\ displaystyle {\ overline {Z}} _ {n} = {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} Z_ {i}}Z¯değil{\ displaystyle {\ overline {Z}} _ {n}}

P(1değil∑ben=1değilXben≥p+ϵ)=P(Z¯değil≥ϵ)≤e-hZ¯değil(ϵ).{\ displaystyle {\ begin {align} P ({\ frac {1} {n}} \ sum _ {i = 1} ^ {n} X_ {i} \ geq p + \ epsilon) & = P ({\ üst üste {Z}} _ {n} \ geq \ epsilon) \\ & \ leq \ mathrm {e} ^ {- h _ {{\ overline {Z}} _ {n}} (\ epsilon)}. \ End {hizalı}}}

Altın . Nitekim, iid ve bu nedenle iid olduğu gibi, hZ¯değil(ϵ)=supt≥0{ϵt-ln⁡(E[etZ¯değil])}=değilhZ(ϵ){\ displaystyle h _ {{\ overline {Z}} _ {n}} (\ epsilon) = \ sup _ {t \ geq 0} \ {\ epsilon t- \ ln (E [\ mathrm {e} ^ { t {\ overline {Z}} _ {n}}]) \} = nh_ {Z} (\ epsilon)}{Xben}ben∈[1,değil]{\ displaystyle \ {X_ {i} \} _ {i \ [\! 1, n \!]}}{Zben}ben∈[1,değil]{\ displaystyle \ {Z_ {i} \} _ {i \ içinde [\! 1, n \!]}}

E[etZ¯değil]=∏ben=1değilE[etdeğilZben]=E[etdeğilZ]değil.{\ 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 {hizalı}}}

Nereden,

hZ¯değil(ϵ)=supt≥0{ϵt-ln⁡(E[etZ¯değil])}=supt≥0{ϵt-değilln⁡(E[etdeğilZ])}=değilsupt≥0{ϵtdeğil-ln⁡(E[etdeğilZ])}=değilhZ(ϵ).{\ 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 {hizalı}}}

Bu nedenle,

P(1değil∑ben=1değilXben≥p+ϵ)≤e-değilsupt≥0{ϵt-ln⁡(E[etZ])}≤edeğilinft≥0{ln⁡(E[etZ])-ϵt}≤edeğil(ln⁡(E[etZ])-ϵt)(için 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 {hizalı}}}

Bunu fark ediyoruz . Bu nedenleE[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 {\ başlar {hizalı} \ ln (E [\ mathrm {e} ^ {tZ}]) - \ epsilon t & = \ ln (1-p + \ mathrm {e} ^ {t}) - ( \ epsilon + p) t \\ & = \ Psi (t) - \ epsilon t, \ end {hizalı}}}

ile . Taylor Lagrange formülünü 2. sırada kullanmak için birinci ve ikinci türevleri hesaplıyoruz , ∀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 {hizalı}}}

ile . Biz artırabilir tarafından . Gerçekten ,. α=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αβ ve (α-β)2=α2+β2-2αβ≥0⇒2αβ≤α2+β2⇒(α+β)2≥4αβ{\ displaystyle (\ alpha + \ beta) ^ {2} = \ alpha ^ {2} + \ beta ^ {2} +2 \ alpha \ beta {\ text {ve}} (\ 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}

Yani, hem 'e göre Taylor formülü 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 {\ başlar {hizalı} \ Psi (t) & = \ Psi (0) + t \ Psi ^ {'} (0) + {\ frac {t ^ {2}} {2}} \ Psi ^ {''} (\ theta t) \\ & \ leq {\ frac {t ^ {2}} {8}}, \ end {hizalı}}}

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

P(1değil∑ben=1değilXben≥p+ϵ)≤edeğil(ln⁡(E[etZ])-ϵt)≤edeğil(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 {hizalı}}}

Ya . Fark ederiz . Yani g minimum giriş olduğunu kabul ediyor . Böylece , ∀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(1değil∑ben=1değilXben≥p+ϵ)≤edeğil(16ϵ28-4ϵ2)≤e-2değilϵ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 {hizalı}}}

İçin ikinci eşitsizlik , , ∀ϵ>0{\ displaystyle \ forall \ epsilon> 0}

P(1değil∑ben=1değilXben≤p-ϵ)=P(Z¯değil≤-ϵ)=P(-Z¯değil≥ϵ)≤e-h-Z¯değil(t) Chernoff eşitsizliğinden≤e-değilh-Z(t)≤edeğilinft≥0{ln⁡(E[e-tZ])-ϵt}≤edeğil(ln⁡(E[e-tZ])-ϵt)(için t≥0).{\ displaystyle {\ begin {align} P ({\ frac {1} {n}} \ sum _ {i = 1} ^ {n} X_ {i} \ leq p- \ epsilon) & = P ({\ üst üste {Z}} _ {n} \ leq - \ epsilon) \\ & = P (- {\ overline {Z}} _ {n} \ geq \ epsilon) \\ & \ leq \ mathrm {e} ^ { -h _ {- {\ overline {Z}} _ {n}} (t)} {\ text {Chernoff eşitsizliğine göre}} \\ & \ 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 {hizalı}}}

Not: , ∀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 {hizalı}}}

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

P(1değil∑ben=1değilXben≤p-ϵ)≤edeğil(t28-ϵt)≤e-2değilϵ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 {hizalı}}}

ilk eşitsizliği göstermeye hizmet eden benzer bir argümanla.

Başvurular

Bu eşitsizlikler, teorik bilgisayar biliminde , özellikle karmaşıklık teorisinde ve olasılıksal algoritmalar üzerinde sonuçları ispatlamayı mümkün kılan algoritmalarda yaygın olarak kullanılmaktadır .

Ayrıca bkz . Büyük sapmalar teorisi .

Uzantılar

İngilizce matris Chernoff bound (en) olarak adlandırılan rastgele matrisler için ilginç genellemeler yazabiliriz .  

Referanslar

1. Brémaud 2009 , s.  184
2. Wolfgang Mulzer, "  Chernoff'un Uygulamalar ile Bağlantısının Beş Kanıtı  ", EATCS Bülteni , n o  124, Şubat 2018( çevrimiçi okuyun ).
3. Joel A Tropp, "  Rastgele matrislerin toplamları için kullanıcı dostu kuyruk sınırları  " , Hesaplamalı Matematik Temelleri , cilt.  12, n, o  , 4, 2012, s.  389-434

Ayrıca görün

Kaynakça

• (fr) Bu makale kısmen veya tamamen alınır İngilizce Vikipedi başlıklı makalesinde "  Chernoff'un eşitsizliği  " ( yazarların listesini görmek ) .
• (tr) Kirill Levchenko ( UCSD ), Chernoff sınırı

• Pierre Brémaud , Olasılığa Giriş: ve Markov Zincirleri , Springer Science & Business Media,2009, 311  s. ( ISBN  978-3-540-31421-9 , çevrimiçi okuyun )