d1-d5 11 hours ago

Невероятные события: насколько корректен размер выборки?

6 min

856

Mathematics * Popular scienceStatistics in IT

Review

Недавно я написал статью про Закон Больших Чисел. Мы начали с такого вопроса

Бросим монетку тысячу раз и посчитаем, сколько выпало орлов. Странно ожидать, что выпадет ровно 500, но какое отклонение от этого числа типично?
Например, если зафиксировать конкретное отклонение, какова вероятность, что оно произойдёт? Если наоборот зафиксировать вероятность, то каким должно быть отклонение? И, наконец, если заданы и вероятность, и отклонение, то сколько раз надо бросать монетку, чтобы с заданной вероятностью попасть в эти рамки?

Суть ЗБЧ — в возможности оценить вероятность отклонений. Мы это делали с помощью неравенства Чебышёва. Оно говорит: отклонение на 100 и более орлов происходит не чаще, чем в 2,5% случаев. Мне стало интересно, насколько эта граница близка к правде

Я решил проверить это с помощью моделирования.

Сначала запустил 100 экспериментов — ни одного такого исхода.

Увеличил число до 1000 — снова ноль. Даже при 100 000 результат не изменился!

Очевидно, оценка Чебышёва слишком грубая. Но какова настоящая вероятность? И можно ли придумать простую, но при этом точную границу для таких редких событий?

Оказывается, что реальная вероятность не превосходит $5 \times 10^{-9}$ — катастрофически меньше, чем 2,5% из оценки Чебышёва. Именно это стало поводом для написания статьи.

Связь с Центральной Предельной Теоремой

Гистограмма сразу наводит на мысль о кривой Гаусса — как и предсказывает ЦПТ. Это позволяет оценить вероятность отклонения, заменив распределение на нормальное. Но у такого подхода есть минусы.

ЦПТ — довольно тяжёлый результат, к которому мы ещё только подбираемся. Эта статья — один из шагов на этом пути.
Использовать нормальное распределение для оценок не очень удобно. Его вероятность отклонения — функция ошибок — не выражается через элементарные функции и ее саму надо как-то оценивать.
А главное — ЦПТ работает только при больших и не даёт точной границы для конкретного числа испытаний. А мы хотим получить оценку, которая будет работать всегда — и для тысячи бросков, и для пяти.

Статья устроена следующим образом:

Сначала мы экспериментально проверим, что вероятность больших отклонений убывает куда быстрее, чем следует из Чебышёва — и предскажем зависимость.
После этого выведем ее строго. Для этого мы воспользуемся очень важным приемом — оценкой Чернова — который очень похож на неравенство Чебышёва: надо применить неравенство Маркова, но не к квадрату, а к экспоненте случайной величины.
В финале мы воспользуемся нашей оценкой чтобы ответить на вопросы из начала статьи.

У экспоненциальных неравенств есть далекие обобщения (неравенство Хёффдинга, Азумы, МакДиамида), в том числе для ситуаций, где не работает Центральная Предельная Теорема.

Такие оценки широко используются в прикладной математике — для анализа эффективности алгоритмов, оценки точности прогнозов, управления редкими событиями, планирования экспериментов и надёжной работы сложных систем.
В этих задачах важно заранее знать, сколько испытаний нужно провести, чтобы частота с заданной вероятностью и точностью приблизилась к истинной вероятности.
Например, это используется для расчёта необходимого числа наблюдений, достаточных чтобы с заданной вероятностью обнаружить статистически значимое отклонение. Зная допустимую вероятность ошибки и величину эффекта, можно заранее понять, сколько данных нужно собрать, чтобы выводы были обоснованными.
Разница между прогнозами, которые дают неравенство Чебышёва и экспоненциальные оценки, может быть колоссальной!

Но сегодня мы сосредоточимся на простейшем случае — симметричной монетке. Это удобная тренировочная площадка, на которой можно шаг за шагом пройти путь от экспериментов до строгого доказательства — и увидеть, как работают эти методы изнутри.

Этот текст — продолжение статьи о Законе Больших Чисел, но её можно читать и отдельно. Больше моих текстов в канале Кроссворд Тьюринга. Там вы найдете короткую шпаргалку с изложением результатов статьи

Как оценить вероятность?

Обозначим за число орлов за бросков. Рассмотрим вероятность

$p_n(\varepsilon) = \mathbb{P}\!\left(\frac{S_n}{n} - \frac12 \ge \varepsilon\right).$

