Изменения

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

Честную монету подбросили <tex>1000</tex> раз. Оценим вероятность тогоГраница Чернова даёт намного более точную оценку, что выпало больше <tex>550</tex> орлов с помощью [[Неравенство Маркова#Неравенство чем неравенство Чебышева | неравенства Чебышева]] и [[Граница Чернова#Относительная оценка | мультипликативной формы границы Чернова]].

Пусть честную монету подбросили <tex>XN</tex> раз. Оценим вероятность того, что сумма бросков <tex>S</tex> отклонилась от матожидания больше, чем на <tex>\delta = \sqrt{\dfrac{\ln N}{---N}} сумма результатов бросков.</tex> с помощью [[Неравенство Маркова#Неравенство Чебышева | неравенства Чебышева]] и [[Граница Чернова#Абсолютная оценка | аддитивной формы границы Чернова]]

По неравенству Чебышева: <tex>P(|\dfrac{XS}{1000N} - \dfrac{1}{2}| \geqslant \delta) \leqslant \dfrac{111}{104N\delta^2}) \leqslant = \dfrac{1211}{4004\ln n}</tex>

Оценка границей Чернова: <tex>P(X |\geqslant (1 + dfrac{S}{N} - \dfrac{1}{102}) | \geqslant \cdot 500delta) \leqslant e2e^{-2N\dfrac{50}{21}delta^2} \approx = \dfrac{12}{100N^2}</tex>

==Применение==Оценка границей Чернова используется в решении проблем уравновешивания множеств <ref>[https://en.wikipedia.org/wiki/Set_balancing Wikipedia {{---}} Set balancing]</ref> и маршрутизации пакетов в разреженных сетях. Задача уравновешивания двух множеств возникает при планировании статистических экспериментов. Обычно при планировании эксперимента известны свойства каждого участника, задача состоит в том, чтобы разделить участников на две группы: контрольную и тестовую, так, чтобы каждое свойство было как можно более сбалансированно между двумя группами.  Граница Чернова даёт намного более точную оценкуиспользуется в теории вычислительного обучения для оценки того, что алгоритм с большой вероятностью имеет небольшую ошибку на достаточно большом наборе обучающих данных.