Неравенство концентраций - Concentration inequality

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

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

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

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

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

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

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

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

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

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

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

• Ожидаемое значение ${\displaystyle \operatorname {E} [X]}$ конечно.
• В отклонение ${\displaystyle \operatorname {Var} [X]=\operatorname {E} [(X-\operatorname {E} [X])^{2}]}$ конечно.

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

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

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

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

куда ${\displaystyle \operatorname {Std} [X]}$ это стандартное отклонение из ${\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 \Pr(X\geq a)\leq {\frac {\operatorname {E} [e^{t\cdot X}]}{e^{t\cdot a}}},}$

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

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

Существуют разные границы Чернова для разных распределений и разных значений параметра ${\displaystyle t}$. Видеть ^[2]:5–7 для компиляции большего количества неравенств концентрации.

Оценки сумм независимых переменных

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

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

${\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 V_{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 V_{n}:=\operatorname {Var} [S_{n}]=\sum _{i=1}^{n}\operatorname {Var} [X_{i}]}$

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

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

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

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

${\displaystyle \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 раза.

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

${\displaystyle \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. В нем говорится, что:

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

5. Первый из Неравенства Бернштейна Говорит, что:

${\displaystyle \Pr \left[|S_{n}-E_{n}|>t\right]<2\exp \left(-{\frac {t^{2}/2}{V_{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}}]}}$.

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

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

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

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

Если ${\displaystyle X_{i}}$ i.i.d., ${\displaystyle |X_{i}|\leq 1}$ и ${\displaystyle \sigma ^{2}}$ это дисперсия ${\displaystyle X_{i}}$, типичный вариант неравенства Чернова:

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

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

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

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

Предположим, что ${\displaystyle X_{1}\dots X_{n}}$, ${\displaystyle X_{1}'\dots X_{n}'}$ независимы с ${\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 {Var} (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}}$ иметь реальную ценность независимые и одинаково распределенные случайные переменные с кумулятивная функция распределения 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}$.

потом

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

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

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

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

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

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

Такое неравенство важно в нескольких областях, в том числе сложность коммуникации (например, в доказательствах проблема разрыва Хэмминга^[5]) и теория графов.^[6]

Интересное неравенство антиконцентрации для взвешенных сумм независимых Радемахер случайные величины могут быть получены с помощью Пейли-Зигмунд и Хинчин неравенства.^[7]

Рекомендации

1. Митценмахер, Майкл; Упфал, Эли (2005). Вероятность и вычисления: рандомизированные алгоритмы и вероятностный анализ. Издательство Кембриджского университета. ISBN  0-521-83540-2.
2. Слэгл, Н. (2012). «Сто статистик и вероятностных неравенств» (PDF).
3. Чанг, Фань; Лу, Линьюань (2010). «Старое и новое неравенство концентрации» (PDF). Сложные графы и сети. Американское математическое общество. Получено 14 августа, 2018.
4. Рао, Ануп; Иегудаофф, Амир (2018). «Антиконцентрация по большинству направлений». Электронный коллоквиум по вычислительной сложности.
5. Шерстов, Александр А. (2012). «Коммуникационная сложность расстояния Хэмминга». Теория вычислений.
6. Мэтью Кван; Бенни Судаков; Туан Тран (2018). «Антиконцентрация для статистики подграфов». Журнал Лондонского математического общества. 99 (3): 757–777. arXiv:1807.05202. Bibcode:2018arXiv180705202K. Дои:10.1112 / jlms.12192. S2CID  54065186.
7. Вераар, Марк (2009). «О неравенствах Хинчина с весом». arXiv:0909.2586v1 [math.PR ].

внешняя ссылка

Картик Шридхаран "Мягкое введение в неравенство концентрации "  —Корнелл Университет