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

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

экспоненциально убывающие границы хвостовых распределений сумм независимых случайных величин

В теории вероятностей, граница Чернова, названная в честь Германа Чернова, но из-за Германа Рубина, дает экспоненциально убывающие границы для хвостовых распределений сумм независимых случайных величин. Это более точная оценка, чем известные границы хвоста на основе первого или второго момента, такие как неравенство Маркова или неравенство Чебышева, которые дают только степенные ограничения на затухание хвоста. Однако оценка Чернова требует, чтобы переменные были независимыми - условие, которое не требуется ни неравенством Маркова, ни неравенством Чебышева, хотя неравенство Чебышева требует, чтобы переменные были попарно независимыми.

Это связано с (исторически предшествующим) неравенствами Бернштейна и неравенством Хёффдинга.

Содержание

1 Общая граница
2 Пример
3 Аддитивная форма (абсолютная ошибка)
4 Мультипликативная форма (относительная ошибка)
5 Приложения
6 Граница матрицы
- 6.1 Теорема без зависимости от размерностей
- 6.2 Теорема с матрицами, которые не являются полностью случайными
7 Вариант выборки
8 Доказательства
- 8.1 Теорема Чернова – Хёффдинга (аддитивная форма)
- 8.2 Мультипликативная форма
9 См. Также
10 Ссылки
11 Дополнительная литература

Общая оценка

Общая граница Чернова для случайной величины X достигается применением неравенства Маркова к e. Для каждого $t>0 {\ displaystyle t>0}$ $t>0$ :

Pr (X ≥ a) = Pr (et ⋅ X ≥ et ⋅ a) ≤ E [et ⋅ X] et ⋅ a. {\ displaystyle \ Pr (X \ geq a) = \ Pr (e ^ {t \ cdot X} \ geq e ^ {t \ cdot a}) \ leq {\ frac {\ mathrm {E} \ left [e ^ {t \ cdot X } \ right]} {e ^ {t \ cdot a}}}.}

\ Pr (X \ geq a) = \ Pr (e ^ {t \ cdot X} \ geq e ^ {t \ cdot a}) \ leq {\ frac {\ mathrm {E} \ left [e ^ {t \ cdot X} \ right]} {e ^ {t \ cdot a}} }.

Когда X является суммой n случайных величин X 1,..., X n, мы получаем для любого t>0,

Pr (X ≥ a) ≤ e - ta E [∏ iet ⋅ X i]. {\ displaystyle \ Pr (X \ geq a) \ leq e ^ {- ta } \ mathrm {E} \ left [\ prod _ {i} e ^ {t \ cdot X_ {i}} \ right].}

\ Pr (X \ geq a) \ leq e ^ {- ta} \ mathrm {E} \ left [\ prod _ {i} e ^ {t \ cdot X_ {i}} \ right].

В частности, оптимизация по t и предположение, что X i независимы, мы получаем,

Pr (X ≥ a) ≤ min t>0 e - ta ∏ i E [et X i]. {\ displaystyle \ Pr (X \ geq a) \ leq \ min _ { t>0} e ^ {- ta} \ prod _ {i} \ mathrm {E} \ left [e ^ {tX_ {i}} \ right].}

\Pr(X\geq a)\leq \min _{t>0} e ^ {- ta } \ prod _ {i} \ mathrm {E} \ left [e ^ {tX_ {i}} \ right].

(1)

Аналогично

Pr (X ≤ a) = Pr ( е - T Икс ≥ е - та) {\ Displaystyle \ Pr (X \ Leq a) = \ Pr \ left (e ^ {- tX} \ geq e ^ {- ta} \ right)}

\ Pr (X \ leq a) = \ Pr \ left (e ^ {- tX} \ geq e ^ {- ta} \ right)

и так,

Pr (Икс ≤ a) ≤ min t>0 эта ∏ я E [е - t X я] {\ Displaystyle \ Pr (X \ Leq a) \ Leq \ min _ {t>0} e ^ {ta } \ prod _ {i} \ mathrm {E} \ left [e ^ {- tX_ {i}} \ right]}

\Pr(X\leq a)\leq \min _{t>0} e ^ {ta} \ prod _ {i} \ mathrm { E} \ left [e ^ {- tX_ {i}} \ right]

Конкретные границы Чернова достигаются путем вычисления $E [e - t ⋅ X i] {\ displaystyle \ mathrm {E} \ left [e ^ {- t \ cdot X_] {i}} \ right]}$ $\ mathrm {E} \ left [e ^ {- t \ cdot X_ {i}} \ right]$ для конкретных экземпляров основных переменных $X i {\ displaystyle X_ {i}}$ $X_ {i}$ .

Пример

Пусть X 1,..., X n быть независимыми случайными величинами Бернулли, сумма которых равна X, каждая из которых имеет вероятность p>1/2 g равно 1. Для переменной Бернулли:

E [et ⋅ X i] = (1 - p) e 0 + pet = 1 + p (et - 1) ≤ ep (et - 1) {\ displaystyle \ mathrm {E} \ left [e ^ {t \ cdot X_ {i}} \ right] = (1-p) e ^ {0} + pe ^ {t} = 1 + p (e ^ {t} -1) \ leq e ^ {p (e ^ {t} -1)}}

{\ displaystyle \ mathrm {E} \ left [e ^ {t \ cdot X_ {i}} \ right] = (1-p) e ^ {0} + pe ^ {t} = 1 + p (e ^ {t} -1) \ leq e ^ {p (e ^ {t} -1)}}

Итак:

