Hacker News Digest

Кратко о ЦПТ
Если из любого распределения с конечным средним и дисперсией брать выборки размера n и считать их средние, то при n → ∞ распределение этих средних стремится к нормальному.

Эксперимент
Сгенерировано по 10 000 значений из шести распределений: uniform, normal, binomial, beta, exponential, χ².
Функция take_random_sample_mean() берёт случайную выборку размера 60 и возвращает среднее. Повторено 20 000 раз.

take_random_sample_mean <- function(data, n) {
  slice_sample(data, n = n) |> summarise(across(everything(), list(mean = mean, sd = sd)))
}

Результаты
Гистограммы 20 000 средних показывают, что даже для сильно ненормальных исходных распределений форма распределения средних близка к нормальной.

• Обсудили аналог ЦПТ для экстремумов — теорему Фишера–Типпета–Гнеденко (GEV).
• Подчеркнули важность симуляций для интуитивного понимания ЦПТ и поделились ссылками на визуализации.
• Отметили, что скорость сходимости к нормальному распределению зависит от исходного распределения (экспоненциальное сходится медленнее).
• Упомянули обобщения ЦПТ: для распределений без конечной дисперсии, ряды Эджворта, устойчивые распределения.
• Предупредили о риске завышенных ожиданий из-за «хорошо ведущих себя» примеров и дали ссылки на литературу.

Monte Carlo Crash Course

• Непрерывные распределения вероятностей
• Экспоненциально лучшая интеграция
• Сэмплинг
• Кейс: рендеринг
• Quasi-Monte Carlo
• Скоро…

Мы уже определили и применили интеграцию Монте‑Карло — по сути, это единственный необходимый инструмент. Далее рассмотрим способы снижать дисперсию и эффективно сэмплировать сложные распределения.

• Дисперсия и корреляция
• Стратифицированный сэмплинг
• Адаптивный сэмплинг
• Латинский гиперкуб
• Quasi‑Monte Carlo
• Последовательности с низкой несоответственностью

Дисперсия и корреляция

Во второй главе мы увидели: дисперсия оценщика Монте‑Карло обратно пропорциональна числу выборок, а ожидаемая ошибка масштабируется как 1/√N в любом измерении. Это намного лучше экспоненциальной зависимости, но для очень высокой точности 1/√N всё ещё может быть недостаточно быстро; на практике N можно увеличивать лишь ограниченно.

Мы также предполагали независимость выборок, чтобы дисперсии складывались. Однако несмещённость интеграции Монте‑Карло не требовала независимости. Если выборки отрицательно коррелированы, ковариация < 0, дисперсия суммы снижается, и сходимость может быть быстрее 1/√N.

Poisson Disk Sampling

Перцептивно отрицательно коррелированные точки выглядят «более случайными»: независимые образуют кластеры и оставляют пробелы; отрицательная корреляция делает обратное — плотные области сэмплируются реже. Можно генерировать такие точки отбором с отказами: отбрасывать точки, слишком близкие к уже принятым (Poisson disk sampling). Это удобно для предгенерации с минимальным расстоянием, но плохо подходит для прогрессивных оценок, где нужно со временем покрыть весь домен.

Стратифицированный сэмплинг

Если минимальная дистанция не нужна, быстрее получать отрицательную корреляцию через стратификацию. Идея сочетает сильные стороны квадратур и Монте‑Карло: вместо N независимых точек по всему домену мы делим область на M равных ячеек и берём N/M независимых точек в каждой. Поскольку в ячейке не может быть больше N/M точек, они отрицательно коррелированы.

Рассмотрим оценщик на N стратифицированных выборках. Группировка по регионам переписывает его как сумму независимых оценок по каждой области Ωm, каждая с N/M выборками. По линейности матожидания такой оценщик несмещён: сумма интегралов по поддоменам равна интегралу по всему домену.

На примере с разбиением круга на M=64 областей получаем заметно меньшую ошибку, особенно при малых N. Точный выигрыш зависит от поведения функции f, но можно показать, что стратификация как минимум не увеличивает дисперсию.

Зачем стратифицировать?

Сравним равномерный N-выборочный оценщик по всему Ω с стратифицированным, равномерно сэмплирующим два поддомена A и B. Далее показывается, когда и почему стратификация уменьшает дисперсию за счёт контроля вариации внутри страт и отрицательной корреляции между ними.

• Участники отметили, что слабый PRNG и фиксированный seed в Монте-Карло часто полезны: ускоряют расчёты и обеспечивают воспроизводимость для отладки.
• Однако @clickety_clack возражает: фиксированный seed создаёт иллюзию точности, а менеджеры должны видеть влияние стандартной ошибки.
• Обсудили, что для 500 акций учесть все ковариации практически невозможно из-за сложности взаимодействий.
• Спор о скорости CSPRNG: один считает их дорогими, другой приводит пример быстрого алгоритма Randen.
• Рекомендовали курс Steve Bruntonа как более доступное введение в вероятность и статистику.