Chernoff egyenlőtlenség
A valószínűségszámítás , Chernoff egyenlőtlenség segítségével a farok egy valószínűségi törvény kell határolt fel , hogy van, ez ad egy maximális érték a valószínűsége, hogy egy véletlenszerűen változó meghalad egy meghatározott értéket. Chernoff kötve is beszélünk .
Összehasonlítható Markov egyenlőtlenségével, de exponenciális korlátot ad. Herman Chernoffról kapta a nevét .
Nyilatkozatok
Sok állítás és sok különleges eset van.
Általános eset
Legyen egy valós véletlen változó, amelynek a momentumokat generáló függvénye :
x{\ displaystyle X}
ϕ(t)=E[etx]<+∞,{\ displaystyle \ phi (t) = \ mathbb {E} [e ^ {tX}] <+ \ infty,}![\ phi (t) = {\ mathbb E} [e ^ {{tX}}] <+ \ infty,](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef15eb49257030fe7df225bcf2acc825e85ac80b)
Tehát mindenért ,
nál nél≥0{\ displaystyle \ scriptstyle a \ geq 0}
P(x≥nál nél)≤e-tnál nélE[etx]{\ displaystyle \ mathbb {P} \ bal (X \ geq a \ jobb) \ leq e ^ {- ta} \ mathbb {E} [e ^ {tX}]}![{\ displaystyle \ mathbb {P} \ bal (X \ geq a \ jobb) \ leq e ^ {- ta} \ mathbb {E} [e ^ {tX}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9cfc945982eb5fd292f5a2ff781013aae0da309)
és
P(x≤-nál nél)≤e-tnál nélE[etx]{\ displaystyle \ mathbb {P} \ bal (X \ leq -a \ jobb) \ leq e ^ {- ta} \ mathbb {E} [e ^ {tX}]}![{\ displaystyle \ mathbb {P} \ bal (X \ leq -a \ jobb) \ leq e ^ {- ta} \ mathbb {E} [e ^ {tX}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f59904c19f8c046b47b6a697da7fc226ff2af182)
Szimmetrikus változókkal és nulla várakozással
Hagyja, hogy a véletlen változók egymástól függetlenek legyenek , és minden i-re . Arra kérünk és hívunk σ 2 a szórás az X .
x1,x2,...,xnem{\ displaystyle X_ {1}, X_ {2}, \ dots, X_ {n}}
E[xén]=0{\ displaystyle \ mathbb {E} [X_ {i}] = 0}![{\ mathbb E} [X_ {i}] = 0](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb2d224569b261f80aefcf837e798e35bd5d2346)
|xén|≤1{\ displaystyle \ left | X_ {i} \ right | \ leq 1 \,}
x=∑én=1nemxén{\ displaystyle X = \ sum _ {i = 1} ^ {n} X_ {i}}
Tehát mindenünk megvan :
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}}
valamint ,
P(-x≥kσ)≤e-k2/4{\ displaystyle \ mathbb {P} (-X \ geq k \ sigma) \ leq e ^ {- k ^ {2} / 4}}
és így is .
P(|x|≥kσ)≤2e-k2/4{\ displaystyle \ mathbb {P} (\ bal | X \ jobb | \ geq k \ sigma) \ leq 2e ^ {- k ^ {2} / 4}}
Boole-i szimmetrikus változókkal
Legyen Boole véletlen változók (azaz értékek {0,1}) független, azonos elvárás p , akkor ,
x1,x2,...,xnem{\ displaystyle X_ {1}, X_ {2}, \ dots, X_ {n}}∀ϵ>0{\ displaystyle \ forall \ epsilon> 0}
P(1nem∑én=1nemxén>o+ε)≤e-2ε2nem{\ displaystyle \ mathbb {P} \ balra ({\ frac {1} {n}} \ sum _ {i = 1} ^ {n} X_ {i}> p + \ varepsilon \ right) \ leq e ^ { - 2 \ varepsilon ^ {2} n}}
, és .
P(1nem∑én=1nemxén<o-ε)≤e-2ε2nem{\ displaystyle \ mathbb {P} \ balra ({\ frac {1} {n}} \ sum _ {i = 1} ^ {n} X_ {i} <p- \ varepsilon \ right) \ leq e ^ { -2 \ varepsilon ^ {2} n}}
Bizonyíték
Ezeknek az egyenlőtlenségeknek többféle módja van.
Általános eset
Demonstráció
Az első egyenlőtlenség miatt
∀nál nél≥0, ∀t≥0{\ displaystyle \ minden a \ geq 0, ~ \ forall t \ geq 0}
et(x-nál nél)≥1{x≥nál nél}⇒E[et(x-nál nél)]≥P(x≥nál nél)⇒E[etx]e-tnál nél≥P(x≥nál nél).{\ displaystyle {\ begin {aligned} \ 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). \\\ vége {igazítva}}}![{\ displaystyle {\ begin {aligned} \ 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). \\\ vége {igazítva}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d5afb3348ab91f699d55094609bd29ed0b1d3659)
Honnan,
P(x≥nál nél)≤e-(tnál nél-ln(ϕ(t))),{\ displaystyle {\ begin {aligned} P (X \ geq a) & \ leq e ^ {- (ta- \ ln (\ phi (t)))}}, \ end {igazított}}}
és mint mindenre igaz , ezt is megkapjuk
t≥0{\ displaystyle t \ geq 0}
P(x≥nál nél)≤inft≥0 e-(tnál nél-ln(ϕ(t))=e-supt≥0{tnál nél-ln(ϕ(t))}=e-h(nál nél).{\ displaystyle {\ begin {aligned} 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 {igazítva}}}
A második egyenlőtlenség miatt
∀nál nél≥0, ∀t≤0{\ displaystyle \ minden a \ geq 0, ~ \ forall t \ leq 0}
et(x+nál nél)≥1{x≤-nál nél}⇒P(x≤-nál nél)≤E[et(x+nál nél)]≤etnál néleln(ϕ(t))≤e-(-tnál nél-ln(ϕ(t))),{\ displaystyle {\ begin {aligned} \ mathrm {e} ^ {t (X + a)} \ geq {1} _ {\ {X \ leq -a \}} \\\ Rightarrow P (X \ leq - a) & \ leq E \ balra [\ mathrm {e} ^ {t (X + a)} \ jobbra] \\ & \ leq \ mathrm {e} ^ {ta} \ mathrm {e} ^ {\ ln ( \ phi (t))} \\ & \ leq \ mathrm {e} ^ {- (- ta- \ ln (\ phi (t)))}}, \ end {igazítva}}}![{\ displaystyle {\ begin {aligned} \ mathrm {e} ^ {t (X + a)} \ geq {1} _ {\ {X \ leq -a \}} \\\ Rightarrow P (X \ leq - a) & \ leq E \ balra [\ mathrm {e} ^ {t (X + a)} \ jobbra] \\ & \ leq \ mathrm {e} ^ {ta} \ mathrm {e} ^ {\ ln ( \ phi (t))} \\ & \ leq \ mathrm {e} ^ {- (- ta- \ ln (\ phi (t)))}}, \ end {igazítva}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8d7a505c8e0cba499f24d9e26932e39e696646f)
úgy, mint korábban:
P(x≤-nál nél)≤e-h(-nál nél).{\ displaystyle P (X \ leq -a) \ leq \ mathrm {e} ^ {- h (-a)}.}
Boole-i szimmetrikus változókkal
Demonstráció
Az első egyenlőtlenségre beállítottuk , ahol X egy Bernoulli-törvényt követ p paraméterrel. A Chernoff által alkalmazott egyenlőtlenség ,
Z=x-o{\ displaystyle Z = Xp}
Z¯nem=1nem∑én=1nemZén{\ displaystyle {\ overline {Z}} _ {n} = {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} Z_ {i}}
Z¯nem{\ displaystyle {\ overline {Z}} _ {n}}
P(1nem∑én=1nemxén≥o+ϵ)=P(Z¯nem≥ϵ)≤e-hZ¯nem(ϵ).{\ displaystyle {\ begin {aligned} 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)}. \ Vége {igazítva}}}
Arany . Valójában, akárcsak az iid és ezért az iid,
hZ¯nem(ϵ)=supt≥0{ϵt-ln(E[etZ¯nem])}=nemhZ(ϵ){\ displaystyle h _ {{\ overline {Z}} _ {n}} (\ epsilon) = \ sup _ {t \ geq 0} \ {\ epsilon t- \ ln (E [\ mathrm {e} ^ { t {\ overline {Z}} _ {n}}]) \} = nh_ {Z} (\ epsilon)}![{\ displaystyle h _ {{\ overline {Z}} _ {n}} (\ epsilon) = \ sup _ {t \ geq 0} \ {\ epsilon t- \ ln (E [\ mathrm {e} ^ { t {\ overline {Z}} _ {n}}]) \} = nh_ {Z} (\ epsilon)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a9c26fcd8cf07de5080991c021afe6dc28e05c50)
{xén}én∈[1,nem]{\ displaystyle \ {X_ {i} \} _ {i \ itt: [\! 1, n \!]}}![{\ displaystyle \ {X_ {i} \} _ {i \ itt: [\! 1, n \!]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e80444a9b19b1566f5374fbdc08e679dd72a75e1)
{Zén}én∈[1,nem]{\ displaystyle \ {Z_ {i} \} _ {i \ itt: [\! 1, n \!]}}![{\ displaystyle \ {Z_ {i} \} _ {i \ itt: [\! 1, n \!]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3960c6c696e7785a45e5a5fba08440c6fc00719b)
E[etZ¯nem]=∏én=1nemE[etnemZén]=E[etnemZ]nem.{\ displaystyle {\ begin {aligned} 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 {igazítva}}}![{\ displaystyle {\ begin {aligned} 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 {igazítva}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/27e32f8d6867080a086f3da03b7a377b40828056)
Honnan,
hZ¯nem(ϵ)=supt≥0{ϵt-ln(E[etZ¯nem])}=supt≥0{ϵt-nemln(E[etnemZ])}=nemsupt≥0{ϵtnem-ln(E[etnemZ])}=nemhZ(ϵ).{\ displaystyle {\ begin {aligned} 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). \ Vége {igazítva}}}![{\ displaystyle {\ begin {aligned} 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). \ Vége {igazítva}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0836287a88d695915fa92f0a1220798ea5039298)
Ebből kifolyólag,
P(1nem∑én=1nemxén≥o+ϵ)≤e-nemsupt≥0{ϵt-ln(E[etZ])}≤eneminft≥0{ln(E[etZ])-ϵt}≤enem(ln(E[etZ])-ϵt)(mert t≥0).{\ displaystyle {\ begin {aligned} 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 {igazítva}}}![{\ displaystyle {\ begin {aligned} 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 {igazítva}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb617683833d36f2b62da74fb1aad47fa6e7aa12)
Ezt észrevesszük .
Ebből kifolyólagE[etZ]=e-otE[etx]=e-ot(1-o+et){\ displaystyle E [\ mathrm {e} ^ {tZ}] = \ mathrm {e} ^ {- pt} E [\ mathrm {e} ^ {tX}] = \ mathrm {e} ^ {- pt} ( 1-p + \ mathrm {e} ^ {t})}![{\ displaystyle E [\ mathrm {e} ^ {tZ}] = \ mathrm {e} ^ {- pt} E [\ mathrm {e} ^ {tX}] = \ mathrm {e} ^ {- pt} ( 1-p + \ mathrm {e} ^ {t})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c49ce781bd0ce0ac36c63ae50f0616f1332abe4)
∀t≥0,{\ displaystyle \ összes t \ geq 0,}
ln(E[etZ])-ϵt=ln(1-o+et)-(ϵ+o)t=Ψ(t)-ϵt,{\ displaystyle {\ begin {aligned} \ ln (E [\ mathrm {e} ^ {tZ}]) - \ epsilon t & = \ ln (1-p + \ mathrm {e} ^ {t}) - ( \ epsilon + p) t \\ & = \ Psi (t) - \ epsilon t, \ end {igazított}}}![{\ displaystyle {\ begin {aligned} \ ln (E [\ mathrm {e} ^ {tZ}]) - \ epsilon t & = \ ln (1-p + \ mathrm {e} ^ {t}) - ( \ epsilon + p) t \\ & = \ Psi (t) - \ epsilon t, \ end {igazított}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f55c3d0138036bf9f12ccf8397c299bf6550a4f)
a . Taylor Lagrange képletének a 2.
sorrendben való használatához kiszámítjuk az első és a második deriváltat ,
∀t∈R, Ψ(t)=-ot+ln(1-o+et){\ displaystyle \ forall t \ in \ mathbb {R}, ~ \ Psi (t) = - pt + \ ln (1-p + \ mathrm {e} ^ {t})}
Ψ{\ displaystyle \ Psi}
∀t∈R, Ψ′(t)=-o+oet1-o+oetΨ″(t)=(1-o)oet(1-o+oet)2=αβ(α+β)2≤14,{\ displaystyle {\ begin {aligned} \ 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 {igazítva}}}
a . Mi növelheti a .
Valóban .
α=1-o, β=oet{\ displaystyle \ alpha = 1-p, ~ \ beta = p \ mathrm {e} ^ {t}}
Ψ″(t){\ displaystyle \ Psi ^ {''} (t)}
14{\ displaystyle {\ frac {1} {4}}}
(α+β)2=α2+β2+2αβ és (α-β)2=α2+β2-2αβ≥0⇒2αβ≤α2+β2⇒(α+β)2≥4αβ{\ displaystyle (\ alpha + \ beta) ^ {2} = \ alpha ^ {2} + \ beta ^ {2} +2 \ alpha \ beta {\ text {és}} (\ 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}
Tehát, mint szerint 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 {aligned} \ Psi (t) & = \ Psi (0) + t \ Psi ^ {'} (0) + {\ frac {t ^ {2}} {2}} \ Psi ^ {''} (\ theta t) \\ & \ leq {\ frac {t ^ {2}} {8}}, \ end {igazítva}}}
a .
Tehát ,
θ∈[0,1]{\ displaystyle \ theta \ itt: [0,1]}![{\ displaystyle \ theta \ itt: [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fead1e7dceab4be5ab2e91f5108144722daa8c36)
∀t≥0{\ displaystyle \ forall t \ geq 0}
P(1nem∑én=1nemxén≥o+ϵ)≤enem(ln(E[etZ])-ϵt)≤enem(t28.-ϵt).{\ displaystyle {\ begin {aligned} 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)}. \ Vége {igazítva}}}![{\ displaystyle {\ begin {aligned} 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)}. \ Vége {igazítva}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c9bf3c5438cae35a6e9937887e8ac5c93f3147b3)
Bármelyiket . Észrevesszük .
Tehát g beismer egy minimumot .
Így ,
∀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(1nem∑én=1nemxén≥o+ϵ)≤enem(16.ϵ28.-4ϵ2)≤e-2nemϵ2.{\ displaystyle {\ begin {aligned} 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 {igazítva}}}
A második egyenlőtlenség esetén ,
∀ϵ>0{\ displaystyle \ forall \ epsilon> 0}
P(1nem∑én=1nemxén≤o-ϵ)=P(Z¯nem≤-ϵ)=P(-Z¯nem≥ϵ)≤e-h-Z¯nem(t) Chernoff egyenlőtlenségéből≤e-nemh-Z(t)≤eneminft≥0{ln(E[e-tZ])-ϵt}≤enem(ln(E[e-tZ])-ϵt)(mert t≥0).{\ displaystyle {\ begin {aligned} 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 {a Chernoff-egyenlőtlenség szerint}} \\ & \ 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 {igazítva}}}![{\ displaystyle {\ begin {aligned} 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 {a Chernoff-egyenlőtlenség szerint}} \\ & \ 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 {igazítva}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/26aa4854dae1730ef9b67076f177d2b35e4f73bd)
Jegyezzük meg, hogy: ,
∀t≥0{\ displaystyle \ forall t \ geq 0}
E[e-tZ]=eotE[e-tx]=eot(1-o+oe-t)⇒ln(E[e-tZ])=ot+ln(1-o+oe-t)=Ψ(-t)≤t28..{\ displaystyle {\ begin {aligned} 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 {igazítva}}}![{\ displaystyle {\ begin {aligned} 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 {igazítva}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cf07fee8b313cb37ea8758ab60f6c7500fa98cf2)
Tehát ,
∀ϵ>0, ∀t≥0{\ displaystyle \ forall \ epsilon> 0, ~ \ forall t \ geq 0}
P(1nem∑én=1nemxén≤o-ϵ)≤enem(t28.-ϵt)≤e-2nemϵ2,{\ displaystyle {\ begin {aligned} 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 {igazítva}}}
hasonló érvvel, amely az első egyenlőtlenség bemutatására szolgált.
Alkalmazások
Ezeket az egyenlőtlenségeket széles körben alkalmazzák az elméleti informatikában , különösen a komplexitáselméletben és az algoritmusokban , ahol valószínűségi algoritmusok eredményeinek bizonyítását teszik lehetővé .
Lásd még a nagy eltérések elméletét .
Hosszabbítások
Érdekes általánosításokat írhatunk véletlenszerű mátrixokról , amelyeket angol mátrixnak nevezünk Chernoff kötött (en) .
Hivatkozások
-
Brémaud 2009 , p. 184
-
Wolfgang Mulzer, " Öt igazolásokat Chernoff kötve a Applications ", Bulletin of the EATCS , N o 124,
2018. február( online olvasás ).
-
Joel A Tropp, „ Felhasználóbarát farokhatárok a véletlenszerű mátrixok összegei számára ” , A számítási matematika alapjai , vol. 12, n o 4,
2012, P. 389-434
Lásd is
Bibliográfia
-
Pierre Brémaud , Bevezetés a valószínűségbe: és Markov láncok , Springer Science & Business Media,2009, 311 p. ( ISBN 978-3-540-31421-9 , online olvasás )
