Неравенство концентрации меры

В теории вероятностей неравенства концентрации меры дают оценки отклонения случайной величины от некоторого значения (обычно от её математического ожидания). Закон больших чисел классической теории вероятностей утверждает, что суммы независимых случайных величин, при соблюдении довольно слабых условий, с большой вероятностью оказываются близкими к их математическим ожиданиям. Такие суммы являются основными примерами случайных величин, которые сконцентрированы около своих средних значений.

Неравенство Маркова

Основная статья: Неравенство Маркова

Пусть ${\displaystyle X}$ случайная величина, почти наверное неотрицательная. Тогда, для всякой константы ${\displaystyle a>0}$

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

Отметим следующее выражение для неравенства Маркова: если ${\displaystyle \Phi }$ — неотрицательная строго возрастающая функция, то

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

Неравенство Чебышёва

Основная статья: Неравенство Чебышёва

Для неравенства Чебышёва требуется, чтобы случайная величина ${\displaystyle X}$ удовлетворяла следующим условиям:

• математическое ожидание ${\displaystyle \operatorname {E} [X]}$ конечно;
• дисперсия ${\displaystyle \operatorname {D} [X]=\operatorname {E} [(X-\operatorname {E} [X])^{2}]=\sigma ^{2}}$ конечна.

Тогда для всякой константы ${\displaystyle a>0}$

${\displaystyle P(|X-\operatorname {E} [X]|\geq a)\leq {\frac {\operatorname {D} [X]}{a^{2}}}}$,

или, равносильно,

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

где ${\displaystyle \operatorname {Std} [X]=\sigma }$ — стандартное отклонение случайной величины ${\displaystyle X}$.

Неравенство Чебышёва может рассматриваться как частный случай обобщённого неравенства Маркова, применённого к случайной величине ${\displaystyle |X-\operatorname {E} [X]|}$ с ${\displaystyle \Phi (x)=x^{2}}$.

Неравенство Высочанского-Петунина

Основная статья: Неравенство Высочанского — Петунина

Неравенство Гаусса

Основная статья: Неравенство Гаусса

Границы Чернова

Основная статья: Граница Чернова

Основной случай границы Чернова^[1]:63–65 требует существования для ${\displaystyle X}$ производящей функции, определяемой как ${\displaystyle M_{X}(t):=\operatorname {E} \!\left[e^{tX}\right]}$. Основываясь на неравенстве Маркова, для каждого ${\displaystyle t>0}$

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

и для каждого ${\displaystyle t<0}$

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

Границы Чернова различны для различных распределений и различных значений параметра ${\displaystyle t}$.

Границы сумм независимых случайных величин

Основные статьи: Неравенство Хёфдинга, Неравенство Азумы, Неравенство Макдиармида, Неравенство Беннета и Неравенство Бернштейна (теория вероятностей)

Пусть ${\displaystyle X_{1},X_{2},\dots ,X_{n}}$ — независимые случайные величины такие, что для всех i:

${\displaystyle a_{i}\leq X_{i}\leq b_{i}}$ почти наверное.

${\displaystyle c_{i}:=b_{i}-a_{i}}$

${\displaystyle \forall i:c_{i}\leq C}$

Пусть ${\displaystyle S_{n}}$- их сумма, ${\displaystyle E_{n}}$- математическое ожидание и ${\displaystyle D_{n}}$ — дисперсия

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

${\displaystyle E_{n}:=\operatorname {E} [S_{n}]=\sum _{i=1}^{n}\operatorname {E} [X_{i}]}$,

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

Часто представляет интерес оценка разности между суммой и её математическим ожиданием. Можно использовать несколько неравенств.

1. Неравенство Хёфдинга утверждает, что

${\displaystyle 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. Случайная величина ${\displaystyle (S_{n}-E_{n})}$ — это специальный случай мартингала, и ${\displaystyle S_{0}-E_{0}=0}$. Следовательно, можно использовать неравенство Азумы, что даёт чуть более слабую оценку

${\displaystyle 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)}$.

При этом здесь появляется возможность рассматривать любые мартингалы, в том числе супермартингалы и субмартингалы.

3. Функция суммирования ${\displaystyle S_{n}=f(X_{1},\dots ,X_{n})}$ — частный случай функции ${\displaystyle n}$ переменных. Эта функция изменяется ограниченным образом: если переменная ${\displaystyle i}$ изменяется, то значение ${\displaystyle f}$ также изменяется самое большее на ${\displaystyle b_{i}-a_{i}<C}$. Следовательно, можно использовать неравенство Макдиармида^[англ.], и оно даст аналогичную оценку

