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

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Граница Чернова (англ. Chernoff bound) дает оценку вероятности того, что сумма n одинаково распределенных независимых случайных величин больше (или меньше) некоторого значения.


Неравенство и его доказательство

Теорема (Граница Чернова):
Пусть даны [math]X_1 X_2 \ldots X_n[/math] — одинаково распределенные независимые случайные величины, принимающие значения из множества [math]\{0, 1\}[/math],

[math]m = {E} \sum\limits_{i=1}^{n} X_i[/math],

Тогда:

[math]{P} (|\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m| \geqslant \delta) \leqslant 2e^{-2 \delta ^2 n}[/math]
Доказательство:
[math]\triangleright[/math]

Так как [math]X_1 X_2 \ldots X_n[/math] — одинаково распределенные и принимают значения из множества [math]\{0, 1\}[/math]:

[math]{P}(X_i = 1) = p[/math]

[math]{P}{(X_i = 0) = 1 - p = q}[/math]

[math]{E} X_i = p[/math]


Пусть [math]\bar{X_i} = X_i - p[/math], тогда [math]{E}\bar{X_i} = 0[/math]

Преобразуем выражение [math]{P} (\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m \geqslant \delta)[/math]. ([math]t[/math] — любое положительное число):

[math]{P}(\dfrac{1}{n}\sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m \geqslant \delta) = {P} (\dfrac{1}{n}\sum\limits_{i=1}^{n}\bar{X_i} \geqslant \delta) = {P}(e^{t\sum\limits_{i=1}^{n} \bar{X_i}} \geqslant e^{t \delta n})[/math]

Используем неравенство Маркова для оценки полученного выражения:

[math]{P}(e^{ t\sum\limits_{i=1}^{n}\bar{X_i}} \geqslant e^{t \delta n}) \leqslant \dfrac{{E} (e^{ t\sum\limits_{i=1}^{n}\bar{X_i}})}{e^{t \delta n}}[/math]

Матожидание можно преобразовать:

[math]{E} (e^{ t\sum\limits_{i=1}^{n}\bar{X_i}}) = \prod\limits_{i = 1}^{n}{E}(e^{t \bar{X_i}})[/math]

Оценим [math]{E}(e^{t \bar{X_i}})[/math] с учётом того, что [math]p \in [0, 1][/math]

[math]{E}(e^{t \bar{X_i}}) = p e^{tq} + qe^{-pt} \leqslant e ^ {\frac{t^2}{8}}[/math]

[math]{P}(e^{ t\sum\limits_{i=1}^{n}\bar{X_i}} \geqslant e^{t \delta n}) \leqslant \dfrac{e^{n\frac{t^2}{8}}}{e^{t \delta n}}[/math]

При [math]t = 4\delta[/math]: [math]\mathbb {P}(e^{ t\sum\limits_{i=1}^{n}\bar{X_i}} \geqslant e^{t \delta n}) \leqslant e^{-2 \delta^2 n}[/math]

Аналогично доказывается, что: [math]{P} (\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m \leqslant -\delta) \leqslant e^{-2 \delta^2 n}[/math]

Таким образом: [math]{P} (|\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m| \geqslant \delta) \leqslant 2e^{-2 \delta ^2 n}[/math]
[math]\triangleleft[/math]

Пример

Граница Чернова используется, когда нужно оценить вероятность того, что сумма одинаково распределенных событий будет отличаться от матожидания этой суммы больше чем на [math]\delta[/math]

Пусть монетку подбросили 1000 раз. Оценить вероятность того, что выпало больше 550 орлов.

[math]m = {E} \sum\limits_{i=1}^{n} X_i = n{E} X_i = \dfrac{n}{2}[/math]

[math]\delta = \dfrac{1}{20}[/math]

[math]{P} (|\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{2}| \geqslant \dfrac{1}{20}) \leqslant 2e^{-2 \dfrac{1000}{400}} = 2e^{-5}[/math]

См. также

Источники информации