Disuguaglianza di Chernoff
Nella teoria della probabilità , la disuguaglianza di Chernoff consente di delimitare la coda di una legge di probabilità , ovvero fornisce un valore massimo per la probabilità che una variabile casuale superi un valore fisso. Parliamo anche di Chernoff legato .
È paragonabile alla disuguaglianza di Markov ma fornisce un limite esponenziale. Prende il nome da Herman Chernoff .
Dichiarazioni
Ci sono molte affermazioni e molti casi speciali.
Caso generale
Sia una variabile casuale reale la cui funzione generatrice di momenti è tale che:
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)
Quindi, per tutto ,
a≥0{\ displaystyle \ scriptstyle a \ geq 0}
P(X≥a)≤e-taE[etX]{\ Displaystyle \ mathbb {P} \ sinistra (X \ geq a \ right) \ leq e ^ {- ta} \ mathbb {E} [e ^ {tX}]}![{\ Displaystyle \ mathbb {P} \ sinistra (X \ geq a \ right) \ leq e ^ {- ta} \ mathbb {E} [e ^ {tX}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9cfc945982eb5fd292f5a2ff781013aae0da309)
e
P(X≤-a)≤e-taE[etX]{\ Displaystyle \ mathbb {P} \ sinistra (X \ leq -a \ right) \ leq e ^ {- ta} \ mathbb {E} [e ^ {tX}]}![{\ Displaystyle \ mathbb {P} \ sinistra (X \ leq -a \ right) \ leq e ^ {- ta} \ mathbb {E} [e ^ {tX}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f59904c19f8c046b47b6a697da7fc226ff2af182)
Con variabili simmetriche e aspettativa zero
Lascia che le variabili casuali siano indipendenti in modo tale che e per ogni i . Chiediamo e ci chiamiamo σ 2 la varianza di X .
X1,X2,...,Xnon{\ displaystyle X_ {1}, X_ {2}, \ dots, X_ {n}}
E[Xio]=0{\ displaystyle \ mathbb {E} [X_ {i}] = 0}![{\ mathbb E} [X_ {i}] = 0](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb2d224569b261f80aefcf837e798e35bd5d2346)
|Xio|≤1{\ displaystyle \ sinistra | X_ {i} \ destra | \ leq 1 \,}
X=∑io=1nonXio{\ displaystyle X = \ sum _ {i = 1} ^ {n} X_ {i}}
Quindi, abbiamo per tutto :
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}}
così come ,
P(-X≥Kσ)≤e-K2/4{\ displaystyle \ mathbb {P} (-X \ geq k \ sigma) \ leq e ^ {- k ^ {2} / 4}}
e così anche .
P(|X|≥Kσ)≤2e-K2/4{\ displaystyle \ mathbb {P} (\ sinistra | X \ destra | \ geq k \ sigma) \ leq 2e ^ {- k ^ {2} / 4}}
Con variabili simmetriche booleane
Siano le variabili casuali booleane (cioè con valori in {0,1}) indipendenti, con la stessa aspettativa p , quindi ,
X1,X2,...,Xnon{\ displaystyle X_ {1}, X_ {2}, \ dots, X_ {n}}∀ϵ>0{\ displaystyle \ forall \ epsilon> 0}
P(1non∑io=1nonXio>p+ε)≤e-2ε2non{\ displaystyle \ mathbb {P} \ left ({\ frac {1} {n}} \ sum _ {i = 1} ^ {n} X_ {i}> p + \ varepsilon \ right) \ leq e ^ { - 2 \ varepsilon ^ {2} n}}
, e .
P(1non∑io=1nonXio<p-ε)≤e-2ε2non{\ displaystyle \ mathbb {P} \ left ({\ frac {1} {n}} \ sum _ {i = 1} ^ {n} X_ {i} <p- \ varepsilon \ right) \ leq e ^ { -2 \ varepsilon ^ {2} n}}
Prova
Esistono diversi modi per dimostrare queste disuguaglianze.
Caso generale
Dimostrazione
Per la prima disuguaglianza ,
∀a≥0, ∀t≥0{\ displaystyle \ forall a \ geq 0, ~ \ forall t \ geq 0}
et(X-a)≥1{X≥a}⇒E[et(X-a)]≥P(X≥a)⇒E[etX]e-ta≥P(X≥a).{\ 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}}}![{\ 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d5afb3348ab91f699d55094609bd29ed0b1d3659)
Da dove,
P(X≥a)≤e-(ta-ln(ϕ(t))),{\ displaystyle {\ begin {allineato} P (X \ geq a) & \ leq e ^ {- (ta- \ ln (\ phi (t)))}, \ end {allineato}}}
e, come è vero per tutto , lo otteniamo
t≥0{\ displaystyle t \ geq 0}
P(X≥a)≤inft≥0 e-(ta-ln(ϕ(t))=e-supt≥0{ta-ln(ϕ(t))}=e-h(a).{\ 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 {allineato}}}
Per la seconda disuguaglianza ,
∀a≥0, ∀t≤0{\ displaystyle \ forall a \ geq 0, ~ \ forall t \ leq 0}
et(X+a)≥1{X≤-a}⇒P(X≤-a)≤E[et(X+a)]≤etaeln(ϕ(t))≤e-(-ta-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 {allineato}}}![{\ 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 {allineato}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8d7a505c8e0cba499f24d9e26932e39e696646f)
così come prima:
P(X≤-a)≤e-h(-a).{\ displaystyle P (X \ leq -a) \ leq \ mathrm {e} ^ {- h (-a)}.}
Con variabili simmetriche booleane
Dimostrazione
Per la prima disuguaglianza , poniamo e dove X segue una legge di Bernoulli con parametro p. Dalla disuguaglianza di Chernoff applicata a ,
Z=X-p{\ displaystyle Z = Xp}
Z¯non=1non∑io=1nonZio{\ displaystyle {\ overline {Z}} _ {n} = {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} Z_ {i}}
Z¯non{\ displaystyle {\ overline {Z}} _ {n}}
P(1non∑io=1nonXio≥p+ϵ)=P(Z¯non≥ϵ)≤e-hZ¯non(ϵ).{\ 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 {align}}}
Oro . Infatti, come sono iid e quindi sono iid,
hZ¯non(ϵ)=supt≥0{ϵt-ln(E[etZ¯non])}=nonhZ(ϵ){\ 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)
{Xio}io∈[1,non]{\ displaystyle \ {X_ {i} \} _ {i \ in [\! 1, n \!]}}![{\ displaystyle \ {X_ {i} \} _ {i \ in [\! 1, n \!]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e80444a9b19b1566f5374fbdc08e679dd72a75e1)
{Zio}io∈[1,non]{\ displaystyle \ {Z_ {i} \} _ {i \ in [\! 1, n \!]}}![{\ displaystyle \ {Z_ {i} \} _ {i \ in [\! 1, n \!]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3960c6c696e7785a45e5a5fba08440c6fc00719b)
E[etZ¯non]=∏io=1nonE[etnonZio]=E[etnonZ]non.{\ 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 {allineato}}}![{\ 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 {allineato}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/27e32f8d6867080a086f3da03b7a377b40828056)
Da dove,
hZ¯non(ϵ)=supt≥0{ϵt-ln(E[etZ¯non])}=supt≥0{ϵt-nonln(E[etnonZ])}=nonsupt≥0{ϵtnon-ln(E[etnonZ])}=nonhZ(ϵ).{\ 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}}}![{\ 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0836287a88d695915fa92f0a1220798ea5039298)
Pertanto,
P(1non∑io=1nonXio≥p+ϵ)≤e-nonsupt≥0{ϵt-ln(E[etZ])}≤enoninft≥0{ln(E[etZ])-ϵt}≤enon(ln(E[etZ])-ϵt)(per 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 {allineato}}}![{\ 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 {allineato}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb617683833d36f2b62da74fb1aad47fa6e7aa12)
Lo notiamo .
pertantoE[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})}![{\ 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 \ 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 {allineato}}}![{\ Displaystyle {\ begin {align} \ ln (E [\ mathrm {e} ^ {tZ}]) - \ epsilon t & = \ ln (1-p + \ mathrm {e} ^ {t}) - ( \ epsilon + p) t \\ & = \ Psi (t) - \ epsilon t, \ end {allineato}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f55c3d0138036bf9f12ccf8397c299bf6550a4f)
con .
Per utilizzare la formula di Taylor Lagrange all'ordine 2, calcoliamo la prima e la seconda derivata ,
∀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}}}
con . Possiamo aumentare di .
Infatti ,.
α=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αβ e (α-β)2=α2+β2-2αβ≥0⇒2αβ≤α2+β2⇒(α+β)2≥4αβ{\ displaystyle (\ alpha + \ beta) ^ {2} = \ alpha ^ {2} + \ beta ^ {2} +2 \ alpha \ beta {\ text {and}} (\ 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}
Così, come , secondo 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}}}
con .
Quindi ,
θ∈[0,1]{\ displaystyle \ theta \ in [0,1]}![{\ displaystyle \ theta \ in [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fead1e7dceab4be5ab2e91f5108144722daa8c36)
∀t≥0{\ displaystyle \ forall t \ geq 0}
P(1non∑io=1nonXio≥p+ϵ)≤enon(ln(E[etZ])-ϵt)≤enon(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 {allineato}}}![{\ 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 {allineato}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c9bf3c5438cae35a6e9937887e8ac5c93f3147b3)
In entrambi i casi . Notiamo .
Quindi g ammette un minimo in .
Quindi ,
∀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(1non∑io=1nonXio≥p+ϵ)≤enon(16ϵ28-4ϵ2)≤e-2nonϵ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 {allineato}}}
Per la seconda disuguaglianza , ,
∀ϵ>0{\ displaystyle \ forall \ epsilon> 0}
P(1non∑io=1nonXio≤p-ϵ)=P(Z¯non≤-ϵ)=P(-Z¯non≥ϵ)≤e-h-Z¯non(t) dalla disuguaglianza di Chernoff≤e-nonh-Z(t)≤enoninft≥0{ln(E[e-tZ])-ϵt}≤enon(ln(E[e-tZ])-ϵt)(per 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 {secondo la disuguaglianza di 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}}}![{\ 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 {secondo la disuguaglianza di 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/26aa4854dae1730ef9b67076f177d2b35e4f73bd)
Si noti che: ,
∀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 {allineato}}}![{\ 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 {allineato}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cf07fee8b313cb37ea8758ab60f6c7500fa98cf2)
Quindi ,
∀ϵ>0, ∀t≥0{\ displaystyle \ forall \ epsilon> 0, ~ \ forall t \ geq 0}
P(1non∑io=1nonXio≤p-ϵ)≤enon(t28-ϵt)≤e-2nonϵ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 {align}}}
da un argomento simile che serviva a dimostrare la prima disuguaglianza.
Applicazioni
Queste disuguaglianze sono ampiamente utilizzate nell'informatica teorica , in particolare nella teoria della complessità e negli algoritmi , dove consentono di dimostrare i risultati su algoritmi probabilistici .
Vedi anche teoria delle grandi deviazioni .
Estensioni
Possiamo scrivere interessanti generalizzazioni per matrici casuali , chiamate in inglese matrice Chernoff bound (en) .
Riferimenti
-
Brémaud 2009 , p. 184
-
Wolfgang Mulzer, " Five Proofs of Chernoff's Bound with Applications ", Bulletin of the EATCS , n . 124,
febbraio 2018( leggi online ).
-
Joel A Tropp, " Limiti di coda user-friendly per somme di matrici casuali " , Foundations of Computational Mathematics , vol. 12, n o 4,
2012, p. 389-434
Vedi anche
Bibliografia
-
Pierre Brémaud , Introduzione alla probabilità: e catene di Markov , Springer Science & Business Media,2009, 311 p. ( ISBN 978-3-540-31421-9 , leggi in linea )
