89
правок
Изменения
Нет описания правки
Оценка границей Чернова: <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>
== См. также ==
* [https://en.wikipedia.org/wiki/Chernoff_bound Wikipedia {{---}} Chernoff bound]
== Примечания ==
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория вероятности]]