E [et ⋅ X] ≤ en ⋅ p (et - 1) {\ displaystyle \ mathrm {E} \ left [e ^ {t \ cdot X} \ right] \ leq e ^ {n \ cdot p (e ^ {t} -1)}}

\ mathrm {E} \ left [e ^ {t \ cdot X} \ right] \ leq e ^ {n \ cdot p (e ^ {t} -1)}

для любого $δ>0 {\ displaystyle \ delta>0}$ $\delta>0$ , принимая $t = ln ⁡ (1 + δ)>0 {\ displaystyle t = \ ln (1+ \ delta)>0}$ $t=\ln(1+\delta)>0$ и $a = (1 + δ) np {\ displaystyle a = (1+ \ delta) np}$ $a = (1+ \ delta) np$ дает:

E [et ⋅ X] ≤ e δ np {\ displaystyle \ mathrm {E} \ left [e ^ {t \ cdot X} \ right] \ leq e ^ {\ delta np}}

\ mathrm {E} \ left [e ^ {t \ cdot X} \ right] \ leq e ^ {\ delta np}

e - ta = 1 (1 + δ) (1 + δ) np {\ displaystyle e ^ {- ta} = {\ frac {1} {(1+ \ delta) ^ {(1+ \ delta) np}}}}

e ^ {- ta} = {\ frac {1} {(1+ \ дельта) ^ {(1+ \ дельта) np}}}

и общая граница Чернова дает:

Pr [X ≥ (1 + δ) np] ≤ e δ np (1 + δ) (1 + δ) np = [e δ (1 + δ) 1 + δ] np {\ displaystyle \ Pr [Икс \ geq (1+ \ delta) np] \ leq {\ frac {e ^ {\ delta np}} {(1+ \ delta) ^ {(1+ \ delta) np}}} = \ left [{\ frac {e ^ {\ delta}} {(1+ \ delta) ^ {1+ \ delta}}} \ right] ^ {np}}

{\ displaystyle \ Pr [X \ geq (1+ \ delta) np] \ leq { \ frac {e ^ {\ delta np}} {(1+ \ delta) ^ {(1+ \ delta) np}}} = \ left [{\ frac {e ^ {\ delta}}} {(1+ \ delta) ^ {1+ \ delta}}} \ right] ^ {np}}

Вероятность одновременного появления более n / 2 из событий {X k = 1} имеют точное значение:

Pr [X>n 2] = ∑ i = ⌊ n 2 ⌋ + 1 n (ni) pi (1 - p) п - я. {\ displaystyle \ Pr \ left [X>{n \ over 2} \ right] = \ sum _ {i = \ lfloor {\ tfrac {n} {2}} \ rfloor +1} ^ {n} {\ binom {n} {i}} p ^ {i} (1-p) ^ {ni}.}

$\Pr \left[X>{n \ over 2} \ right] = \ sum _ {i = \ lfloor {\ tfrac {n} {2}} \ rfloor +1} ^ {n} {\ binom {n} {i}} p ^ {i} (1-p) ^ {ni}.$

Нижняя граница этой вероятности может быть рассчитана на основе неравенства Чернова:

Pr [X>N 2] ≥ 1 - e - 1 2 pn (p - 1 2) 2. {\ Displaystyle \ Pr \ left [X>{n \ over 2} \ right] \ geq 1-e ^ {- {\ frac {1} {2p}} n \ left (p - {\ frac {1} {2}} \ right) ^ {2}}.}

$\Pr \left[X>{n \ over 2 } \ right] \ geq 1-e ^ {- {\ frac {1} {2p}} n \ left (p - {\ frac {1} {2}} \ right) ^ {2}}.$

Действительно, замечая, что μ = np, мы получаем мультипликативную форму оценки Чернова (см. ниже или следствие 13.3 в классе Синклера примечания),

Pr (X ≤ ⌊ n 2 ⌋) = Pr (X ≤ (1 - (1 - 1 2 p)) μ) ≤ e - μ 2 (1 - 1 2 p) 2 = e - n 2 п (п - 1 2) 2 {\ Displaystyle {\ begin {align} \ Pr \ left (X \ leq \ left \ lfloor {\ tfrac {n} {2}} \ right \ rfloor \ right) = \ Pr \ left (X \ leq \ left (1- \ left (1 - {\ tfrac {1} {2p}} \ right) \ right) \ mu \ right) \\ \ leq e ^ {- {\ frac {\ mu} {2}} \ left (1 - {\ frac {1} {2p}} \ right) ^ {2}} \\ = e ^ {- {\ frac {n} {2p}} \ left (p - {\ frac {1} {2}} \ right) ^ {2}} \ end {align}}}

{\ displaystyle {\ begin {aligne d} \ Pr \ left (X \ leq \ left \ lfloor {\ tfrac {n} {2}} \ right \ rfloor \ right) = \ Pr \ left (X \ leq \ left (1- \ left (1 - {\ tfrac {1} {2p}} \ right) \ right) \ mu \ right) \\ \ leq e ^ {- {\ frac {\ mu} {2}} \ left (1 - {\ frac {1} {2p}} \ right) ^ {2}} \\ = e ^ {- {\ frac {n} {2p}} \ left (p - {\ frac {1} {2}} \ right) ^ {2}} \ конец {выравнивается}}}

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

Аддитивная форма (абсолютная ошибка)

Следующая теорема принадлежит Василию Хёффдингу и поэтому называется теоремой Чернова – Хёффдинга.

Теорема Чернова – Хёффдинга. Предположим, что X 1,..., X n - iid случайные величины, принимающие значения в {0, 1}. Пусть p = E [X] / n и ε>0. Тогда

