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

Ме́тод Мо́нте-Ка́рло (за назвою міста Монте-Карло, Монако, яке відоме своїми казино) — загальна назва групи числових методів, заснованих на одержанні великої кількості реалізацій стохастичного (випадкового) процесу, який формується у той спосіб, щоб його ймовірнісні характеристики збігалися з аналогічними величинами задачі, яку потрібно розв'язати. Використовується для розв'язування задач у фізиці, математиці, економіці, оптимізації, теорії управління тощо.

Метод Монте-Карло — це метод імітації для приблизного відтворення реальних явищ. Він об'єднує аналіз чутливості (сприйнятливості) і аналіз розподілу ймовірностей вхідних змінних. Цей метод дає змогу побудувати модель, мінімізуючи дані, а також максимізувати значення даних, які використовуються в моделі. Побудова моделі починається з визначення функціональних залежностей у реальній системі. Після чого можна одержати кількісний розв'язок, використовуючи теорію ймовірності й таблиці випадкових чисел.

Метод Монте-Карло широко використовується у всіх випадках симуляції на комп'ютері.

Огляд

Не існує єдиного методу Монте-Карло, цей термін описує великий і широко використовуваний клас підходів. Проте ці підходи використовують в своїй основі єдиний шаблон:

1. Визначити область можливих вхідних даних.
2. Випадковим чином згенерувати вхідні дані із визначеної вище області за допомогою деякого заданого розподілу ймовірностей.
3. Виконати детерміновані обчислення над вхідними даними.
4. Проміжні результати окремих розрахунків звести у кінцевий результат.

Наприклад, можна отримати наближене значення числа ${\displaystyle \pi }$ за допомогою методу Монте-Карло:

1. Намалюйте квадрат на підлозі, а потім впишіть круг всередину квадрата. З геометрії, співвідношення площі вписаною круга до площі зовнішнього квадрата становить ${\displaystyle \pi /4}$.
2. Рівномірно розкидати деякі об'єкти однакового розміру по всій площі квадрата. Наприклад, це можуть бути зерна рису.
3. Оскільки дві області знаходяться в співвідношенні ${\displaystyle \pi /4}$, об'єкти повинні потрапити в області приблизно в тій же пропорції. Таким чином, підрахувавши кількість об'єктів в колі і розділити на загальну кількість об'єктів в квадраті, отримаємо наближене значення ${\displaystyle \pi /4}$.
4. Помноживши результат на 4 буде отримано наближене значення власне самого ${\displaystyle \pi }$.

У цій процедурі вхідною областю є квадрат, який описує коло. Генеруються випадкові вхідні дані, тобто розсіювання зерна на квадрат, потім виконуються обчислення на кожному вході(проводиться перевірка на те, чи попало зерно в коло). Кінцево, ми сумуємо результати, щоб отримати остаточний результат, безпосередньо наближення ${\displaystyle \pi }$.

Є два важливих моменти, які слід враховувати: По-перше, якщо зерна не розподілені рівномірно, то наше наближення буде мінімальним.

По-друге, потрібно, щоб була велика кількість вхідних даних. Наближення, як правило, є поганим, якщо лише декілька зерен випадково впали на площу.

Використання методів Монте-Карло вимагає великої кількості випадкових чисел, їх використання стимулювало розвиток багатьох генераторів псевдовипадкових чисел, які є набагато швидшими в використанні, ніж таблиці випадкових чисел, що раніше використовувалися для статистичної вибірки.

Історія

Передісторія

Хоча термін «Монте-Карло» з'явився лише у 1940-х роках, окремі елементи методу стохастичного моделювання відомі з XVIII століття. Найвідомішим раннім прикладом є Задача Бюффона про голку (1777), де французький природознавець Жорж-Луї Леклерк де Бюффон запропонував спосіб наближеного обчислення числа π шляхом кидання голки на розліновану площину.

У 1901 році Лорд Кельвін використовував подібну техніку, яку він назвав «вибіркою випадкових чисел», для обговорення кінетичної теорії газів, перемішуючи папірці з номерами у глечику для генерації даних. Однак до появи електронних обчислювальних машин такі методи були надто трудомісткими для масового використання.

