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

редактировать

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

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

Содержание

1 Неравенство Маркова
2 Неравенство Чебышева
3 Неравенство Высочанского – Петунина
4 Неравенство Пэли – Зигмунда
5 Неравенство Кантелли
6 Неравенство Гаусса
7 Границы Черноффа
8 Границы сумм независимых переменных
9 Неравенство Эфрона – Штейна
10 Неравенство Дворецкого – Кифера – Вулфовица
11 Неравенства антиконцентрации
12 Ссылки
13 Внешние ссылки

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

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

Pr (X ≥ a) ≤ E ⁡ (X) a. {\ displaystyle \ Pr (X \ geq a) \ leq {\ frac {\ operatorname {E} (X)} {a}}.}

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

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

Pr (X ≥ a) = Pr (Φ (X) ≥ Φ (a)) ≤ E ⁡ (Φ (X)) Φ (a). {\ displaystyle \ Pr (X \ geq a) = \ Pr (\ Phi (X) \ geq \ Phi (a)) \ leq {\ frac {\ operatorname {E} (\ Phi (X))} {\ Phi (a)}}.}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Pr (X ≥ a) ≤ E ⁡ [et ⋅ X] et ⋅ a, {\ displaystyle \ Pr (X \ geq a) \ leq {\ frac {\ operatorname {E} [e ^ {t \ cdot X}]} {e ^ {t \ cdot a}}},}

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

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

Pr (X ≤ a) ≤ E ⁡ [et ⋅ X] et ⋅ a. {\ Displaystyle \ Pr (X \ leq a) \ leq {\ frac {\ operatorname {E} [e ^ {t \ cdot X}]} {e ^ { t \ cdot a}}}.}

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

Существуют различные границы Чернова для разных распределений и разных значений параметра $t {\ displaystyle t}$ $t$ . См. компиляцию дополнительных неравенств концентраций.

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

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

ai ≤ X i ≤ bi {\ displaystyle a_ {i} \ leq X_ {i} \ leq b_ {i}}

{\ displaystyle a_ {i} \ leq X_ {i} \ leq b_ {i}}

почти наверняка.

ci: = bi - ai {\ displaystyle c_ {i}: = b_ {i} -a_ {i}}

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

∀ i: ci ≤ C {\ displaystyle \ forall i: c_ {i} \ leq C}

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

Пусть $S n {\ displaystyle S_ {n}}$ $S_ {n}$ будет их суммой, $E n {\ displaystyle E_ {n}}$ $E_ {n}$ его ожидаемым значение и $V n {\ displaystyle V_ {n}}$ $V_ {n}$ его дисперсия:

S n: = ∑ i = 1 n X i {\ displaystyle S_ {n}: = \ sum _ {i = 1} ^ {n} X_ {i}}

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

E n: = E ⁡ [S n] = ∑ i = 1 n E ⁡ [X i] {\ displaystyle E_ {n}: = \ operatorname {E} [S_ {n}] = \ sum _ {i = 1} ^ {n} \ operatorname {E} [X_ {i}]}

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

V n: = Var ⁡ [S n] Знак равно ∑ я = 1 N Var ⁡ [X i] {\ displaystyle V_ {n}: = \ operatorname {Var} [S_ {n}] = \ sum _ {i = 1} ^ {n} \ operatorname {Var} [X_ {i}]}

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

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

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

Pr [| S n - E n |>t] < 2 exp ⁡ ( − 2 t 2 ∑ i = 1 n c i 2) < 2 exp ⁡ ( − 2 t 2 n C 2) {\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)}

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

Pr [| S n - E n |>t] < 2 exp ⁡ ( − 2 t 2 ∑ i = 1 n c i 2) < 2 exp ⁡ ( − 2 t 2 n C 2) {\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)}

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

Pr [| S n - E n |>t] < 2 exp ⁡ ( − 2 t 2 ∑ i = 1 n c i 2) < 2 exp ⁡ ( − 2 t 2 n C 2) {\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)}

\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 [| S n - E n |>T] ≤ 2 ехр ⁡ [- V N C 2 час (C t V N)], {\ 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],}

\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],

где

час (u) = (1 + u) журнал ⁡ (1 + u) - u {\ displaystyle h (u) = (1 + u) \ log (1 + u) -u}

{\ displaystyle h (u) = (1 + u) \ log (1 + u) -u}

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

Pr [| S n - E n |>t] < 2 exp ⁡ ( − t 2 / 2 V n + C ⋅ t / 3) {\displaystyle \Pr \left[|S_{n}-E_{n}|>t\right ]<2\exp \left(-{\frac {t^{2}/2}{V_{n}+C\cdot t/3}}\right)}

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

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

6. Границы Чернова имеют особенно простой вид в случае суммы независимых переменные, поскольку $E ⁡ [et ⋅ S n] = ∏ i = 1 N E ⁡ [et ⋅ X i] {\ displaystyle \ operatorname {E} [e ^ {t \ cdot S_ {n}}] = \ prod _ {i = 1} ^ {n} {\ operatorname {E} [e ^ {t \ cdot X_ {i}}]}}$ ${\ displaystyle \ operatorname {E} [e ^ {t \ cdot S_ {n}}] = \ prod _ {i = 1} ^ {n} {\ operatorname {E} [e ^ {t \ cdot X_ {i}} ]}}$ .