Pr (1 n ∑ X i ≥ p + ε) ≤ ((pp + ε) p + ε (1 - p 1 - p - ε) 1 - p - ε) n = e - D (p + ε ∥ p) n Pr (1 n ∑ X i ≤ p - ε) ≤ ((pp - ε) p - ε (1 - p 1 - p + ε) 1 - p + ε) n = e - D (p - ε ∥ п) N {\ Displaystyle {\ begin {align} \ Pr \ left ({\ frac {1} {n}} \ sum X_ {i} \ geq p + \ varepsilon \ right) \ leq \ left (\ left ({\ frac {p} {p + \ varepsilon}} \ right) ^ {p + \ varepsilon} {\ left ({\ frac {1-p} {1-p- \ varepsilon}} \ right)} ^ { 1-p- \ varepsilon} \ right) ^ {n} = e ^ {- D (p + \ varepsilon \ parallel p) n} \\\ Pr \ left ({\ frac {1} {n}} \ sum X_ {i} \ leq p- \ varepsilon \ right) \ leq \ left (\ left ({\ frac {p} {p- \ varepsilon}} \ right) ^ {p- \ varepsilon} {\ left ({\ frac {1-p} {1-p + \ varepsilon}} \ right)} ^ {1-p + \ varepsilon} \ right) ^ {n} = e ^ {- D (p- \ varepsilon \ parallel p) n } \ end {align}}}

{\ displaystyle {\ begin {align} \ Pr \ left ({\ frac {1} {n}} \ sum X_ {i} \ geq p + \ varepsilon \ right) \ le q \ left (\ left ({\ frac {p} {p + \ varepsilon}} \ right) ^ {p + \ varepsilon} {\ left ({\ frac {1-p} {1-p- \ varepsilon}} \ right)} ^ {1-p- \ varepsilon} \ right) ^ {n} = e ^ {- D (p + \ varepsilon \ parallel p) n} \\\ Pr \ left ({\ frac {1} { n}} \ sum X_ {i} \ leq p- \ varepsilon \ right) \ leq \ left (\ left ({\ frac {p} {p- \ varepsilon}} \ right) ^ {p- \ varepsilon} { \ left ({\ frac {1-p} {1-p + \ varepsilon}} \ right)} ^ {1-p + \ varepsilon} \ right) ^ {n} = e ^ {- D (p- \ varepsilon \ parallel p) n} \ end {align}}}

где

D (x ∥ y) = x ln ⁡ xy + (1 - x) ln ⁡ (1 - x 1 - y) {\ displaystyle D (x \ parallel y) = x \ ln {\ frac {x} {y}} + (1-x) \ ln \ left ({\ frac {1-x} {1-y}} \ right)}

D(x\parallel y)=x\ln {\frac {x}{y}}+(1-x)\ln \left({\frac {1-x}{1-y}}\right)

- это Расхождение Кульбака – Лейблера между распределенным Бернулли случайные величины с параметрами x и y соответственно. Если p ≥ 1/2, то

Pr (∑ X i>n p + x) ≤ exp ⁡ (- x 2 2 n p (1 - p)). {\ displaystyle \ Pr \ left (\ sum X_ {i}>np + x \ right) \ leq \ exp \ left (- {\ frac {x ^ {2}} {2np (1-p)}} \ right).}

\Pr \left(\sum X_{i}>np + x \ right) \ leq \ exp \ left (- {\ frac {x ^ {2}} {2np (1-p)}} \ right).

Расслабление теоремы дает более простую оценку D (p + ε || p) ≥ 2ε, что следует из выпуклости D (p + ε || p) и того факта, что

d 2 d ε 2 D (p + ε ∥ п) знак равно 1 (п + ε) (1 - п - ε) ≥ 4 знак равно d 2 d ε 2 (2 ε 2). {\ Displaystyle {\ frac {d ^ {2}} {d \ varepsilon ^ { 2}}} D (p + \ varepsilon \ parallel p) = {\ frac {1} {(p + \ varepsilon) (1-p- \ varepsilon)}} \ geq 4 = {\ frac {d ^ {2}} {d \ varepsilon ^ {2}}} (2 \ varepsilon ^ {2}).}

{\frac {d^{2}}{d\varepsilon ^{2}}}D(p+\varepsilon \parallel p)={\frac {1}{(p+\varepsilon)(1-p-\varepsilon)}}\geq 4={\frac {d^{2}}{d\varepsilon ^{2}}}(2\varepsilon ^{2}).

Этот результат является частным случаем неравенства Хёффдинга. Иногда границы

D (( 1 + x) p ∥ p) ≥ 1 4 x 2 p, - 1 2 ≤ x ≤ 1 2, D (x ∥ y) ≥ 3 (x - y) 2 2 (2 y + x), D (x ∥ y) ≥ (x - y) 2 2 y, x ≤ y, D (x ∥ y) ≥ (x - y) 2 2 Икс, Икс ≥ Y {\ Displaystyle {\ begin {align} D ((1 + x) p \ parallel p) \ geq {\ frac {1} {4}} x ^ {2} p, {- {\ tfrac {1} {2}}} \ leq x \ leq {\ tfrac {1} {2}}, \\ [6pt] D (x \ parallel y) \ geq {\ frac {3 ( xy) ^ {2}} {2 (2y + x)}}, \\ [6pt] D (x \ parallel y) \ geq {\ frac {(xy) ^ {2}} {2y}}, x \ leq y, \\ [6pt] D (x \ parallel y) \ geq {\ frac {(xy) ^ {2}} {2x}}, x \ geq y \ end {align}}}

