Неравенство Азумы

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

Предполагать $\{X_{k}:k=0,1,2,3,\dots \}$ является мартингейлом (или супермартингейлом ) и

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

почти наверняка . Тогда для всех положительных целых чисел N и всех положительных действительных чисел $\epsilon$,

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

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

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

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

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

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

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

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

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

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

Заявление

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

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

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

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

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

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

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

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

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

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

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

Применяя Чернова, связанного с $Y_{n}-Y_{0}$, у нас есть для $\epsilon >0$,

${\begin{aligned}{\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)\mid {\mathcal {F}}_{n-1}\right]\right]\end{aligned}}$

Для внутреннего ожидаемого члена, поскольку

(я) $\mathbb {E} [Y_{t}-Y_{t-1}\mid {\mathcal {F}}_{t-1}]=0$ как $\left\{Y_{t}\right\}$ является мартингейлом;

(ii) $-(Z_{t}-Z_{t-1})+A_{t}\leq Y_{t}-Y_{t-1}\leq -(Z_{t}-Z_{t-1})+B_{t}$;

(iii) $-(Z_{t}-Z_{t-1})+A_{t}$ и $-(Z_{t}-Z_{t-1})+B_{t}$ оба ${\mathcal {F}}_{t-1}$-измеримый как $\left\{Z_{t}\right\}$ это предсказуемый процесс;

(iv) $B_{t}-A_{t}\leq c_{t}$;

применив лемму Хеффдинга , у нас есть

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

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

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

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

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

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

${\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$

Примечание

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

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

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

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

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

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

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

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

$\operatorname {P} \left(X_{n}>{\sqrt {2n\ln n}}\right)\leq {\frac {1}{n}},$

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

Примечание

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

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

См. также

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

Ссылки

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