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

Що таке метод Монте-Карло?

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

Детермінована формула не існує або надто складна для обчислення.
Задача живе в багатьох вимірностях (де сітчасті методи непрактичні).
Наближена відповідь прийнятна, і ви можете дозволити собі багато випадкових вибірок.

Точність оцінки Монте-Карло покращується як $\frac{1}{\sqrt{N}}$ — подвоєння точності потребує вчетверо більше зразків. Це звучить повільно, але в багатовимірних просторах цей метод перевершує будь-який конкуруючий метод.

Оцінка π киданням дротиків

Найвідоміша демонстрація Монте-Карло включає одиничне коло всередині квадрата 2×2. Якщо кидати дротики рівномірно в квадрат, частка тих, що потрапляють у коло, дорівнює $\pi/4$ — тому що площа кола $\pi r^2 = \pi$, а площа квадрата $4$.

1
Вибірка: Оберіть випадкову точку $(x, y)$ з $x, y \in [-1, 1]$.
2
Перевірка: Обчисліть $d = x^2 + y^2$. Точка всередині кола, якщо $d \le 1$.
3
Підрахунок: Відстежуйте влучання $h$ і загальну кількість кидків $N$.
4
Оцінка: $\pi \approx 4 \cdot h / N$. Повторюйте нескінченно — оцінка сходиться.

Збіжність π: як кількість вибірок впливає на точність

N = 100

≈ 3.16

N = 1 тис.

≈ 3.14

N = 10 тис.

≈ 3.141

N = 1 млн

≈ 3.1416

Зверніть увагу, довжини стовпчиків не досягають 100% — оцінка сходиться, але ніколи не досягає точного значення. Похибка $\sigma \propto 1/\sqrt{N}$ означає, що у 100 разів більше вибірок дає лише один додатковий десятковий знак.

          function estimatePi(N)
          { let hits = 0;
          for (let i = 0; i <
          N; i++) { const x = Math.random() * 2 - 1;
          // [-1, 1] const y =
          Math.random() * 2 - 1; if (x*x + y*y <= 1)
          hits++; // всередині одиничного кола?
          }
          return 4 * hits / N;
          // π ≈ 4 · (площа_кола / площа_квадрата)
          }
        

Інтегрування Монте-Карло

Ідея кидання дротиків узагальнюється. Щоб проінтегрувати будь-яку функцію $f(x)$ на $[a, b]$:

Виберіть $N$ випадкових зразків $x_i$ рівномірно в $[a, b]$.
Обчисліть середнє: $\bar{f} = \frac{1}{N} \sum f(x_i)$.
Оцінка: $\int_a^b f(x)\, dx \approx (b - a) \cdot \bar{f}$.

Це працює, бо середнє значення $f$, помножене на ширину інтервалу, дорівнює інтегралу. Що важливіше, для $d$-вимірного інтеграла похибка залишається $O(1/\sqrt{N})$ незалежно від $d$ — тоді як сітчаста квадратура коштує $O(N^{1/d})$ на вимірність. У 20 вимірностях Монте-Карло перемагає з величезним відривом.

Де ми використовуємо Монте-Карло на цьому сайті

Симуляція π методом Монте-Карло

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

Поширення хвороби (стохастична SIR)

Симуляція Поширення хвороби використовує випадкові події контакту замість диференціальних рівнянь. На кожному кроці часу кожен заражений агент контактує з $k$ випадковими іншими — макрорівневі криві S/I/R виникають з тисяч індивідуальних вибірок Монте-Карло.

Пошук нонсу для майнінгу біткоїна

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

Дифузійно-обмежена агрегація

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

Зменшення дисперсії: більше за менше

Базовий Монте-Карло кидає дротики рівномірно. Але розумніші стратегії можуть досягти тієї самої точності з меншою кількістю зразків:

Стратифікована вибірка: поділіть область на рівні підобласті й вибирайте з кожної — зменшує кластеризацію.
Вибірка за важливістю: кидайте більше дротиків там, де функція найбільша, потім скоригуйте ваги. Ключове в трасуванні шляхів (3D-рендеринг).
Контрольні змінні: використовуйте аналітично відому пов'язану функцію, щоб зменшити дисперсію навколо оцінки.
Квазі-Монте-Карло: замініть псевдовипадкові числа послідовностями з низькою розбіжністю (Гальтона, Соболя) для кращого покриття й похибки $O((\log N)^d / N)$.

Методи Монте-Карло живлять глобальне освітлення в кожному сучасному 3D-фільмі та грі. Трасування шляхів — основний алгоритм за Pixar і NVIDIA RTX — це інтегрування Монте-Карло рівняння рендерингу за напрямками півсфери. Кожне «відбиття» — це випадкова вибірка.

Коли не варто використовувати Монте-Карло

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

Емпіричне правило: якщо вимірність $d > 4$, а точності до 2-3 значущих цифр достатньо, Монте-Карло — правильний інструмент.