{\ displaystyle {\ begin {align} D ((1 + x) p \ parallel p) \ geq {\ frac {1} {4} } x ^ {2} p, {- {\ tfrac {1} {2}}} \ leq x \ leq {\ tfrac {1} {2}}, \\ [6pt] D (x \ parallel y) \ geq {\ frac {3 (xy) ^ {2}} {2 (2y + x)}}, \\ [6pt] D (x \ parallel y) \ geq {\ frac {(xy) ^ {2} }{2y}},x\leq y,\\[6pt]D(x\parallel y)\geq {\frac {(xy)^{2}}{2x}},x\geq y\end{aligned }}}

, которые сильнее для p < 1/8, are also used.

Мультипликативная форма (относительная ошибка)

Мультипликативная граница Чернова. Предположим, что X 1,..., X n независимых случайных величин, принимающих значения в {0, 1}. Пусть X обозначает их сумму, а μ = E [X] обозначает ожидаемое значение суммы. Тогда для любого δ>0

Pr (X>(1 + δ) μ) < ( e δ ( 1 + δ) 1 + δ) μ. {\displaystyle \Pr(X>(1+ \ delta) \ mu) <\left({\frac {e^{\delta }}{(1+\delta)^{1+\delta }}}\right)^{\mu }.}

\Pr(X>(1+ \ delta) \ mu) <\left({\frac {e^{\delta }}{(1+\delta)^{1+\delta }}}\right)^{\mu }.

Аналогичное Стратегия доказательства может использоваться, чтобы показать, что

Pr (X < ( 1 − δ) μ) < ( e − δ ( 1 − δ) 1 − δ) μ. {\displaystyle \Pr(X<(1-\delta)\mu)<\left({\frac {e^{-\delta }}{(1-\delta)^{1-\delta }}}\right)^{\mu }.}

{\ displaystyle \ Pr ( X <(1- \ delta) \ mu) <\ left ({\ frac {e ^ {- \ delta}} {(1- \ delta) ^ {1- \ delta}}} \ right) ^ {\ mu }.}

Вышеупомянутая формула часто бывает громоздкой на практике, поэтому часто используются следующие более свободные, но более удобные границы:

Pr (X ≤ (1 - δ) μ) ≤ е - δ 2 μ 2, 0 ≤ δ ≤ 1, {\ displaystyle \ Pr (X \ leq (1- \ delta) \ mu) \ leq e ^ {- {\ frac {\ delta ^ {2} \ mu} {2}}}, \ qquad 0 \ leq \ delta \ leq 1,}

{ \ Displaystyle \ Pr (Икс \ Leq (1- \ delta) \ mu) \ Leq e ^ {- {\ frac {\ delta ^ {2} \ mu} {2}}}, \ qquad 0 \ leq \ delta \ leq 1,}

Pr (X ≥ (1 + δ) μ) ≤ e - δ 2 μ 2 + δ, 0 ≤ δ, { \ Displaystyle \ Pr (Икс \ geq (1+ \ delta) \ mu) \ leq e ^ {- {\ frac {\ delta ^ {2} \ mu} {2+ \ delta}}}, \ qquad 0 \ leq \ delta,}

{\ displaystyle \ Pr (X \ geq (1+ \ delta) \ mu) \ leq e ^ {- {\ frac {\ delta ^ {2} \ mu} {2+ \ delta}}}, \ qquad 0 \ leq \ delta,}

, которые следуют из неравенства $2 δ 2 + δ ≤ log ⁡ (1 + δ) {\ displaystyle {\ frac {2 \ delta} {2+ \ delta}} \ leq \ log (1+ \ delta)}$ ${\frac {2\delta }{2+\delta }}\leq \log(1+\delta)$ из списка логарифмических неравенств. Или, что еще хуже:

Pr (X ≥ (1 + δ) μ) ≤ e - δ 2 μ 3, 0 ≤ δ ≤ 1. {\ Displaystyle \ Pr (Икс \ geq (1+ \ delta) \ mu) \ leq e ^ {- {\ frac {\ delta ^ {2} \ mu} {3}}}, \ qquad 0 \ leq \ delta \ leq 1.}

\Pr(X\geq (1+\delta)\mu)\leq e^{-{\frac {\delta ^{2}\mu }{3}} },\qquad 0\leq \delta \leq 1.

Аппликат ion

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

Проблема балансировки множеств возникает при разработке статистических экспериментов. Обычно при разработке статистического эксперимента, учитывая особенности каждого участника эксперимента, нам необходимо знать, как разделить участников на 2 непересекающиеся группы, чтобы каждая характеристика была как можно более сбалансирована между двумя группами. Обратитесь к разделу книги для получения дополнительной информации о проблеме.

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

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

Границы Чернова могут быть эффективно использованы для оценки «уровня устойчивости» приложения / алгоритма путем исследования его пространства возмущений с рандомизацией. Использование границы Чернова позволяет отказаться от гипотезы сильных и в большинстве случаев нереалистичных малых возмущений (величина возмущения мала). Уровень устойчивости, в свою очередь, может использоваться либо для подтверждения или отклонения конкретного алгоритмического выбора, аппаратной реализации или соответствия решения, структурные параметры которого зависят от неопределенностей.

Граница матрицы

Рудольф Алсведе и Андреас Винтер ввели границу Чернова для матричнозначных случайных величин. Следующий вариант неравенства можно найти в работе Троппа.

