Алгоритм Бюффона для определения числа Пи
Ме́тод Мо́нте-Ка́рло (методы Монте-Карло, ММК) — общее название группы численных методов, основанных на получении большого числа реализаций стохастического (случайного) процесса, который формируется таким образом, чтобы его вероятностные характеристики совпадали с аналогичными величинами решаемой задачи. Используется для решения задач в различных областях физики, химии, математики, экономики, оптимизации, теории управления и др.
История
Алгоритм Бюффона для определения числа Пи
Случайные величины использовались для решения различных прикладных задач достаточно давно. Примером может служить способ определения числа Пи, который был предложен Бюффоном еще в 1777 году. Суть метода была в бросании иглы длиной L на плоскость, расчерченную параллельными прямыми, расположенными на расстоянии r друг от друга (см. Рис. 1).
Рисунок 1. Метод Бюффона
Вероятность (как видно из дальнейшего контекста, речь идёт не о вероятности, а о математическом ожидании количества пересечений за один опыт; вероятностью это становится лишь при условии, что r > L) того, что отрезок пересечет прямую, связана с числом Пи:
, где
- A — расстояние от начала иглы до ближайшей к ней прямой;
- θ — угол иглы относительно прямых.
Этот интеграл просто взять: 
(при условии, что r > L), поэтому подсчитав долю отрезков, пересекающих прямые, можно приближенно определить это число. При увеличении количества попыток точность получаемого результата будет увеличиваться.
В 1864 году капитан Фокс, выздоравливая после ранения, чтобы как-то занять себя, реализовал эксперимент по бросанию иглы. Результаты представлены в следующей таблице:
| Число бросаний | Число пересечений | Длина иглы | Расстояние между прямыми | Вращение | Значение Пи | |
| Первая попытка | 500 | 236 | 3 | 4 | отсутствует | 3.1780 |
| Вторая попытка | 530 | 253 | 3 | 4 | присутствует | 3.1423 |
| Третья попытка | 590 | 371 | 5 | 2 | присутствует | 3.1416 |
Комментарии:
- Вращение плоскости применялось (и как показывают результаты — успешно) для того, чтобы уменьшить систематическую ошибку.
- В третьей попытке длина иглы была больше расстояния между линиями, что позволило не увеличивая числа бросаний эффективно увеличить число событий и повысить точность.
Связь стохастических процессов и дифференциальных уравнений
Создание математического аппарата стохастических методов началось в конце XIX века. В 1899 году лорд Релей показал, что одномерное случайное блуждание на бесконечной решётке может давать приближенное решение параболического дифференциального уравнения. Андрей Колмогоров в 1931 году дал большой толчок развитию стохастических подходов к решению различных математических задач, поскольку он сумел доказать, что цепи Маркова связаны с некоторыми интегро-дифференциальными уравнениями. В 1933 году Иван Петровский показал, что случайное блуждание, образующее Марковскую цепь, асимптотически связано с решением эллиптического дифференциального уравнения в частных производных. После этих открытий стало понятно, что стохастические процессы можно описывать дифференциальными уравнениями и, соответственно, исследовать при помощи хорошо на тот момент разработанных математических методов решения этих уравнений.