Например, вероятность, о которой мы говорили во введении, равна

$\mathbb{P}\left(\left| {S_{1000}} - 500 \right| \ge 100 \right) = \mathbb{P}\!\left(\left|\frac{S_{1000}}{1000} - \frac12\right| \ge 0.1 \right) = 2\, p_{1000}(0.1).$

Так как дисперсия монетки равна , неравенство Чебышёва дает $p_n(\varepsilon) \le 1/(8 n \varepsilon^2).$

Как мы видели, оценка из неравенства Чебышева далека от идеала. Мы хотим придумать гораздо более точную оценку значений $p_n(\varepsilon)$ для каждого и $\varepsilon$ .

Нормировка

Мы хотим посмотреть на графики $p_n(\varepsilon)$ . Чтобы сравнивать результаты для разных на одном графике, нужно их отнормировать. Как это сделать? Как наша оценка зависит от ?

Эксперимент и простые оценки (дисперсия , неравенство Чебышёва) показывают: с хорошей точностью $p_n(\varepsilon)$ определяется не и $\varepsilon$ по отдельности, а $\eta = \varepsilon^2 n$ .

Это статистический принцип:

Чтобы увеличить точность в раз, нужно примерно в раз больше испытаний.

Мы будем искать оценку, которая зависит только от $\eta$ . Это упрощение делает оценку чуть более грубой, но взамен мы получаем короткое неравенство, которое легко применять.

Эксперименты

Построим графики $p_n(\eta)$ для нескольких и сравним их с оценкой Чебышёва $1/(8\eta)$ .

Видно, что частоты убывают экспоненциально, гораздо быстрее гиперболы. В любом масштабе на одном графике их адекватно изобразить не получаются.

Чтобы лучше увидеть структуру, вместо $p_n(\eta)$ рассмотрим $-\log p_n(\eta)$ . Теперь почти ложатся на одну прямую. Поскольку $-\log$ — убывающая функция, нижняя граница для него даёт верхнюю границу для $p_n(\eta)$ .

Самое простое приближение здесь — линейная функция через начало координат: $-\log p_n(\eta) \ge 2\eta$ .

Эксперимент показывает, что эта оценка действительно выполняется, а значит:

$p_n(\varepsilon) < \exp(-2 \varepsilon^2 n).$

В следующем разделе мы строго докажем эту оценку обсудим ее обобщения.

Неравенство Хёффдинга

Метод Чернова

Начнем с ключевой идеи, которая полезная сама по себе.

Вместо того чтобы оценивать вероятность через квадрат отклонения (как в Чебышёве), мы будем использовать показательную функцию.

Эта идея принадлежит математику Герману Чернову, который ещё в середине XX века применил ее для анализа «хвостов» распределений. Она оказалась весьма плодотворной.

Недавно Чернову испольнолось 102 года, но он продолжает преподавать в MIT

Обозначим отклонение среднего числа орлов от за $\Delta = {S_n}/{n} - 1/2.$ Выберём $\lambda>0$ и перепишем условие $\Delta \ge \varepsilon$ как $e^{\lambda \Delta } \ge e^{\lambda n \varepsilon}.$ Применим неравенство Маркова

$\mathbb{P}(\Delta \ge \varepsilon) \le \frac{\mathbb{E}\,e^{\lambda \Delta }}{e^{\lambda \varepsilon}}.$

Выражение $\mathbb{E}e^{\lambda \Delta}$ можно посчитать явно. Для этого понадобится гиперболический косинус

$\cosh x = \frac{e^x + e^{-x}}{2}.$

Прямое вычисление показывает, что $\mathbb{E} e^{\lambda \Delta} = \bigl(\cosh(\lambda/2)\bigr)^n.$

Откуда берется последнее равенство

Введём $Y_i = X_i - \tfrac12$ . Тогда $\Delta = S_n - n/2 = Y_1+\cdots+Y_n$ .

Так как независимы, независимы и $e^{\lambda Y_i}$ . Поэтому

$\mathbb{E}\, [\Delta] = \mathbb{E}\, [e^{\lambda \sum Y_i}] = \mathbb{E} \left[\prod_{i=1}^n e^{\lambda Y_i}\right] = \prod_{i=1}^n \mathbb{E}\, [e^{\lambda Y_i}].$

Осталось найти $\mathbb{E}[e^{\lambda Y_i}]$ . Так как $Y_i = \pm 1/2$ с вероятностями ,