Пусть M 1,..., M t - независимые матричные случайные величины, такие как что $M i ∈ C d 1 × d 2 {\ displaystyle M_ {i} \ in \ mathbb {C} ^ {d_ {1} \ times d_ {2}}}$ $M_{i}\in \mathbb {C} ^{d_{1}\times d_{2}}$ и $E [M i] = 0 {\ displaystyle \ mathbb {E} [M_ {i}] = 0}$ $\mathbb {E} [M_{i}]=0$ . Обозначим через $‖ M ‖ {\ displaystyle \ lVert M \ rVert}$ ${\ displaystyle \ lVert M \ rVert}$ операторную норму матрицы $M {\ displaystyle M}$ $M$ . Если $‖ M я ‖ ≤ γ {\ displaystyle \ lVert M_ {i} \ rVert \ leq \ gamma}$ , ${\ displaystyle \ lVert M_ {i} \ rVert \ leq \ gamma}$ почти наверняка выполняется для всех $i ∈ {1,…, t} { \ displaystyle i \ in \ {1, \ ldots, t \}}$ ${\ displaystyle i \ in \ {1, \ ldots, t \}}$ , затем для каждого ε>0

Pr (‖ 1 t ∑ i = 1 t M i ‖>ε) ≤ ( d 1 + d 2) ехр ⁡ (- 3 ε 2 t 8 γ 2). {\ displaystyle \ Pr \ left (\ left \ | {\ frac {1} {t}} \ sum _ {i = 1} ^ {t} M_ {i} \ right \ |>\ varepsilon \ right) \ leq (d_ {1} + d_ {2}) \ exp \ left (- {\ frac {3 \ varepsilon ^ {2} t} {8 \ gamma ^ {2}}} \ right).}

\Pr \left(\left\|{\frac {1}{t}}\sum _{i=1}^{t}M_{i}\right\|>\ varepsilon \ right) \ leq (d_ {1} + d_ {2}) \ exp \ left (- {\ frac {3 \ varepsilon ^ {2} t} {8 \ gamma ^ {2}}} \ right).

Обратите внимание, что в чтобы сделать вывод о том, что отклонение от 0 с большой вероятностью ограничено ε, нам нужно выбрать количество выборок $t {\ displaystyle t}$ $t$ , пропорциональное логарифму $d 1 + d 2 {\ displaystyle d_ {1} + d_ {2}}$ $d_{1}+d_{2}$ . В общем, к сожалению, зависимость от $log ⁡ (min (d 1, d 2)) {\ displaystyle \ log (\ min (d_ {1}, d_ {2}))}$ ${\ displaystyle \ log (\ min (d_ {1}, d_ {2}))}$ неизбежно: возьмем, например, диагональную матрицу случайных знаков размерности $d × d {\ displaystyle d \ times d}$ ${\ displaystyle d \ times d}$ . Операторная норма суммы t независимых выборок предварительно То есть максимальное отклонение среди d независимых случайных блужданий длины t. Чтобы достичь фиксированной границы максимального отклонения с постоянной вероятностью, легко увидеть, что t должно логарифмически расти с d в этом сценарии.

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

Теорема без зависимости от размеров

Пусть 0 < ε < 1 and M be a random symmetric real matrix with $‖ E [M] ‖ ≤ 1 {\ displaystyle \ | \ mathrm {E} [M] \ | \ leq 1 }$ ${\ displaystyle \ | \ mathrm {E} [M] \ | \ leq 1}$ и $‖ M ‖ ≤ γ {\ displaystyle \ | M \ | \ leq \ gamma}$ ${\ displaystyle \ | M \ | \ leq \ gamma}$ почти наверняка. Предположим, что каждый элемент на носителе M имеет ранг не более r. Положим

t = Ω (γ log ⁡ (γ / ε 2) ε 2). {\ displaystyle t = \ Omega \ left ({\ frac {\ gamma \ log (\ gamma / \ varepsilon ^ {2})} {\ varepsilon ^ {2}}} \ right).}

t=\Omega \left({\fra c {\gamma \log(\gamma /\varepsilon ^{2})}{\varepsilon ^{2}}}\right).

Если $r ≤ t {\ displaystyle r \ leq t}$ $r \ leq t$ почти наверняка, тогда

Pr (‖ 1 t ∑ i = 1 t M i - E [M] ‖>ε) ≤ 1 poly (T) {\ Displaystyle \ Pr \ left (\ left \ | {\ frac {1} {t}} \ sum _ {i = 1} ^ {t} M_ {i} - \ mathrm {E} [M] \ right \ |>\ varepsilon \ right) \ leq {\ frac {1} {\ mathbf {poly} (t)}}}

\Pr \left(\left\|{\frac {1}{t}}\sum _{i=1}^{t}M_{i}-\mathrm {E} [M]\right\|>\ varepsilon \ right) \ leq {\ frac {1} { \ mathbf {poly} (t)}}

где M 1,..., M t - iid-копии M.

Теорема с матрицами, которые не являются полностью случайными

Гарг, Ли, Сонг и Шривастава доказали оценку типа Чернова для сумм матричнозначных случайных величин, выбранных с помощью случайного блуждания на расширителе, подтверждая гипотезу Вигдерсона и Сяо.

Кинг и Сонг доказал оценку типа Чернова для su мс лапласовской матрицы случайных остовных деревьев.

Вариант выборки

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

Предположим, что есть общая популяция A и подгруппа B⊆A. Отметьте относительный размер подгруппы населения (| B | / | A |) с помощью r.

Предположим, мы выбрали целое число k и случайную выборку S⊂A размера k. Отметьте относительный размер подгруппы в выборке (| B∩S | / | S |) как r S.

Затем для каждой фракции d∈ [0,1]:

P r (r S < ( 1 − d) ⋅ r) < exp ⁡ ( − r ⋅ d 2 ⋅ k / 2) {\displaystyle \mathrm {Pr} \left(r_{S}<(1-d)\cdot r\right)<\exp \left(-r\cdot d^{2}\cdot k/2\right)}

