Голка Буффона: Оцінка числа π шляхом кидання голки на підлогу

Геометрична задача, що приховує число пі

У 1733 році Жорж-Луї Леклюер, герцог Буффон, поставив химерне питання: потрібно було випадково опустити голку довжиною L на підлогу, поділену паралельними лініями на відстані d один від одного (де L ≤ d), і обчислити ймовірність того, що голка перетне одну з цих ліній. Здивувальною відповіддю є число пі, оскільки проблема поєднує лінійну випадковість (коли центр голки потрапляє між двома паралельними лініями) з кутовою (у якому напрямку голка вказує), а інтегрування за кутом природним чином призводить до появи числа пі.

Обчислення ймовірності перетину

Нехай x – це відстань від центра голки до найближчої лінії (рівномірно розподілена між 0 та d/2), а θ – гостре кут, під яким голка утворює з лініями (рівномірно розподілений між 0 та π/2, або еквівалентно від 0 до π за симетрією). Голка перетинає лінію точно тоді, коли вертикальна досяжність її півдовжини, (L/2)·sin(θ), більша або рівна x. Усереднення цієї умови перетину по всіх однаково ймовірних парах (x, θ) – інтегрування sin(θ) за кутом та ділення на діапазон x – дає чисте замкнене вираження:

P(перетин) = (2 * L) / (π * d) // для L Переставляючи цю ймовірнісну формулу, щоб знайти π, та замінюючи справжню ймовірність на спостережувану частку перетинів з N загальних падінь, отримуємо експериментальну оцінку π, побудовану повністю на основі фізичного випадкового процесу – жодної цифри π не було припущено ніде в схемі, вони виникають чисто за допомогою геометрії та випадковості.

P(crossing) = (2 * L) / (pi * d)        // for L <= d
pi_estimate = (2 * L * N) / (d * crossings)   // solve for pi using observed crossings

Чому це метод Монте-Карло, за десятиліття до появи назви

Голку Буффона сьогодні визнають одним із найраніших відомих методів Монте-Карло — використовуючи повторне випадкове відбирання для оцінки детермінованого значення, яке в іншому випадку вимагало б точних геометричних або аналітичних обчислень. Це передує терміну «Монте-Карло» (винайдений у 1940-х роках на Los Alamos) приблизно на два століття, але основна ідея ідентична сучасній Монте-Карло інтеграції: виразити невідому константу як очікуване значення деякого випадкового експерименту, а потім наблизити це очікування шляхом усереднення великої кількості незалежних спроб.

Закон больших чисел і чому оцінка коливається та потім стабілізується

З невеликою кількістю випадків впадання голки спостережувана частка перетинів може значно відрізнятися від справжньої ймовірності 2L/(πd) лише через випадковість — мало спроб призводить до великої дисперсії вибірки. Закон великих чисел гарантує, що зі збільшенням кількості спроб (N) спостережувана частка збігається зі справжньою ймовірністю з ймовірністю одиниці, тому отримана оцінка π збігається з дійсною вартістю π. Однак збіжність відбувається повільно: стандартна похибка Monte Carlo оцінки, така як ця, зменшується лише як 1/√N, тобто збільшення кількості спроб в чотири рази лише вдвійно знижує типову похибку — щоб отримати ще одну надійну десяткову цифру π таким чином, потрібно приблизно збільшити кількість випадків впадання голки у сто разів, що робить експеримент Буффона чудовим ілюстратором збіжності Monte Carlo, але жахливим способом обчислення π до багатьох знаків.

Довжина голки також має значення

Формула P = 2L/(πd) припускає, що L ≤ d, тобто голка може перетнути максимум одну лінію на краплю; встановлення L рівним d максимізує ймовірність перетину для цього режиму та дає найбільшу "інформацію" – найвищу очікувану кількість перетинів – на краплю, що в свою чергу мінімізує відносну похибку вибірки при заданій кількості спроб. Значно коротша голка відносно відстані між лініями рідко перетинає їх, витрачаючи більшість крапель на невдалі спроби, і потребує значно більшої кількості спроб, щоб з точністю до позначення визначити π; голка довшою за d (пізніше розширення Лапласа) може перетнути більше однієї лінії та потребує цілком іншої формули ймовірності.

Демонстрація, а не обчислення

Ніхто ніколи не використовував голку Буффона для встановлення рекорду в обчисленні знаків числа π — цю роль виконують швидкі алгоритми збіжності, незалежні від випадкового семплювання. Її стійкий інтерес полягає в педагогічній цінності: це відчутне, фізичне демонстрація того, що чисто геометричної ймовірності може бути достатньо для закодування π, і що випадкове семплювання — хоч і повільно збігається — дійсно може витягти детерміновану математичну константу із нічого, крім повторних випадкових подій, що є точною інтуїцією, яка лежить в основі кожного сучасного алгоритму Монте-Карло, які використовуються сьогодні у фінансах, фізиці та комп’ютерній графіці.

Часті запитання

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

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