Карта → событие
Улам и фон Нейман: вычислять вероятностью
Момент
Станислав Улам (1909–1984), математик из львовской школы (кафе «Шкоцка»), с 1943 года работавший в Лос-Аламосе, в 1946-м перенёс тяжёлый энцефалит и восстанавливался, раскладывая пасьянс «Кэнфилд».
Ему стало любопытно, какова вероятность успешного расклада. Он начал считать комбинаторно и быстро упёрся: перебор безнадёжен. И тогда пришла мысль, которую он сам описал так: а не проще ли разложить, скажем, сто пасьянсов и просто посчитать, сколько сошлось?
Мысль тривиальная — но Улам немедленно связал её с рабочей задачей: диффузия нейтронов в делящемся веществе. Уравнение переноса нейтронов в реальной геометрии не решается ни аналитически, ни разностными методами. Но траекторию отдельного нейтрона легко разыграть: пролетел столько-то (случайная длина свободного пробега), рассеялся под таким-то углом, поглотился или вызвал деление. Разыграв достаточно траекторий, получим ответ.
Улам рассказал идею Джону фон Нейману, тот немедленно оценил и в марте 1947 года послал Роберту Рихтмайеру детальный план вычисления на ЭНИАКе. Первые расчёты — 1948 год. Николас Метрополис предложил кодовое название по казино в Монако, где играл дядя Улама.
Метод
Простейшая иллюстрация — вычисление $\pi$. Бросаем точки равномерно в квадрат $[0,1]^2$ и считаем долю попавших в четверть круга $x^2+y^2\leqslant1$. Эта доля стремится к $\pi/4$.
$$\hat\pi = 4\cdot\frac{\text{попаданий}}{N}.$$
Общая схема. Чтобы вычислить $I = \int_{\Omega} g(x)\,dx$, представим его как ожидание:
$$I = \int g(x)\,dx = E\left[\frac{g(X)}{p(X)}\right], \qquad X\sim p,$$
и оценим средним по выборке:
$$\hat I_{N} = \frac{1}{N}\sum_{i=1}^{N}\frac{g(X_{i})}{p(X_{i})}.$$
По усиленному закону больших чисел (точка о Бореле) $\hat I_N \to I$ почти наверное, а по центральной предельной теореме (Лаплас) погрешность имеет порядок
$$\left|\hat I_{N}-I\right| \sim \frac{\sigma}{\sqrt{N}}.$$
Почему это революция: проклятие размерности
Скорость $1/\sqrt{N}$ выглядит удручающе: чтобы добавить один десятичный знак, нужно в сто раз больше вычислений. Детерминированные квадратуры куда точнее: метод трапеций даёт $O(h^{2})$, Симпсона — $O(h^{4})$.
Но это в одном измерении. В размерности $d$ сетка из $n$ узлов по каждой оси требует $N = n^{d}$ вычислений, и погрешность метода порядка $k$ ведёт себя как
$$O\!\left(n^{-k}\right) = O\!\left(N^{-k/d}\right).$$
Показатель делится на размерность. А у Монте-Карло погрешность равна $O(N^{-1/2})$ независимо от $d$.
Сравним для метода Симпсона ($k=4$):
| Размерность $d$ | Порядок сходимости Симпсона | Монте-Карло |
|---|---|---|
| 1 | $N^{-4}$ | $N^{-1/2}$ |
| 4 | $N^{-1}$ | $N^{-1/2}$ |
| 8 | $N^{-1/2}$ | $N^{-1/2}$ |
| 20 | $N^{-0{,}2}$ | $N^{-1/2}$ |
| 100 | $N^{-0{,}04}$ | $N^{-1/2}$ |
Начиная примерно с восьмого измерения Монте-Карло выигрывает, а дальше выигрывает безнадёжно. Задача о переносе нейтронов имеет размерность 7 (три координаты, две угловые, энергия, время) — Улам и фон Нейман попали ровно в точку перелома.
Это и есть содержание метода: случайность побеждает проклятие размерности. Плата — только вероятностная гарантия вместо детерминированной.
Побочный результат: где брать случайность
Компьютеру нужны случайные числа в огромных количествах, а компьютер детерминирован. Фон Нейман предложил метод серединных квадратов (1949): возводим число в квадрат, берём средние цифры. Метод плох (быстро зацикливается), но он поставил задачу.
Ему же принадлежит формулировка парадокса: всякий, кто пытается получать случайные числа арифметическими средствами, пребывает в состоянии греха. Из этого «греха» выросла целая дисциплина — линейные конгруэнтные генераторы, вихрь МерсеннаМарен МерсеннМонах-минимит, работавший научным журналом за сто лет до появления журналов: через его келью в Париже шла переписка всей учёной Европы. Числа его имени до сих пор дают рекордные простые., криптографические генераторы, тесты Кнута и Марсальи.
Продолжение
- Алгоритм Метрополиса (Метрополис, Розенблуты, Теллеры, 1953) — метод Монте-Карло по марковским цепям (MCMC). Позволяет выбирать из распределения, которое известно только с точностью до множителя. Это, возможно, важнейший вычислительный алгоритм XX века после быстрого преобразования ФурьеЖозеф ФурьеУтверждал, что любую функцию можно сложить из синусов, — и был не прав ровно настолько, чтобы математике понадобилось сто лет и три новые теории, чтобы разобраться.. Обобщение — алгоритм Гастингса (1970).
- MCMC и байесовский ренессанс. Именно MCMC сделал байесовскую статистику практичной: апостериорные распределения, которые невозможно вычислить, можно из них выбирать. Программы BUGS, Stan, PyMC.
- Метод отжига (Киркпатрик, 1983) — оптимизация через управляемую случайность.
- Метод Монте-Карло по деревьям (MCTS) — основа AlphaGo.
- Физика частиц, финансовая инженерия, климатические модели, оценка рисков.
Смысл поворота
До 1946 года вся линия шла в одну сторону: математика изучала случайность. Кости, смертность, ошибки измерений, броуновское движение — во всех точках случай был предметом.
Здесь направление меняется: случайность становится инструментом для решения задач, в которых никакого случая нет. Число $\pi$ детерминировано; интеграл детерминирован; уравнение переноса детерминировано — а вычисляем мы их бросанием костей.
Тот же поворот в чистой математике совершает вероятностный метод (Борель, затем ЭрдёшПал ЭрдёшПолторы тысячи статей, пятьсот соавторов, ни дома, ни семьи, ни постоянной работы — сорок лет он ездил из университета в университет с одним чемоданом.): случайный объект как доказательство существования детерминированного. Три точки — БорельЭмиль БорельПридумал меру, на которой стоит вся современная теория вероятностей, а потом ушёл в политику — был министром флота, депутатом и сидел в тюрьме при Виши., Улам и фон Нейман, Эрдёш и Реньи — стоит рассматривать как одну идею в трёх воплощениях.