В недавней статье про Закон больших чисел мы оценивали вероятность больших отклонений с помощью неравенства Чебышёва. Для тысячи бросков монетки оно даёт границу 2,5% для отклонения в 100 и более орлов. Мне стало интересно, насколько это близко к правде.
Я написал симуляцию и проверил — сначала на сотне прогонов, потом на тысяче, потом на ста тысячах. Ни одного такого исхода. Реальная вероятность оказалась меньше 5 ⋅ 10⁹ — катастрофически меньше, чем 2,5% из оценки Чебышёва. Именно это стало поводом для написания статьи.
Мы хотим понять, как связано число испытаний, отклонение и вероятность. Если зафиксировать отклонение, какова вероятность его превышения? Если зафиксировать вероятность, каким должно быть допустимое отклонение? И, наконец, если заданы и вероятность, и отклонение, то сколько испытаний нужно провести, чтобы с заданной вероятностью уложиться в эти рамки?
В этой статье мы начнём с эксперимента и дойдём до строгой экспоненциальной оценки, которая работает для любого числа испытаний. По дороге докажем оценку Чернова и выведем частный случай неравенства Хёффдинга и разберём, как они устроены.
Такие оценки широко используются в прикладной математике. Нам важно заранее знать, сколько испытаний провести, чтобы с частота с заданной точностью приблизилась к истинной вероятности события.
Например, для расчёта необходимого числа наблюдений, достаточных чтобы с заданной вероятностью обнаружить статистически значимое отклонение. Зная допустимую вероятность ошибки и величину эффекта, можно заранее понять, сколько данных нужно собрать, чтобы выводы были обоснованными.
Разница между прогнозами, которые дают неравенство Чебышёва и экспоненциальные оценки, может быть колоссальной!
К неравенству Хёффдинга