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

В теории вероятностей неравенства концентрации меры дают оценки отклонения случайной величины от некоторого значения (обычно от её математического ожидания). Закон больших чисел классической теории вероятностей утверждает, что суммы независимых случайных величин, при соблюдении довольно слабых условий, с большой вероятностью оказываются близкими к их математическим ожиданиям. Такие суммы являются основными примерами случайных величин, которые сконцентрированы около своих средних значений.

Неравенство Маркова

Шаблон:Main Пусть $X$ случайная величина, почти наверное неотрицательная. Тогда, для всякой константы $a>0$

$P(X\ge a)\le \frac{\mathrm{E}(X)}{a}$.

Отметим следующее выражение для неравенства Маркова: если $\mathrm{\Phi }$ — неотрицательная строго возрастающая функция, то

$P(X\ge a)=P(\mathrm{\Phi }(X)\ge \mathrm{\Phi }(a))\le \frac{\mathrm{E}(\mathrm{\Phi }(X))}{\mathrm{\Phi }(a)}$.

Неравенство Чебышёва

Шаблон:Main Для неравенства Чебышёва требуется, чтобы случайная величина $X$ удовлетворяла следующим условиям:

• математическое ожидание $\mathrm{E}[X]$ конечно;
• дисперсия $\mathrm{D}[X]=\mathrm{E}[(X-\mathrm{E}[X]{)}^2]={\sigma }^2$ конечна.

Тогда для всякой константы $a>0$

$P(|X-\mathrm{E}[X]|\ge a)\le \frac{\mathrm{D}[X]}{a^2}$,

или, равносильно,

$P(|X-\mathrm{E}[X]|\ge a\cdot \mathrm{Std}[X])\le \frac{1}{a^2}$,

где $\mathrm{Std}[X]=\sigma$ — стандартное отклонение случайной величины $X$.

Неравенство Чебышёва может рассматриваться как частный случай обобщённого неравенства Маркова, применённого к случайной величине $|X-\mathrm{E}[X]|$ с $\mathrm{\Phi }(x)=x^2$.

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

Шаблон:Main Основной случай границы ЧерноваШаблон:Rp требует существования для $X$ производящей функции, определяемой как $M_X(t):=\mathrm{E}\left[e^{tX}\right]$. Основываясь на неравенстве Маркова, для каждого $t>0$

$P(X\ge a)\le \frac{\mathrm{E}[e^{t\cdot X}]}{e^{t\cdot a}}$,

и для каждого $t<0$

$P(X\le a)\le \frac{\mathrm{E}[e^{t\cdot X}]}{e^{t\cdot a}}$.

Границы Чернова различны для различных распределений и различных значений параметра $t$.

Границы сумм независимых случайных величин

Шаблон:Main Пусть $X_1,X_2,\dots ,X_n$ — независимые случайные величины такие, что для всех i:

$a_i\le X_i\le b_i$ почти наверное.

$c_i:=b_i-a_i$

$\mathrm{\forall }i:c_i\le C$

Пусть $S_n$- их сумма, $E_n$- математическое ожидание и $D_n$ — дисперсия

$S_n:=\sum _{i=1}^n{X}_i$,

$E_n:=\mathrm{E}[S_n]=\sum _{i=1}^n\mathrm{E}[X_i]$,

$D_n:=\mathrm{D}[S_n]=\sum _{i=1}^n\mathrm{D}[X_i]$.

Часто представляет интерес оценка разности между суммой и её математическим ожиданием. Можно использовать несколько неравенств.

1. Неравенство Хёфдинга утверждает, что

$P[|S_n-E_n|>t]<2\exp (-\frac{2t^2}{\sum _{i=1}^n{c}_i^2})<2\exp (-\frac{2t^2}{n{C}^2})$.

2. Случайная величина $(S_n-E_n)$ — это специальный случай мартингала, и $S_0-E_0=0$. Следовательно, можно использовать неравенство Азумы, что даёт чуть более слабую оценку

$P[|S_n-E_n|>t]<2\exp (-\frac{t^2}{2\sum _{i=1}^n{c}_i^2})<2\exp (-\frac{t^2}{2n{C}^2})$.

При этом здесь появляется возможность рассматривать любые мартингалы, в том числе супермартингалы и субмартингалы.

3. Функция суммирования $S_n=f(X_1,\dots ,X_n)$ — частный случай функции $n$ переменных. Эта функция изменяется ограниченным образом: если переменная $i$ изменяется, то значение $f$ также изменяется самое большее на $b_i-a_i<C$. Следовательно, можно использовать Шаблон:Не переведено 5, и оно даст аналогичную оценку

