Изменения

{{Лемма|about=О производящей функции моментов суммы случайных величин|id= Граница Чернова lemma1 |statement=Если <tex>X =\sum\limits_{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\limits_{i=1}^{n} {X_i}}) = </tex> <tex>{E}( {\prod\limits_{i=1}^{n} {e^{t X_i}}}) =</tex> <tex>\prod\limits_{i=1}^{n} {{E}( {e^{t X_i}}}) =</tex> <tex> \prod\limits_{i=1}^{n} M_{X_i} (t)</tex>}}

{{ОпределениеЛемма |definition about= '''Граница Чернова''' Об ограниченности производящей функции моментов|id=lemma2 |statement= <tex>X</tex> {{---}} независимая случайная величина принимающая значения из множества <tex>\{0, 1\}</tex>, <tex>{P}(англ. ''Chernoff bound''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>npe^t + (1 - p) \cdot 1 =</tex> одинаково распределенных независимых случайных величин больше <tex>1 + p(или меньшеe^t - 1) некоторого значения.\leqslant e^{p(e^t - 1)}</tex>

| about = Граница Чернова(аддитивная форма)

<tex>m = \mathbb{E} \sum_sum\limits_{i=1}^{n} X_i</tex>,

<tex>\mathbb{P} (|\dfrac{1}{n} \sum_sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m| \geqslant \delta) \leqslant 2e^{-2 \delta ^2 n}</tex>

<tex>\mathbb {P}(X_i = 1) = p</tex>

<tex>\mathbb{P}{(X_i = 0) = 1 - p = q}</tex>

<tex>\mathbb {E} X_i = p</tex>

Пусть <tex>\bar{X_i} = X_i - p</tex>, тогда <tex>\mathbb {E}\bar{X_i} = 0</tex>

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

<tex>\mathbb{P}(\dfrac{1}{n}\sum_sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m \geqslant \delta) = \mathbb {P} (\dfrac{1}{n}\sum_sum\limits_{i=1}^{n}\bar{X_i} \geqslant \delta) = \mathbb {P}(e^{t\sum_sum\limits_{i=1}^{n} \bar{X_i}} \geqslant e^{t \delta n})</tex>

<tex>\mathbb {P}(e^{ t\sum_sum\limits_{i=1}^{n}\bar{X_i}} \geqslant e^{t \delta n}) \leqslant \dfrac{\mathbb{E} (e^{ t\sum_sum\limits_{i=1}^{n}\bar{X_i}})}{e^{t \delta n}}</tex>

[[Математическое ожидание случайной величины| Матожидание]] можно преобразоватьпо :

<tex>\mathbb{E} (e^{ t\sum_sum\limits_{i=1}^{n}\bar{X_i}}) = </tex> <tex>{E}(\prod\prod_limits_{i = 1}^{n}{e^{\bar{X_i}}}) = </tex> <tex>\prod\mathbblimits_{i = 1}^{n}{E}(e^{t \bar{X_i}})</tex>

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

<tex>\mathbb{E}(e^{t \bar{X_i}}) = </tex> <tex>p e^{tq} + qe^{-pt} \leqslant e ^ {\frac{t^2}{8}}</tex>

<tex>\mathbb {P}(e^{ t\sum_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>\mathbb {P}(e^{ t\sum_sum\limits_{i=1}^{n}\bar{X_i}} \geqslant e^{t \delta n}) \leqslant e^{-2 \delta^2 n}</tex> Аналогично доказывается, что: <tex>{P} (\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m \leqslant -\delta) \leqslant e^{-2 \delta^2 n}</tex> Таким образом: <tex>{P} (|\dfrac{1}{n} \sum\limits_{i=1}^{n} X_i - \dfrac{1}{n} m| \geqslant \delta) \leqslant 2e^{-2 \delta ^2 n}</tex>}} == Относительная оценка == {{Теорема| id = thChernov| about = Граница Чернова (мультипликативная форма)| statement = Пусть даны <tex>X_1 X_2 \ldots X_n</tex> {{---}} независимые случайные величины, принимающие значения из множества <tex>\{0, 1\}</tex>, <tex>{P}(X_i = 1) = p</tex>, <tex>{P}{(X_i = 0) = 1 - p}</tex> <tex>X = \sum\limits_{i=1}^{n} X_i</tex> <tex>m = {E}X = np</tex> Тогда: <tex>{P} (X \geqslant (1 + \delta)m) \leqslant e^{m(\delta - (1 + \delta)\ln(1 + \delta))} \leqslant e^{- \frac{\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^{tX} \geqslant e^{ta}) \leqslant </tex> <tex>\dfrac{{E}(e^{tX})}{e^{ta}}</tex> Воспользуемся [[#lemma1|леммой о производящей функции моментов суммы случайных величин ]] и [[#lemma2|леммой об ограниченности производящей функции моментов]]: <tex>\dfrac{{E}(e^{tX})}{e^{ta}} \leqslant</tex> <tex>\dfrac{\prod\limits_{i = 1}^{n}e^{p(e^t - 1)}}{e^{ta}} =</tex> <tex>\dfrac{e^{(e^t - 1)\sum\limits_{i = 1}^{n}p}}{e^{ta}}</tex>  Заметим, что <tex>\sum\limits_{i = 1}^{n} p = m</tex>, кроме того <tex>a = (1 + \delta)m</tex> (по замене). <tex>\dfrac{e^{(e^t - 1)\sum\limits_{i = 1}^{n}p}}{e^{ta}} = </tex> <tex>e^{m(e^t - 1 - t - t\delta)}</tex>

Аналогично доказывается, что: Функция <tex>\mathbbe^{P} m(\dfrac{1}{n} \sum_{i=1}e^{n} X_i t - \dfrac{1}{n} m \leqslant -t - t\delta) }</tex> принимает своё минимальное значение в точке <tex>t = \leqslant e^{-2 ln (1 + \delta^2 n})</tex>

Таким образомВоспользуемся неравенством (<tex>x > 0</tex>): <tex>\mathbb{P} ln(|1 + x) \geqslant \dfrac{1x}{n1 + x^2} </tex>, для оценки выражения <tex>m(\delta - (1 + \delta)\ln(1 + \delta))</tex>: <tex>m(\delta - (1 + \delta)\sum_{i=ln(1}^{n} X_i + \delta)) \leqslant</tex> <tex>- \dfrac{1\delta^2}{n2 + \delta} m| </tex> Отсюда: <tex>{P} (X \geqslant (1 + \delta)m) \leqslant 2ee^{-2 \frac{\delta ^2 n}{2 + \delta}m }</tex>, для <tex>\delta > 0</tex> Второе неравенство доказывается аналогично.

== Пример Сравнение с оценкой неравенством Чебышева==

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

Пусть честную монету подбросили <tex>m N</tex> раз. Оценим вероятность того, что сумма бросков <tex>S</tex> отклонилась от матожидания больше, чем на <tex>\delta = \mathbbsqrt{E} \sum_dfrac{i=1}^{n} X_i = n\mathbb{Eln N} X_i = \dfrac{nN}{2}</tex>с помощью [[Неравенство Маркова#Неравенство Чебышева | неравенства Чебышева]] и [[Граница Чернова#Абсолютная оценка | аддитивной формы границы Чернова]]

По неравенству Чебышева: <tex>P(|\dfrac{S}{N} - \dfrac{1}{2}| \geqslant \delta) \leqslant \dfrac{1}{4N\delta ^2} = \dfrac{1}{204\ln N}</tex>

Оценка границей Чернова: <tex>\mathbb{P} (|\dfrac{1}{n} \sum_{i=1S}^{nN} X_i - \dfrac{1}{2}| \geqslant \dfrac{1}{20}delta) \leqslant 2e^{-2N\delta^2 } = \dfrac{10002}{400}N^2} </tex> ==Применение== 2e^Оценка границей Чернова используется в решении проблем уравновешивания множеств <ref>[https://en.wikipedia.org/wiki/Set_balancing Wikipedia {{-5--}} Set balancing]</texref>и маршрутизации пакетов в разреженных сетях. Задача уравновешивания двух множеств возникает при планировании статистических экспериментов. Обычно при планировании эксперимента известны свойства каждого участника, задача состоит в том, чтобы разделить участников на две группы: контрольную и тестовую, так, чтобы каждое свойство было как можно более сбалансированно между двумя группами.  Граница Чернова используется в теории вычислительного обучения для оценки того, что алгоритм с большой вероятностью имеет небольшую ошибку на достаточно большом наборе обучающих данных.