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

Площади как вероятности

Выберите случайную точку в квадрате так, чтобы любое место было равновероятным. Вероятность того, что она попадёт в некоторую область, равна площади этой области, делённой на площадь квадрата. Круг радиуса 1 имеет площадь π, а квадрат вокруг него — сторону 2 и площадь 4. Значит, случайная точка попадает в круг с вероятностью P = π/4 ≈ 0,785.

От попаданий к π

Бросьте N дротиков и посчитайте попадания H в круг. Доля H/N оценивает π/4, поэтому

π ≈ 4H / N

Для проверки попадания π вообще не нужно: точка (x, y), отсчитанная от центра в единицах радиуса, лежит внутри круга, когда x² + y² ≤ 1. Число π появляется из подсчёта.

В варианте с четвертью круга центр находится в углу квадрата со стороной 1. Четверть круга тоже занимает π/4 этого квадрата, так что формула та же.

Закон больших чисел

Каждый дротик — это маленький опыт с двумя исходами: попадание с вероятностью p = π/4 или промах. Закон больших чисел, доказанный Якобом Бернулли и опубликованный в 1713 году, гласит, что с ростом N доля попаданий сколь угодно близко подходит к p. Он не утверждает, что попадания и промахи уравновешиваются за короткое время: оценка может долго уходить от π, прежде чем вернуться.

Как быстро это работает?

Число попаданий подчиняется биномиальному распределению. Его стандартное отклонение, пересчитанное в масштаб π, даёт типичную погрешность

σ ≈ 4 · √(p(1 − p) / N) ≈ 1.64 / √N

После 100 дротиков это около 0,16, после 10 000 — около 0,016, после миллиона — около 0,0016. Погрешность убывает обратно пропорционально квадратному корню из N: в сто раз больше дротиков дают одну дополнительную верную цифру. В приложении затенённая полоса — это ±1,96σ, она вмещает 95% всех серий, а ± после оценки — одна стандартная ошибка.

Откуда взялось название

В 1946 году Станислав Улам, выздоравливая после болезни, задумался, насколько вероятно, что сойдётся пасьянс. Вместо того чтобы перебирать все возможные раскладки, он решил просто разложить пасьянс много раз и посчитать удачные попытки. Вместе с Джоном фон Нейманом он превратил эту идею в метод для расчётов нейтронов в Лос-Аламосе, а их коллега Николас Метрополис назвал его в честь казино Монте-Карло, где любил играть дядя Улама. Гораздо более старые опыты со случайностью, например игла Бюффона 1777 года, уже оценивали π в том же духе.

Исследуйте в PictorX

Откройте «π методом Монте-Карло», и дротики уже летят, тысяча в секунду. Счётчик окрашивает цифры, которые уже совпадают с π, а график показывает оценку на логарифмической оси внутри полосы, куда попадают 95% серий. «Замедленно» бросает один дротик в секунду и рисует его расстояние до центра; щёлкните по квадрату, чтобы бросить дротик самостоятельно. «Миллион дротиков» бросает их все сразу. «Четверть круга» переключает на вариант с углом, а «Приглушать старые дротики» сохраняет картинку живой на высокой скорости. Сохраните PNG или сравните с иглой Бюффона, которая оценивает π падающими иглами.