Azuma nerovnost
Nerovnost Azuma , někdy nazývané nerovné Azuma-Hoeffding je koncentrace nerovnost pro martingalu jehož zvyšuje jsou ohraničeny. Jde o zobecnění Hoeffdingovy nerovnosti , nerovnosti koncentrace, která se týká pouze součtu nezávislých a ohraničených náhodných proměnných.
Společné prohlášení
Jedním z nejběžnějších tvrzení je
Azuma nerovnost - buď martingale s ohledem na filtraci a ověřování
M=(Mt)0≤t≤m {\ displaystyle M = (M_ {t}) _ {0 \ leq t \ leq m} \} F=(F0={Ω,∅}⊂F1⊂F2⊂⋯⊂Fm) {\ displaystyle {\ mathcal {F}} = ({\ mathcal {F}} _ {0} = \ {\ Omega, \ varnothing \} \ podmnožina {\ mathcal {F}} _ {1} \ podmnožina {\ mathcal {F}} _ {2} \ subset \ dots \ subset {\ mathcal {F}} _ {m}) \}
∀t∈[[1,m]],P(|Mt-Mt-1|≤1)=1.{\ displaystyle \ forall t \ in [\! [1, m] \!], \ qquad \ mathbb {P} (| M_ {t} -M_ {t-1} | \ leq 1) = 1.}
Takže za všechno λ>0, {\ displaystyle \ lambda> 0, \}
P(Mm-E[Mm]≥λ)≤exp(-λ22m),P(Mm-E[Mm]≤-λ)≤exp(-λ22m),P(|Mm-E[Mm]|≥λ)≤2exp(-λ22m).{\ displaystyle {\ begin {aligned} \ mathbb {P} \ left (M_ {m} - \ mathbb {E} [M_ {m}] \ geq \ lambda \ right) & \ leq \ exp \ left (- { \ frac {\ lambda ^ {2}} {2m}} \ vpravo), \\\ mathbb {P} \ vlevo (M_ {m} - \ mathbb {E} [M_ {m}] \ leq - \ lambda \ vpravo) & \ leq \ exp \ left (- {\ frac {\ lambda ^ {2}} {2m}} \ right), \\\ mathbb {P} \ left (\ left | M_ {m} - \ mathbb {E} [M_ {m}] \ right | \ geq \ lambda \ right) & \ leq 2 \ exp \ left (- {\ frac {\ lambda ^ {2}} {2m}} \ right). \ End {zarovnaný}}}
Všimněte si, že to volba znamenáF0={Ω,∅} {\ displaystyle {\ mathcal {F}} _ {0} = \ {\ Omega, \ varnothing \} \}M0=E[Mm]. {\ displaystyle M_ {0} = \ mathbb {E} [M_ {m}]. \}
Obecné prohlášení
Obecnější tvrzení (McDiarmid, Theorem 6.7) je následující
Věta - Nechť je martingálem s ohledem na filtraci Předpokládejme, že existuje posloupnost náhodných proměnných a posloupnost konstant taková, že pro všechnyM=(Mt)0≤t≤m {\ displaystyle M = (M_ {t}) _ {0 \ leq t \ leq m} \} F=(F0={Ω,∅}⊂F1⊂F2⊂⋯⊂Fm). {\ displaystyle {\ mathcal {F}} = ({\ mathcal {F}} _ {0} = \ {\ Omega, \ varnothing \} \ podmnožina {\ mathcal {F}} _ {1} \ podmnožina {\ mathcal {F}} _ {2} \ subset \ dots \ subset {\ mathcal {F}} _ {m}). \}(Zk)1≤k≤m {\ displaystyle (Z_ {k}) _ {1 \ leq k \ leq m} \}(ℓk)1≤k≤m {\ displaystyle (\ ell _ {k}) _ {1 \ leq k \ leq m} \}k∈[[1,m]], {\ displaystyle k \ in [\! [1, m] \!], \}
-
Zk {\ displaystyle Z_ {k} \}být měřitelný;Fk-1 {\ displaystyle {\ mathcal {F}} _ {k-1} \}
- P(Zk≤Mk≤Zk+ℓk)=1.{\ displaystyle \ mathbb {P} (Z_ {k} \ leq M_ {k} \ leq Z_ {k} + \ ell _ {k}) = 1.}
Takže za všechno λ>0, {\ displaystyle \ lambda> 0, \}
P(Mm-E[Mm]≥λ)≤exp(-2λ2∑i=1mℓi2),P(Mm-E[Mm]≤-λ)≤exp(-2λ2∑i=1mℓi2),P(|Mm-E[Mm]|≥λ)≤2exp(-2λ2∑i=1mℓi2).{\ displaystyle {\ begin {aligned} \ mathbb {P} \ left (M_ {m} - \ mathbb {E} [M_ {m}] \ geq \ lambda \ right) & \ leq \ exp \ left (- { \ frac {2 \ lambda ^ {2}} {\ sum _ {i = 1} ^ {m} \ ell _ {i} ^ {2}}} \ vpravo), \\\ mathbb {P} \ vlevo ( M_ {m} - \ mathbb {E} [M_ {m}] \ leq - \ lambda \ right) & \ leq \ exp \ left (- {\ frac {2 \ lambda ^ {2}} {\ sum _ { i = 1} ^ {m} \ ell _ {i} ^ {2}}} \ right), \\\ mathbb {P} \ left (\ left | M_ {m} - \ mathbb {E} [M_ { m}] \ right | \ geq \ lambda \ right) & \ leq 2 \ exp \ left (- {\ frac {2 \ lambda ^ {2}} {\ sum _ {i = 1} ^ {m} \ ell _ {i} ^ {2}}} \ vpravo). \ end {zarovnáno}}}
Aktuální příkaz uvedený v předchozí části je získán specializací obecného příkazu s možnostmi ℓk=2, Zk=-1+Mk-1. {\ displaystyle \ ell _ {k} = 2, \ Z_ {k} = - 1 + M_ {k-1}. \}
Demonstrace
Důkaz je obdobný jako u Hoeffdingovy nerovnosti : stanovili jsme
Yi=Mi-Mi-1,vs.i=Zi-Mi-1,di=Zi-Mi-1+ℓi,{\ displaystyle {\ begin {zarovnáno} Y_ {i} & = M_ {i} -M_ {i-1}, \\ c_ {i} & = Z_ {i} -M_ {i-1}, \ quad d_ {i} = Z_ {i} -M_ {i-1} + \ ell _ {i}, \ end {zarovnáno}}}
a všimli jsme si toho
P(vs.i≤Yi≤di)=1,di-vs.i=ℓi,Mm-E[Mm]=Y1+Y2+⋯+Ym.{\ displaystyle {\ begin {aligned} \ mathbb {P} \ left (c_ {i} \ leq Y_ {i} \ leq d_ {i} \ right) & = 1, \\ d_ {i} -c_ {i } & = \ ell _ {i}, \\ M_ {m} - \ mathbb {E} [M_ {m}] & = Y_ {1} + Y_ {2} + \ dots + Y_ {m}. \ end {zarovnaný}}}
Za všechno, co tedy máme, díky Markovově nerovnosti :
s>0, {\ displaystyle s> 0, \}
P(Mm-E[Mm]≥λ)≤E[Es(Mm-E[Mm])]E-sλ=E[Es(Y1+Y2+⋯+Ym)]E-sλ{\ displaystyle {\ begin {zarovnáno} \ mathbb {P} \ vlevo (M_ {m} - \ mathbb {E} [M_ {m}] \ geq \ lambda \ vpravo) & \ leq \ mathbb {E} \ vlevo [e ^ {s (M_ {m} - \ mathbb {E} [M_ {m}])} \ vpravo] e ^ {- s \ lambda} \\ & = \ mathbb {E} \ vlevo [e ^ { s (Y_ {1} + Y_ {2} + \ dots + Y_ {m})} \ right] e ^ {- s \ lambda} \ end {zarovnáno}}}
Pak si toho všimneme
E[EsYm|Fm-1]≤exp(s2ℓm2/8),{\ displaystyle {\ begin {aligned} \ mathbb {E} \ left [e ^ {sY_ {m}} \ left | {\ mathcal {F}} _ {m-1} \ right. \ right] & \ leq \ exp \ left (s ^ {2} \ ell _ {m} ^ {2} / 8 \ right), \ end {zarovnáno}}}
na základě následující nerovnosti (což je první krok k prokázání Hoeffdingovy nerovnosti ):
Proposition -
Dovolit být omezená a soustředil skutečnou náhodnou proměnnou (s ověřením ). Nechť dvě reálná čísla jsou taková a taková, že Pak pro všechna reálná čísla Y {\ displaystyle Y \}E[Y]=0 {\ displaystyle \ mathbb {E} [Y] = 0 \}vs.,d {\ displaystyle c, \, d \}vs.<d {\ displaystyle c <d \}P(vs.≤Y≤d)=1. {\ displaystyle \ mathbb {P} (c \ leq Y \ leq d) = 1. \}s>0, {\ displaystyle s> 0, \}
E[EsY]≤exp(s2(d-vs.)2/8).{\ displaystyle \ mathbb {E} \ left [e ^ {sY} \ right] \ leq \ exp \ left (s ^ {2} (dc) ^ {2} / 8 \ right).}
Vskutku
E[Ym|Fm-1]=0,P(vs.m≤Ym≤vs.m+ℓm|Fm-1)=1,{\ displaystyle {\ begin {aligned} \ mathbb {E} \ left [Y_ {m} \ left | {\ mathcal {F}} _ {m-1} \ right. \ right] & = 0, \\\ mathbb {P} \ left (c_ {m} \ leq Y_ {m} \ leq c_ {m} + \ ell _ {m} \ left | {\ mathcal {F}} _ {m-1} \ right. \ vpravo) & = 1, \ end {zarovnáno}}}
a náhodná proměnná je -measurable, funguje jako konstanta, alespoň v podmíněné očekávání , pokud jde o kmen
tedy
vs.m, {\ displaystyle c_ {m}, \}Fm-1 {\ displaystyle {\ mathcal {F}} _ {m-1} \} Fm-1. {\ displaystyle {\ mathcal {F}} _ {m-1}. \}
E[Es(Y1+Y2+⋯+Ym)]=E[E[Es(Y1+Y2+⋯+Ym)|Fm-1]]=E[Es(Y1+Y2+⋯+Ym-1) E[EsYm|Fm-1]]≤E[Es(Y1+Y2+⋯+Ym-1)] Es2ℓm2/8≤exp((∑i=1mℓi2)s2/8),{\ displaystyle {\ begin {aligned} \ mathbb {E} \ left [e ^ {s (Y_ {1} + Y_ {2} + \ dots + Y_ {m})} \ right] & = \ mathbb {E } \ left [\ mathbb {E} \ left [e ^ {s (Y_ {1} + Y_ {2} + \ dots + Y_ {m})} \ left | {\ mathcal {F}} _ {m- 1} \ right. \ Right] \ right] \\ & = \ mathbb {E} \ left [e ^ {s (Y_ {1} + Y_ {2} + \ dots + Y_ {m-1})}} \ \ mathbb {E} \ left [e ^ {sY_ {m}} \ left | {\ mathcal {F}} _ {m-1} \ right. \ right] \ right] \\ & \ leq \ mathbb {E } \ left [e ^ {s (Y_ {1} + Y_ {2} + \ dots + Y_ {m-1})} \ right] \ e ^ {s ^ {2} \ ell _ {m} ^ { 2} / 8} \\ & \ leq \ exp \ left ((\ sum _ {i = 1} ^ {m} \ ell _ {i} ^ {2}) s ^ {2} / 8 \ right), \ end {zarovnáno}}}
poslední nerovnost získaná indukcí. Získáváme tedy stejnou mezilehlou nerovnost jako v důkazu Hoeffdingovy nerovnosti , a proto dokazujeme stejným způsobem jako v případě Hoeffdingovy nerovnosti .
Maureyho princip
Maureyho princip poprvé uvedl Maurey v poznámce ke sborníku Akademie věd v roce 1979 a později objevil, zdá se, nezávisle na tom , v teorii perkolace , Harry Kesten . Často se používá v teorii náhodných grafů, v analýze randomizovaných algoritmů a v teorii perkolace . Někdy se jí říká metoda omezených rozdílů nebo MOBD .
Státy
Vzhledem k tomu, dvě sady A a B , a to buď všechny aplikace B do A . Dáme si filtraciΩ=NAB {\ displaystyle \ Omega = A ^ {B} \} B = (B0=∅⊂B1⊂B2⊂⋯⊂Bm=B). {\ displaystyle {\ mathcal {B}} \ = \ (B_ {0} = \ varnothing \, \ podmnožina \, B_ {1} \, \ podmnožina \, B_ {2} \, \ podmnožina \ tečky \ podmnožina \ , B_ {m} = B). \}
Definice - O aplikaci se říká, že je -lipshitzianská, pokud na všechno a na všechno máme implikaci:
X:Ω→R {\ displaystyle X \ ,: \, \ Omega \ rightarrow \ mathbb {R} \}B{\ displaystyle {\ mathcal {B}}}t∈[[1,m]] {\ displaystyle t \ v [\! [1, m] \!] \}(ω,ω~)∈Ω, {\ displaystyle (\ omega, {\ tilde {\ omega}}) \ v \, \ Omega, \}
{ω|(Bt∖Bt-1)vs.≡ω~|(Bt∖Bt-1)vs.}⇒{|X(ω)-X(ω~)|≤1}.{\ displaystyle \ left \ {\ omega _ {| (B_ {t} \ zpětné lomítko B_ {t-1}) ^ {c}} \ equiv {\ tilde {\ omega}} _ {| (B_ {t} \ zpětné lomítko B_ {t-1}) ^ {c}} \ right \} \ quad \ Rightarrow \ quad \ left \ {\ left | X (\ omega) -X ({\ tilde {\ omega}}) \ right | \ leq 1 \ right \}.}
Jinými slovy, pokud se tyto dvě mapy shodují uvnitř a vně (tj. V zelené a modré oblasti níže uvedeného obrázku), pak se X od jedné k druhé liší jen nepatrně.
Bt-1 {\ displaystyle B_ {t-1} \}Bt {\ displaystyle B_ {t} \}
Věta - Předpokládejme, že se strukturou o pravděpodobnosti rozmístí tak, že obrazy jsou rodina náhodné veličiny nezávislé . Předpokládáme také, že skutečná náhodná proměnná X , definovaná na , je -lipshitzian. Takže za všechnoΩ {\ displaystyle \ Omega \}(Ω,NA,P) {\ displaystyle (\ Omega, {\ mathcal {A}}, \ mathbb {P}) \}(ω(b))b∈B {\ displaystyle (\ omega (b)) _ {b \ v B} \} (Ω,NA,P) {\ displaystyle (\ Omega, {\ mathcal {A}}, \ mathbb {P}) \}B{\ displaystyle {\ mathcal {B}}}λ>0, {\ displaystyle \ lambda> 0, \}
P(X-E[X]≥λ)≤exp(-λ22m),P(X-E[X]≤-λ)≤exp(-λ22m),P(|X-E[X]|≥λ)≤2exp(-λ22m).{\ displaystyle {\ begin {aligned} \ mathbb {P} \ left (X- \ mathbb {E} [X] \ geq \ lambda \ right) & \ leq \ exp \ left (- {\ frac {\ lambda ^ {2}} {2m}} \ right), \\\ mathbb {P} \ left (X- \ mathbb {E} [X] \ leq - \ lambda \ right) & \ leq \ exp \ left (- { \ frac {\ lambda ^ {2}} {2m}} \ vpravo), \\\ mathbb {P} \ vlevo (\ vlevo | X- \ mathbb {E} [X] \ vpravo | \ geq \ lambda \ vpravo ) & \ leq 2 \ exp \ left (- {\ frac {\ lambda ^ {2}} {2m}} \ right). \ end {zarovnáno}}}
Demonstrace
Domníváme se, že filtrace filtrace definována, pro aplikace
F=(F0={Ω,∅}⊂F1⊂F2⊂⋯⊂Fm) {\ displaystyle {\ mathcal {F}} = ({\ mathcal {F}} _ {0} = \ {\ Omega, \ varnothing \} \ podmnožina {\ mathcal {F}} _ {1} \ podmnožina {\ mathcal {F}} _ {2} \ subset \ dots \ subset {\ mathcal {F}} _ {m}) \}1≤t≤m, {\ displaystyle 1 \ leq t \ leq m, \}
Ft=σ(ω(b) | b∈Bt).{\ displaystyle {\ mathcal {F}} _ {t} = \ sigma \ left (\ omega (b) \ | \ b \ in B_ {t} \ right).}
Protože pózujeme
0≤t≤m, {\ displaystyle 0 \ leq t \ leq m, \}
Mt=E[X| Ft].{\ displaystyle M_ {t} = \ mathbb {E} \ vlevo [X \ vlevo | \ {\ mathcal {F}} _ {t} \ vpravo. \ vpravo].}
Takový je martingale a Aby bylo možné aplikovat nerovnost Azumy, zbývá pouze prokázat, že „rozdíly jsou omezené“ . K tomu si povšimneme, pro(Mt)0≤t≤m {\ displaystyle \ left (M_ {t} \ right) _ {0 \ leq t \ leq m} \}M0=E[X], {\ displaystyle M_ {0} = \ mathbb {E} \ doleva [X \ doprava], \} Mm=X. {\ displaystyle M_ {m} = X. \}1≤t≤m,{\ displaystyle 1 \ leq t \ leq m,}
-
ω1{\ displaystyle \ omega _ {1}}omezení od doω{\ displaystyle \ omega}VS1=Bt-1, {\ displaystyle C_ {1} = B_ {t-1}, \}
-
ω2{\ displaystyle \ omega _ {2}}omezení od doω{\ displaystyle \ omega}VS2=Bt∖Bt-1, {\ displaystyle C_ {2} = B_ {t} \ zpětné lomítko B_ {t-1}, \}
-
ω3{\ displaystyle \ omega _ {3}}omezení na viz obrázek výše.ω{\ displaystyle \ omega}VS3=Btvs., {\ displaystyle C_ {3} = B_ {t} ^ {c}, \}
Protože tvoří oddíl B , vyplývá z toho na jedné straně, že jde o korespondenci one-to-one s tripletem , na druhé straně o tom, že na základě seskupovacího lemmatu je triplet triplet nezávislých náhodných proměnných. Všimněte si, že zákon pravděpodobnosti, který je mírou pravděpodobnosti na Máme pak
VSi, {\ displaystyle C_ {i}, \} 1≤i≤3, {\ displaystyle 1 \ leq i \ leq 3, \}ω{\ displaystyle \ omega}(ω1,ω2,ω3) {\ displaystyle (\ omega _ {1}, \, \ omega _ {2}, \, \ omega _ {3}) \}(ω1,ω2,ω3) {\ displaystyle (\ omega _ {1}, \, \ omega _ {2}, \, \ omega _ {3}) \}Pi {\ displaystyle \ mathbb {P} _ {i} \}ωi, {\ displaystyle \ omega _ {i}, \}NAVSi. {\ displaystyle A ^ {C_ {i}}. \}
E[X| Ft](ω)=∫NAVS3X(ω1,ω2,w3)P3(dw3),=∫NAVS3(∫NAVS2X(ω1,ω2,w3)P2(dw2))P3(dw3).E[X| Ft-1](ω)=∫NAVS3(∫NAVS2X(ω1,w2,w3)P2(dw2))P3(dw3).{\ displaystyle {\ begin {aligned} \ mathbb {E} \ left [X \ left | \ {\ mathcal {F}} _ {t} \ right. \ right] (\ omega) & = \ int _ {A ^ {C_ {3}}} X (\ omega _ {1}, \, \ omega _ {2}, \, w_ {3}) \ mathbb {P} _ {3} (dw_ {3}), \ \ & = \ int _ {A ^ {C_ {3}}} \ left (\ int _ {A ^ {C_ {2}}} X (\ omega _ {1}, \, \ omega _ {2}, \, w_ {3}) \ mathbb {P} _ {2} (dw_ {2}) \ right) \ mathbb {P} _ {3} (dw_ {3}). \\\ mathbb {E} \ vlevo [X \ left | \ {\ mathcal {F}} _ {t-1} \ right. \ Right] (\ omega) & = \ int _ {A ^ {C_ {3}}} \ left (\ int _ {A ^ {C_ {2}}} X (\ omega _ {1}, \, w_ {2}, \, w_ {3}) \ mathbb {P} _ {2} (dw_ {2}) \ vpravo ) \ mathbb {P} _ {3} (dw_ {3}). \ end {zarovnáno}}}
Tak
|Mt(ω)-Mt-1(ω)|=|∫NAVS3(∫NAVS2(X(ω1,ω2,w3)-X(ω1,w2,w3))P2(dw2))P3(dw3)|≤∫NAVS3(∫NAVS2|X(ω1,ω2,w3)-X(ω1,w2,w3)|P2(dw2))P3(dw3).{\ displaystyle {\ begin {aligned} \ left | M_ {t} (\ omega) -M_ {t-1} (\ omega) \ right | & = \ left | \ int _ {A ^ {C_ {3} }} \ left (\ int _ {A ^ {C_ {2}}} \ left (X (\ omega _ {1}, \ omega _ {2}, \, w_ {3}) - X (\ omega _ {1}, \, w_ {2}, \, w_ {3}) \ right) \ mathbb {P} _ {2} (dw_ {2}) \ right) \ mathbb {P} _ {3} (dw_ {3}) \ right | \\ & \ leq \ int _ {A ^ {C_ {3}}} \ left (\ int _ {A ^ {C_ {2}}} \ left | X (\ omega _ { 1}, \ omega _ {2}, \, w_ {3}) - X (\ omega _ {1}, \, w_ {2}, \, w_ {3}) \ right | \ mathbb {P} _ {2} (dw_ {2}) \ right) \ mathbb {P} _ {3} (dw_ {3}). \ End {aligned}}}
Ale dva triplety a určují dvě mapy B v A, které se liší pouze v jejich omezeních na (jejich omezení jsou a respektive). Tedy X je -lipshitzian,
(ω1,ω2,w3) {\ displaystyle (\ omega _ {1}, \ omega _ {2}, \, w_ {3}) \}(ω1,w2,w3) {\ displaystyle (\ omega _ {1}, \, w_ {2}, \, w_ {3}) \}VS2=Bt∖Bt-1, {\ displaystyle C_ {2} = B_ {t} \ zpětné lomítko B_ {t-1}, \}ω2 {\ displaystyle \ omega _ {2} \}w2, {\ displaystyle w_ {2}, \}B{\ displaystyle {\ mathcal {B}}}
|X(ω1,ω2,w3)-X(ω1,w2,w3)|≤1.{\ displaystyle \ left | X (\ omega _ {1}, \ omega _ {2}, \, w_ {3}) - X (\ omega _ {1}, \, w_ {2}, \, w_ { 3}) \ vpravo | \ leq 1.}
Proto
|Mt(ω)-Mt-1(ω)|≤1.{\ displaystyle \ left | M_ {t} (\ omega) -M_ {t-1} (\ omega) \ vpravo | \ leq 1.}
Aplikace na model uren a koulí
V tomto příkladu je zájmem přesné nerovnosti koncentrace ospravedlnit statistickou metodu přibližného počítání, kterou lze použít například k detekci napadení počítačovým virem.
Nerovnost koncentrace
Hodíme m koule náhodně do n polí, pravděpodobnostní experiment, ve kterém je elementární událost popsána aplikací in : je číslo pole, ve kterém je uloženo číslo koule k . Jde tedy o skutečně nezávislé náhodné proměnné a mimochodem o jednotné náhodné proměnné . Zvážit použití X , které do distribuce o m koulí v n polí, přidruží počet prázdných krabic na konci tohoto distribution.We lze snadno vypočítat očekávání X pomocí rozklad X do součtu Bernoulliho proměnných . Pak to zjistíme
ω {\ displaystyle \ omega \}B=[[1,m]] {\ displaystyle B = [\! [1, m] \!] \}NA=[[1,ne]] {\ displaystyle A = [\! [1, n] \!] \}ω(k) {\ displaystyle \ omega (k) \}ω(k) {\ displaystyle \ omega (k) \}ω {\ displaystyle \ omega \} X(ω) {\ displaystyle X (\ omega) \} ω. {\ displaystyle \ omega. \}
E[X] = ne(1-1ne)m.{\ displaystyle \ mathbb {E} [X] \ = \ n \ vlevo (1 - {\ tfrac {1} {n}} \ vpravo) ^ {m}.}
Pro volbu aplikace X je -lipshitzian: skutečně, když se z jednoho distribuce do druhého, pouze místo kulového n ° t změny ( je redukován na jediný prvek t ), pak počet prázdných krabic se liší nejvýše jednu jednotka. Na základě Maureyho principu tedy
Bt=[[1,t]], {\ displaystyle B_ {t} = [\! [1, t] \!], \}B{\ displaystyle {\ mathcal {B}}}Bt∖Bt-1={t} {\ displaystyle B_ {t} \ zpětné lomítko B_ {t-1} = \ {t \} \}
P(|X-ne(1-1ne)m|≥λ)≤2exp(-λ22m).{\ displaystyle {\ begin {zarovnáno} \ mathbb {P} \ left (\ left | Xn \ left (1 - {\ tfrac {1} {n}} \ right) ^ {m} \ right | \ geq \ lambda \ right) & \ leq 2 \ exp \ left (- {\ frac {\ lambda ^ {2}} {2m}} \ right). \ end {zarovnáno}}}
Přesnější nerovnost se získá použitím obecné formy nerovnosti Azuma.
Přiblížený problém počítání
To zahrnuje odhad počtu m různých uživatelů identifikovaných v síťovém uzlu podle záhlaví datového paketu, který odesílají. Myšlenka spočívá v tom, že virový útok nevede k zjistitelnému zvýšení objemu provozu (většina svazku je poskytována například stahováním souborů, které jsou rozděleny do mnoha paketů, které mají všechny stejné záhlaví, charakterizující stejný uživatel), ale drastickým nárůstem počtu různých uživatelů v důsledku masivního a koordinovaného odesílání e-mailů (vše malého objemu ve srovnání se stahováním).
Pokaždé, když je datový paket přijat v síťovém uzlu, je uživatel b odesílající paket rozpoznán pomocí záhlaví datového paketu (řada délky L 0 a 1). Tato hlavička je hašována , tj. Transformována na jednotné náhodné číslo v intervalu [0,1]: tato transformace ( hashovací funkce ) je navržena tak, aby m paketů odeslaných m různými uživateli vytvořilo m různých hlaviček a po hašování těchto hlaviček , produkují sekvence o m nezávislé a jednotné náhodné proměnné v intervalu [0,1]. Na druhou stranu pakety odeslané stejným uživatelem b vytvářejí stejné časy záhlaví a následné hashy této záhlaví vytvářejí řadu stejných náhodných hodnot , které se rovnají stejnému počtu náhodně vylosovaných, jednou provždy, rovnoměrně přes interval [0, 1].
Eb {\ displaystyle {\ mathcal {E}} _ {b} \}Eb {\ displaystyle {\ mathcal {E}} _ {b} \}U(Eb) {\ displaystyle U ({\ mathcal {E}} _ {b}) \}(Eb)1≤b≤m {\ displaystyle \ left ({\ mathcal {E}} _ {b} \ right) _ {1 \ leq b \ leq m} \}(Ub)1≤b≤m {\ displaystyle \ left (U_ {b} \ right) _ {1 \ leq b \ leq m} \}ℓ {\ displaystyle \ ell \}ℓ {\ displaystyle \ ell \}Eb {\ displaystyle {\ mathcal {E}} _ {b} \}ℓ {\ displaystyle \ ell \} ℓ {\ displaystyle \ ell \}
Ve velmi krátké době je přijat velký počet ( P ) paketů. Máme pouze n paměťových buněk a chceme spočítat počet m různých uživatelů vysílajících tyto pakety. Z důvodu nedostatku místa v paměti není možné ukládat záhlaví již přijatých paketů za běhu a pro nedostatek času by bylo nemožné otestovat, zda je nová přijatá záhlaví součástí seznamu již shromážděných záhlaví. Přesný výpočet m je proto nemožný. Potom si dáme n krabic, očíslovaných od 1 do n , považovaných za volné nebo jinak obsazené . Na začátku jsou všechna pole považována za bezplatná. Na každém přijatém paketu je odpovídající záhlaví hašováno , čímž se vytvoří jednotné náhodné U číslo nad [0,1] a pole # je označeno jako obsazené, bez ohledu na jeho předchozí stav. Ať už se záhlaví objeví jednou nebo 10 000krát, výsledek bude stejný: je to kvůli této hlavičce stejné náhodné číslo U, které bude vygenerováno, a stejné číslo pole, které bude označeno jako obsazené.
⌈neU⌉ {\ displaystyle \ lceil nU \ rceil \}⌈neU⌉ {\ displaystyle \ lceil nU \ rceil \}
Tak stav souboru n polí po převzetí P paketů nezávisí na množství P v provozu, ale pouze na sérii m hash záhlaví odpovídajících m různí uživatelé. Přesněji řečeno, počet X volných buněk na konci procesu má stejný zákon jako v problému krabic a koulí zmíněných v předchozí části. Nerovnost koncentrace zajišťuje, že pro n a m dostatečně velké, s velkou pravděpodobností, aproximace pomocí X , to znamená, že:
(Ub)1≤b≤m {\ displaystyle (U_ {b}) _ {1 \ leq b \ leq m} \}E[X] {\ displaystyle \ mathbb {E} [X] \}
Xne ≃ (1-1ne)m ≃ E-m/ne{\ displaystyle {\ frac {X} {n}} \ \ simeq \ \ vlevo (1 - {\ tfrac {1} {n}} \ vpravo) ^ {m} \ \ simeq \ e ^ {- m / n }}
je dostatečně přesná, aby bylo možné rekonstruovat poměr r = m / n , a, počínaje tam, počet m různých uživatelů, neznámé do té doby, v závislosti na X a n , které jsou známé : zvolíme jako aproximace r čísla V této konkrétní situaci budeme spokojeni, pokud přesnost aproximace umožní detekovat náhlou změnu hodnoty m z jednoho okamžiku do druhého, změnu ohlašující virový útok: za to, a hrubá aproximace m by měla stačit.
-ln(X/ne). {\ displaystyle - \ ln (X / n). \}
Podívejte se také
Poznámky
-
navrhováno (v) Kyu-Young Whang a Ravi Krishnamurthy , „ Optimalizace dotazu v paměťovém rezidenčním databázovém systému s relační doménou “ , ACM Transaction on Database Systems (TODS) , New York, NY, USA, ACM, sv. 15, n o 1,Březen 1990, str. 67–95 ( ISSN 0362-5915 , číst online )
-
(en) Rajeev Motwani a Prabhakar Raghavan , Randomizované algoritmy , Cambridge; New York, Cambridge University Press ( repr. 1997, 2000) ( 1 st ed. 1995), 476 str. ( ISBN 9780521474658 ) , kap. 4 („Nerovnosti ocasu“) , s. 4 94–95, Věta 4.18.
Bibliografie
- (en) N. Alon a J. Spencer , Pravděpodobnostní metoda , New York, Wiley,1992
- (en) K. Azuma , „ Vážené součty určitých závislých náhodných proměnných “ , Tôhoku Math. Journ. , sv. 19,1967, str. 357-367
- (ru) Sergei N. Bernstein , „ O určitých modifikacích Čebyševovy nerovnosti “ , Doklady Akademii Nauk SSSR , sv. 17, n O 6,1937, str. 275–277
- (en) C. McDiarmid , „ O metodě omezených rozdílů “ , London Math. Soc. Poznámky ke čtení , Cambridge (Velká Británie), Cambridge Univ. Stisknutím N o 141 „průzkumy v kombinatorice“ ,1989, str. 148–188
- (en) W. Hoeffding , „ Pravděpodobnostní nerovnosti pro součet omezených náhodných proměnných “ , J. Amer. Statist. Doc. , sv. 58,1963, str. 13–30
- B. Maurey , „ Constructions de suites symetriques “, CR Acad. Sci. Paříž, řada A - B , sv. 288,1979, str. 679–681
Pro další
- (en) S. Boucheron , G. Lugosi a P. Massart , „ Koncentrační nerovnosti pomocí metody entropie “ , Annals of Probability ,2003
Propojené stránky
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">