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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

и для каждого $t<0$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$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. Случайная величина $(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)$.

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

3. Функция суммирования $S_{n}=f(X_{1},\dots ,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)$.

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

4. Неравенство Беннета даёт некоторые улучшения по сравнению с неравенством Хёфдинга, когда дисперсии слагаемых малы по сравнению с их «почти наверное-границами» 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],$ где $h(u)=(1+u)\log(1+u)-u$

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

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

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

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

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

Например, пусть случайные величины $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}+\sum _{i=1}^{n}a_{i}^{2}+M\lambda /3)}}\right)$.

Если $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}+\sum _{i=1}^{n}a_{i}^{2}+M\lambda /3)}}\right)$.

Если $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. Аналогичные границы можно найти в разделе: распределение Радемахера (Границы сумм)

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

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

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

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

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

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

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

Пусть для данного натурального $n$ $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} .$

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

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

$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.$

Ссылки

• 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»