$\mathbb{E}\, e^{\lambda Y_i} = \frac{e^{\lambda/2} + e^{-\lambda/2}}{2} = \cosh(\lambda/2).$

Финальное доказательство

Мы получили, что для любого $\lambda > 0$ вероятность $p_n(\varepsilon)$ не превышает $\cosh(\lambda/2)^n / e^{\lambda n \varepsilon}$ . С гиперболическим косинусом напрямую работать сложно. Однако из разложения Тейлора

$\cosh x = \sum_{k=0}^\infty \frac{x^{2k}}{(2k)!} \;\le\; \sum_{k=0}^\infty \frac{x^{2k}}{2^k k!} = e^{x^2/2}.$

Подставляя неравенство $\cosh (\lambda/2) \le e^{\lambda^2/8}$ в оценку Чернова, получаем

$p_n(\varepsilon) \le \frac{e^{\lambda^2 n/8}}{e^{\lambda \varepsilon n}} = \exp\!\Big( \frac{\lambda^2}{8}n - \lambda \varepsilon n \Big).$

Выражение под знаком экспоненты квадратично по $\lambda$ , и достигает минимума при $\lambda = 4\varepsilon$ . Подставляя $\lambda = 4\varepsilon$ наконец получаем оценку, которую мы нашли экспериментально

$p_n(\varepsilon) \le 2 \exp(-2\varepsilon^2 n).$

Таким образом, мы получили простую и наглядную оценку, которая является частным случаем более общего неравенства Хёффдинга.

Неравенство Хёффдинга: Пусть $X_1,\dots,X_n$ — независимые случайные величины, такие что $a_i \le X_i \le b_i$ . Тогда для любого $\varepsilon > 0$

$\mathbb{P}\left( \frac{1}{n} \sum_{i=1}^n X_i - \mathbb{E}\!\left[\frac{1}{n} \sum_{i=1}^n X_i\right] \ge \varepsilon \right) \le \exp\!\left( - \frac{2n^2\varepsilon^2}{\sum_{i=1}^n (b_i-a_i)^2} \right).$

В нашем случае — индикаторы выпадения орла, и подстановка $a_i=0, \, b_i=1$ даёт именно ту экспоненциальную оценку, которую мы вывели.

От теории к практике

Теперь мы готовы вернуться к вопросам, которые поставили в начале. Имея в руках оценку

$p_n(\varepsilon) \le e^{-2n\varepsilon^2},$

мы можем вычислить, насколько малой окажется вероятность большого отклонения, или наоборот — какое отклонение допустимо при заданной вероятности и числе испытаний.

Посмотрим на несколько графиков.

На первом графике мы фиксируем число испытаний n = 1000 и спрашиваем: какое отклонение ε допустимо, если вероятность превышения этого отклонения не должна превышать заданное значение p?

Здесь видно, что при p = 40% допустимое отклонение около 0.020, при p = 30% — около 0.024, при p = 20% — около 0.028, при p = 10% — около 0.033, и при p = 5% — около 0.037.

На втором графике мы фиксируем отклонение ε = 0.035 и спрашиваем: как вероятность такого отклонения зависит от числа испытаний n?

Видно, что при увеличении числа испытаний вероятность быстро уменьшается: при n ≈ 400 она уже около 40%, при n ≈ 500 — около 30%, при n ≈ 660 — около 20%, а при n ≈ 940 падает до 10%.

В обоих случаях мы имеем дело не с реальными вероятностями, а с их верхними оценками по Хёффдингу. На практике отклонения могут быть даже реже.

Заключение

В этой статье мы начали с простого эксперимента с подбрасыванием монетки и вопроса о «типичных» отклонениях частоты от 50%. Чебышёв дал слишком грубую оценку, и мы пошли дальше — через метод Чернова вывели экспоненциальную границу, получив частный случай неравенства Хёффдинга.

Эта оценка достаточно точная, чтобы использовать её на практике: по ней легко планировать эксперименты, подбирая число испытаний под нужную точность или, наоборот, оценивая, какую точность можно гарантировать при заданных ресурсах. Разница с оценкой Чебышёва — колоссальная: в реальных задачах она может менять порядок величины требуемых данных.

Экспоненциальные неравенства — мощный инструмент, который позволяет ответить на конкретные прикладные вопросы.

Больше моих текстов в канале Кроссворд Тьюринга. Подписывайтесь!

Hubs: