Закон больших чисел

Вводная заметка показала, как доля орлов в бросках монеты приближается к половине, и назвала вероятность частотой в длинной серии испытаний. Закон больших чисел превращает это наблюдение в теорему: среднее независимых копий случайной величины сходится к её математическому ожиданию. Именно он делает вероятность измеримой, валидационный результат — осмысленным, а симуляцию — методом вычислений. В этой заметке мы формулируем закон в двух формах, объясняем два вида сходимости, которые они используют, и превращаем закон в метод Монте-Карло.

Обозначения. $X_1, X_2, \dots$ — н.о.р. величины со средним $\mu$ (и, где это нужно, дисперсией $\sigma^2$); $\bar X_n = (X_1 + \dots + X_n)/n$. Событие происходит почти наверное (almost surely), если его вероятность равна 1.

Слабый закон#

Для любого $\varepsilon > 0$

$$P\big(\lvert \bar X_n - \mu \rvert \ge \varepsilon\big) \to 0 \quad \text{при } n \to \infty .$$

Среднее сходится по вероятности (converges in probability) к $\mu$: при большом $n$ отклонение любого фиксированного размера маловероятно. При конечной дисперсии доказательство занимает одну строку предыдущей заметки: неравенство Чебышёва ограничивает вероятность величиной $\sigma^2/(n\varepsilon^2)$. Хинчин показал, что достаточно конечного среднего, без каких-либо предположений о дисперсии.

Усиленный закон#

Слабый закон говорит об одном большом $n$ за раз. Он оставляет открытым вопрос, не может ли конкретная бесконечная последовательность бросков вечно совершать отклонения от среднего — всё более редкие, но не прекращающиеся. Усиленный закон (strong law) это исключает:

$$P\big(\bar X_n \to \mu\big) = 1 .$$

Среднее сходится почти наверное: с вероятностью 1 последовательность средних как числовая последовательность имеет предел $\mu$. Колмогоров доказал это при том же предположении, что и Хинчин, — конечном среднем. Из сходимости почти наверное следует сходимость по вероятности, но не наоборот.

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

Леммы Бореля–Кантелли#

Дополнительный материал: инструмент, который различает два вида сходимости, и идея простейшего доказательства усиленного закона. Остальная часть заметки на него не опирается.

Разницу легче всего увидеть на индикаторах. Пусть $A_1, A_2, \dots$ — независимые события и $X_n = \mathbb 1_{A_n}$. Если $P(A_n) \to 0$, то $X_n \to 0$ по вероятности. Сходится ли $X_n \to 0$ почти наверное, т. е. перестают ли события в конце концов происходить, решают леммы Бореля–Кантелли (Borel–Cantelli lemmas): если $\sum_n P(A_n) < \infty$, то почти наверное происходит лишь конечное число событий $A_n$; если события независимы и $\sum_n P(A_n) = \infty$, то почти наверное их происходит бесконечно много.

Рисунок

Сходимость по вероятности и почти наверное

При $P(A_n) = 1/n$ ожидаемое число событий до $10^5$ равно $1 + \frac12 + \dots + \frac{1}{10^5} \approx 12.1$, и они не прекращаются: вероятность хотя бы одного события между $10^4$ и $10^5$ равна $1 - \frac{10^4}{10^5} = 0.9$. При $P(A_n) = 1/n^2$ ожидаемое общее число равно $\pi^2/6 \approx 1.64$, и почти всё оно приходится на первые шаги. Простейшее доказательство усиленного закона применяет первую лемму к событиям $\{\lvert \bar X_n - \mu \rvert \ge \varepsilon\}$, вероятности которых убывают достаточно быстро, если хвосты распределения достаточно лёгкие, например при конечном четвёртом моменте; если конечно только среднее, доказательство требует более тонкого рассуждения.

Оценка методом Монте-Карло#

Интегралы становятся математическими ожиданиями, если выбрать распределение. Площадь четверти круга $x^2 + y^2 \le 1$ в единичном квадрате равна $P(U_1^2 + U_2^2 \le 1) = \pi/4$ для независимых равномерных $U_1, U_2$, поэтому $\pi$ оценивается учетверённой долей случайных точек, попавших внутрь:

