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. Далее показывается, когда и почему стратификация уменьшает дисперсию за счёт контроля вариации внутри страт и отрицательной корреляции между ними.