${\displaystyle 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)}$.

Это уже другое обобщение неравенства Хёфдинга, поскольку здесь имеется возможность работать не только с функцией суммирования, но и с другими функциями, если они изменяются ограниченным образом.

4. Неравенство Беннета^[англ.] даёт некоторые улучшения по сравнению с неравенством Хёфдинга, когда дисперсии слагаемых малы по сравнению с их «почти наверное-границами» C.

${\displaystyle 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],}$ где ${\displaystyle h(u)=(1+u)\log(1+u)-u}$

5. Первое из неравенств Бернштейна^[англ.] утверждает, что

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

Как и неравенство Хёфдинга, для которого данная оценка является обобщением, первое неравенство Бернштейна учитывает почти наверное ограниченные случайные величины. Более того, оно позволяет получить более точную оценку при условии, что случайные величины имеют ограниченные дисперсии.

6. Границы Чернова имеют особенно простую форму для суммы независимых величин, поскольку

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

Например,^[2] пусть случайные величины ${\displaystyle X_{i}}$ удовлетворяют неравенству ${\displaystyle X_{i}\geq E(X_{i})-a_{i}-M}$ при ${\displaystyle 1\leq i\leq n}$, тогда для нижнего хвоста мы имеем неравенство

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

Если ${\displaystyle X_{i}}$ удовлетворяет неравенству ${\displaystyle X_{i}\leq E(X_{i})+a_{i}+M}$, то для верхнего хвоста мы имеем неравенство

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

Если ${\displaystyle X_{i}}$ независимы и одинаково распределены, ${\displaystyle |X_{i}|\leq 1}$ и ${\displaystyle \sigma ^{2}}$ — дисперсия ${\displaystyle X_{i}}$, то типичный вид неравенства Чернова следующий:

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

7. Аналогичные границы можно найти в разделе: распределение Радемахера (Границы сумм)^[англ.]

Неравенство Эфрона-Стейна

Неравенство Эфрона-Стейна (неравенство влияния, или MG-оценка дисперсии) оценивает дисперсию функции общего вида от случайных величин.

Пусть ${\displaystyle X_{1}\dots X_{n}}$, ${\displaystyle X_{1}'\dots X_{n}'}$ независимы, a ${\displaystyle X_{i}'}$ и ${\displaystyle X_{i}}$ имеют одинаковое распределение при всех ${\displaystyle i}$.

Положим ${\displaystyle X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).}$ Тогда

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

Неравенство Дворецкого-Кифера-Вольфовица

Неравенство Дворецкого-Кифера-Вольфовица^[англ.] оценивает разность между фактической и эмпирической функциями распределения.

Пусть для данного натурального ${\displaystyle n}$ ${\displaystyle X_{1},X_{2},\dots ,X_{n}}$ — независимые и одинаково распределённые вещественнозначные случайные величины с функцией распределения ${\displaystyle F}$. Пусть ${\displaystyle F_{n}}$ обозначает соответствующую эмпирическую функцию распределения, определённую формулой

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

Таким образом, ${\displaystyle F(x)}$ — вероятность события, что отдельная случайная величина ${\displaystyle X}$ меньше, чем ${\displaystyle x}$, а ${\displaystyle F_{n}(x)}$ — это среднее количество величин из выборки ${\displaystyle X_{1},X_{2},\dots ,X_{n}}$, реализации которых меньше, чем ${\displaystyle x}$.

Тогда верны следующие односторонняя и двусторонняя оценки:

${\displaystyle 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}},}$

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

Примечания

1. Mitzenmacher, Michael. Probability and Computing: Randomized Algorithms and Probabilistic Analysis / Mitzenmacher, Michael, Upfal, Eli. — Cambridge University Press, 2005. — ISBN 0-521-83540-2. Архивная копия от 16 апреля 2021 на Wayback Machine
2. Chung, Fan; Lu, Linyuan Old and new concentration inequalities  (неопр.). Complex Graphs and Networks. American Mathematical Society (2010). Дата обращения: 14 августа 2018. Архивировано 15 апреля 2021 года.

Ссылки

• Karthik Sridharan, «A Gentle Introduction to Concentration Inequalities Архивная копия от 9 мая 2020 на Wayback Machine» — Cornell University
• One Hundred Probability/Statistics Inequalities Архивная копия от 13 апреля 2021 на Wayback Machine. См. «4 Concentration Inequalities»