\mathrm {Pr} \left(r_{S}<(1-d)\cdot r\right)<\exp \left(-r\cdot d^{2}\cdot k/2\right)

В частности, если B составляет большинство в A (т.е. r>0,5), мы можем ограничить вероятность того, что B останется большинством в S (r S>0,5), взяв: d = 1 - 1 / (2 р):

п р (р S>0,5)>1 - ехр ⁡ (- р ⋅ (1 - 1 2 р) 2 ⋅ к / 2) {\ displaystyle \ mathrm {Pr} \ left ( r_ {S}>0,5 \ right)>1- \ exp \ left (-r \ cdot \ left (1 - {\ frac {1} {2r}} \ right) ^ {2} \ cdot k / 2 \ right)}

\mathrm {Pr} \left(r_{S}>0,5 \ right)>1- \ exp \ left (-r \ cdot \ left (1 - {\ frac {1} {2r}} \ right) ^ {2} \ cdot k / 2 \ right)

Эта граница конечно, совсем не плотно. Например, когда r = 0,5, мы получаем тривиальную оценку Prob>0.

Доказательства

Теорема Чернова – Хёффдинга (аддитивная форма)

Пусть q = p + ε. Взяв a = nq в (1), получим:

Pr (1 n ∑ X i ≥ q) ≤ inf t>0 E [∏ е т X я] е т н д = инф т>0 (е [е т х я] е т д) п. {\ displaystyle \ Pr \ left ({\ frac {1} {n}} \ sum X_ {i} \ geq q \ right) \ leq \ inf _ {t>0} {\ frac {E \ left [\ prod e ^ {tX_ {i}} \ right]} {e ^ {tnq}}} = \ inf _ {t>0} \ left ({\ frac {E \ left [e ^ {tX_ {i}} \ right ]} {e ^ {tq}}} \ right) ^ {n}.}

\Pr \left({\frac {1}{n}}\sum X_{i}\geq q\right)\leq \inf _{t>0} {\ frac {E \ left [\ prod e ^ {tX_ {i}} \ right]} { e ^ {tnq}}} = \ inf _ {t>0} \ left ({\ frac {E \ left [e ^ {tX_ {i}} \ right]} {e ^ {tq}}} \ right) ^ {n}.

Сейчас, зная, что Pr (X i = 1) = p, Pr (X i = 0) = 1 - p, мы имеем

(E [et X i] etq) N = (ПЭТ + (1 - p) etq) n = (pe (1 - q) t + (1 - p) e - qt) n. {\ displaystyle \ left ({\ frac {\ mathrm {E}) \ left [e ^ {tX_ {i}} \ right]} {e ^ {tq}}} \ right) ^ {n} = \ left ({\ frac {pe ^ {t} + (1-p)} {e ^ {tq}}} \ right) ^ {n} = \ left (pe ^ {(1-q) t} + (1-p) e ^ {- qt} \ right) ^ {n}.}

\ left ({\ frac {\ mathrm {E} \ left [e ^ {tX_ {i}} \ right]} {e ^ { tq}}} \ right) ^ {n} = \ left ({\ frac {pe ^ {t} + (1-p)} {e ^ {tq}}} \ right) ^ {n} = \ left ( pe ^ {(1-q) t} + (1-p) e ^ {- qt} \ right) ^ {n}.

Следовательно, мы можем легко вычислить нижнюю грань, используя исчисление:

ddt (pe (1 - q) t + (1 - p) e - qt) = (1 - q) pe (1 - q) t - q ( 1 - p) е - qt {\ displaystyle {\ frac {d} {dt}} \ left (pe ^ {(1-q) t} + (1-p) e ^ {- qt} \ right) = ( 1-q) pe ^ {(1-q) t} -q (1-p) e ^ {- qt}}

{\frac {d}{dt}}\left(pe^{(1-q)t}+(1-p)e^{-qt}\right)=(1-q)pe^{(1-q)t}-q(1-p)e^{-qt}

Обнуляя уравнение и решая, мы имеем

(1 - q) pe (1 - q) t знак равно q (1 - p) e - qt (1 - q) pet = q (1 - p) {\ displaystyle {\ begin {align} (1-q) pe ^ {(1-q) t} = q (1-p) e ^ {- qt} \\ (1-q) pe ^ {t} = q (1-p) \ end {align}}}

{\ begin {align} (1-q) pe ^ {(1 -q) t} = q (1-p) e ^ {- qt} \\ (1-q) pe ^ {t} = q (1-p) \ end {align}}

так, чтобы

et = (1 - p) q (1 - q) p. {\ displaystyle e ^ {t} = {\ frac {(1-p) q} {(1-q) p}}.}

e ^ {t} = {\ frac {(1-p) q} { (1-q) p}}.

Таким образом,

t = log ⁡ ((1 - p) q (1 - q) п). {\ displaystyle t = \ log \ left ({\ frac {(1-p) q} {(1-q) p}} \ right).}

t=\log \left({\frac {(1- p)q}{(1-q)p}}\right).

Поскольку q = p + ε>p, мы видим, что t>0, поэтому наша оценка на t выполнена. Решив для t, мы можем вернуться к приведенным выше уравнениям и найти, что

