Квази-Монте-Карло: последовательности с низким расхождением и Соболь

Проблемы псевдослучайных чисел в методе Монте-Карло

Классический метод Монте-Карло (МК), как мы выяснили ранее, является незаменимым инструментом для вычисления интегралов в пространствах высокой размерности (от 5 до 100 и более измерений), где традиционные сеточные методы бессильны из-за «проклятия размерности». Однако стандартный МК имеет серьезный недостаток — очень медленную сходимость, пропорциональную O(1/sqrt(N)). Чтобы увеличить точность результата всего на один знак (в 10 раз), нужно сгенерировать в 100 раз больше случайных точек.

Эта медленная сходимость вызвана самой природой случайности. При генерации точек с помощью обычных генераторов псевдослучайных чисел в многомерном пространстве неизбежно возникают сгущения (кластеры), где точки слипаются друг с другом, и огромные пустые области (дыры). Алгоритм тратит вычислительные ресурсы на избыточное исследование одних участков и полностью игнорирует другие. Это похоже на то, как капли дождя падают на асфальт: сначала они ложатся неравномерно, оставляя сухие пятна, и лишь спустя долгое время смачивают поверхность целиком.

Последовательности с низким расхождением

Чтобы решить эту проблему, математики разработали метод Квази-Монте-Карло (КМК). Ключевое отличие заключается в том, что КМК полностью отказывается от случайности! Вместо псевдослучайных генераторов используются жестко детерминированные алгоритмы, которые генерируют так называемые последовательности с низким расхождением (Low-discrepancy sequences). Эти последовательности заполняют многомерный гиперкуб максимально равномерно, избегая образования как кластеров, так и пустых дыр. Точки расставляются так, чтобы каждое новое значение ложилось точно в самый большой незаполненный пробел.

С точки зрения математики, расхождение (discrepancy) — это мера того, насколько плотность точек в произвольном параллелепипеде отклоняется от идеальной равномерной плотности. Для случайных чисел расхождение велико. Для сеток оно мало, но их невозможно построить в высоких размерностях. Последовательности КМК (такие как последовательности Холтона, Фора, Нидеррайтера) дают идеальный компромисс. Самой популярной и эффективной в индустрии является ЛП-тау последовательность Соболя, разработанная выдающимся советским математиком Ильей Мееровичем Соболем в 1967 году.

Применение КМК на финансовых рынках и в графике

Замена генератора случайных чисел на последовательность Соболя превращает классический Монте-Карло в Квази-Монте-Карло, при этом скорость сходимости меняется радикально: она приближается к O(1/N). Это означает, что для достижения той же точности требуется не в 100 раз больше вычислений, а всего лишь в 10 раз. Это колоссальный скачок в эффективности.

Метод КМК произвел настоящую революцию в инвестиционных банках. При ценообразовании сложных финансовых производных (например, азиатских или ипотечных опционов), где выплаты зависят от траектории цены актива за каждый из 365 дней в году, возникает интеграл 365-й размерности. Применение КМК позволило оценивать такие портфели за секунды вместо часов. Также последовательности Соболя стали индустриальным стандартом в компьютерной графике и рендеринге (алгоритмы Path Tracing). Фотореалистичное освещение в современных голливудских фильмах (Pixar, Disney) рассчитывается путем трассировки лучей, где направления лучей выбираются именно на основе последовательностей КМК, обеспечивая гладкую картинку без цифрового шума при минимальном количестве лучей на пиксель.