Метод Монте-Карло (Monte-Carlo technique)
Синонимы: Метод статистических испытаний
Разделы: Алгоритмы
Методы Монте-Карло представляют собой широкий класс вычислительных алгоритмов, которые основаны на многократной случайной выборке. Часто методы Монте-Карло позволяют получить результат там, где другие подходы не работают.
Методы Монте-Карло используются при решении задач оптимизации, численного интегрирования, анализа рисков в бизнесе и других задач. В принципе, методы Монте-Карло могут быть использованы для решения любой задачи, имеющей вероятностную постановку.
Несмотря на различия, методы Монте-Карло используют примерно одну и ту же схему:
- Определяется модель или алгоритм, которые лучше всего соответствуют данным, описывающим исследуемый объект или процесс.
- Модель многократно применяется к данным, сгенерированным случайным образом в соответствии с распределением вероятности исходных данных, формируя каждый раз некоторую реализацию случайной выходной переменной.
- Полученные реализации усредняются, и к результатам усреднения применяются статистические методы для оценки параметров вариации, доверительных интервалов и т.д.
Например, пусть нужно определить, как долго покупателям придется ожидать в очереди при заданной пропускной способности магазина (скажем, с целью принять решение о необходимости его расширения).
Появление покупателей носит случайный характер, распределение времени подхода (промежутка времени между двумя приходами покупателей) может быть установлено из информации, собираемой контрольно-кассовыми машинами. Время, требуемое для обслуживания покупателей, также носит случайный характер, и его распределение тоже может быть определено. Таким образом, имеются два случайных процесса, взаимодействие которых и определяет очередь.
Теперь, если случайно генерировать все комбинации (например, число покупателей, приходящих за час), сохраняя те же характеристики распределения, можно искусственно воссоздать картину данного процесса. Повторяя данное испытание многократно, каждый раз меняя условия (число приходящих покупателей), можно изучать получаемые результаты так, как если бы они были получены при наблюдении над реальным потоком покупателей.
Таким образом, смысл метода заключается в моделировании исследуемого процесса путем многократных повторений его случайных реализаций, называемых статистическими испытаниями.
Методы Монте-Карло впервые были применены Энрико Ферми в исследованиях электронной диффузии.