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

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

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

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

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

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

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

${ Displaystyle Pr (Икс geq a) = Pr ( Phi (X) geq Phi (a)) leq { frac { operatorname {E} ( Phi (X))} { Phi (а)}}.}$

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

Неравенство Чебышева требует следующей информации о случайной величине ${ 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 (х) = х ^ {2}}$.

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

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

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

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

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

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

${ Displaystyle Pr (Икс 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 а_ {я} leq X_ {я} leq b_ {я}}$ почти наверняка.

${ 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_ {п}: = сумма _ {я = 1} ^ {п} X_ {я}}$

${ 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_ {п} = е (X_ {1}, точки, X_ {n})}$, является частным случаем функции п переменные. Эта функция изменяется ограниченным образом: если переменная я изменяется, значение ж изменяется не более чем на ${ displaystyle b_ {i} -a_ {i}$. Следовательно, Неравенство МакДиармида также можно использовать, и это дает аналогичную оценку:

${ 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 ч (и) = (1 + и) журнал (1 + и) -у}$

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 я Leq п}$. Тогда у нас есть неравенство нижнего хвоста:

${ 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} точки 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 (х)}$ вероятность того, что Один случайная переменная ${ displaystyle X}$ меньше чем ${ displaystyle x}$, и ${ Displaystyle F_ {п} (х)}$ это среднее число случайных величин, меньших, чем ${ 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 {для каждого}} varepsilon geq { sqrt {{ tfrac {1} {2n}} ln 2}}.}$

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

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

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

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

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

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

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

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

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

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