Внесок Енріко Фермі

Існує свідчення, що Енріко Фермі використовував подібний метод ще у 1930-х роках у Римі для розрахунку властивостей нейтрона, який сповільнюється у речовині. Фермі не опублікував свої результати, але використовував їх для перевірки своїх аналітичних розрахунків, називаючи цей підхід «статистичним експериментом». Пізніше, дізнавшись про роботу Улама та фон Неймана в Лос-Аламосі, Фермі розробив спеціальний аналоговий пристрій — «FERMIAC», який механічно відстежував випадкові траєкторії нейтронів.

Народження методу в Лос-Аламосі

Офіційне народження методу як систематичного інструменту досліджень відбулося у 1946 році в Лос-Аламоській національній лабораторії та пов'язане з іменем Станіслава Улама.

Ідея виникла в Улама під час хвороби (вірусного енцефаліту), коли він відновлювався вдома і, щоб згаяти час, розкладав пасьянс «Кенфілд». Його зацікавило питання: яка ймовірність того, що пасьянс зійдеться? Спроби вивести точну комбінаторну формулу виявилися надто складними. Тоді Улам зрозумів, що простіше зіграти тисячі партій, підрахувати кількість вдалих результатів і отримати наближену ймовірність:

Я подумав, чи не краще зіграти сотню партій і просто підрахувати успіхи, ніж намагатися обчислити все це за допомогою чистої комбінаторики? Я одразу ж подумав про задачу дифузії нейтронів...

Улам поділився цією ідеєю з Джоном фон Нейманом у березні 1946 року. Фон Нейман миттєво оцінив потенціал методу для нових електронних обчислювальних машин, зокрема ENIAC, який саме тоді вводили в експлуатацію.

Розробка та назва

Фон Нейман розробив алгоритмічну базу для реалізації методу на комп'ютері. Оскільки зчитування великих масивів випадкових чисел з перфокарт було надто повільним для ENIAC, фон Нейман винайшов метод «середини квадрата» (Middle-square method) для генерації псевдовипадкових чисел — це стало критично важливим кроком для комп'ютерної реалізації методу.

Робота велася в рамках секретних досліджень з розробки термоядерної зброї, тому методу була потрібна кодова назва. Її запропонував фізик Ніколас Метрополіс на честь казино в Монте-Карло, де дядько Уляма часто позичав гроші для гри.

Перша стаття, що відкрила метод для широкої наукової спільноти, була опублікована Метрополісом та Уламом у 1949 році під назвою «The Monte Carlo Method» у журналі Американської статистичної асоціації.

У 1950-х роках метод отримав подальший розвиток. Зокрема, у 1953 році Метрополіс разом із Едвардом Теллером та іншими опублікували опис алгоритму (нині відомий як Алгоритм Метрополіса — Гастінгса), який дозволив моделювати фізичні системи в термодинамічній рівновазі, що стало основою обчислювальної фізики.

Математичні основи

В основі методу Монте-Карло лежить закон великих чисел. Нехай ${\displaystyle X}$ — випадкова величина з математичним сподіванням ${\displaystyle \mathbb {E} [X]}$. Для послідовності незалежних і однаково розподілених випадкових величин ${\displaystyle X_{1},X_{2},\dots ,X_{N}}$ їхнє середнє арифметичне збігається до істинного математичного сподівання при ${\displaystyle N\to \infty }$: ${\displaystyle {\bar {X}}_{N}={\frac {1}{N}}\sum _{i=1}^{N}X_{i}\xrightarrow {P} \mathbb {E} [X]}$

Обчислення інтегралів

Розглянемо задачу обчислення визначеного інтеграла функції ${\displaystyle f(x)}$ у багатовимірному просторі ${\displaystyle \Omega \subset \mathbb {R} ^{d}}$ з об'ємом ${\displaystyle V}$: ${\displaystyle I=\int _{\Omega }f(\mathbf {x} )\,d\mathbf {x} }$ Наївний підхід Монте-Карло полягає у виборі ${\displaystyle N}$ випадкових точок ${\displaystyle \mathbf {x} _{1},\dots ,\mathbf {x} _{N}}$, рівномірно розподілених в ${\displaystyle \Omega }$. Тоді оцінка інтеграла (${\displaystyle {\hat {I}}}$) дорівнює: ${\displaystyle {\hat {I}}\approx V\cdot {\frac {1}{N}}\sum _{i=1}^{N}f(\mathbf {x} _{i})}$ Ця оцінка є незміщеною, тобто ${\displaystyle \mathbb {E} [{\hat {I}}]=I}$.

Збіжність та похибка

Згідно з центральною граничною теоремою, розподіл похибки оцінки прямує до нормального розподілу. Стандартне відхилення оцінки спадає як: ${\displaystyle \sigma _{N}\propto {\frac {1}{\sqrt {N}}}}$ Це означає, що для зменшення похибки в 10 разів необхідно збільшити кількість точок моделювання в 100 разів.

Хоча збіжність ${\displaystyle O(N^{-1/2})}$ є повільною, її головна перевага — **незалежність від розмірності простору** ${\displaystyle d}$. Для порівняння, класичні детерміновані методи сіток (наприклад, метод Сімпсона) мають похибку порядку ${\displaystyle O(N^{-r/d})}$, де ${\displaystyle r}$ залежить від гладкості функції. При великих ${\displaystyle d}$ (наприклад, у статистичній фізиці чи фінансовій математиці, де ${\displaystyle d}$ може сягати сотень) детерміновані методи стають неефективними через катастрофічне зростання кількості необхідних вузлів сітки (проблема, відома як «прокляття розмірності»), тоді як метод Монте-Карло залишається застосовним.

Монте-Карло і випадкові числа

Методи моделювання Монте-Карло не завжди вимагають дійсно випадкових чисел для того, щоб бути корисними (хоча, для деяких додатків, таких як тестування на простоту, непередбачуваність є необхідною ознакою). Більшість найбільш корисних методів використовують детерміновані, псевдовипадкові послідовності, що роблять їх легкими для тестування і повторного запуску.

Все залежить від програми, але, як правило, вони повинні пройти ряд статистичних тестів. Тестування того чи іншого числа рівномірно розподілені або слідують іншому бажаному розподілу, коли визначена досить велика кількість елементів послідовності, вважається одним з найпростіших і найбільш поширених з цих методів. Слабкість кореляції між послідовними вибірками є часто бажаною або необхідною.

Савіловський^[en] перерахував характеристики високоякісного моделювання методом Монте-Карло:

• (Псевдо-випадковий) генератор чисел має певні характеристики (наприклад, довгий «період» до того, як послідовність повторюється)
• (Псевдо-випадковий) генератор чисел генерує значення, які проходять випробування на випадковість
• є достатня кількість зразків для забезпечення точних результатів
• використовується належний метод вибірки
• алгоритм, який використовується, є дієвим для ситуації, що моделюється
• він імітує явища.

Алгоритми генерації (семплінгу)

Для реалізації методу часто необхідно генерувати випадкові величини зі складним розподілом ймовірностей ${\displaystyle p(x)}$, відмінним від рівномірного.

Метод зворотної функції

Якщо відома функція розподілу ${\displaystyle F(x)}$ та існує обернена до неї ${\displaystyle F^{-1}(u)}$, то для отримання випадкової величини ${\displaystyle X\sim p(x)}$ достатньо згенерувати рівномірне число ${\displaystyle u\in [0,1]}$ і обчислити ${\displaystyle X=F^{-1}(u)}$. Цей метод є точним, але застосовним лише для простих розподілів.

Метод відбору-відмови

Запропонований Дж. фон Нейманом метод дозволяє генерувати числа з розподілу ${\displaystyle p(x)}$, використовуючи допоміжний розподіл ${\displaystyle g(x)}$ (наприклад, рівномірний), з якого легко отримувати зразки.