log ⁡ (pe (1 - q) t + (1 - p) e - qt) = log ⁡ (e - qt (1 - p + пет)) = журнал ⁡ (e - q журнал ⁡ ((1 - p) q (1 - q) p)) + журнал ⁡ (1 - p + pe log ⁡ (1 - p 1 - q) e журнал ⁡ qp) = - q log ⁡ 1 - p 1 - q - q log ⁡ qp + log ⁡ (1 - p + p (1 - p 1 - q) qp) = - q log ⁡ 1 - p 1 - q - q журнал ⁡ qp + журнал ⁡ ((1 - p) (1 - q) 1 - q + (1 - p) q 1 - q) = - q журнал ⁡ qp + (- q журнал ⁡ 1 - p 1 - q + журнал ⁡ 1 - p 1 - q) = - q журнал ⁡ qp + (1 - q) журнал ⁡ 1 - p 1 - q = - D (q ∥ p). {\ Displaystyle {\ begin {align} \ log \ left (pe ^ {(1-q) t} + (1-p) e ^ {- qt} \ right) = \ log \ left (e ^ {- qt} (1-p + pe ^ {t}) \ right) \\ = \ log \ left (e ^ {- q \ log \ left ({\ frac {(1-p) q} {(1- q) p}} \ right)} \ right) + \ log \ left (1-p + pe ^ {\ log \ left ({\ frac {1-p} {1-q}} \ right)} e ^ {\ log {\ frac {q} {p}}} \ right) \\ = - q \ log {\ frac {1-p} {1-q}} - q \ log {\ frac {q} { p}} + \ log \ left (1-p + p \ left ({\ frac {1-p} {1-q}} \ right) {\ frac {q} {p}} \ right) \\ = -q \ log {\ frac {1-p} {1-q}} - q \ log {\ frac {q} {p}} + \ log \ left ({\ frac {(1-p) (1 -q)} {1-q}} + {\ frac {(1-p) q} {1-q}} \ right) \\ = - q \ log {\ frac {q} {p}} + \ left (-q \ log {\ frac {1-p} {1-q}} + \ log {\ frac {1-p} {1-q}} \ right) \\ = - q \ log { \ frac {q} {p}} + (1-q) \ log {\ frac {1-p} {1-q}} \\ = - D (q \ parallel p). \ end {выравнивается}} }

{\ displaystyle {\ begin {align} \ log \ left (pe ^ {(1- q) t} + (1-p) e ^ {- qt} \ right) = \ log \ left (e ^ {- qt} (1-p + pe ^ {t}) \ right) \\ = \ log \ left (e ^ {- q \ log \ left ({\ frac {(1-p) q} {(1-q) p}} \ right)} \ right) + \ log \ left (1- p + pe ^ {\ log \ left ({\ frac {1-p} {1-q}} \ right)} e ^ {\ log {\ frac {q} {p}}} \ right) \\ = -q \ log {\ frac {1-p} {1-q}} - q \ log {\ frac {q} {p}} + \ log \ left (1-p + p \ left ({\ frac {1-p} {1-q }} \ right) {\ frac {q} {p}} \ right) \\ = - q \ log {\ frac {1-p} {1-q}} - q \ log {\ frac {q} {p}} + \ log \ left ({\ frac {(1-p) (1-q)} {1-q}} + {\ frac {(1-p) q} {1-q}} \ справа) \\ = - q \ log {\ frac {q} {p}} + \ left (-q \ log {\ frac {1-p} {1-q}} + \ log {\ frac {1 -p} {1-q}} \ right) \\ = - q \ log {\ frac {q} {p}} + (1-q) \ log {\ frac {1-p} {1-q }} \\ = - D (q \ parallel p). \ End {align}}}

Теперь у нас есть желаемый результат:

Pr (1 n ∑ X i ≥ p + ε) ≤ e - D (p + ε ∥ p) n. {\ displaystyle \ Pr \ left ({\ tfrac {1} {n}} \ sum X_ {i} \ geq p + \ varepsilon \ right) \ leq e ^ {- D (p + \ varepsilon \ parallel p) n}. }

{\ displaystyle \ Pr \ left ({\ tfrac {1} {n}} \ sum X_ {i} \ geq p + \ varepsilon \ right) \ leq е ^ {- D (п + \ varepsilon \ parallel p) n}.}

Чтобы завершить доказательство для симметричного случая, мы просто определяем случайную величину Y i = 1 - X i, применяем то же доказательство и вставляем его в нашу оценку.

Мультипликативная форма

Установите Pr (X i = 1) = p i. Согласно (1),

Pr (X>(1 + δ) μ) ≤ inf t>0 E ⁡ [∏ i = 1 n exp ⁡ (t X i)] exp ⁡ (t (1 + δ) μ) = inf t>0 ∏ i = 1 n E ⁡ [et X i] exp ⁡ (t (1 + δ) μ) = inf t>0 ∏ i = 1 n [piet + (1 - pi) ] ехр ⁡ (T (1 + δ) μ) {\ Displaystyle {\ begin {align} \ Pr (X>(1+ \ delta) \ mu) \ Leq \ Inf _ {t>0} {\ frac { \ operatorname {E} \ left [\ prod _ {i = 1} ^ {n} \ exp (tX_ {i}) \ right]} {\ exp (t (1+ \ delta) \ mu)}} \\ [4pt] = \ inf _ {t>0} {\ frac {\ prod _ {i = 1} ^ {n} \ operatorname {E} \ left [e ^ {tX_ {i}} \ right]} { \ exp (t (1+ \ delta) \ mu)}} \\ [4pt] = \ inf _ {t>0} {\ frac {\ prod _ {i = 1} ^ {n} \ left [p_ {i} e ^ {t} + (1-p_ {i}) \ right]} {\ exp (t (1+ \ delta) \ mu)}} \ end {align}}}

