Неравенство Адзума - Википедия - Azumas inequality

В теория вероятности, то Неравенство Адзумы – Хёффдинга (названный в честь Кадзуоки Адзума и Василий Хёффдинг ) дает результат концентрации для значений мартингалы которые имеют ограниченные различия.

Предполагать { Икс_k : k = 0, 1, 2, 3, ...} является мартингейл (или же супер-мартингейл ) и

${ Displaystyle | X_ {k} -X_ {k-1} | leq c_ {k}, ,}$

почти наверняка. Тогда для всех натуральных чисел N и все положительное реалы ${ displaystyle epsilon}$,

${ displaystyle { text {P}} (X_ {N} -X_ {0} geq epsilon) leq exp left ({- epsilon ^ {2} over 2 sum _ {k = 1 } ^ {N} c_ {k} ^ {2}} right).}$

И симметрично (когда Икс_k является субмартингейлом):

${ displaystyle { text {P}} (X_ {N} -X_ {0} leq - epsilon) leq exp left ({- epsilon ^ {2} over 2 sum _ {k = 1} ^ {N} c_ {k} ^ {2}} right).}$

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

${ displaystyle { text {P}} (| X_ {N} -X_ {0} | geq epsilon) leq 2 exp left ({- epsilon ^ {2} over 2 sum _ { k = 1} ^ {N} c_ {k} ^ {2}} right).}$

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

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

Общая форма неравенства Адзумы

Ограничение неравенства ванильной Адзумы

Обратите внимание, что ванильное неравенство Адзумы требует симметричных оценок приращений мартингала, т.е. ${ displaystyle -c_ {t} leq X_ {t} -X_ {t-1} leq c_ {t}}$. Итак, если известная граница асимметрична, например ${ displaystyle a_ {t} leq X_ {t} -X_ {t-1} leq b_ {t}}$, чтобы использовать неравенство Адзумы, нужно выбрать ${ displaystyle c_ {t} = max (| a_ {t} |, | b_ {t} |)}$ что может быть пустой тратой информации об ограниченности ${ displaystyle X_ {t} -X_ {t-1}}$. Однако эта проблема может быть решена, и можно получить более жесткую оценку вероятности с помощью следующей общей формы неравенства Адзумы.

Заявление

