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

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

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

Неравенства концентрации можно сортировать по тому, сколько информации о случайной величине необходимо для их использования.

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

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

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

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

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

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

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

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

Неравенство Чебышева требует следующей информации о случайной величине $X$:

• Ожидаемое значение $\operatorname {E} [X]$ конечно.
• Дисперсия ​ $\operatorname {Var} [X]=\operatorname {E} [(X-\operatorname {E} [X])^{2}]$ конечно.

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

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

или эквивалентно,

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

где $\operatorname {Std} [X]$ стандартное отклонение ​ $X$.

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

Vysochanskij–Petunin inequality

Main article: Vysochanskij–Petunin inequality

Пусть X — случайная величина с унимодальным распределением, средним значением µ и конечной ненулевой дисперсией σ. ² . Тогда для любого ${\textstyle \lambda >{\sqrt {\frac {8}{3}}}=1.63299\ldots ,}$

${\text{Pr}}(\left|X-\mu \right|\geq \lambda \sigma )\leq {\frac {4}{9\lambda ^{2}}}.$

(Относительно элементарное доказательство см., например, ).

Одностороннее неравенство Высочанского–Петунина.

Main article: Vysochanskij–Petunin inequality

Для унимодальной случайной величины $X$ и $r\geq 0$, одностороннее неравенство Высочанского-Петунина имеет место следующее:

${\text{Pr}}(X-E[X]\geq r)\leq {\begin{cases}{\dfrac {4}{9}}{\dfrac {\operatorname {Var} (X)}{r^{2}+\operatorname {Var} (X)}}&{\text{for }}r^{2}\geq {\dfrac {5}{3}}\operatorname {Var} (X),\\[5pt]{\dfrac {4}{3}}{\dfrac {\operatorname {Var} (X)}{r^{2}+\operatorname {Var} (X)}}-{\dfrac {1}{3}}&{\text{otherwise.}}\end{cases}}$

Неравенство Пэли – Зигмунда

Основная статья: неравенство Пэли – Зигмунда

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

Неравенство Кантелли

Основная статья: неравенство Кантелли

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

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

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

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

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

$\Pr(X\geq a)\leq {\frac {\operatorname {E} [e^{tX}]}{e^{ta}}},$

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

$\Pr(X\leq a)\leq {\frac {\operatorname {E} [e^{tX}]}{e^{ta}}}.$

Существуют различные границы Чернова для разных распределений и разных значений параметра $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}$ его ожидаемое значение и $V_{n}$ его дисперсия:

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

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

$V_{n}:=\operatorname {Var} [S_{n}]=\sum _{i=1}^{n}\operatorname {Var} [X_{i}]$

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

1. Неравенство Хеффдинга гласит, что:

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

2. Случайная величина $S_{n}-E_{n}$ является частным случаем мартингейла , и $S_{0}-E_{0}=0$. Следовательно, можно также использовать общую форму неравенства Азумы , которая дает аналогичную оценку:

$\Pr \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)$

Это обобщение метода Хоффдинга, поскольку оно может обрабатывать другие типы мартингалов, а также супермартингалы и субмартингалы . См. Fan et al. (2015). Обратите внимание: если используется более простая форма неравенства Азумы, показатель степени в оценке будет хуже в 4 раза.

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

$\Pr \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 . Там говорится, что:

$\Pr \left[|S_{n}-E_{n}|>t\right]\leq 2\exp \left[-{\frac {V_{n}}{C^{2}}}h\left({\frac {Ct}{V_{n}}}\right)\right],$ где $h(u)=(1+u)\log(1+u)-u$

5. Первое из неравенств Бернштейна гласит, что:

