1632
правки
Изменения
м
== Примечания ==
rollbackEdits.php mass rollback
Тогда:
<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 X \geqslant a) =</tex> <tex>{P}(e^x {tX} \geqslant e^a{ta}) \leqslant </tex> <tex>\dfrac{{E}(e^{tX})}{e^a{ta}}</tex>
Воспользуемся [[#lemma1|леммой о производящей функции моментов суммы случайных величин ]] и [[#lemma2|леммой об ограниченности производящей функции моментов]]:
<tex>\dfrac{{E}(e^{tX})}{e^a{ta}} \leqslant</tex> <tex>\dfrac{\prod\limits_{i = 1}^{n}e^{p(e^t - 1)}}{e^{ata}} =</tex> <tex>\dfrac{e^{(e^t - 1)\sum\limits_{i = 1}^{n}p}}{e^{ata}}</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^{ata}} = </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>N</tex> раз. Оценим вероятность того, что сумма бросков <tex>S</tex> отклонилась от матожидания больше, чем на <tex>\delta = \sqrt{\dfrac{\ln N}{N}}</tex> с помощью [[Неравенство Маркова#Неравенство Чебышева | неравенства Чебышева]] и [[Граница Чернова#Абсолютная оценка | аддитивной формы границы Чернова]]
По неравенству Чебышева: <tex>P(|\dfrac{S}{N} - \dfrac{1}{2}| \geqslant \delta) \leqslant \dfrac{1}{4N\delta^2} = \dfrac{1}{4\ln nN}</tex>
Оценка границей Чернова: <tex>P(|\dfrac{S}{N} - \dfrac{1}{2}| \geqslant \delta) \leqslant 2e^{-2N\delta^2} = \dfrac{2}{N^2}</tex>
==Применение==
Оценка границей Чернова используется в решении проблем уравновешивания множеств <ref>[https://en.wikipedia.org/wiki/Set_balancing Wikipedia {{{---}}} Set balancing]</ref> и маршрутизации пакетов в разреженных сетях.<ref>Michael Mitzenmacher, Eli Upfal. «Probability and Computing: Randomized Algorithms and Probabilistic Analysis» {{---}} «Cambridge University Press», 2005 г. {{---}} 72-83 стр. {{---}} ISBN 0-521-835540-2</ref>
Задача уравновешивания двух множеств возникает при планировании статистических экспериментов. Обычно при планировании эксперимента известны свойства каждого участника, задача состоит в том, чтобы разделить участников на две группы: контрольную и тестовую, так, чтобы каждое свойство было как можно более сбалансированно между двумя группами. <ref>Michael Mitzenmacher, Eli Upfal. «Probability and Computing: Randomized Algorithms and Probabilistic Analysis» {{---}} «Cambridge University Press», 2005 г. {{---}} 71-72 стр. {{---}} ISBN 0-521-835540-2</ref>
Граница Чернова используется в теории вычислительного обучения для оценки того, что алгоритм с большой вероятностью имеет небольшую ошибку на достаточно большом наборе обучающих данных<ref>M. Kearns, U. Vazirani. «An Introduction to Computational Learning Theory» {{---}} «MIT Press», 1994 г. {{---}} 190-192 стр. {{---}} ISBN 0-262-11193-4</ref>
== См. также ==
* [[Математическое ожидание случайной величины]]
== Примечания ==
<references/>
== Источники информации ==
* [https://www.lektorium.tv/lecture/12871 Лекториум CS-центра {{---}} Лекция Дмитрия Ицыксона]
* [https://en.wikipedia.org/wiki/Chernoff_bound Wikipedia {{---}} Chernoff bound]
* Michael Mitzenmacher, Eli Upfal. «Probability and Computing: Randomized Algorithms and Probabilistic Analysis» {{---}} «Cambridge University Press», 2005 г. {{---}} 61-83 стр. {{---}} ISBN 0-521-83540-2
* M. Kearns, U. Vazirani. «An Introduction to Computational Learning Theory» {{---}} «MIT Press», 1994 г. {{---}} 190-192 стр. {{---}} ISBN 0-262-11193-4
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория вероятности]]
