Оцінка числа Пі за допомогою Монте Карло: Що випадкові точки можуть і не можуть сказати вам

Оцінювання площі, яку неможливо інтегрувати, шляхом кидання дротиків

Намалюйте коло одиниці, вписане у квадрат 2х2. Площа кола дорівнює π; площа квадрата – 4. Розпорохуйте точки рівномірно та випадково всередині квадрата і порахуйте, яка частка з них потрапляє всередину кола — геометрично, ця частка повинна сходитися до π/4. Помножте спостережувану частку на 4 і ви отримаєте оцінку π, побудовану повністю шляхом підрахунку, без необхідності використання числення. Це є канонічним прикладом Монте-Карло інтегрування: перетворення геометричної ймовірності на числову відповідь за допомогою повторних випадкових відборів, названого на честь казино Монте-Карло фізиками з Лос-Аламос у 1940-х роках, які використовували ту ж саму хитрощі для оцінки інтегралів нейтронного розповсюдження, які не мали замкнутої форми.

let inside = 0, total = 0;
function samplePoint() {
  const x = Math.random() * 2 - 1;   // uniform in [-1, 1]
  const y = Math.random() * 2 - 1;
  total++;
  if (x * x + y * y <= 1) inside++;   // inside the unit circle?
  return 4 * inside / total;           // running estimate of pi
}

Чому це збігається як 1/√n, а не швидше

Кожний зразок є Бернульським експериментом: він потрапляє всередину кола з ймовірністю p = π/4 ≈ 0.7854, або випадає за межі з ймовірністю 1 − p. Спостережуваний відсоток попадань після n зразків є упередженим оцінником p, і відповідно до Центральної теореми про граничне розподілення його стандартне відхилення зменшується як σ/√n, де σ² = p(1 − p) фіксується геометрією. На практиці це означає, що помилка падає лише приблизно на 3.16× (√10) кожного разу, коли ви берете десять разів більше зразків — щоб отримати один додатковий правильний десятковий знак π, потрібно приблизно 100× більше точок. Цей 1/√n темп є визначальним, неминучим сигнатурою простого Монте-Карло інтегрування, і тому він виглядає незатишно поряд із детермінованими серіями для π (Лебніца, формули типу Машина або алгоритм Чудновського), які збігаються експоненціально швидко з кількістю членів.

Де саме Монте Карло перемагає

Метод з дротиком – жахливий спосіб обчислення π, особливо – будь-яка з низки класичних серій виграє після кількох термінів. Його справжня цінність проявляється в протилежному режимі: багатовимірних інтегралах, де чисельні сітки втрачають на практичному значенні. Метод із 100 точками на осі потребує 100^d оцінок для d-вимірного інтеграла – при d = 10 це 10^20 точок, що нереально. Помилка Монте Карло все одно зменшується як 1/√n незалежно від розмірності, тому мільйон випадкових вибірок дає прийнятну оцінку при d = 10, де жодна розумна сітка не могла б цього зробити. Саме тому методи Монте Карло домінують у обчислювальній фінанси (ціноутворення залежних від шляху дериватів), статистичній фізиці (модель Ізинга, Латтейн QCD) та інтегралах транспорту світла всередині фізично обґрунтованого рендерингу.

Зменшення дисперсії: підвищення точності на зразок

Оскільки похибка визначається як σ/√n, і n є дорогим, більшість практичних покращень методів Монте-Карло зосереджені на зменшенні σ замість збільшення n. Стратифікований зразок розділяє квадрат на сітку та гарантує щонайменше один зразок на клітинку, уникаючи випадкового утворення кластерів, яке іноді виникає при чистому рівномірному випадковому семплюванні. Важливе семплювання відбирає більше зразків там, де інтеграл найбільший (не має значення для рівної окружності, але критичне, коли функція, яку інтегрують, різко пікове). Квазі-Монте-Карло замінює справжній випадковий вибір на послідовності з низькою дисперсією, такі як Собол або Гальтон, які заповнюють простір більш рівномірно, ніж незалежні випадкові точки, і можуть підняти швидкість збіжності майже до 1/n для гладких інтегралів — асимптотично набагато краще, ніж 1/√n, ціною втрати простих статистичних похибок.

Перевірка на розумність: стандартна похибка в один момент

З p = π/4, σ = √(p(1−p)) ≈ 0.4105, отже стандартна похибка оцінки π (яка є 4-кратною оцінкою відношення) після n вибірок становить приблизно 4 × 0.4105 / √n ≈ 1.642/√n. При n = 10 000 це прогнозує похибку близько ±0.016 — що відповідає тому, що ви побачите коливатися на життєвому лічильнику навіть після тисяч точок, і є хорошим свідченням того, що "більше вибірок" поступово забезпечує точність, а не безкоштовно.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Monte Carlo Pi Estimation і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.