Рисунок

Число π методом Монте-Карло

С миллионом точек оценка равна $3.1413$ при стандартной ошибке $0.0016$: метод Монте-Карло медленный — три верных знака за миллион сэмплов, а каждый следующий знак обходится в сто раз дороже. Его сила в том, что скорость $1/\sqrt n$ не зависит от размерности. Сетке с 10 точками на ось в 10 измерениях нужно $10^{10}$ точек; оценка объёма 10-мерного единичного шара, $\pi^5/120 = 2.55$, методом Монте-Карло по миллиону случайных точек куба $[-1, 1]^{10}$ равна $2.53$. Относительная стандартная ошибка, 2%, велика (фактическая ошибка в этом запуске — 0.9%) потому, что внутрь шара попадает лишь одна точка из 400: оценивать вероятность редкого события простым сэмплированием дорого, и именно эту задачу решает выборка по значимости (importance sampling).

Тот же принцип проходит через всё машинное обучение. Функция потерь на отложенных данных — оценка риска методом Монте-Карло, градиент по мини-батчу — оценка полного градиента, доля правильных ответов на валидационной выборке — оценка вероятности верного ответа, а функция потерь вариационного автоэнкодера после репараметризации — оценка математического ожидания по латентным кодам.

Когда средние не сходятся#

Закону нужно конечное среднее, а его скорость зависит от хвостов.

• Нет среднего. У распределения Коши из заметки о математическом ожидании его нет, и среднее $n$ сэмплов стандартного распределения Коши снова имеет стандартное распределение Коши — с тем же разбросом, что и один сэмпл. Его средние по $10^2$, $10^4$ и $10^6$ сэмплам в коде ниже равны $-0.01$, $-0.33$ и $2.86$: больше данных не помогает.
• Среднее есть, дисперсии нет. Распределение Парето с показателем хвоста $1.5$ имеет среднее 3 и бесконечную дисперсию. Его средние сходятся, но медленно и скачками — всякий раз, когда приходит одно огромное значение: $3.22$, $3.74$, $3.04$ при тех же объёмах выборки. Так ведут себя доходы, размеры файлов и число подписчиков аккаунта, а вместе с ними и посчитанные по ним средние.
• Зависимость. Средние зависимых значений, например последовательных состояний цепи Маркова, всё равно сходятся при условиях, которые изучает заметка о цепях Маркова, но эффективное число сэмплов, как правило, меньше $n$.

Что изменилось#

	До	С законом больших чисел
Вероятность как частота	наблюдение	теорема: $\bar X_n \to \mu$ почти наверное
Сходимость	интуитивная	по вероятности (слабый закон) и почти наверное (усиленный закон), их разделяют леммы Бореля–Кантелли
Математические ожидания и интегралы	вычисляются аналитически	оцениваются усреднением сэмплов, ошибка $\sigma/\sqrt n$ в любой размерности
Когда не работает		нет среднего (Коши), бесконечная дисперсия (медленно), зависимость (меньше эффективных сэмплов)

Ограничения#

• Закон ничего не говорит о скорости. Насколько $\bar X_n$ близко к $\mu$ при данном $n$, говорят неравенства предыдущей заметки или центральная предельная теорема следующей.
• Одинаковая распределённость — это предположение. Если распределение дрейфует, как поведение пользователей между обучением и развёртыванием, среднее сходится к среднему меняющейся цели или вообще ни к чему.
• Метод Монте-Карло медленный для редких событий и малой допустимой погрешности. Относительная ошибка растёт, когда целевая вероятность уменьшается; для этого и существуют снижение дисперсии, выборка по значимости и квазислучайные последовательности.

Что нужно запомнить#

