89
правок
Изменения
Нет описания правки
{{Определение
|definition = '''Граница Чернова''' (англ. ''Chernoff bound'') дает оценку вероятности того, что сумма n одинаково распределенных независимых случайных величин больше (или меньше) некоторого значения.
}}
==Некоторые вспомогательные определения и леммы==
{{Определение
|definition = '''Производящая функция моментов''' (англ. ''moment-generating function'') случайной величины <tex>X</tex> {{---}} функция из <tex>\mathbb R</tex> в <tex>\mathbb R</tex>, определяемая как: <br>
<tex>M_x(t) =</tex> <tex>{E}(e^{tX})</tex>.
}}
{{Определение
|definition = Распишем производящую функцию моментов по формуле Тейлора: <br>
<tex>M_x(t) =</tex> <tex>{E}(e^{tX}) =</tex> <tex>{E}(1 + tX + \dfrac{1}{2}t^2 X^2 + \cdots + \dfrac{1}{n!}t^n X^n + \cdots =</tex> <tex>\sum\limits_{1}^{\infty} \dfrac{1}{i!} {E}(X^i)</tex> <br>
Величина <tex>{E}(X^i)</tex> называется '''моментом''' (англ. ''moment'') случайной величины <tex>X</tex>.
}}
{{Лемма
|id=lemma1
|statement= Если <tex>X = \sum_{i=1}^{n} X_i</tex>, где <tex>X_1 X_2 \cdots X_n</tex> {{---}} независимые случайные величины, то:<br>
<tex>M_X(t) =</tex><tex> \prod\limits_{i=1}^{n} M_{X_i} (t)</tex>
|proof= <tex>M_X(t) =</tex> <tex>{E}(e^{tX}) =</tex> <tex>{E}(e^{t \sum_{i=1}^{n} {X_i}}) = </tex> <tex>{E}( {\prod_{i=1}^{n} {e^{t X_i}}}) =</tex> <tex>\prod_{i=1}^{n} {{E}( {e^{t X_i}}}) =</tex> <tex> \prod\limits_{i=1}^{n} M_{X_i} (t)</tex>
}}
{{Лемма
|id=lemma2
|statement= <tex>X</tex> {{---}} независимая случайная величина принимающая значения из множества <tex>\{0, 1\}</tex>, <tex>{P}(X = 1) = p</tex>, <tex>{P}{(X = 0) = 1 - p}</tex>, тогда для любого <tex>t \in \mathbb{R}</tex>: <br>
<tex>M_X(t) =</tex><tex>{E}e^{t X} \leqslant e^{p(e^t - 1)}</tex>
|proof= <tex>M_X(t) =</tex> <tex>{E}e^{t X} = </tex> <tex>pe^t + (1 - p) \cdot 1 =</tex> <tex>1 + p(e^t - 1) \leqslant e^{p(e^t - 1)}</tex>
}}
<tex>{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}}</tex>
[[Математическое ожидание случайной величины| Матожидание]] можно преобразоватьпо :
<tex>{E} (e^{ t\sum\limits_{i=1}^{n}\bar{X_i}}) = </tex> <tex>{E}(\prod\limits_{i = 1}{n}{e^{\bar{X_i}}}) = </tex> <tex>\prod\limits_{i = 1}^{n}{E}(e^{t \bar{X_i}})</tex>
Оценим <tex>{E}(e^{t \bar{X_i}})</tex> с учётом того, что <tex>p \in [0, 1]</tex>
<tex>{E}(e^{t \bar{X_i}}) = </tex> <tex>p e^{tq} + qe^{-pt} \leqslant e ^ {\frac{t^2}{8}}</tex>
<tex>{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}}</tex>
== Относительная оценка ==
{{Теорема
Второе неравенство доказывается аналогично.
}}
==Пример==
Честную монету подбросили <tex>1000</tex> раз. Оценим вероятность того, что выпало больше <tex>550</tex> орлов с помощью [[Неравенство Маркова#Неравенство Чебышева | неравенства Чебышева]] и [[Граница Чернова#Относительная оценка | мультипликативной формы границы Чернова]]
Пусть <tex>X</tex> {{---}} сумма результатов бросков.
По неравенству Чебышева: <tex>P(|\dfrac{X}{1000} - \dfrac{1}{2}| \geqslant \dfrac{11}{10}) \leqslant \dfrac{121}{400}</tex>
Оценка границей Чернова: <tex>P(X \geqslant (1 + \dfrac{1}{10}) \cdot 500) \leqslant e^{-\dfrac{50}{21}} \approx \dfrac{1}{100}</tex>
Граница Чернова даёт намного более точную оценку.
== См. также ==
