Предельные теоремы

Два разных утверждения

Закон больших чисел и центральная предельная теорема говорят о одном и том же выборочном среднем, но отвечают на разные вопросы. Их постоянно путают, потому что оба «про то, что среднее сходится».

$$\htmlData{k=lln}{\bar{X}_n \xrightarrow{\ \text{п.н.}\ } \mu} \qquad\qquad \htmlData{k=clt}{\sqrt{n}\,\big(\bar{X}_n - \mu\big) \xrightarrow{\ d\ } \mathcal{N}(0, \sigma^2)}$$

• ЗБЧ отвечает куда: среднее сходится к ожиданию. Утверждение о пределе и только о нём;
• ЦПТ отвечает как быстро и какой формы отклонение: масштаб $1/\sqrt{n}$, форма — гауссова, независимо от того, из какого распределения пришли данные.

Второе — сильнее и удивительнее. Форма предельного распределения не зависит от исходного: сумма многих независимых слагаемых забывает, откуда они, и оставляет от них только $\mu$ и $\sigma^2$. Именно поэтому гауссиана встречается везде, где что-то складывается.

Множитель $\sqrt{n}$ здесь не украшение. Без него левая часть сошлась бы к нулю (это и есть ЗБЧ), а с ним предел нетривиален — то есть $\sqrt{n}$ ровно тот масштаб, на котором отклонение видно. Это тот же $1/\sqrt{n}$, что был в уроке про Монте-Карло, и теперь понятно, откуда он: он не про метод, а про суммы.

Кривая наивной оценки в виджете — иллюстрация обоих утверждений сразу: она сходится (ЗБЧ), и её колебания сжимаются как $1/\sqrt{n}$, а не как $1/n$ (ЦПТ). Поставьте $t = 1$, чтобы попаданий было много, и увеличьте $n$.

истина: 1.587e-1 выборочное среднее

порог t

1

сэмплов n

2000

сравнить с importance sampling

попаданий

291 / 2000

выборочное среднее · оценка

1.455e-1

выборочное среднее · ст. ошибка

7.89e-3

Чего требует ЗБЧ

Условие одно и его легко потерять: ожидание должно существовать. Если нет, никакой сходимости не будет — не медленной, а никакой.

Классический контрпример — распределение Коши. У него нет ожидания (интеграл $\int |x| p(x)\,dx$ расходится), и выборочное среднее $n$ независимых наблюдений Коши само распределено как Коши — с теми же параметрами, что одно наблюдение. Усреднение не даёт ровно ничего.

Проверяется это численно и выглядит убедительно:

| $n$ | доля прогонов с $|\bar{X}_n| > 1$ | максимум $|\bar{X}_n|$ | |---|---|---| | $10$ | $50\%$ | $818$ | | $100$ | $48\%$ | $511$ | | $1000$ | $50\%$ | $415$ | | $10\,000$ | $52\%$ | $7344$ |

Доля не падает, а держится ровно на половине — и это не шум, а точное значение $P(|\text{Cauchy}| > 1) = 1/2$. Десять тысяч наблюдений знают о центре не больше, чем одно.

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

Насколько быстро работает ЦПТ

«При $n \ge 30$ можно считать нормальным» — фольклор, а не теорема. Скорость сходимости зависит от асимметрии исходного распределения. Для $\text{Exp}(1)$, у которого асимметрия равна $2$:

$n$	$P\big(\bar{X}_n > 1 + 2/\sqrt{n}\big)$
$1$	$0.0495$
$5$	$0.0404$
$30$	$0.0314$
$100$	$0.0280$
$1000$	$0.0245$
предел ЦПТ	$0.0228$

При $n = 30$ ошибка ещё почти $40\%$, а при $n = 1000$ — около $8\%$. Сходимость есть, но она медленная (теорема Берри–Эссеена даёт скорость $O(1/\sqrt{n})$, а не экспоненциальную), и в хвостах хуже, чем в центре. Считать $p$-значение $10^{-6}$ по нормальной аппроксимации на трёх десятках наблюдений — плохая идея.

Неравенства концентрации

ЦПТ — приближение, а не оценка: она не даёт границы, верной при конкретном $n$. Для границ есть неравенства, и их три уровня.

Маркова — для неотрицательной величины: $P(X \ge a) \le \frac{\mathbb{E}[X]}{a}$. Требует только ожидания, и оттого слаба:

$a$	$P(X \ge a)$ для $\text{Exp}(1)$	граница Маркова
$2$	$0.135$	$0.5$
$5$	$0.0067$	$0.2$
$10$	$0.000045$	$0.1$

Разрыв растёт: на $a = 10$ граница завышена в две тысячи раз. Зато она верна всегда.

Чебышёва — используем ещё и дисперсию: $P(|X - \mu| \ge k\sigma) \le \frac{1}{k^2}$. Убывает полиномиально.

Хёфдинга — для среднего ограниченных независимых величин:

$P\big(|\bar{X}_n - \mu| \ge \varepsilon\big) \le 2\exp\big(-2n\varepsilon^2\big)$

Убывает экспоненциально по $n$, и это качественный скачок. Сравним все три на выборочном среднем монеты:

$n$	$\varepsilon$	точно	Чебышёв	Хёфдинг	ЦПТ (приближение)
$100$	$0.05$	$0.368$	$1.0$	$1.0$	$0.317$
$100$	$0.1$	$0.057$	$0.25$	$0.271$	$0.045$
$1000$	$0.05$	$0.0017$	$0.1$	$0.0135$	$0.0016$

Читается так. При малых $n$ и малых $\varepsilon$ обе границы вырождаются в бесполезное «не больше единицы». При $n = 1000$ Чебышёв всё ещё даёт $0.1$ — в шестьдесят раз хуже истины, — а Хёфдинг подбирается к $0.0135$. ЦПТ ближе всех, но она не граница: её значение может оказаться и ниже истинного, что для гарантии недопустимо.

Отсюда разделение труда, которое стоит запомнить:

• нужна гарантия (bound на риск, PAC-оценка, дифференциальная приватность) — Хёфдинг и его родня, ценой пессимизма;
• нужна оценка (доверительный интервал, стандартная ошибка, размер выборки для A/B-теста) — ЦПТ, ценой того, что это приближение.

Условие Хёфдинга — ограниченность величин — тоже не формальность. Для неограниченных нужны субгауссовы или субэкспоненциальные предположения, и в анализе SGD в блоке 5 именно они и будут стоять в условиях теорем о сходимости.