Неравенство Хефдинга

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

Неравенство Хеффдинга является частным случаем неравенства Азумы-Хеффдинга и неравенства Мак-Диармида . Она похожа на границу Чернова , но имеет тенденцию быть менее точной, особенно когда дисперсия случайных величин мала. Оно похоже на одно из неравенств Бернштейна , но несравнимо с ним .

Заявление

Пусть X ₁ , ..., X _n — независимые случайные величины такие, что $a_{i}\leq X_{i}\leq b_{i}$ почти наверняка . Рассмотрим сумму этих случайных величин:

$S_{n}=X_{1}+\cdots +X_{n}.$

Тогда теорема Хеффдинга утверждает, что для всех t > 0

${\begin{aligned}\operatorname {P} \left(S_{n}-\mathrm {E} \left[S_{n}\right]\geq t\right)&\leq \exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right)\\\operatorname {P} \left(\left|S_{n}-\mathrm {E} \left[S_{n}\right]\right|\geq t\right)&\leq 2\exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right)\end{aligned}}$

Здесь [ Sn _​ ] — значение Sn E _{ожидаемое} .

Обратите внимание, что неравенства также выполняются, когда X _i получено с использованием выборки без замены; в этом случае случайные величины больше не являются независимыми. Доказательство этого утверждения можно найти в статье Хеффдинга. Немного лучшие оценки в случае выборки без замещения см., например, в статье Серфлинга (1974) .

Обобщение

Позволять $Y_{1},\dots ,Y_{n}$ быть независимыми наблюдениями такими, что $\operatorname {E} (Y_{i})=0$ и $a_{i}\leq Y_{i}\leq b_{i}$. Позволять $\epsilon >0$. Тогда для любого $t>0$, $$P\left(\sum _{i=1}^{n}Y_{i}\geq \epsilon \right)\leq \exp \left(-t\epsilon +\sum _{i=1}^{n}t^{2}(b_{i}-a_{i})^{2}/8\right)$$

Особый случай: дома на колесах Бернулли

Предполагать $a_{i}=0$ и $b_{i}=1$ для всех я . Это может произойти, когда X _i являются независимыми случайными величинами Бернулли , хотя они не обязательно должны быть одинаково распределены. Тогда мы получаем неравенство

${\begin{aligned}\operatorname {P} \left(S_{n}-\mathrm {E} \left[S_{n}\right]\geq t\right)&\leq \exp(-2t^{2}/n)\\\operatorname {P} \left(\left|S_{n}-\mathrm {E} \left[S_{n}\right]\right|\geq t\right)&\leq 2\exp(-2t^{2}/n)\end{aligned}}$

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

$${\begin{aligned}\operatorname {P} \left((S_{n}-\mathrm {E} \left[S_{n}\right])/n\geq t\right)&\leq \exp(-2nt^{2})\\\operatorname {P} \left(\left|(S_{n}-\mathrm {E} \left[S_{n}\right])/n\right|\geq t\right)&\leq 2\exp(-2nt^{2})\end{aligned}}$$

для всех $t\geq 0$. Это версия аддитивной границы Чернова , которая является более общей, поскольку она допускает случайные величины, которые принимают значения от нуля до единицы, но также и более слабая, поскольку граница Чернова дает лучшую хвостовую границу, когда случайные величины имеют небольшую дисперсию.

Общий случай ограниченных сверху случайных величин

Неравенство Хёффдинга можно распространить на случай ограниченных сверху случайных величин.

Пусть X ₁ , ..., X _n — независимые случайные величины такие, что $\mathrm {E} X_{i}=0$ и $X_{i}\leq b_{i}$ почти наверняка . Обозначим через

${\begin{aligned}C_{i}^{2}=\left\{{\begin{array}{ll}\mathrm {E} X_{i}^{2},&\mathrm {if} \ \mathrm {E} X_{i}^{2}\geq b_{i}^{2},\\\displaystyle {\frac {1}{4}}\left(b_{i}+{\frac {\mathrm {E} X_{i}^{2}}{b_{i}}}\right)^{2},&{\textrm {otherwise}}.\end{array}}\right.\end{aligned}}$

Неравенство Хеффдинга для ограниченных из вышеперечисленных случайных величин утверждает, что для всех $t\geq 0$,

$\mathrm {P} \left(\left|\sum _{i=1}^{n}X_{i}\right|\geq t\right)\leq 2\exp \left(-{\frac {t^{2}}{2\sum _{i=1}^{n}C_{i}^{2}}}\right).$

В частности, если $\mathrm {E} X_{i}^{2}\geq b_{i}^{2}$ для всех $i$, тогда для всех $t\geq 0$,

$\mathrm {P} \left(\left|\sum _{i=1}^{n}X_{i}\right|\geq t\right)\leq 2\exp \left(-{\frac {t^{2}}{2\sum _{i=1}^{n}\mathrm {E} X_{i}^{2}}}\right).$

Общий случай субгауссовских случайных величин

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

$\mathrm {P} (|X|\geq t)\leq 2e^{-ct^{2}},$

для некоторых $c>0$. Для любой ограниченной X переменной $\mathrm {P} (|X|\geq t)=0\leq 2e^{-ct^{2}}$ для $t>T$ для некоторого достаточно большого T . Затем $2e^{-cT^{2}}\leq 2e^{-ct^{2}}$ для всех $t\leq T$ так принимая $c=\log(2)/T^{2}$ урожайность

$\mathrm {P} (|X|\geq t)\leq 1\leq 2e^{-cT^{2}}\leq 2e^{-ct^{2}},$

для $t\leq T$. Таким образом, каждая ограниченная переменная является субгауссовой.

Для случайной величины X следующая норма конечна тогда и только тогда, когда X субгауссова:

$\Vert X\Vert _{\psi _{2}}:=\inf \left\{c\geq 0:\mathrm {E} \left(e^{X^{2}/c^{2}}\right)\leq 2\right\}.$

Тогда пусть X ₁ , ..., X _n — независимые субгауссовы случайные величины с нулевым средним, общая версия неравенства Хёффдинга гласит, что:

$\mathrm {P} \left(\left|\sum _{i=1}^{n}X_{i}\right|\geq t\right)\leq 2\exp \left(-{\frac {ct^{2}}{\sum _{i=1}^{n}\Vert X_{i}\Vert _{\psi _{2}}^{2}}}\right),$

где c > 0 — абсолютная константа.

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

Доказательство неравенства Хеффдинга аналогично доказательству неравенства концентрации, такого как границы Чернова . Основное отличие заключается в использовании леммы Хеффдинга :

Предположим, что X — действительная случайная величина такая, что $X\in \left[a,b\right]$ почти наверняка . Затем

$\mathrm {E} \left[e^{s\left(X-\mathrm {E} \left[X\right]\right)}\right]\leq \exp \left({\tfrac {1}{8}}s^{2}(b-a)^{2}\right).$

Используя эту лемму, мы можем доказать неравенство Хеффдинга. Как и в формулировке теоремы, предположим, что X ₁ , ..., X _n — n независимых случайных величин таких, что $X_{i}\in [a_{i},b_{i}]$ почти наверняка для всех я , и пусть $S_{n}=X_{1}+\cdots +X_{n}$.

Тогда для s , t > 0 неравенство Маркова и независимость X _i влекут за собой:

${\begin{aligned}\operatorname {P} \left(S_{n}-\mathrm {E} \left[S_{n}\right]\geq t\right)&=\operatorname {P} \left(\exp(s(S_{n}-\mathrm {E} \left[S_{n}\right]))\geq \exp(st)\right)\\&\leq \exp(-st)\mathrm {E} \left[\exp(s(S_{n}-\mathrm {E} \left[S_{n}\right]))\right]\\&=\exp(-st)\prod _{i=1}^{n}\mathrm {E} \left[\exp(s(X_{i}-\mathrm {E} \left[X_{i}\right]))\right]\\&\leq \exp(-st)\prod _{i=1}^{n}\exp {\Big (}{\frac {s^{2}(b_{i}-a_{i})^{2}}{8}}{\Big )}\\&=\exp \left(-st+{\tfrac {1}{8}}s^{2}\sum _{i=1}^{n}(b_{i}-a_{i})^{2}\right)\end{aligned}}$

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

$s={\frac {4t}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}.$

Записав приведенную выше оценку для этого значения s , мы получим желаемую оценку:

$\operatorname {P} \left(S_{n}-\mathrm {E} \left[S_{n}\right]\geq t\right)\leq \exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right).$

