ИнтВизТеория вероятностей · модуль 14 из 14
Метод Монте-Карло: число π из случайных точек
Бросаем случайные точки в квадрат 1×1. Доля точек внутри четверти круга стремится к π/4. Точность растёт медленно: для ещё одного верного знака нужно в 100 раз больше точек.
- внутри круга
- снаружи
- точное π
- коридор ±2σ
Теория
Метод Монте-Карло оценивает величину как среднее по случайным испытаниям. Если точка $(x, y)$ равномерно распределена в единичном квадрате, вероятность попасть в четверть круга радиуса 1 равна отношению площадей:
$$ P(x^2 + y^2 \le 1) = \frac{\pi / 4}{1} = \frac{\pi}{4} . $$
Бросив $N$ точек и подсчитав $N_{\text{внутри}}$ попаданий, получаем оценку
$$ \hat\pi = 4 \cdot \frac{N_{\text{внутри}}}{N} . $$
По закону больших чисел $\hat\pi \to \pi$ при $N \to \infty$. Число попаданий распределено биномиально, поэтому стандартное отклонение оценки
$$ \sigma = 4 \sqrt{\frac{p(1 - p)}{N}}, \qquad p = \frac{\pi}{4}, $$
убывает как $1 / \sqrt{N}$. По центральной предельной теореме примерно в 95% случаев оценка отличается от $\pi$ не больше чем на $2\sigma$. Чтобы получить ещё один верный десятичный знак, число точек нужно увеличить в 100 раз.
Скорость сходимости $1 / \sqrt{N}$ не зависит от размерности задачи. Для многомерных интегралов это преимущество перед сеточными методами, число узлов которых растёт экспоненциально с размерностью.
Где это применяется в IT
Монте-Карло решает задачи, где точная формула слишком сложна: фотореалистичный рендеринг (трассировка путей в играх и кино), оценка финансовых рисков, расчёт надёжности систем, поиск хода в играх (MCTS в AlphaGo).
- Многомерность. Ошибка убывает как $1 / \sqrt{N}$ и не зависит от размерности, поэтому метод выигрывает на многомерных интегралах.
- Шум рендеринга. Зернистость рендеров в Blender при малом числе сэмплов — та же погрешность Монте-Карло.
- Генераторы случайных чисел. Качество ответа зависит от генератора: коррелированные числа дают смещённую оценку.
Код на Python
Загружаю пример…