От пасьянса к атомной бомбе.

Станислав Улам в 1946 году перенёс операцию на мозге. Энцефалит. Тяжёлое восстановление. От скуки он раскладывал пасьянс «Канфилд».

Пасьянс «Канфилд»: 52 карты, сложная раскладка. Улам хотел знать: какова вероятность что пасьянс сойдётся? Комбинаторический расчёт невозможен — слишком много вариантов. Но можно сыграть сто раз и посчитать.

Улам подумал1: если можно так считать вероятность пасьянса — можно так же считать любой интеграл. Любую сложную задачу где аналитического решения нет. Запусти случайные числа. Считай результаты. Повторяй достаточно много раз. Ответ сойдётся к правильному по закону больших чисел.

Улам написал письмо Джону фон Нейману. Фон Нейман немедленно понял значение идеи. В Лос-Аламосе шли работы над водородной бомбой. Нужно было моделировать нейтронную диффузию — как нейтроны движутся через делящееся вещество. Уравнения слишком сложны для аналитического решения. Метод Улама подходил идеально.

Николас Метрополис — физик в Лос-Аламосе — реализовал метод на компьютере ENIAC. Ему нужно было название для секретных отчётов. Дядя Улама регулярно проигрывался в казино Монте-Карло. Метрополис предложил: Монте-Карло. Лучшее название в истории науки.

Статья «Equation of State Calculations by Fast Computing Machines» опубликована в 1953 году2. Авторы: Метрополис, Розенблут (двое), Теллер (двое). Улама нет среди авторов — его вклад был устным. Это алгоритм Метрополиса-Гастингса3. Одна из самых цитируемых статей в истории физики.

Идея метода: хочешь вычислить площадь произвольной фигуры. Вписываешь её в прямоугольник. Случайно бросаешь точки в прямоугольник. Считаешь сколько попало внутрь фигуры. Площадь фигуры ≈ площадь прямоугольника × доля попавших.

Чем больше точек — тем точнее. Ошибка убывает как 1/√n. 10 000 точек — точность ~1%. 1 000 000 точек — точность ~0.1%.

Метод Монте-Карло работает для любой размерности. Аналитические методы интегрирования теряют точность в высоких размерностях. Монте-Карло — нет. В 100-мерном пространстве всё то же самое. Это делает его незаменимым в физике частиц, финансах, машинном обучении.

MCMC — Markov Chain Monte Carlo. Если хочешь сэмплировать из сложного распределения — строишь цепь Маркова со стационарным распределением π. Запускаешь. Записываешь состояния. Это и есть сэмплы из π. Основа байесовской статистики. Стандартный способ считать то, что не берётся формулой.

Применения сегодня: физика частиц — симуляция столкновений в CERN. Финансы — оценка деривативов, VaR, симуляция портфелей. Климатология — модели атмосферы. Медицина — клинические испытания, дозирование. Компьютерная графика — рейтрейсинг (каждый пиксель Pixar). Машинное обучение — dropout, вариационные автоэнкодеры.

Улам выздоровел. Вернулся в Лос-Аламос. Вместе с Теллером — отец водородной бомбы. Вместе с фон Нейманом — у истоков клеточных автоматов. Написал автобиографию «Adventures of a Mathematician». Про пасьянс там тоже есть.

Метрополис умер в 1999-м. Улам — в 1984-м. Казино в Монако работает до сих пор4.