Теория вероятностей и статистика · Метод Монте-Карло

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

Метод Монте-Карло оценивает число с помощью случайной выборки. Если независимо и равномерно бросить N точек в единичный квадрат, доля попаданий в область оценивает её площадь со стандартной ошибкой, пропорциональной 1/√N. Бросайте точки и следите, как стабилизируется оценка π и меняется её неопределённость.

Метод Монте-Карло на этом графике

Метод Монте-Карло оценивает фиксированное число с помощью случайной выборки. Здесь это площадь. В единичный квадрат равномерно и случайно бросают NN точек. Если HH из них попали в область, то H/NH/N оценивает её площадь aa. Площадь четверти круга равна π/4\pi/4, поэтому 4H/N4H/N оценивает π\pi. Для области под кривой y=e−x2y = e^{-x^2} интеграл без элементарной первообразной сводится к такому же подсчёту. На нижнем графике показана оценка при росте NN до миллиона и диапазон, в который она должна попадать примерно в 95% повторений.

Почему доля попаданий оценивает площадь

Для равномерно выбранной точки в квадрате площади 1 вероятность попасть в область равна её площади. Каждая точка — независимое испытание с этой вероятностью, поэтому по закону больших чисел доля попаданий приближается к aa. Форма области неважна, если можно определить, попала ли в неё точка.

Насколько точна оценка

Число попаданий имеет биномиальное распределение, поэтому стандартное отклонение доли H/NH/N равно a(1−a)/N\sqrt{a(1-a)/N}. Типичная ошибка убывает как 1/N1/\sqrt{N}: в десять раз больше точек уменьшают её примерно в 10≈3.16\sqrt{10} \approx 3.16 раза. Чтобы уменьшить ошибку в десять раз, нужно примерно в сто раз больше точек. Даже при миллионе точек неопределённость для π составляет около ±0.003. Для её оценки не требуется знать истинную площадь: подстановка наблюдаемой доли p^=H/N\hat p = H/N вместо aa даёт погрешность ±1.96p^(1−p^)/N\pm 1.96\sqrt{\hat p(1-\hat p)/N} для приближённого 95%-го доверительного интервала. Здесь он строится при наличии хотя бы десяти попаданий и десяти промахов. Если много раз повторить опыт при одном и том же NN, примерно один из двадцати интервалов не накроет истинное значение. Голубая воронка на нижнем графике показывает диапазон вокруг истинного значения для каждого NN по отдельности. Вся траектория не обязана лежать внутри, а ошибка отдельного опыта не обязательно убывает: дополнительные точки могут немного отдалить оценку от истины. Закономерно сужается именно диапазон неопределённости.

Когда метод выгоден

Для гладкой функции одной переменной детерминированное правило, например формула Симпсона (см. численное интегрирование), гораздо точнее при том же числе вычислений функции. Достоинство метода Монте-Карло в том, что показатель степени в скорости сходимости 1/N1/\sqrt{N} не зависит от размерности. А сетке с mm точками вдоль каждой оси нужно mdm^d точек в пространстве размерности dd, поэтому в высокой размерности метод Монте-Карло может оказаться предпочтительнее. Малые цели обнаруживают его слабость: стандартная ошибка относительно площади равна (1−a)/(aN)\sqrt{(1-a)/(aN)}. Для области, занимающей сотую часть квадрата, нужно гораздо больше точек, чтобы получить ту же относительную точность.

На что обратить внимание

  • Случайные точки не лежат через равные промежутки: при нескольких сотнях точек скопления и пустые участки — обычное явление.
  • Точки порождает генератор псевдослучайных чисел с заданным начальным значением. По ссылке восстанавливается тот же набор. Когда точек станет миллион, кнопка «Бросить точки» начнёт заново со следующим начальным значением.

Связанные темы