$P[|S_n-E_n|>t]<2\exp (-\frac{2t^2}{\sum _{i=1}^n{c}_i^2})<2\exp (-\frac{2t^2}{n{C}^2})$.

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

4. Шаблон:Не переведено 5 даёт некоторые улучшения по сравнению с неравенством Хёфдинга, когда дисперсии слагаемых малы по сравнению с их «почти наверное-границами» C.

$P[|S_n-E_n|>t]\le 2\exp [-\frac{D_n}{C^2}h\left(\frac{Ct}{D_n}\right)],$ где $h(u)=(1+u)\log (1+u)-u$

5. Первое из Шаблон:Не переведено 5 утверждает, что

$P[|S_n-E_n|>t]<2\exp (-\frac{t^2/2}{D_n+C\cdot t/3})$.

Как и неравенство Хёфдинга, для которого данная оценка является обобщением, первое неравенство Бернштейна учитывает почти наверное ограниченные случайные величины. Более того, оно позволяет получить более точную оценку при условии, что случайные величины имеют ограниченные дисперсии.

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

$\mathrm{E}[e^{t\cdot S_n}]=\prod _{i=1}^n\mathrm{E}[e^{t\cdot X_i}]$].

Например, пусть случайные величины $X_i$ удовлетворяют неравенству $X_i\ge E(X_i)-a_i-M$ при $1\le i\le n$, тогда для нижнего хвоста мы имеем неравенство

$P[S_n-E_n<-\lambda ]\le \exp (-\frac{{\lambda }^2}{2(D_n+\sum _{i=1}^n{a}_i^2+M\lambda /3)})$.

Если $X_i$ удовлетворяет неравенству $X_i\le E(X_i)+a_i+M$, то для верхнего хвоста мы имеем неравенство

$P[S_n-E_n>\lambda ]\le \exp (-\frac{{\lambda }^2}{2(D_n+\sum _{i=1}^n{a}_i^2+M\lambda /3)})$.

Если $X_i$ независимы и одинаково распределены, $|X_i|\le 1$ и ${\sigma }^2$ — дисперсия $X_i$, то типичный вид неравенства Чернова следующий:

$P[|S_n|\ge k\sigma ]\le 2e^{-k^2/4n},0\le k\le 2\sigma$.

7. Аналогичные границы можно найти в разделе: Шаблон:Не переведено 5

Неравенство Эфрона-Стейна

Неравенство Эфрона-Стейна (неравенство влияния, или MG-оценка дисперсии) оценивает дисперсию функции общего вида от случайных величин.

Пусть $X_1\dots X_n$, ${X_1}^{\prime }\dots {X_n}^{\prime }$ независимы, a ${X_i}^{\prime }$ и $X_i$ имеют одинаковое распределение при всех $i$.

Положим $X=(X_1,\dots ,X_n),X^{(i)}=(X_1,\dots ,X_{i-1},{X_i}^{\prime },X_{i+1},\dots ,X_n).$ Тогда

$\mathrm{D}(f(X))\le \frac{1}{2}\sum _{i=1}^{n}E[(f(X)-f(X^{(i)}){)}^2]$.

Неравенство Дворецкого-Кифера-Вольфовица

Шаблон:Не переведено 5 оценивает разность между фактической и эмпирической функциями распределения.

Пусть для данного натурального $n$ $X_1,X_2,\dots ,X_n$ — независимые и одинаково распределённые вещественнозначные случайные величины с функцией распределения $F$. Пусть $F_n$ обозначает соответствующую эмпирическую функцию распределения, определённую формулой

$F_n(x)=\frac{1}{n}\sum _{i=1}^n{\mathrm{𝟏}}_{\{X_i\le x\}},x\in ℝ.$

Таким образом, $F(x)$ — вероятность события, что отдельная случайная величина $X$ меньше, чем $x$, а $F_n(x)$ — это среднее количество величин из выборки $X_1,X_2,\dots ,X_n$, реализации которых меньше, чем $x$.

Тогда верны следующие односторонняя и двусторонняя оценки:

$P\left(\underset{x\in ℝ}{\sup }\right(F_n(x)-F(x))>\epsilon )\le e^{-2n{\epsilon }^2},\mathrm{\forall }\epsilon \ge \sqrt{\frac{1}{2n}\ln 2},$

$P(\underset{x\in ℝ}{\sup }|F_n(x)-F(x)|>\epsilon )\le 2e^{-2n{\epsilon }^2},\mathrm{\forall }\epsilon >0.$

Ссылки

• Karthik Sridharan, «A Gentle Introduction to Concentration Inequalities Шаблон:Wayback» — Cornell University
• One Hundred Probability/Statistics Inequalities Шаблон:Wayback. См. «4 Concentration Inequalities»