Měřit koncentrační nerovnost

V teorii pravděpodobnosti míry nerovností koncentrace dávají odhady odchylky náhodné proměnné od nějaké hodnoty (obvykle od jejího matematického očekávání ). Zákon velkého počtu klasické teorie pravděpodobnosti říká, že součty nezávislých náhodných proměnných, za dosti slabých podmínek, se s vysokou pravděpodobností blíží jejich matematickým očekáváním. Takové součty jsou hlavními příklady náhodných proměnných, které jsou soustředěny kolem jejich středních hodnot .

Markovova nerovnost

Nechť náhodnou veličinu, téměř jistě nezápornou. Pak pro jakoukoli konstantu $X$ $a>0$

P(X\geq a)\leq {\frac {\operatorname {E} (X)}{a))

Všimněte si následujícího výrazu pro Markovovu nerovnost: if je nezáporná přísně rostoucí funkce, pak $\Phi$

P(X\geq a)=P(\Phi (X)\geq \Phi (a))\leq {\frac {\operatorname {E} (\Phi (X))}{\Phi (a )}}

Čebyševova nerovnost

Čebyševova nerovnost vyžaduje, aby náhodná proměnná splňovala následující podmínky: $X$

matematické očekávání samozřejmě; $\operatorname {E} [X]$
rozptyl je konečný. ${\displaystyle \operatorname {D} [X]=\operatorname {E} [(X-\operatorname {E} [X])^{2}]=\sigma ^{2))$

Pak pro jakoukoli konstantu $a>0$

{\displaystyle P(|X-\jméno operátora {E} [X]|\geq a)\leq {\frac {\jméno operátora {D} [X]}{a^{2))))

nebo ekvivalentně,

{\displaystyle P(|X-\operatorname {E} [X]|\geq a\cdot \operatorname {Std} [X])\leq {\frac {1}{a^{2))))

kde je směrodatná odchylka náhodné veličiny . $\operatorname {Std} [X]=\sigma$ $X$

Čebyševovu nerovnost lze považovat za speciální případ zobecněné Markovovy nerovnosti aplikované na náhodnou veličinu c . $|X-\jméno operátora {E} [X]|$ ${\displaystyle \Phi (x)=x^{2))$

Vysochansky-Petuninova nerovnost

Gaussova nerovnost

Černovské hranice

Hlavní případ černovské hranice [1] :63–65 vyžaduje existenci generující funkce definované jako . Na základě Markovovy nerovnosti pro každého $X$ $M_{X}(t):=\jméno operátora {E} \!\left[e^{tX}\right]$ $t>0$

{\displaystyle P(X\geq a)\leq {\frac {\název operátora {E} [e^{t\cdot X}]}{e^{t\cdot a))))

a pro každého $t<0$

{\displaystyle P(X\leq a)\leq {\frac {\operatorname {E} [e^{t\cdot X}]}{e^{t\cdot a))))

Chernoffovy meze jsou různé pro různá rozdělení a různé hodnoty parametru . $t$

Hranice pro součty nezávislých náhodných veličin

Nechť jsou nezávislé náhodné proměnné takové, že pro všechna i: ${\displaystyle X_{1},X_{2},\dots ,X_{n))$

{\displaystyle a_{i}\leq X_{i}\leq b_{i))

skoro pravděpodobně .

c_{i}:=b_{i}-a_{i}

\forall i:c_{i}\leq C

Nechť - jejich součet, - matematické očekávání a - rozptyl $S_{n}$ $E_{n}$ $D_{n}$

{\displaystyle S_{n}:=\sum _{i=1}^{n}X_{i))

E_{n}:=\jméno operátora {E} [S_{n}]=\sum _{i=1}^{n}\jméno operátora {E} [X_{i}]

D_{n}:=\operatorname {D} [S_{n}]=\sum _{i=1}^{n}\operatorname {D} [X_{i}]

