Метод Монте-Карло

Считать сложное через случайность: метод Монте-Карло и закон 1/√N.

Метод Монте-Карло — приём вычислений, в котором ответ получают усреднением результатов множества случайных испытаний; точность растёт как 1/√N с числом испытаний N.

Случайность как инструмент

Звучит парадоксально: как случайные числа помогают точно что-то посчитать? Идея в законе больших чисел: отдельное случайное испытание непредсказуемо, но среднее по многим испытаниям сходится к точному значению. Метод назван в честь казино в Монте-Карло — намёк на роль случая. Он незаменим там, где прямой расчёт невозможен: интегралы в многомерных пространствах, сложные вероятности, физика многих частиц.

Классика: оценка числа π

Самый наглядный пример. Впишем четверть круга в единичный квадрат. Бросаем случайные точки в квадрат; доля попавших внутрь круга равна отношению площадей — π/4. Значит π ≈ 4·(попало внутрь)/(всего):

import random, math
random.seed(1)
def estimate_pi(n):
    inside = 0
    for _ in range(n):
        x, y = random.random(), random.random()
        if x*x + y*y <= 1.0:
            inside += 1
    return 4*inside/n
for n in (100, 1000, 10000, 100000):
    p = estimate_pi(n)
    print(f"N={n:6d}:  pi ≈ {p:.4f}   ошибка {abs(p-math.pi):.4f}")
print(f"Точное pi = {math.pi:.4f}")

Вывод:

N=   100:  pi ≈ 3.2000   ошибка 0.0584
N=  1000:  pi ≈ 3.1280   ошибка 0.0136
N= 10000:  pi ≈ 3.1456   ошибка 0.0040
N=100000:  pi ≈ 3.1386   ошибка 0.0030
Точное pi = 3.1416

С ростом числа бросков оценка приближается к π, а ошибка падает. Но падает не линейно: при увеличении N в 100 раз (с 100 до 10000) ошибка упала примерно в 10 раз. Это и есть закон 1/√N — чтобы добавить один знак точности, нужно в 100 раз больше испытаний.

Закон 1/√N и его цена

Медленная сходимость — главная слабость Монте-Карло. Точность 1/√N означает дорогую борьбу за каждую цифру. Зато у метода есть козырь: эта скорость не зависит от размерности задачи. Обычные методы интегрирования по сетке в десятимерном пространстве требуют астрономического числа узлов («проклятие размерности»), а Монте-Карло одинаково работает и в одном измерении, и в тысяче. Поэтому в статистической физике, финансах и машинном обучении он часто единственный реальный вариант.

Как работает под капотом

За методом стоит центральная предельная теорема: среднее N независимых случайных величин имеет разброс (стандартное отклонение), убывающий как σ/√N. Отсюда и берётся 1/√N. Уменьшить разброс σ (а значит ускорить сходимость при том же N) помогают приёмы снижения дисперсии: выборка по важности, антитетические переменные, стратификация. Но фундаментальный закон 1/√N они не отменяют, лишь улучшают константу.

Частые ошибки

• Ждать линейного роста точности. Удвоение N улучшает точность лишь в √2 раз.
• Не фиксировать seed при отладке. Без фиксированного зерна результат меняется от запуска к запуску, и трудно сравнивать.
• Коррелированные «случайные» числа. Плохой генератор с корреляциями искажает оценку; в физике важно качество ГПСЧ.

Итоги

• Монте-Карло получает ответ усреднением случайных испытаний.
• Ошибка убывает как 1/√N — медленно, но независимо от размерности.
• Оценка π бросками точек — наглядная демонстрация метода.
• Метод незаменим в многомерных задачах, где сетка бессильна.