• Слабый закон: $P(\lvert \bar X_n - \mu \rvert \ge \varepsilon) \to 0$ (сходимость по вероятности); усиленный закон: $P(\bar X_n \to \mu) = 1$ (сходимость почти наверное). Обоим нужно только конечное среднее.
• Леммы Бореля–Кантелли: если $\sum P(A_n) < \infty$, то почти наверное происходит лишь конечное число $A_n$; для независимых событий из $\sum P(A_n) = \infty$ следует, что почти наверное их происходит бесконечно много.
• Метод Монте-Карло: $E[g(X)] \approx \frac1n \sum g(X_i)$ сходится, если $E\lvert g(X) \rvert < \infty$; при конечной дисперсии его стандартная ошибка равна $\sigma/\sqrt n$, где $\sigma$ — стандартное отклонение $g(X)$; скорость не зависит от размерности.
• Без среднего (Коши) средние не стабилизируются; при бесконечной дисперсии они стабилизируются медленно и скачками.

Код#

Два вида сходимости, два интеграла методом Монте-Карло и средние, которые ведут себя плохо:

import numpy as np, math

rng = np.random.default_rng(0)

# independent events with P(A_n) = 1/n and 1/n^2, n up to 100,000: how many happen, 1,000 runs each
N = 100_000
n = np.arange(1, N + 1)
c1 = [int((rng.random(N) < 1 / n).sum()) for _ in range(1000)]
c2 = [int((rng.random(N) < 1 / n**2).sum()) for _ in range(1000)]
print(round(float(np.mean(c1)), 2), round(float(np.sum(1 / n)), 2), round(float(np.mean(c2)), 2), round(math.pi**2 / 6, 2))   # 12.05 12.09 1.68 1.64
print(1 - 10_000 / 100_000, round(1 - float(np.prod(1 - 1 / n[100:] ** 2)), 4))   # 0.9 0.0099: an event after 10^4 (1/n); after 100 (1/n^2)

# Monte Carlo: pi from the unit square, and the volume of the 10-dimensional unit ball
u = rng.random((2, 1_000_000))
print(round(4 * float(((u**2).sum(axis=0) <= 1).mean()), 4), round(4 * math.sqrt(math.pi / 4 * (1 - math.pi / 4) / 1e6), 4))   # 3.1413 0.0016
x = rng.uniform(-1, 1, (1_000_000, 10))
share = float(((x**2).sum(axis=1) <= 1).mean())
print(round(share * 2**10, 3), round(math.pi**5 / 120, 3), round(math.sqrt(share * (1 - share) / 1e6) / share, 3))   # 2.527 2.55 0.02

# no mean: Cauchy averages wander; a finite mean with infinite variance (Pareto, mean 3) converges slowly
c = rng.standard_cauchy(10**6)
p = rng.pareto(1.5, 10**6) + 1
print([round(float(c[:k].mean()), 2) for k in (10**2, 10**4, 10**6)], [round(float(p[:k].mean()), 2) for k in (10**2, 10**4, 10**6)])
# [-0.01, -0.33, 2.86] [3.22, 3.74, 3.04]

Дальше#

Закон больших чисел говорит, куда идёт среднее; правило $1/\sqrt n$ — насколько далеко от цели оно обычно находится. Ни то ни другое не говорит, какую форму имеют его колебания. Следующая заметка показывает, что эта форма почти всегда одна и та же — нормальное распределение, каким бы ни было распределение отдельных слагаемых, — и превращает этот факт в интервалы погрешности.

Литература#

• J. K. Blitzstein, J. Hwang. Introduction to Probability, 2nd ed. CRC Press, 2019. Глава 10 (закон больших чисел).
• W. Feller. An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd ed. Wiley, 1968. Глава X (закон больших чисел), глава VIII (леммы Бореля–Кантелли).
• A. N. Shiryaev. Probability-1, 3rd ed. Springer, 2016. Глава 2, §10 (виды сходимости).
• A. N. Shiryaev. Probability-2, 3rd ed. Springer, 2019. Глава 4, §1–3 (законы нуля или единицы и усиленный закон больших чисел).
• C. P. Robert, G. Casella. Monte Carlo Statistical Methods, 2nd ed. Springer, 2004. Глава 3 (интегрирование методом Монте-Карло).