Использование

Доверительные интервалы

Неравенство Хёффдинга можно использовать для получения доверительных интервалов . Мы рассматриваем монету, у которой орёл появляется с вероятностью p, а решка — с вероятностью 1 − p . Мы подбрасываем монету n раз, генерируя n выборок. $X_{1},\ldots ,X_{n}$ (которые являются ) случайными величинами Бернулли . количество Ожидаемое раз, когда монета выпадет орлом, равно pn . Более того, вероятность того, что монета выпадет орлом как минимум k раз, может быть точно определена количественно с помощью следующего выражения:

$\operatorname {P} (H(n)\geq k)=\sum _{i=k}^{n}{\binom {n}{i}}p^{i}(1-p)^{n-i},$

где H ( n ) — количество орлов при n бросках монеты.

Когда k = ( p + ε ) n для некоторого ε > 0 , неравенство Хеффдинга ограничивает эту вероятность членом, который экспоненциально мал по ε ² н :

$\operatorname {P} (H(n)-pn>\varepsilon n)\leq \exp \left(-2\varepsilon ^{2}n\right).$

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

$\operatorname {P} \left(|H(n)-pn|>\varepsilon n\right)\leq 2\exp \left(-2\varepsilon ^{2}n\right).$

Думая о ${\overline {X}}={\frac {1}{n}}H(n)$ как «наблюдаемое» среднее значение, эту вероятность можно интерпретировать как уровень значимости $\alpha$ (вероятность совершения ошибки) для доверительного интервала около $p$ размера 2 ɛ :

$\alpha =\operatorname {P} (\ {\overline {X}}\notin [p-\varepsilon ,p+\varepsilon ])\leq 2e^{-2\varepsilon ^{2}n}$

Нахождение n для противоположного знака неравенства в приведенном выше примере, т. е. n , которое нарушает неравенство, но не равенство, указанное выше, дает нам:

$n\geq {\frac {\log(2/\alpha )}{2\varepsilon ^{2}}}$

Поэтому нам потребуется как минимум $\textstyle {\frac {\log(2/\alpha )}{2\varepsilon ^{2}}}$ образцы для приобретения $\textstyle (1-\alpha )$-доверительный интервал $\textstyle p\pm \varepsilon$.

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

См. также

• Неравенство концентрации - сводка хвостовых границ случайных величин.
• Лемма Хёффдинга
• Неравенства Бернштейна (теория вероятностей)

Ссылки

• Серфлинг, Роберт Дж. (1974). «Вероятностные неравенства для суммы при выборке без замены» . Анналы статистики . 2 (1): 39–48. дои : 10.1214/aos/1176342611 . МР   0420967 .
• Хеффдинг, Василий (1963). «Вероятностные неравенства для сумм ограниченных случайных величин» (PDF) . Журнал Американской статистической ассоциации . 58 (301): 13–30. дои : 10.1080/01621459.1963.10500830 . JSTOR   2282952 . МР   0144363 .
• Фан, Х.; Грама, И.; Лю, К. (2015). «Экспоненциальные неравенства для мартингалов с приложениями» . Электрон. Дж. Вероятность . 20 (1): 1–22. arXiv : 1311.6273 . дои : 10.1214/EJP.v20-3496 .
• Вершинин, Роман (2018). Многомерная вероятность . Издательство Кембриджского университета. ISBN  9781108415194 .
• Бушерон, Стефан (2013). Неравенства концентрации: неасимптотическая теория независимости . Габор Лугоши, Паскаль Массар. Оксфорд: Издательство Оксфордского университета. ISBN  978-0-19-953525-5 . OCLC   837517674 .
• Кахане, JP (1960). «Локальные свойства случайных функций ряда Фурье». Стад. Математика . Полет. 19.стр. 1–25. [1] .