Неравенства Бернштейна (теория вероятностей)

В вероятностей теории неравенства Бернштейна дают границы вероятности отклонения суммы случайных величин от своего среднего значения. В простейшем случае пусть X ₁ , ..., X _n — независимые случайные величины Бернулли, принимающие значения +1 и −1 с вероятностью 1/2 (это распределение известно также как распределение Радемахера ), тогда для каждого положительного $\varepsilon$,

$\mathbb {P} \left(\left|{\frac {1}{n}}\sum _{i=1}^{n}X_{i}\right|>\varepsilon \right)\leq 2\exp \left(-{\frac {n\varepsilon ^{2}}{2(1+{\frac {\varepsilon }{3}})}}\right).$

Неравенства Бернштейна были доказаны и опубликованы Сергеем Бернштейном в 1920-х и 1930-х годах. Позднее эти неравенства несколько раз открывались заново в различных формах. Таким образом, частные случаи неравенств Бернштейна также известны как граница Чернова , неравенство Хеффдинга и неравенство Азумы . Мартингальный случай неравенства Бернштейна известно как неравенство Фридмана и его доработка известно как неравенство Хеффдинга.

Некоторые из неравенств

1. Пусть $X_{1},\ldots ,X_{n}$ быть независимыми случайными величинами с нулевым средним значением. Предположим, что $|X_{i}|\leq M$ почти наверняка, для всех $i.$ Тогда при всех положительных $t$,

$\mathbb {P} \left(\sum _{i=1}^{n}X_{i}\geq t\right)\leq \exp \left(-{\frac {{\tfrac {1}{2}}t^{2}}{\sum _{i=1}^{n}\mathbb {E} \left[X_{i}^{2}\right]+{\tfrac {1}{3}}Mt}}\right).$

2. Пусть $X_{1},\ldots ,X_{n}$ быть независимыми случайными величинами с нулевым средним значением. Предположим, что для некоторого положительного действительного $L$ и каждое целое число $k\geq 2$,

$\mathbb {E} \left[\left|X_{i}^{k}\right|\right]\leq {\frac {1}{2}}\mathbb {E} \left[X_{i}^{2}\right]L^{k-2}k!$

Затем

$\mathbb {P} \left(\sum _{i=1}^{n}X_{i}\geq 2t{\sqrt {\sum \mathbb {E} \left[X_{i}^{2}\right]}}\right)<\exp(-t^{2}),\qquad {\text{for}}\quad 0\leq t\leq {\frac {1}{2L}}{\sqrt {\sum \mathbb {E} \left[X_{j}^{2}\right]}}.$

3. Пусть $X_{1},\ldots ,X_{n}$ быть независимыми случайными величинами с нулевым средним значением. Предположим, что

$\mathbb {E} \left[\left|X_{i}^{k}\right|\right]\leq {\frac {k!}{4!}}\left({\frac {L}{5}}\right)^{k-4}$

для всех целых чисел $k\geq 4.$ Обозначим

$A_{k}=\sum \mathbb {E} \left[X_{i}^{k}\right].$

Затем,

$\mathbb {P} \left(\left|\sum _{j=1}^{n}X_{j}-{\frac {A_{3}t^{2}}{3A_{2}}}\right|\geq {\sqrt {2A_{2}}}\,t\left[1+{\frac {A_{4}t^{2}}{6A_{2}^{2}}}\right]\right)<2\exp(-t^{2}),\qquad {\text{for}}\quad 0<t\leq {\frac {5{\sqrt {2A_{2}}}}{4L}}.$

4. Бернштейн также доказал обобщение приведенных выше неравенств на слабозависимые случайные величины. Например, неравенство (2) можно расширить следующим образом. Позволять $X_{1},\ldots ,X_{n}$ быть, возможно, ненезависимыми случайными величинами. Предположим, что для всех целых чисел $i>0$,

${\begin{aligned}\mathbb {E} \left.\left[X_{i}\right|X_{1},\ldots ,X_{i-1}\right]&=0,\\\mathbb {E} \left.\left[X_{i}^{2}\right|X_{1},\ldots ,X_{i-1}\right]&\leq R_{i}\mathbb {E} \left[X_{i}^{2}\right],\\\mathbb {E} \left.\left[X_{i}^{k}\right|X_{1},\ldots ,X_{i-1}\right]&\leq {\tfrac {1}{2}}\mathbb {E} \left.\left[X_{i}^{2}\right|X_{1},\ldots ,X_{i-1}\right]L^{k-2}k!\end{aligned}}$

Затем

$\mathbb {P} \left(\sum _{i=1}^{n}X_{i}\geq 2t{\sqrt {\sum _{i=1}^{n}R_{i}\mathbb {E} \left[X_{i}^{2}\right]}}\right)<\exp(-t^{2}),\qquad {\text{for}}\quad 0<t\leq {\frac {1}{2L}}{\sqrt {\sum _{i=1}^{n}R_{i}\mathbb {E} \left[X_{i}^{2}\right]}}.$

Более общие результаты для мартингалов можно найти у Fan et al. (2015).

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

Доказательства основаны на применении неравенства Маркова к случайной величине

$\exp \left(\lambda \sum _{j=1}^{n}X_{j}\right),$

для подходящего выбора параметра $\lambda >0$.

Обобщения

Неравенство Бернштейна можно обобщить на случайные гауссовы матрицы. Позволять $G=g^{H}Ag+2\operatorname {Re} (g^{H}a)$ быть скаляром, где $A$ представляет собой комплексную эрмитову матрицу и $a$ комплексный вектор размера $N$. Вектор $g\sim {\mathcal {CN}}(0,I)$ представляет собой гауссов вектор размера $N$. Тогда для любого $\sigma \geq 0$, у нас есть

$\mathbb {P} \left(G\leq \operatorname {tr} (A)-{\sqrt {2\sigma }}{\sqrt {\Vert \operatorname {vec} (A)\Vert ^{2}+2\Vert a\Vert ^{2}}}-\sigma s^{-}(A)\right)<\exp(-\sigma ),$

где $\operatorname {vec}$ — операция векторизации и $s^{-}(A)=\max(-\lambda _{\max }(A),0)$ где $\lambda _{\max }(A)$ является наибольшим собственным значением $A$. Доказательство подробно описано здесь. Другое аналогичное неравенство формулируется как

$\mathbb {P} \left(G\geq \operatorname {tr} (A)+{\sqrt {2\sigma }}{\sqrt {\Vert \operatorname {vec} (A)\Vert ^{2}+2\Vert a\Vert ^{2}}}+\sigma s^{+}(A)\right)<\exp(-\sigma ),$

где $s^{+}(A)=\max(\lambda _{\max }(A),0)$.

См. также

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

Ссылки

(по: С. Н. Бернштейн, Собрание сочинений, Наука, 1964)

Современный перевод некоторых из этих результатов можно также найти в Прохоров А.В.; Корнейчук, Н.П.; Моторный, В.П. (2001) [1994], «Неравенство Бернштейна» , Энциклопедия математики , EMS Press