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

Неравенство Хёфдинга даёт верхнюю границу вероятности того, что сумма случайных величин отклоняется от своего математического ожидания. Неравенство Хёфдинга было доказано Василием Хёфдингом^[en] в 1963 году. Неравенство Хёфдинга является частным случаем неравенства Адзума — Хёфдинга^[en] и более общим случаем неравенства Бернштейна^[en], доказанного Сергеем Бернштейном в 1923 году. Они также являются частными случаями неравенства МакДиармида.

Частный случай для случайных величин БернуллиПравить

Неравенство Хефдинга может быть применено к важному частному случаю одинаково распределенных бернуллиевских случайных величин, и, как неравенство, часто используется в комбинаторике и информатике. Рассматриваем смещённую монету, у которой орёл выпадает с вероятностью $p$$p$  и решка — с вероятностью $1-<!--\; -\; -->p$$1-p$ . Мы бросаем монету $n$$n$  раз. Математическое ожидание того, сколько раз монета упадет орлом, есть $p\cdot <!--\; \cdot \; -->n$$p\cdot n$ . Далее, вероятность того, что монета упадет орлом не более $k$$k$  раз, может быть точно оценена выражением:

$Pr(H(n)⩽<!--\; ⩽\; -->k)=\underset{i=0}{\overset{k}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n}{i})p^i(1-<!--\; -\; -->p{)}^{n-<!--\; -\; -->i}.$$\Pr {\Big (}H(n)\leqslant k{\Big )}=\sum _{i=0}^{k}{\binom {n}{i}}p^{i}(1-p)^{n-i}\,.$ 

В случае $k=(p-<!--\; -\; -->\mathrm{\epsilon <!--\; \epsilon \; -->})n$$k=(p-\varepsilon )n$  для некоторого $\mathrm{\epsilon <!--\; \epsilon \; -->}>0$$\varepsilon >0$  неравенство Хёфдинга ограничивает эту вероятность выражением, которое экспоненциально убывает от ${\mathrm{\epsilon <!--\; \epsilon \; -->}}^2\cdot <!--\; \cdot \; -->n$$\varepsilon ^{2}\cdot n$ :

$Pr(H(n)⩽<!--\; ⩽\; -->(p-<!--\; -\; -->\mathrm{\epsilon <!--\; \epsilon \; -->})n)⩽<!--\; ⩽\; -->\exp <!--\; \; -->(-<!--\; -\; -->2{\mathrm{\epsilon <!--\; \epsilon \; -->}}^{2}n).$$\Pr {\Big (}H(n)\leqslant (p-\varepsilon )n{\Big )}\leqslant \exp {\big (}-2\varepsilon ^{2}n{\big )}\,.$ 

Похожим образом, в случае $k=(p+\mathrm{\epsilon <!--\; \epsilon \; -->})n$$k=(p+\varepsilon )n$  для некоторого $\mathrm{\epsilon <!--\; \epsilon \; -->}>0$$\varepsilon >0$  неравенство Хёфдинга ограничивает вероятность того, что выпадет не меньше $\mathrm{\epsilon <!--\; \epsilon \; -->}n$$\varepsilon n$  орлов, чем ожидаемо, выражением:

$Pr(H(n)⩾<!--\; ⩾\; -->(p+\mathrm{\epsilon <!--\; \epsilon \; -->})n)⩽<!--\; ⩽\; -->\exp <!--\; \; -->(-<!--\; -\; -->2{\mathrm{\epsilon <!--\; \epsilon \; -->}}^{2}n).$$\Pr {\Big (}H(n)\geqslant (p+\varepsilon )n{\Big )}\leqslant \exp {\big (}-2\varepsilon ^{2}n{\big )}\,.$ 

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

$Pr((p-<!--\; -\; -->\mathrm{\epsilon <!--\; \epsilon \; -->})n⩽<!--\; ⩽\; -->H(n)⩽<!--\; ⩽\; -->(p+\mathrm{\epsilon <!--\; \epsilon \; -->})n)⩾<!--\; ⩾\; -->1-<!--\; -\; -->2\exp <!--\; \; -->(-<!--\; -\; -->2{\mathrm{\epsilon <!--\; \epsilon \; -->}}^{2}n).$$\Pr {\Big (}(p-\varepsilon )n\leqslant H(n)\leqslant (p+\varepsilon )n{\Big )}\geqslant 1-2\exp {\big (}-2\varepsilon ^{2}n{\big )}\,.$ 

Общий случайПравить

Пусть $X_1,\dots <!--\; \dots \; -->,X_n$$X_{1},\dots ,X_{n}$  — независимые случайные величины.

Положим, что $X_i$$X_{i}$  являются почти достоверно ограниченными, то есть, положим для $1⩽<!--\; ⩽\; -->i⩽<!--\; ⩽\; -->n$$1 \leqslant i \leqslant n$ , что:

$Pr(X_i\in <!--\; \in \; -->[a_i,b_i])=1.$$\Pr(X_{i}\in [a_{i},b_{i}])=1.$ 

Мы определяем эмпирическое среднее этих переменных:

$\stackrel{¯<!--\; ¯\; -->}{X}=(X_1+\cdots <!--\; \cdots \; -->+X_n)/n.$${\overline {X}}=(X_{1}+\cdots +X_{n})/n\,.$ 

Теорема 2 из Hoeffding (1963), доказывает неравенства:

$Pr(\stackrel{¯<!--\; ¯\; -->}{X}-<!--\; -\; -->\mathrm{E}[\stackrel{¯<!--\; ¯\; -->}{X}]⩾<!--\; ⩾\; -->t)⩽<!--\; ⩽\; -->\exp <!--\; \; -->\left(-<!--\; -\; -->\frac{2t^2{n}^2}{\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}(b_i-<!--\; -\; -->a_i{)}^2}\right),$$\Pr({\overline {X}}-\mathrm {E} [{\overline {X}}]\geqslant t)\leqslant \exp \left(-{\frac {2t^{2}n^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right),$ 

$Pr(|\stackrel{¯<!--\; ¯\; -->}{X}-<!--\; -\; -->\mathrm{E}[\stackrel{¯<!--\; ¯\; -->}{X}]|⩾<!--\; ⩾\; -->t)⩽<!--\; ⩽\; -->2\exp <!--\; \; -->\left(-<!--\; -\; -->\frac{2t^2{n}^2}{\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}(b_i-<!--\; -\; -->a_i{)}^2}\right),$$\Pr(|{\overline {X}}-\mathrm {E} [{\overline {X}}]|\geqslant t)\leqslant 2\exp \left(-{\frac {2t^{2}n^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right),$ 

которые верны для всех положительных значений t. Здесь $\mathrm{E}[\stackrel{¯<!--\; ¯\; -->}{X}]$$\mathrm {E} [{\overline {X}}]$  является мат.ожиданием $\stackrel{¯<!--\; ¯\; -->}{X}$$\overline {X}$ .

Заметим, что неравенство также верно, если $X_i$$X_{i}$  были получены с использованием выборки без замены, в данном случае случайные переменные не являются больше независимыми. Доказательство этого утверждения можно найти в статье Хёфдинга. Для несколько лучших оценок границ в случае выборки без замены, см., например, статью, .

См. такжеПравить

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