§3. Кратные интегралы: где жребий незаменим

В §1 мы честно признали: для одномерного интеграла Монте-Карло проигрывает методу прямоугольников. Напомню минусы жребия:

• точность всего $1/\sqrt{n}$ против $1/n^2$ у прямоугольников;
• чтобы оценить погрешность по формуле (2), надо знать (или прикидывать) разброс $\mathbf{D}\xi$;
• и сама оценка верна лишь с некоторой вероятностью, а не железно.

Казалось бы, фуфловый метод. Но сейчас будет разворот на 180 градусов — есть задачи, где Монте-Карло единственный, кто вообще справляется.

Проклятие размерности

Представь интеграл не по отрезку, а по $k$-мерному кубу — по многим переменным сразу:

Попробуй взять его честной сеткой (как прямоугольники). Беда в том, что число узлов сетки растёт как $n^k$ — степень $k$ в показателе. Это называют проклятием размерности. Прикинь масштаб: чтобы обсчитать десятимерный куб, беря узлами хотя бы только его вершины, надо $2^{10} = 1024$ раза вычислить функцию. А если сетка погуще — число узлов улетает в космос. И это при том, что одно вычисление $\varphi$ может само по себе быть долгим (например, требовать решения уравнений).

Монте-Карло плюёт на размерность

А теперь фишка, ради которой всё затевалось. Методу Монте-Карло на размерность вообще плевать. Чтобы оценить тот же $k$-мерный интеграл, делаешь ровно то же, что в §1:

• кидаешь $n$ случайных точек в $k$-мерный куб (просто берёшь псевдослучайные числа и режешь их на группы по $k$ координат);
• усредняешь значения $\varphi$ в этих точках: $\hat I_n = \tfrac1n \sum \varphi(\eta_i)$.

И точность остаётся той же — порядка $1/\sqrt{n}$, независимо от $k$. Хоть два измерения, хоть сто — жребию без разницы, он просто кидает точки да усредняет. Вот где он бьёт все честные методы: там, где сетка захлёбывается от размерности, Монте-Карло спокойно работает.

Объём области через долю попаданий

Особый и очень наглядный случай — когда $\varphi$ это индикатор области: равна $1$ внутри некоторой фигуры $D$ и $0$ снаружи. Тогда среднее $\hat I_n$ — это просто доля точек, попавших внутрь $D$, и она приближает объём этой области.

Классика: кинем точки в единичный квадрат и посчитаем долю, попавшую под дугу четверти круга ($x^2 + y^2 \le 1$). Площадь четверти круга равна $\pi/4$, значит доля попаданий $\approx \pi/4$. Умножив на 4, снова ловим число $\pi$ — но теперь не усреднением функции, а подсчётом попаданий в область:

По-дворовому: хочешь прикинуть площадь кривой лужи на асфальте — не меряй линейкой, а раскидай горсть семок наугад по размеченному квадрату и посчитай, сколько легло в лужу. Доля попавших, умноженная на площадь квадрата, и есть площадь лужи. И этот трюк работает в любой размерности — хоть лужа, хоть шар в десятимерном кубе (а вот тут нас ждёт сюрприз — см. §4).

Есть и улучшенная версия — расслоённая выборка: куб заранее режут на мелкие подкубики и в каждый кидают по точке. Так точность чуть выше, чем при полностью случайном разбросе, — но суть та же.

Проверь себя