Граница Чернова
Версия от 19:42, 24 апреля 2019; DespairedController (обсуждение | вклад)
Определение: |
Граница Чернова (англ. Chernoff bound) дает оценку вероятности того, что сумма n одинаково распределенных независимых случайных величин больше (или меньше) некоторого значения. |
Производящая функция моментов
Определение: |
Производящая функция моментов (англ. moment-generating function) случайной величины
| — функция из в и определяется как:
Лемма (О производящей функции моментов суммы случайных величин): |
Если , где — независимые случайные величины, то: |
Доказательство: |
Лемма (Об ограниченности производящей функции моментов): |
Доказательство: |
Абсолютная оценка
Теорема (Граница Чернова (аддитивная форма)): |
Пусть даны — одинаково распределенные независимые случайные величины, принимающие значения из множества ,
, Тогда: |
Доказательство: |
Так как — одинаково распределенные и принимают значения из множества :
Преобразуем выражение . ( — любое положительное число):
Используем неравенство Маркова для оценки полученного выражения:
Матожидание можно преобразовать по :
Оценим с учётом того, что
При :Аналогично доказывается, что: Таким образом: |
Относительная оценка
Теорема (Граница Чернова (мультипликативная форма)): |
Пусть даны — независимые случайные величины, принимающие значения из множества , ,
Тогда: , для , для |
Доказательство: |
Воспользуемся леммой о производящей функции моментов суммы случайных величин и леммой об ограниченности производящей функции моментов:
Заметим, что , кроме того (по замене).
Функция принимает своё минимальное значение в точкеВоспользуемся неравенством ( ): , для оценки выражения :
Отсюда: Второе неравенство доказывается аналогично. , для |
Пример
Честную монету подбросили неравенства Чебышева и мультипликативной формы границы Чернова
раз. Оценим вероятность того, что выпало больше орлов с помощьюПусть
— сумма результатов бросков.По неравенству Чебышева:
Оценка границей Чернова:
Граница Чернова даёт намного более точную оценку.