Často je zajímavé odhadnout rozdíl mezi součtem a jeho matematickým očekáváním. Lze použít několik nerovností.

1. Hoefdingova nerovnost říká, že

P\left[|S_{n}-E_{n}|>t\right]<2\exp \left(-{\frac {2t^{2}}{\sum _{i=1} ^{n}c_{i}^{2}}\right)<2\exp \left(-{\frac {2t^{2}}{nC^{2}}}\right)

2. Náhodná veličina je speciální případ martingalu a . Proto lze použít Azumovu nerovnost , která dává o něco slabší odhad $(S_{n}-E_{n})$ $S_{0}-E_{0}=0$

P\left[|S_{n}-E_{n}|>t\right]<2\exp \left(-{\frac {t^{2}}{2\sum _{i=1 }^{n}c_{i}^{2}}}\right)<2\exp \left(-{\frac {t^{2}}{2nC^{2}}}\right)

Zde je možné uvažovat jakékoli martingaly , včetně supermartingalů a submartingalů .

3. Sčítací funkce je speciální případ funkce proměnných. Tato funkce se mění omezeně: změní-li se proměnná , změní se také hodnota nejvýše o . Proto lze použít McDiarmidovu nerovnost , která dá podobný odhad $S_{n}=f(X_{1},\tečky ,X_{n})$ $n$ $i$ $F$ $b_{i}-a_{i}<C$

P\left[|S_{n}-E_{n}|>t\right]<2\exp \left(-{\frac {2t^{2}}{\sum _{i=1} ^{n}c_{i}^{2}}\right)<2\exp \left(-{\frac {2t^{2}}{nC^{2}}}\right)

Jde o další zobecnění Hoefdingovy nerovnosti, neboť zde lze pracovat nejen se sčítací funkcí, ale i s dalšími funkcemi, pokud se omezeně mění.

4. Bennettova nerovnost poskytuje určité zlepšení oproti Höfdingově nerovnosti, když jsou rozptyly členů malé ve srovnání s jejich "téměř pravděpodobně-mezi" C .

P\left[|S_{n}-E_{n}|>t\right]\leq 2\exp \left[-{\frac {D_{n}}{C^{2}}}h \left({\frac {Ct}{D_{n))}\right)\right],

kde

h(u)=(1+u)\log(1+u)-u

5. První z Bernsteinových nerovností říká, že

P\left[|S_{n}-E_{n}|>t\right]<2\exp \left(-{\frac {t^{2}/2}{D_{n}+C \cdot t/3}}\right)

Stejně jako Höfdingova nerovnost, pro kterou je tento odhad zobecněním, bere Bernsteinova první nerovnost téměř jistě v úvahu ohraničené náhodné veličiny. Navíc umožňuje získat přesnější odhad za předpokladu, že náhodné proměnné mají omezené rozptyly.

6. Chernoffovy meze mají zvláště jednoduchý tvar pro součet nezávislých veličin, protože

\operatorname {E} [e^{t\cdot S_{n}}]=\prod _{i=1}^{n}{\operatorname {E} [e^{t\cdot X_{i }}]}

Například [2] nechť náhodné proměnné splňují nerovnost pro , pak pro spodní konec máme nerovnost $X_{i}$ $X_{i}\geq E(X_{i})-a_{i}-M$ $1\leq i\leq n$

P[S_{n}-E_{n}<-\lambda ]\leq \exp \left(-{\frac {\lambda ^{2)){2(D_{n}+\součet _{ i=1}^{n}a_{i}^{2}+M\lambda /3)}}\right)

Pokud splňuje nerovnost , pak pro horní ocas máme nerovnost $X_{i}$ $X_{i}\leq E(X_{i})+a_{i}+M$

P[S_{n}-E_{n}>\lambda ]\leq \exp \left(-{\frac {\lambda ^{2)){2(D_{n}+\součet _{i =1}^{n}a_{i}^{2}+M\lambda /3)}}\right)

Pokud jsou nezávislé a rovnoměrně rozložené a jsou rozptylem , pak typická forma Chernoffovy nerovnosti je následující: $X_{i}$ $|X_{i}|\leq 1$ $\sigma ^{2}$ $X_{i}$

P[|S_{n}|\geq k\sigma ]\leq 2e^{-k^{2}/4n},\qquad 0\leq k\leq 2\sigma

7. Podobné hranice lze nalézt v sekci: Distribuce Rademacher (Hranice součtů)

Efron-Steinova nerovnost

Efron-Steinova nerovnost (nerovnost vlivu nebo MG-odhad rozptylu) odhaduje rozptyl obecné funkce náhodných veličin.

Dovolit , být nezávislý, a a mít stejné rozdělení pro všechny . $X_{1}\dots X_{n}$ $X_{1}'\dots X_{n}'$ $X_{i}'$ $X_{i}$ $i$

Dejte Pak $X=(X_{1},\tečky ,X_{n}),X^{(i)}=(X_{1},\tečky ,X_{i-1},X_{i}', X_{i+1},\tečky ,X_{n}).$

\mathrm {D} (f(X))\leq {\frac {1}{2}}\sum _{i=1}^{n}E[(f(X)-f(X^) {(i)}))^{2}]

Dvoretsky-Kiefer-Wolfowitzova nerovnost

Dvoretsky-Kiefer-Wolfowitz nerovnost odhaduje rozdíl mezi aktuální a empirickou distribuční funkcí .

Nechť jsou pro dané přirozené číslo nezávislé a shodně rozdělené reálné hodnoty náhodné veličiny s distribuční funkcí . Označme odpovídající empirickou distribuční funkci , definovanou vzorcem $n$ ${\displaystyle X_{1},X_{2},\dots ,X_{n))$ $F$ $F_{n}$

F_{n}(x)={\frac {1}{n}}\sum _{i=1}^{n}\mathbf {1} _{\{X_{i}\leq x\ }},\qquad x\in \mathbb {R} .

Je tedy pravděpodobnost události, že jedna náhodná proměnná je menší než , a je průměrný počet hodnot ze vzorku , jehož realizace jsou menší než . $F(x)$ $X$ $X$ $F_{n}(x)$ ${\displaystyle X_{1},X_{2},\dots ,X_{n))$ $X$

Potom platí následující jednostranné a oboustranné odhady:

P\left(\sup _{x\in \mathbb {R} }{\bigl (}F_{n}(x)-F(x){\bigr )}>\varepsilon \right)\leq e^{-2n\varepsilon ^{2)),\qquad \forall \varepsilon \geq {\sqrt ({\tfrac {1}{2n))\ln 2)),

P{\Bigl (}\sup _{x\in \mathbb {R} }|F_{n}(x)-F(x)|>\varepsilon {\Bigr )}\leq 2e^{- 2n\varepsilon ^{2}},\qquad \forall \varepsilon >0.

Poznámky

↑ Mitzenmacher, Michael. Pravděpodobnost a výpočty: Randomizované algoritmy a pravděpodobnostní analýza / Mitzenmacher, Michael, Upfal, Eli. - Cambridge University Press, 2005. - ISBN 0-521-83540-2 . Archivováno 16. dubna 2021 na Wayback Machine
↑ Chung, Fan; Lu, Linyuan Staré a nové koncentrační nerovnosti . Komplexní grafy a sítě . Americká matematická společnost (2010). Získáno 14. srpna 2018. Archivováno z originálu 15. dubna 2021. (neurčitý)

Odkazy

Karthik Sridharan, „ Jemný úvod do koncentračních nerovností archivováno 9. května 2020 na Wayback Machine “ – Cornell University
Sto pravděpodobností/statistických nerovností archivováno 13. dubna 2021 na Wayback Machine . Viz "4 koncentrační nerovnosti"