$\Pr \left[|S_{n}-E_{n}|>t\right]<2\exp \left(-{\frac {t^{2}/2}{V_{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$. Тогда мы имеем нижнее хвостовое неравенство:

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

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

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

Если $X_{i}$ являются идентификаторами, $|X_{i}|\leq 1$ и $\sigma ^{2}$ это дисперсия $X_{i}$, типичная версия неравенства Чернова:

$\Pr[|S_{n}|\geq k\sigma ]\leq 2e^{-k^{2}/4n}{\text{ for }}0\leq k\leq 2\sigma .$

7. Подобные оценки можно найти в: Распределение Радемахера#Границы сумм.

Неравенство Эфрона – Штейна

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

Предположим, что $X_{1}\dots X_{n}$, $X_{1}'\dots X_{n}'$ независимы с $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 {Var} (f(X))\leq {\frac {1}{2}}\sum _{i=1}^{n}E[(f(X)-f(X^{(i)}))^{2}].$

Доказательство можно найти, например, в.

Неравенство Бретаньоля – Хубера – Кэрола

Неравенство Бретаньолля – Хубера – Кэрол ограничивает разницу между вектором полиномиально распределенных случайных величин и вектором ожидаемых значений. Простое доказательство появляется в (Раздел Приложения).

Если случайный вектор $(Z_{1},Z_{2},Z_{3},\ldots ,Z_{n})$ имеет полиномиальное распределение с параметрами $(p_{1},p_{2},\ldots ,p_{n})$и удовлетворяет $Z_{1}+Z_{2}+\dots +Z_{n}=M,$ затем

$\Pr \left(\sum _{i=1}^{n}|Z_{i}-Mp_{i}|\geq 2M\varepsilon \right)\leq 2^{n}e^{-2M\varepsilon ^{2}}.$

Это неравенство используется для оценки общего расстояния вариации .

Неравенство Мэйсона и Ван Цвета

Неравенство Мэйсона и Ван Цвета для полиномиальных случайных векторов речь идет о небольшой модификации классической статистики хи-квадрат.

Пусть случайный вектор $(N_{1},\ldots ,N_{k})$ быть полиномиально распределены с параметрами $n$ и $(p_{1},\ldots ,p_{k})$ такой, что $p_{i}>0$ для $i<k.$ Тогда для каждого $C>0$ и $\delta >0$ существуют константы $a,b,c>0,$ такой, что для всех $n\geq 1$ и $\lambda ,p_{1},\ldots ,p_{k-1}$ удовлетворяющий $\lambda >Cn\min\{p_{i}|1\leq i\leq k-1\}$ и $\sum _{i=1}^{k-1}p_{i}\leq 1-\delta ,$ у нас есть

$\Pr \left(\sum _{i=1}^{k-1}{\frac {(N_{i}-np_{i})^{2}}{np_{i}}}>\lambda \right)\leq ae^{bk-c\lambda }.$

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

Основная статья: неравенство Дворецкого – Кифера – Вольфовица

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

Учитывая натуральное число $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$.

Затем

$\Pr \left(\sup _{x\in \mathbb {R} }{\bigl (}F_{n}(x)-F(x){\bigr )}>\varepsilon \right)\leq e^{-2n\varepsilon ^{2}}{\text{ for every }}\varepsilon \geq {\sqrt {{\tfrac {1}{2n}}\ln 2}}.$

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

неравенства против концентрации С другой стороны, обеспечивают верхнюю границу того, насколько случайная величина может концентрироваться вокруг величины.

Например, Рао и Йегудаев. показать, что существует некоторый $C>0$ такая, что для большинства направлений гиперкуба $x\in \{\pm 1\}^{n}$, верно следующее:

$\Pr \left(\langle x,Y\rangle =k\right)\leq {\frac {C}{\sqrt {n}}},$

где $Y$ извлекается равномерно из подмножества $B\subseteq \{\pm 1\}^{n}$ достаточно большого размера.

Такие неравенства важны в нескольких областях, включая сложность связи ( например , в доказательстве проблемы Хэмминга ) и теория графов .

Интересное неравенство антиконцентрации для взвешенных сумм независимых случайных величин Радемахера можно получить с помощью неравенств Пэли – Зигмунда и Хинчина .

Внешние ссылки

• Картик Шридхаран, « Нежное введение в неравенство концентрации » — Корнельский университет