Знакомство с методом Монте-Карло

В данной статье мы не будем углубляться в математику, а постараемся дать общее представление о методе Монте-Карло.

Суть метода заключается в следующем: для целевой случайной величины генерируется набор случайных значений, а затем на его основе рассчитываются требуемые значения.

Метод Монте-Карло имеет множество различных приложений. Он применяется в следующих областях: в промышленности для моделирования изменчивости производственных процессов; в физике, химии и биологии для моделирования разнообразных явлений; в области игр для моделирования искусственного интеллекта, например, в китайской игре го; в области финансов для оценки производных финансовых инструментов и опционов. По сути, метод Монте-Карло используется везде.

Современный вариант метода сформировался в рамках Манхэттенского проекта, где он применялся для моделирования расстояний, которые могут пройти нейтроны в различных материалах. Идея моделирования на основе генерации набора случайных значений существовала уже в течение некоторого времени, но особое развитие получила при создании атомной бомбы, распространившись затем во многих других областях знаний.

Большим преимуществом метода Монте-Карло является то, что он позволяет учесть в модели элемент случайности и сложность реального мира. Кроме того, метод является робастным по отношению к изменению различных параметров, таких как распределение случайной величины. В его основе лежит закон больших чисел.

Одним из типичных примеров использования метода Монте-Карло являются задачи, в которых необходимо найти математическое ожидание некоторой случайной величины. Для этого нужно сгенерировать набор случайных значений данной величины и найти среднее. Случайная величина обычно характеризуется определенным распределением вероятностей.

Вычисление числа Пи

С помощью метода Монте-Карло можно вычислить число Пи. Код на R для данного примера находится здесь.

Вписав круг в квадрат (диаметр круга равен стороне квадрата), можно выразить отношение площади круга к площади квадрата следующим образом:

Если мы сможем вычислить это отношение, значит, мы сможем получить значение числа Пи.

Заполним квадрат точками со случайными координатами. Рассчитаем отношение количества точек, попавших в круг, к общему количеству точек. Умножим результат на 4, чтобы получить значение числа Пи.

Чем больше количество точек, тем ближе полученное значение к истинному значению числа Пи.

Этот простой пример демонстрирует метод Монте-Карло в действии.

Моделирование транспортных потоков

Рассмотрим более полезный пример. Мы можем смоделировать транспортный поток с помощью модели Нагеля-Шрекенберга (Nagel-Schreckenberg model). В рамках этой модели трасса состоит из ячеек, задана максимально допустимая скорость и определенное количество автотранспортных средств (АТС). На каждом шаге состояние всех АТС обновляется в соответствии со следующими правилами:

1. Скорость данного АТС v увеличивается на единицу, если она меньше максимально допустимой скорости.
2. Найдем расстояние d между данным АТС и впереди идущим АТС. Если скорость данного АТС больше либо равна расстоянию d, она уменьшается до величины d-1.
3. С помощью метода Монте-Карло добавим элемент случайности. С вероятностью p скорость данного АТС уменьшается на единицу.
4. Данное АТС перемещается вперед на v единиц.

Эта модель достаточно проста, но при этом очень эффективна. В данной модели не учитываются ДТП или плохое вождение. Ее назначением является моделирование спонтанных изменений в характере транспортных потоков. Существуют и более сложные модели, но многие из них основаны на модели Нагеля-Шрекенберга.

Код для моделирования находится здесь, а для визуализации на языке Processing – здесь.

Проблемы в рамках метода Монте-Карло

Основной проблемой является генерация независимых случайных величин. Это не такая простая задача, как может показаться на первый взгляд. В примерах кода мы просто вызывали встроенные функции R или Python для генерации случайных чисел, но этот процесс может быть намного более сложным. При необходимости вы можете обратиться к научным источникам по данной теме.

По этой ссылке вы можете найти информацию о том, как в R осуществляется генерация случайных чисел с равномерным распределением (uniform distribution).

Другая проблема состоит в том, как обеспечить сходимость ошибки. Обратите внимание на то, что в примере вычисления числа Пи ошибка перестала уменьшаться. В большинстве приложений метода Монте-Карло для решения этой проблемы используются очень большие выборки.

Метод Монте-Карло – очень интересная тема для изучения. Надеюсь, данная статья сделает этот метод еще более популярным за пределами сферы физики и финансов.

По материалам: Analyticbridge