Учебное пособие по решению распространенных вероятностных головоломок с использованием моделирования Монте-Карло на Python
Если вы интересуетесь разгадыванием вероятностных головоломок, велика вероятность, что вы столкнулись с головоломками, которые требуют от вас найти ожидаемое количество попыток, прежде чем вы увидите требуемый результат.
Если вы решили достаточно из них, скорее всего, вы знаете, как решать их аналитически. Я надеюсь, что эта статья позволит вам решить те же вопросы с использованием другого подхода, снабдив вас еще одним трюком в рукаве, если вам сложно решить проблему аналитически.
Но сначала, что такое методы Монте-Карло (МК)? Согласно Википедии,
«Методы Монте-Карло - это широкий класс вычислительных алгоритмов, которые полагаются на повторную случайную выборку для получения численных результатов. Основная идея заключается в использовании случайности для решения проблем, которые в принципе могут быть детерминированными ».
Давайте попробуем понять MC дальше с помощью простой, но практической задачи. Как можно оценить значение π с помощью MC?
- Нарисуйте квадрат и начертите квадрант круга с радиусом, равным стороне квадрата внутри него.
- Равномерно разбросайте заданное количество точек по поверхности квадрата.
- Подсчитайте количество точек, лежащих внутри круга.
- Найдите отношение точек, попавших внутрь этого круга, к общему количеству точек. Теоретически это соотношение составляет π / 4. Умножьте указанное соотношение на 4, чтобы получить значение π.
Интуитивно видно, что точность увеличивается по мере увеличения количества точек, которые мы разбрасываем по поверхности квадрата. Отношение приближается к π / 4 для бесконечного числа точек.
Солома, сломавшая верблюжью спину
Эта головоломка сформулирована на основе известной идиомы о том, как верблюд прогибается под, казалось бы, незначительным дополнительным весом последней соломинки.
Математически предположим, что соломинки одну за другой кладут на спину верблюда. Вес соломинки с равной вероятностью будет иметь любое реальное значение от 0 до 1. Спина верблюда ломается, когда вес соломинки превышает 1. Найдите ожидаемое значение веса последней соломинки.
Вы можете подумать, будет ли ожидаемый вес последней соломинки отличаться от 0,5, что является ожидаемым значением веса одной соломинки. Ответ - да, потому что более тяжелая соломка с большей вероятностью сломает спину верблюду, чем более легкая. Следовательно, интуитивно понятно, что ожидаемый вес последней соломинки больше 0,5.
Прежде чем двигаться дальше, попробуйте решить эту проблему аналитически и посмотрите, сможете ли вы прийти к правильному ответу.
Подход Монте-Карло
Используя Python, давайте смоделируем перелом спины верблюда, добавив соломинку к его спине.
Отказ от ответственности: во время моделирования этой головоломки ни один верблюд не пострадал.
Определите функцию break_camel_back (), чтобы возвращать вес соломы, которая сломала спину верблюда, и expected_weight_of_last_straw (n), который имитирует сломание спины верблюда n раз и возвращает средний вес соломы, которая каждый раз сломала спину верблюда. Для больших значений n результат этой функции является ответом на наш вопрос.
Видно, что для больших значений (в данном случае 2¹⁹) ожидаемое значение приближается к значению около 0,64, что соответствует нашей интуиции.
Точное математическое ожидание равно 2-e / 2, что составляет примерно 0,640859 (Престижность тем, кто успешно решил это аналитически). Не волнуйтесь, если вы не смогли решить ее аналитически, вы можете найти решение здесь.
Дополнительное упражнение: настройте код, чтобы найти ожидаемое количество соломинок, которые сломают спину верблюда при таком же распределении веса. (Ответ - e)
Ожидаемое количество подбрасываний монеты для получения шаблона "TXT"
Найдите ожидаемое значение количества переворотов, которое вам нужно будет сделать, чтобы увидеть шаблон «TXT», где T - решка, а X - орел или решка.
(Вы будете подбрасывать монету, пока не заметите TTT или THT и не подсчитаете количество сделанных подбрасываний монеты)
Подход Монте-Карло
Определите функцию coin_toss (), которая имитирует подбрасывание монеты с помощью выбора из случайной библиотеки. Инициализировать res как 3 (минимальное количество бросков для получения шаблона TXT) и вернуть количество бросков, когда это произойдет.
Как и раньше, определите expected_tosses (), чтобы возвращать среднее количество бросков, необходимых для генерации шаблона «TXT».
Видно, что для больших значений (в данном случае 2¹⁹) ожидаемое значение стремится к значению около 6,8.
Аналитически это легко решить с помощью набора линейных уравнений.
После решения уравнений для E мы находим ответ 34/5 (6,8), и моделирование MC соответствует результату.
Это оно!
Мы установили, что методы Монте-Карло служат мощным инструментом для моделирования простых случайных событий. Применение этих методов не ограничивается только вероятностными головоломками, но охватывает области финансов, вычислительной биологии, науки о данных, инженерии и даже права!
Дайте мне знать, что вы думаете в комментариях, или что бы вы хотели, чтобы я подробно рассказал.
Новичкам рекомендую начинать здесь.
