§4. Шар в k-мерном кубе: как геометрия кидает интуицию

В §3 мы сказали: Монте-Карло одинаково работает в любой размерности. Звучит буднично. Но сама многомерная геометрия устроена так дико, что обычная интуиция там садится в лужу. Покажем это на одном опыте, который ломает здравый смысл.

Шар, вписанный в куб

Возьмём $k$-мерный шар — множество точек $\{x : x_1^2 + \dots + x_k^2 \le 1\}$ (все, кто не дальше единицы от центра). И впишем его в $k$-мерный куб $\{x : |x_j| \le 1\}$ со стороной 2. Шар касается стенок куба изнутри — обычная картинка (для $k = 3$ — шар в коробке).

Вопрос: какова вероятность $p_k$, что случайно брошенная в куб точка попадёт в шар? Это просто отношение объёмов:

Посчитаем для малых размерностей:

• $k = 1$: отрезок внутри отрезка, $p_1 = 1$ (весь куб и есть шар).
• $k = 2$: круг в квадрате, $p_2 = \dfrac{\pi r^2}{2^2} = \dfrac{\pi}{4} \approx 0{,}785$.
• $k = 3$: шар в кубе, $p_3 = \dfrac{\frac43 \pi r^3}{2^3} = \dfrac{\pi}{6} \approx 0{,}524$.

Уже видно: доля падает. А в общем случае есть формула:

Тут новый значок — $\Gamma$ (гамма-функция Эйлера). Не пугайся: это просто обобщение факториала на нецелые числа, со свойством $\Gamma(n) = (n-1)!$. Для нас важно одно: знаменатель с ростом $k$ раздувается как факториал, а числитель $(\sqrt\pi/2)^k < 1$ ещё и убывает. Вместе они гонят $p_k$ к нулю, и очень быстро.

Куда девается шар

Вот тут интуиция и получает по щам. Спроси себя: какова доля $p_{10}$ для десятимерного куба? Здравый смысл шепчет что-то вроде «ну, половина, или хотя бы треть — шар же вписан, касается стенок». А на деле:

Четверть процента! Почти весь объём десятимерного куба сидит не в шаре. Покрути виджет — двигай размерность $k$ и смотри, как столбик доли проваливается почти в ноль (и как Монте-Карло-оценка это подтверждает):

Почему так? В многомерном кубе почти весь объём утекает в углы. У $k$-мерного куба углов аж $2^k$ штук (для $k=10$ это $1024$ угла), и они торчат далеко от центра — дальше, чем радиус вписанного шара. Шар сидит в серединке, крошечный на фоне растопыренных во все стороны углов. По-дворовому: в многомерном районе вся территория — это окраины и закоулки по углам, а центральная площадь (шар) — микроскопический пятачок, куда почти никто случайно не забредает.

При чём тут Монте-Карло

Оценить $p_k$ жребием — проще некуда: кидай точки в куб, считай долю попавших в шар (ровно приём из §3). Но заметь оборотную сторону многомерия: при большом $k$ шар настолько мелкий, что в него почти никто не попадает, и чтобы поймать хоть сколько-то попаданий, нужна прорва точек. Так что даже всемогущий жребий в высоких размерностях начинает кряхтеть — редкие события ловить трудно. Это ещё аукнется нам дальше, в задачах про редкие попадания.

Проверь себя