Например, предположим, что переменные $Икс i {\ displaystyle X_ {i}}$ $X_ {i}$ удовлетворяет $X i ≥ E (X i) - ai - M {\ displaystyle X_ {i} \ geq E (X_ {i})) -a_ {i} -M}$ $X_i \ geq E (X_i) -a_i-M$ , для $1 ≤ i ≤ n {\ displaystyle 1 \ leq i \ leq n}$ $1 \ leq i \ leq n$ . Тогда у нас есть неравенство нижнего хвоста:

Pr [S n - E n < − λ ] ≤ exp ⁡ ( − λ 2 2 ( V n + ∑ i = 1 n a i 2 + M λ / 3)) {\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 \ 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 {\ displaystyle X_ {i}}$ $X_ {i}$ удовлетворяет $X i ≤ E (X i) + ai + M {\ displaystyle X_ {i} \ leq E (X_ {i}) + a_ {i} + M}$ $X_i \ leq E (X_i) + a_i + M$ , мы имеем неравенство верхнего хвоста:

Pr [S n - E n>λ] ≤ ехр - (- λ 2 2 (V n + ∑ я = 1 nai 2 + M λ / 3)) {\ 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)}

\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 {\ displaystyle X_ {i}}$ $X_ {i}$ являются iid, $X i | ≤ 1 {\ displaystyle | X_ {i} | \ leq 1}$ $| X_i | \ Leq 1$ и $σ 2 {\ displaystyle \ sigma ^ {2}}$ $\ sigma ^ {2}$ - дисперсия $Икс i {\ displaystyle X_ {i}}$ $X_ {i}$ , типичная версия неравенства Чернова:

Pr [| S n | ≥ k σ] ≤ 2 e - k 2/4 n для 0 ≤ k ≤ 2 σ. {\ displaystyle \ Pr [| S_ {n} | \ geq k \ sigma] \ leq 2e ^ {- k ^ {2} / 4n} {\ text {for}} 0 \ leq k \ leq 2 \ sigma.}

{\ displaystyle \ Pr [| S_ {n} | \ geq к \ сигма] \ leq 2e ^ {- к ^ {2} / 4n} {\ текст {for}} 0 \ leq k \ leq 2 \ sigma.}

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

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

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

Предположим, что $X 1… X n {\ displaystyle X_ {1} \ dots X_ {n}}$ $X_1 \ dots X_n$ , $X 1 ′… X n ′ {\ displaystyle X_ {1} '\ dots X_ {n} '}$ $X_1' \dots X_n'$ независимы с $X i ′ {\ displaystyle X_ {i}'}$ $X_i'$ и $X i {\ displaystyle X_ {i}}$ $X_ {i}$ с одинаковым распределением для всех $i {\ displaystyle i}$ $i$ .

Пусть $X = (X 1,…, X n), X (i) = (X 1,…, X i - 1, X i ′, X i + 1,…, X n). {\ displaystyle X = (X_ {1}, \ dots, X_ {n}), X ^ {(i)} = (X_ {1}, \ dots, X_ {i-1}, X_ {i} ', X_ {i + 1}, \ dots, X_ {n}).}$ $X = (X_1,\dots, X_n), X^{(i)} = (X_1, \dots, X_{i-1}, X_i',X_{i+1}, \dots, X_n).$ Тогда

V ar (f (X)) ≤ 1 2 ∑ i = 1 n E [(f (X) - f (X (i))) 2]. {\ displaystyle \ mathrm {Var} (f (X)) \ leq {\ frac {1} {2}} \ sum _ {i = 1} ^ {n} E [(f (X) -f (X ^ {(i)})) ^ {2}].}

\ mathrm {Var} (f (X)) \ leq \ frac {1} {2} \ sum_ {i = 1} ^ {n} E [(f (X) -f (X ^ {(i)})) ^ 2].

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

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

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

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

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

Итак, $F (x) {\ displaystyle F (x)}$ $F (x)$ - это вероятность того, что одна случайная величина $X {\ displaystyle X}$ $X$ меньше, чем $x {\ displaystyle x}$ $x$ и $F n (x) {\ displaystyle F_ {n} (x)}$ $F_n (x)$ - среднее количество случайных величин, меньших, чем $x {\ displaystyle x}$ $x$ .

Тогда

Pr (sup x ∈ R (F n (x) - F ( x))>ε) ≤ e - 2 n ε 2 для любого ε ≥ 1 2 n ln ⁡ 2. {\ 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}}.}

\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 }}.

Anti- неравенства концентрации

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

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

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

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

где $Y {\ displaystyle Y}$ $Y$ - равномерно нарисованный из подмножества $B ⊆ {± 1} n {\ displaystyle B \ substeq \ {\ pm 1 \} ^ {n}}$ ${\ displaystyle B \ substeq \ {\ pm 1 \} ^ {n}}$ достаточно большого размера.

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

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

Ссылки

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

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