89
правок
Изменения
Нет описания правки
}}
==Неравенство и его доказательствоАбсолютная оценка==
{{Теорема
| id = thChernov
| about = Граница Чернова(аддитивная форма)
| statement = Пусть даны <tex>X_1 X_2 \ldots X_n</tex> {{---}} одинаково распределенные независимые случайные величины, принимающие значения из множества <tex>\{0, 1\}</tex>,
}}
== Пример Относительная оценка ==Граница Чернова используется, когда нужно оценить вероятность того, что сумма одинаково распределенных событий будет отличаться от матожидания этой суммы больше чем на <tex>\delta</tex> Пусть монетку подбросили 1000 раз. Оценить вероятность того, что выпало больше 550 орлов.
{{Определение |definition = '''Производящая функция моментов''' (англ. ''moment-generating function'') случайной величины <tex>m = X</tex> {{E---}} функция из <tex>\summathbb R</tex> в <tex>\limits_{imathbb R</tex>, определяемая как: <br><tex>M_x(t) =1}^{n} X_i = n</tex> <tex>{E} X_i = \dfrac{n}(e^{2tX})</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 + \delta cdots = </tex> <tex>\sum\limits_{1}^{\infty} \dfrac{1}{20i!} {E}(X^i)</tex> <br>Величина <tex>{E}(X^i)</tex> называется '''моментом''' (англ. ''moment'') случайной величины <tex>X</tex>.}}
{{Лемма|id=lemma1 |statement= <tex>X</tex>, <tex>Y</tex> {{---}} независимые случайные величины, тогда:<br><tex>{E}(e^{tX}e^{tY}) = {E}(e^{tX}){E}(e^{tY})</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>{E}e^{t X} \leqslant e^{p(e^t - 1)}</tex>}} {{Теорема| id = thChernov| about = Граница Чернова (мультипликативная форма)|statement = Пусть даны <tex>X_1 X_2 \dfracldots X_n</tex> {{---}} независимые случайные величины, принимающие значения из множества <tex>\{0, 1\}</tex>, <tex>{P}(X_i = 1) = p</tex>, <tex>{P}{n(X_i = 0) = 1 - p} </tex> <tex>X = \sum\limits_sum_{i=1}^{n} X_i </tex> <tex>m = {E}X = np</tex> Тогда: <tex>{P} (X \geqslant (1 + \delta)m) \leqslant e^{- \dfracfrac{\delta^2}{2 + \delta}m }</tex>, для <tex>\delta > 0</tex><tex>{P} (X \leqslant (1- \delta)m) \leqslant e^{- \frac{\delta^2}{2}m }</tex>, для <tex>0 < \delta < 1</tex>| proof = По [[Неравенство Маркова| неравенству Маркова]]:<tex>{P}(x \geqslant a) =</tex> <tex>{P}(e^x \geqslant e^a) \leqslant </tex> <tex>\dfrac{{E}(e^tX)}{e^a}</tex> Воспользуемся [[#lemma1|первой]] и [[#lemma2|второй]] леммами: <tex>\dfrac{{E}(e^tX)}{e^a} \leqslant</tex> <tex>\dfrac{\prod\limits{i = 1}{n}e^{p(e^t - 1)}}{e^{a}} =</tex> <tex>\dfrac{e^{(e^t - 1)\sum\limits{i = 1}{n}p}}{e^{a}}</tex> Заметим, что <tex>\sum\limits{i = 1}{20n}p = m</tex>, кроме того <tex>a = (1 + \delta)m</tex> (по замене). <tex>\dfrac{e^{(e^t - 1) \leqslant 2esum\limits{i = 1}{n}}}{e^{a}} = </tex> <tex>e^{m(e^t - 1 - t - t\delta)}</tex> Функция <tex>e^{m(e^t -1 - t - t\delta)}</tex> принимает своё минимальное значение в точке <tex>t = \ln (1 + \delta)</tex> Воспользуемся неравенством (<tex>x > 0</tex>): <tex>\ln(1 + x) \geqslant \dfrac{x}{1 + x^2 }</tex>, для оценки выражения <tex>m(\delta - (1 + \delta)\ln(1 + \delta))</tex>: <tex>m(\delta - (1 + \delta)\ln(1 + \delta)) \leqslant</tex> <tex>- \dfrac{1000\delta^2}{4002 + \delta}m</tex> Отсюда: <tex>{P} = 2e(X \geqslant (1 + \delta)m) \leqslant e^{-5\frac{\delta^2}{2 + \delta}m }</tex>, для <tex>\delta > 0</tex> Второе неравенство доказывается аналогично. }}
== См. также ==
* [[Неравенство Маркова]]
* [[Математическое ожидание случайной величины]]
== Источники информации ==
* [https://www.lektorium.tv/lecture/12871 Лекториум CS-центра {{---}} Лекция Дмитрия Ицыксона]
* [https://en.wikipedia.org/wiki/Chernoff_bound Wikipedia {{---}} Chernoff bound]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория вероятности]]