1. Знаходиться константа ${\displaystyle M}$ така, що ${\displaystyle Mg(x)\geq p(x)}$ для всіх ${\displaystyle x}$.
2. Генерується кандидат ${\displaystyle x}$ з розподілу ${\displaystyle g(x)}$ та випадкове число ${\displaystyle u\in [0,1]}$.
3. Якщо ${\displaystyle u\leq {\frac {p(x)}{Mg(x)}}}$, то точка приймається. В іншому випадку — відкидається, і процедура повторюється.

Марковські ланцюги Монте-Карло

Для багатовимірних задач, де пряме семплювання є неможливим, використовуються методи MCMC. Ідея полягає в побудові ланцюга Маркова, стаціонарний розподіл якого збігається з шуканим розподілом. Найвідомішим є Алгоритм Метрополіса — Гастінгса, опублікований у 1953 році групою вчених з Лос-Аламоса.

Застосування

Методи Монте-Карло особливо корисні для моделювання явищ зі значною невизначеністю вхідних даних і систем з великим числом пов'язаних ступенів вільності. Області застосування:

Фізичні науки

Методи Монте Карло дуже важливі в розрахунковій області фізики, фізичної хімії і пов'язаних з ними прикладних областях, а також в різноманітних додатках від розрахунків квантової хромодинаміки до проектування теплових екранів. У статистичній фізиці молекулярне моделювання Монте-Карло є альтернативою обчислювальної молекулярної динаміки, а також методи Монте-Карло використовуються для обчислення теорії статистичних полів елементарних частинок і полімерних систем. У радіаційному матеріалознавстві бінарне наближення зіткнень для моделювання іонної імплантації, відбувається, як правило, на основі підходу Монте-Карло для вибору наступного атома при зіткненні. У експериментальній фізиці елементарних частинок методи Монте-Карло використовуються для розробки детекторів, розуміння їх поведінки і порівняння експериментальних даних з теорією. Методи Монте-Карло також використовуються для моделей, які складають основу сучасного прогнозування погоди.

Інженерія

Методи Монте-Карло широко використовується в техніці для аналізу чутливості та кількісного ймовірнісного аналізу в процесі проектування. Наприклад,

• У геостатистиці методи Монте-Карло лежать в основі проектування технологічних схем збагачення корисних копалин.
• При аналізі використання енергії вітру.
• Вплив забруднення при використанні дизельного палива в порівнянні з бензином.
• В динаміці рідин, зокрема, динаміці розрідженого газу.
• В автономних роботів, локалізацією Монте-Карло можна визначити положення робота. Це часто застосовується до стохастичних фільтрів, таких як фільтр Кальмана, який формує основу SLAM (одночасне відображення локалізації і алгоритму).
• В області телекомунікацій, при плануванні бездротової мережі, конструкція повинна працювати для широкого спектра сценаріїв, які залежать головним чином від кількості користувачів, їх місць і послуг, які вони хочуть використовувати. Продуктивність мережі потім оцінюються і, якщо результати не є задовільними, конструкція мережі підлягає процесу оптимізації.
• Для дослідження надійності техніки можна використовувати метод Монте-Карло, щоб генерувати середній час між виникненням несправностей і середній час ремонту компонентів.

Комп'ютерна графіка

Сучасний фотореалістичний рендеринг базується на методах Монте-Карло для розв'язання рівняння рендерингу (Rendering equation). Техніка, відома як Path Tracing (трасування шляхів), полягає у стохастичному інтегруванні освітленості сцени. Алгоритм випускає промені з камери, які випадковим чином відбиваються від поверхонь (згідно з їхніми оптичними властивостями BRDF). Усереднення тисяч таких шляхів для кожного пікселя дозволяє моделювати такі складні ефекти, як м'які тіні, глобальне освітлення, каустику та розмиття руху (Motion blur). Цей підхід є стандартом у кіновиробництві та сучасних ігрових рушіях (технологія RTX).

Фінанси і бізнес

Методи Монте-Карло у фінансах часто використовуються для оцінки інвестицій в проектах на корпоративному рівні або для оцінки похідних фінансових інструментів. Вони можуть бути використані для моделювання графіків проекту, де використовуються агреговані оцінки для найгіршого випадку та найкращого варіанту, і найбільш ймовірна тривалість для кожного завдання, щоб визначити результати для всього проекту.