Позволять ${ Displaystyle left {X_ {0}, X_ {1}, cdots right }}$ быть мартингейлом (или супермартингейлом) относительно фильтрация ${ displaystyle left {{ mathcal {F}} _ {0}, { mathcal {F}} _ {1}, cdots right }}$. Предположим, есть предсказуемые процессы ${ Displaystyle left {A_ {0}, A_ {1}, cdots right }}$ и ${ displaystyle left {B_ {0}, B_ {1}, dots right }}$ относительно ${ displaystyle left {{ mathcal {F}} _ {0}, { mathcal {F}} _ {1}, cdots right }}$, т.е. для всех ${ displaystyle t}$, ${ displaystyle A_ {t}, B_ {t}}$ находятся ${ Displaystyle { mathcal {F}} _ {т-1}}$-измеримый, а константы ${ Displaystyle 0$ такой, что

${ displaystyle A_ {t} leq X_ {t} -X_ {t-1} leq B_ {t} quad { text {and}} quad B_ {t} -A_ {t} leq c_ { t}}$

почти наверняка. Тогда для всех ${ displaystyle epsilon> 0}$,

${ displaystyle { text {P}} (X_ {n} -X_ {0} geq epsilon) leq exp left (- { frac {2 epsilon ^ {2}} { sum _ { t = 1} ^ {n} c_ {t} ^ {2}}} right).}$

Поскольку субмартингейл - это супермартингейл с переставленными знаками, мы имеем вместо ${ displaystyle left {X_ {0}, X_ {1}, dots right }}$ мартингейл (или субмартингейл),

${ displaystyle { text {P}} (X_ {n} -X_ {0} leq - epsilon) leq exp left (- { frac {2 epsilon ^ {2}} { sum _ {t = 1} ^ {n} c_ {t} ^ {2}}} right).}$

Если ${ displaystyle left {X_ {0}, X_ {1}, dots right }}$ является мартингалом, поскольку он является одновременно супермартингалом и субмартингалом, применяя объединение, связанное с двумя приведенными выше неравенствами, мы можем получить двустороннюю оценку:

${ displaystyle { text {P}} (| X_ {n} -X_ {0} | geq epsilon) leq 2 exp left (- { frac {2 epsilon ^ {2}} { sum _ {t = 1} ^ {n} c_ {t} ^ {2}}} right).}$

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

Мы докажем только случай супермартингейла, поскольку все остальное самоочевидно. К Разложение Дуба, мы могли бы разложить супермартингейл ${ displaystyle left {X_ {t} right }}$ в качестве ${ Displaystyle X_ {t} = Y_ {t} + Z_ {t}}$ куда ${ displaystyle left {Y_ {t}, { mathcal {F}} _ {t} right }}$ это мартингейл и ${ displaystyle left {Z_ {t}, { mathcal {F}} _ {t} right }}$ - невозрастающая предсказуемая последовательность (обратите внимание, что если ${ displaystyle left {X_ {t} right }}$ сам по себе мартингейл, то ${ displaystyle Z_ {t} = 0}$). Из ${ Displaystyle A_ {t} leq X_ {t} -X_ {t-1} leq B_ {t}}$, у нас есть

${ displaystyle - (Z_ {t} -Z_ {t-1}) + A_ {t} leq Y_ {t} -Y_ {t-1} leq - (Z_ {t} -Z_ {t-1} ) + B_ {t}}$

Применение Граница Чернова к ${ displaystyle Y_ {n} -Y_ {0}}$, у нас есть для ${ displaystyle epsilon> 0}$,

${ displaystyle { begin {align} { text {P}} (Y_ {n} -Y_ {0} geq epsilon) & leq { underset {s> 0} { min}} e ^ {-s epsilon} mathbb {E} [e ^ {s (Y_ {n} -Y_ {0})}] & = { underset {s> 0} { min}} e ^ { -s epsilon} mathbb {E} left [ exp left (s sum _ {t = 1} ^ {n} (Y_ {t} -Y_ {t-1}) right) right] & = { underset {s> 0} { min}} e ^ {- s epsilon} mathbb {E} left [ exp left (s sum _ {t = 1} ^ { n-1} (Y_ {t} -Y_ {t-1}) right) mathbb {E} left [ exp left (s (Y_ {n} -Y_ {n-1} right) середина { mathcal {F}} _ {n-1} right] right] end {выравнивается}}}$

Для члена внутреннего ожидания, поскольку (i) ${ displaystyle mathbb {E} [Y_ {n} -Y_ {n-1} mid { mathcal {F}} _ {n-1}] = 0}$ в качестве ${ Displaystyle влево {Y_ {п} вправо }}$ мартингейл; (ii) ${ displaystyle - (Z_ {n} -Z_ {n-1}) + A_ {n} leq Y_ {n} -Y_ {n-1} leq - (Z_ {n} -Z_ {n-1} ) + B_ {n}}$; (iii) ${ displaystyle - (Z_ {n} -Z_ {n-1}) + A_ {n}}$ и ${ displaystyle - (Z_ {n} -Z_ {n-1}) + B_ {n}}$ оба ${ displaystyle { mathcal {F}} _ {n-1}}$-измеримый как ${ Displaystyle влево {Z_ {т} вправо }}$ предсказуемый процесс; и (iv) ${ displaystyle B_ {n} -A_ {n} leq c_ {n}}$, применяя Лемма Хёффдинга^{[примечание 1]}, у нас есть

${ Displaystyle mathbb {E} left [ exp left (s (Y_ {n} -Y_ {n-1}) mid { mathcal {F}} _ {n-1} right) right) right ] leq exp left ({ frac {s ^ {2} (B_ {n} -A_ {n}) ^ {2}} {8}} right) leq exp left ({ frac {s ^ {2} c_ {n} ^ {2}} {8}} right).}$

Повторяя этот шаг, можно получить

${ displaystyle { text {P}} (Y_ {n} -Y_ {0} geq epsilon) leq { underset {s> 0} { min}} e ^ {- s epsilon} exp left ({ frac {s ^ {2} sum _ {t = 1} ^ {n} c_ {t} ^ {2}} {8}} right).}$

Обратите внимание, что минимум достигается при ${ displaystyle s = { frac {4 epsilon} { sum _ {t = 1} ^ {n} c_ {t} ^ {2}}}}$, так что у нас есть

${ displaystyle { text {P}} (Y_ {n} -Y_ {0} geq epsilon) leq exp left (- { frac {2 epsilon ^ {2}} { sum _ { t = 1} ^ {n} c_ {t} ^ {2}}} right).}$

Наконец, поскольку ${ displaystyle X_ {n} -X_ {0} = (Y_ {n} -Y_ {0}) + (Z_ {n} -Z_ {0})}$ и ${ Displaystyle Z_ {п} -Z_ {0} leq 0}$ в качестве ${ Displaystyle влево {Z_ {п} вправо }}$ не увеличивается, поэтому событие ${ displaystyle left {X_ {n} -X_ {0} geq epsilon right }}$ подразумевает ${ displaystyle left {Y_ {n} -Y_ {0} geq epsilon right }}$, и поэтому

${ displaystyle { text {P}} (X_ {n} -X_ {0} geq epsilon) leq { text {P}} (Y_ {n} -Y_ {0} geq epsilon) leq exp left (- { frac {2 epsilon ^ {2}} { sum _ {t = 1} ^ {n} c_ {t} ^ {2}}} right). square}$

Замечание

Обратите внимание, что, установив ${ displaystyle A_ {t} = - c_ {t}, B_ {t} = c_ {t}}$, мы могли бы получить ванильное неравенство Адзумы.

Обратите внимание, что для субмартингейла или супермартингейла выполняется только одна сторона неравенства Адзумы. Мы не можем много сказать о том, насколько быстро растет субмартингейл с ограниченными приращениями (или как падает супермартингейл).

Эта общая форма неравенства Адзумы применима к Дуб мартингейл дает Неравенство МакДиармида что является обычным при анализе рандомизированные алгоритмы.

Простой пример неравенства Адзумы для подбрасывания монеты

Позволять F_я - последовательность независимых и одинаково распределенных случайных подбрасываний монеты (т. е. пусть F_я равновероятно иметь -1 или 1 независимо от других значений F_я). Определение ${ Displaystyle X_ {я} = сумма _ {j = 1} ^ {i} F_ {j}}$ дает мартингейл с |Икс_k − Икс_k−1| ≤ 1, что позволяет применить неравенство Адзумы. В частности, мы получаем

${ displaystyle { text {P}} (X_ {n}> t) leq exp left ({ frac {-t ^ {2}} {2n}} right).}$

Например, если мы установим т пропорционально п, то это говорит нам, что хотя максимум возможное значение Икс_п линейно масштабируется с п, то вероятность что сумма масштабируется линейно с п убывает экспоненциально быстро сп.

Если мы установим ${ displaystyle t = { sqrt {2n ln n}}}$ мы получили:

${ displaystyle { text {P}} (X_ {n}> { sqrt {2n ln n}}) leq 1 / n,}$

что означает, что вероятность отклонения более чем ${ displaystyle { sqrt {2n ln n}}}$ приближается к 0 как п уходит в бесконечность.

Замечание

А аналогичное неравенство было доказано при более слабых предположениях Сергей Бернштейн в 1937 г.

Хёффдинг доказал этот результат для независимых переменных, а не для разностей мартингалов, а также заметил, что небольшие модификации его аргумента устанавливают результат для разностей мартингалов (см. Стр. 18 его статьи 1963 года).

Смотрите также

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

Примечания

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

• Alon, N .; Спенсер, Дж. (1992). Вероятностный метод. Нью-Йорк: Вили.
• Адзума, К. (1967). «Взвешенные суммы некоторых зависимых случайных величин» (PDF). Математический журнал Тохоку. 19 (3): 357–367. Дои:10.2748 / tmj / 1178243286. МИСТЕР  0221571.
• Бернштейн, Сергей Н. (1937). На определенных модификациях неравенства Чебишева [О некоторых модификациях неравенства Чебышева]. Доклады Академии Наук СССР (на русском). 17 (6): 275–277. (т. 4, поз. 22 в Собрании сочинений)
• МакДиармид, К. (1989). «О методе ограниченных разностей». Обзоры по комбинаторике. Лондонская математика. Soc. Конспект лекций 141. Кембридж: Cambridge Univ. Нажмите. С. 148–188. МИСТЕР  1036755.
• Хёффдинг, В. (1963). «Вероятностные неравенства для сумм ограниченных случайных величин». Журнал Американской статистической ассоциации. 58 (301): 13–30. Дои:10.2307/2282952. JSTOR  2282952. МИСТЕР  0144363.
• Годболе, А. П .; Хитченко, П. (1998). Помимо метода ограниченных разностей. Серия DIMACS по дискретной математике и теоретической информатике. 41. С. 43–58. Дои:10.1090 / dimacs / 041/03. ISBN  9780821808276. МИСТЕР  1630408.