Точность Монте-Карло: закон 1/√N

У метода Монте-Карло есть железный закон точности: чтобы уменьшить ошибку вдвое, нужно увеличить число испытаний вчетверо. Эта простая дробь определяет и силу метода, и его главную слабость.

Закон 1/√N — правило, по которому типичная ошибка оценки методом Монте-Карло убывает обратно пропорционально корню из числа испытаний N: чтобы повысить точность в 2 раза, число испытаний приходится увеличивать в 4 раза.

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

Эксперимент: измеряем ошибку при разных N

Лучше один раз увидеть закон в действии, чем поверить на слово. Прогоним оценку π при четырёх значениях N — 100, 1000, 10000 и 100000 бросков. Чтобы результат не зависел от везения конкретного запуска, для каждого N повторим оценку 30 раз с разными зёрнами и усредним модуль ошибки.

import random, math, statistics

def est_pi(N, seed):
    random.seed(seed)
    inside = sum(1 for _ in range(N) if random.random()**2 + random.random()**2 <= 1)
    return 4 * inside / N

for N in (100, 1000, 10000, 100000):
    errs = [abs(est_pi(N, s) - math.pi) for s in range(30)]
    print(f"N={N:>6}  средняя ошибка={statistics.mean(errs):.4f}")

Вывод:

N=   100  средняя ошибка=0.1251
N=  1000  средняя ошибка=0.0254
N= 10000  средняя ошибка=0.0098
N=100000  средняя ошибка=0.0036

Всмотритесь в числа. При росте N в 10 раз ошибка падает не в 10 раз, а примерно в √10 ≈ 3.16 раза. От 100 к 1000 ошибка упала с 0.1251 до 0.0254 — это почти в 5 раз (тут сказался случайный разброс), но дальше картина выравнивается: 0.0254 → 0.0098 → 0.0036, и каждый раз делитель близок к 3. Именно так выглядит закон 1/√N вживую.

Что значит «убывает как 1/√N»

Расшифруем правило в практических терминах. Типичная ошибка пропорциональна 1/√N. Отсюда два важных следствия.

Чтобы добавить всего один верный знак после запятой (уточнить ответ в 10 раз), нужно увеличить число испытаний в 100 раз. Это и есть оборотная сторона метода: точность даётся дорого.

Одновременно сила и слабость

Закон 1/√N — двуликий. Разберём обе его стороны честно.

Слабость: медленная сходимость

Скорость 1/√N — это медленно. Сравните: метод трапеций для гладких одномерных функций даёт ошибку порядка 1/N², а это несравнимо быстрее. Поэтому для простых одномерных интегралов Монте-Карло проигрывает классике вчистую. Если вам нужно много верных знаков в одномерной задаче, Монте-Карло — плохой выбор: придётся ждать слишком долго.

Сила: независимость от размерности

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

Вывод прост: на одномерных гладких задачах используйте классические методы, а в многомерье и там, где геометрия запутана, доставайте Монте-Карло — пусть и ценой большого числа испытаний.

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

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

дисперсия одного испытания: σ²
        |
   усредняем N штук
        v
дисперсия среднего: σ² / N
        |
   берём корень (= ошибка)
        v
типичная ошибка: σ / √N  -->  пропорционально 1/√N

В коде функция est_pi(N, seed) делает одну оценку π по N броскам с заданным зерном. Цикл по s in range(30) повторяет оценку 30 раз с зёрнами от 0 до 29 — это даёт 30 независимых «выстрелов», и statistics.mean(errs) усредняет их ошибки, сглаживая случайный разброс отдельного запуска. Без такого усреднения по нескольким зёрнам одна неудачная оценка могла бы исказить картину.

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

• Думать, что вдвое больше испытаний дают вдвое меньшую ошибку. Чтобы ошибка упала вдвое, испытаний нужно вчетверо больше — закон именно квадратичный.
• Применять Монте-Карло к простой одномерной задаче ради высокой точности. Метод трапеций или Симпсона сойдётся куда быстрее.
• Делать выводы о точности по одному запуску. Из-за случайности отдельная оценка может «повезти» или «не повезти»; нужно усреднять по нескольким зёрнам, как в примере.
• Забывать, что закон 1/√N не зависит от размерности — и потому недооценивать метод в многомерных задачах, где у него нет конкурентов.
• Путать дисперсию и стандартное отклонение: ошибка убывает как 1/√N, а не как 1/N, именно потому, что ошибка — это корень из дисперсии.

Итоги

• Типичная ошибка Монте-Карло убывает как 1/√N: чтобы повысить точность вдвое, число испытаний нужно увеличить вчетверо.
• Эксперимент это подтверждает: при росте N в 10 раз средняя ошибка падает примерно в √10 ≈ 3.16 раза.
• Медленная сходимость — слабость метода: классические методы для гладких одномерных задач быстрее.
• Независимость от размерности — сила метода: закон 1/√N один и тот же в любом числе измерений, где сеточные методы бессильны.
• Корень возникает потому, что дисперсия среднего падает как 1/N, а ошибка — это её квадратный корень.