почему симуляция, а не формула.
кажется, что бросать кости — признак того, что не умеешь решать честно. но есть огромный класс задач, где случайные пробы бьют и точную формулу, и аккуратный перебор. вопрос не в лени, а в размерности.
| тема | проклятие размерности · Монте-Карло · симуляция · закон больших чисел |
| читать | ~7 минут |
| связано | Монте-Карло · турнир · Бюффон · π · чемпион · ЗБЧ |
Школа приучает: у задачи есть «правильное» решение — формула, в которую подставляешь числа и получаешь ответ. Симуляция на этом фоне выглядит как жульничество: вместо того чтобы вывести ответ, мы тысячу раз бросаем кости и смотрим, что вышло в среднем. Но для огромного класса задач честная формула либо не существует, либо бесполезна — и тогда случайность оказывается не костылём, а самым умным инструментом.
Возьми турнир. Чтобы посчитать вероятность чемпиона точно, нужно перебрать все варианты сетки: кто кого, на каждом этапе, во всех сочетаниях. Число путей растёт как снежный ком, формулы нет, перебор бессмыслен. А симуляция берёт и разыгрывает турнир — десять тысяч раз — и просто считает доли. То же с интегралом сложной формы, с траекторией нейтрона, с ценой опциона: точное выражение либо не выводится, либо занимает том.
Можно возразить: ну хорошо, нет формулы — посчитаем численно, по сетке. Разобьём пространство на клетки, пройдём по всем. И вот тут вскрывается главное. В одном измерении сетка из ста точек — это сто вычислений. В двух — уже десять тысяч. В десяти измерениях сетка из ста точек на ось требует 100¹⁰ вычислений — больше, чем атомов в комнате. Это называют проклятием размерности: честный перебор дорожает экспоненциально с числом измерений12.
В многомерном пространстве сетка тонет, а случайные точки — нет.
И вот фокус. Точность оценки методом Монте-Карло зависит только от числа бросков N — как 1/√N — и совершенно не зависит от размерности3. Сетке в десяти измерениях нужны астрономические 100¹⁰ узлов; Монте-Карло хватит тех же десяти тысяч случайных точек, что и в двумерном случае. В многомерье случайные пробы не просто удобнее — они единственный реальный способ. Поэтому ими считают всё, от физики частиц до финансов и машинного обучения, где измерений сотни.
Почему так выходит? Потому что Монте-Карло превращает вычисление в измерение. Вместо того чтобы обходить пространство, ты случайно тыкаешь в него точками и усредняешь — а закон больших чисел гарантирует, что среднее по случайной выборке сходится к истине4. Это ровно то, что делал Бюффон иглой и что показывает дождь точек, вычисляющий π: ты не выводишь ответ, ты его сэмплируешь.
У робастности есть цена — медлительность. Сходимость 1/√N «decelerating»: чтобы добавить один знак точности, нужно в сто раз больше проб; вчетверо больше счёта дают лишь вдвое точнее5. Монте-Карло — не быстрый метод, а универсальный: он почти всегда работает и почти никогда не работает быстро. Поэтому половина суперкомпьютерного времени в мире уходит ровно на него, и поэтому же придумали хитрости (квази-случайные последовательности, важностную выборку), чтобы сходимость подогнать.
Так что симуляция — не признак того, что ты не осилил вывод. Это признание честной границы: за определённой сложностью формула молчит, перебор захлёбывается, а случайность продолжает считать ровно с той же скоростью. Иногда самый точный способ узнать ответ — перестать его выводить и начать бросать кости. Достаточно много раз, достаточно честно — и среднее само скажет правду.