Hacker News Digest

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а как более доступное введение в вероятность и статистику.