Hacker News Digest

• История генераторов случайных чисел от LCG до PCG, включая вклад Джорджа Марсальи и Меллора О'Нилла.
• Обсуждение того, что PCG "решил" проблему генераторов, но не стал стандартом, и почему это может быть связано с тем, что никто не может объяснить, что именно делает PCG лучше.
• Сомнения в том, что реально ли PCG лучше, чем xorshift и другие современные генераторы, и что это может быть просто результатом того, что никто не хочет тратить время на их взлом.
• Поднятие вопроса о том, что "случайность" может быть не более чем иллюзия, вызванная нашим незнанием точных условий, и что это может быть применимо к обсуждению генераторов случайных чисел.
• Несколько замечаний о том, что "естественные" случайные числа не являются таковыми, и что это может быть применимо к обсуждению генераторов случайных чисел.

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