{\begin{aligned}\Pr(X>(1+ \ delta) \ mu) \ leq \ inf _ {t>0} {\ frac {\ operatorname {E} \ left [\ prod _ {i = 1} ^ {n} \ exp (tX_ {i }) \ right]} {\ exp (t (1+ \ delta) \ mu)}} \\ [4pt] = \ inf _ {t>0} {\ frac {\ prod _ {i = 1} ^ {n} \ operatorname {E} \ left [e ^ {tX_ {i}} \ right]} {\ exp (t (1+ \ delta) \ mu)}} \\ [4pt] = \ inf _ { t>0} {\ frac {\ prod _ {i = 1} ^ {n} \ left [p_ {i} e ^ {t} + (1-p_ {i}) \ right]} {\ exp (t (1+ \ delta) \ mu)}} \ end {ali gned}}

Третий строка выше следует, потому что $et X i {\ displaystyle e ^ {tX_ {i}}}$ $e^{tX_{i}}$ принимает значение e с вероятностью p i и значение 1 с вероятностью 1 - р и. Это идентично вычислению выше в доказательстве теоремы для аддитивной формы (абсолютная ошибка).

Переписывание $piet + (1 - pi) {\ displaystyle p_ {i} e ^ {t} + (1-p_ {i})}$ $p_ {i} e ^ {t} + (1-p_ {i})$ как $pi (et - 1) + 1 {\ displaystyle p_ {i} (e ^ {t} -1) +1}$ $p_{i}(e^{t}-1)+1$ и вспоминая, что $1 + x ≤ ex {\ displaystyle 1 + x \ leq e ^ {x}}$ $1+x\leq e^{x}$ (со строгим неравенством, если x>0), мы устанавливаем $x = пи (эт - 1) {\ Displaystyle х = р_ {я} (е ^ {т} -1)}$ $x = p_ {i} (e ^ {t } -1)$ . Тот же результат может быть получен путем прямой замены a в уравнении для оценки Чернова на (1 + δ) μ.

Таким образом,

Pr (X>(1 + δ) μ) < ∏ i = 1 n exp ⁡ ( p i ( e t − 1)) exp ⁡ ( t ( 1 + δ) μ) = exp ⁡ ( ( e t − 1) ∑ i = 1 n p i) exp ⁡ ( t ( 1 + δ) μ) = exp ⁡ ( ( e t − 1) μ) exp ⁡ ( t ( 1 + δ) μ). {\displaystyle \Pr(X>(1+ \ delta) \ mu) <{\frac {\prod _{i=1}^{n}\exp(p_{i}(e^{t}-1))}{\exp(t(1+\delta)\mu)}}={\frac {\exp \left((e^{t}-1)\sum _{i=1}^{n}p_{i}\right)}{\exp(t(1+\delta)\mu)}}={\frac {\exp((e^{t}-1)\mu)}{\exp(t(1+\delta)\mu)}}.}

\Pr(X>(1+ \ delta) \ mu) <{\frac {\prod _{i=1}^{n}\exp(p_{i}(e^{t}-1))}{\exp(t(1+\delta)\mu)}}={\frac {\exp \left((e^{t}-1)\sum _{i=1}^{n}p_{i}\right)}{\exp(t(1+\delta)\mu)}}={\frac {\exp((e^{t}-1)\mu)}{\exp(t(1+\delta)\mu)}}.

Если мы просто установим t = log (1 + δ) так, чтобы t>0 вместо δ>0, мы можем заменить и найти

exp ⁡ ((et - 1) μ) exp ⁡ (t (1 + δ) μ) = exp ⁡ ((1 + δ - 1) μ) (1 + δ) (1 + δ) μ = [е δ (1 + δ) (1 + δ)] μ {\ displaystyle {\ frac {\ exp ((e ^ {t} -1) \ mu)} {\ exp (t (1+ \ delta) \ mu)}} = {\ frac {\ exp ((1+ \ delta -1) \ mu)} {(1+ \ delta) ^ {(1+ \ delta) \ mu}}} = \ left [{\ frac {e ^ {\ delta}} {(1+ \ delta) ^ {(1+ \ delta)}}} \ right] ^ {\ mu}}

{\ frac {\ exp ((e ^ {t} - 1) \ mu)} {\ exp (t (1+ \ delta) \ mu)}} = {\ frac {\ exp ((1+ \ delta -1) \ mu)} {(1+ \ delta) ^ {(1+ \ delta) \ mu}}} = \ left [{\ frac {e ^ {\ delta}} {(1+ \ delta) ^ {(1+ \ delta)}}} \ right] ^ { \ mu}

Это доказывает желаемый результат.

См. Также

Неравенство концентрации - сводка хвостовых границ случайных величин.
Энтропическое значение в условиях риска

Ссылки

Дополнительная литература

Чернофф, Х. (1952). «Мера асимптотической эффективности для проверки гипотезы на основе суммы наблюдений». Анналы математической статистики. 23(4): 493–507. doi : 10.1214 / aoms / 1177729330. JSTOR 2236576. MR 0057518. Zbl 0048.11804.
Чернов, Х. (1981). «Примечание о неравенстве, связанном с нормальным распределением». Анналы вероятности. 9(3): 533–535. doi : 10.1214 / aop / 1176994428. JSTOR 2243541. MR 0614640. Zbl 0457.60014.
Hagerup, T.; Руб, К. (1990). "Экскурсия по границам Чернова". Письма об обработке информации. 33(6): 305. doi : 10.1016 / 0020-0190 (90) 90214-I.
Нильсен, Ф. (2011). "Информация Чернова экспоненциальных семейств". arXiv :1102.2684 [cs.IT provided.