Метод Монте Карло Казино

метод монте карло казино

править код]

Предположим, требуется вычислить определённый интеграл

$\int \limits _{{a}}^{{b}}f(x)\,dx$

Рассмотрим случайную величину , равномерно распределённую на отрезке интегрирования [a,b] . Тогда f(u) также будет случайной величиной, причём её математическое ожидание выражается как

$\mathbb {E} f(u)=\int \limits _{a}^{b}f(x)\varphi (x)\,dx,$

где $\varphi (x)$ &#;— плотность распределения случайной величины , равная ${\frac {1}{b-a}}$ на участке [a,b] . Таким образом, искомый интеграл выражается как

$\int \limits _{a}^{b}f(x)\,dx=(b-a)\mathbb {E} f(u),$

но математическое ожидание случайной величины f(u) можно легко оценить, смоделировав эту случайную величину и посчитав выборочное среднее.

Итак, бросаем точек, равномерно распределённых на [a,b] , для каждой точки $u_{i}$ вычисляем $f(u_{i})$ . Затем вычисляем выборочное среднее: ${\frac {1}{N}}\sum _{{i=1}}^{{N}}f(u_{i})$ . В итоге получаем оценку интеграла:

$\int \limits _{a}^{b}f(x)\,dx\approx {\frac {b-a}{N}}\sum _{i=1}^{N}f(u_{i}).$

Точность оценки зависит только от количества точек .

Этот метод имеет и геометрическую интерпретацию. Он очень похож на описанный выше детерминистический метод, с той разницей, что вместо равномерного разделения области интегрирования на маленькие интервалы и суммирования площадей получившихся «столбиков» мы забрасываем область интегрирования случайными точками, на каждой из которых строим такой же «столбик», определяя его ширину как ${\frac {b-a}{N}}$ , и суммируем их площади.

Геометрический алгоритм Монте-Карло интегрирования[править править код]

Соболь И. М. Метод Монте-Карло.&#;— М.: Наука, &#;— 64&#;с.&#;— (Популярные лекции по математике).&#;— 79&#; экз.
Статья «Моделируя жизнь», автор Андрей Тепляков
Metropolis, N., Ulam, S. The Monte Carlo Method,&#;— Journal of the American Statistical Association 44 №&#; —
Alex F Bielajew. Fundamentals of the Monte Carlo method for neutral and charged particle transport.
W. M. C. Foulkes, L. Mitas, R. J. Needs and G. Rajagopal Quantum Monte Carlo simulations of solids,&#;— Reviews of Modern Physics 73 ()
Статья «Metropolis, Monte Carlo and the MANIAC»
Fishman, George S. Monte Carlo&#;: concepts, algorithms, and applications.&#;— Springer, &#;— ISBN X.

Метод Монте-Карло — один из самых полезных алгоритмов в ИТ

Казино и математика

Сегодня сложная тема, но мы объясним её просто и понятно. Разговор пойдёт про алгоритмы и немного про математику.

Методы Монте-Карло — это набор методов в математике для изучения случайных процессов. Случайных — это когда что-то в них происходит непредсказуемым образом, например:

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

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

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

Своё название метод получил в честь Монте-Карло — района Монако, где находится много казино с рулеткой, самым доступным источником случайных чисел в начале го века.

Если совсем примитивно, то работает так:

Вместо того чтобы строить сложную математическую модель, мы берём простую формулу и пуляем в неё случайные числа. Считаем результат по каждому числу и получаем результат с нужной нам точностью. Чем больше случайных чисел — тем точнее результат.

Вот то же самое немного подробнее:

Выбираем, что мы хотим найти или посчитать — значение формулы, площадь, объём, распределение материала или что-то ещё.
Смотрим, как это считается в математике, и находим нужные формулы.
На основе формул составляем критерий проверки — если случайное значение попало в этот критерий, мы его учитываем как совпавшее число, а если не попало — как не совпавшее.
Запускаем алгоритм, который выдаёт случайные числа, и проверяем каждое по этому критерию.
Как наберётся достаточное количество случайных чисел — считаем результат. Обычно это соотношение чисел, которые попали в критерий и которые не попали.

Чем больше будет случайных чисел — тем точнее результат.

Плюс этого метода в том, что нам не нужно запрягать весь математический аппарат для решения задачи — достаточно подставлять числа в формулу и смотреть, получилось верное значение или нет.

Для примера покажем классическое использование метода Монте-Карло — найдём число пи. Для этого нам понадобится круг, вписанный в квадрат, причём у круга радиус будет равен 1. Это значит, что сторона квадрата равна 2 — это диаметр (или два радиуса) круга:

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

Теперь смотрим на формулы:

площадь квадрата со стороной 2 равна четырём;
площадь круга радиусом 1 равна πR² → π×1² = π.

Если мы разделим площадь круга на площадь квадрата, то получим π / 4. Но мы ещё не можем по условию посчитать площадь круга, потому что мы не знаем число π. Вместо этого мы можем разделить количество одних песчинок на другие — в этом и суть метода Монте-Карло.

Это соотношение даст нам результат — π / 4. Получается, что если мы умножим этот результат на 4, то получим число π, причём чем больше песчинок мы кинем, тем точнее будет результат.

Кидать песчинки будем так: в качестве координат попадания X и Y будем брать случайные числа от 0 до 1. Это значит, что все числа попадут только в один квадрант — правый верхний:

Но так как в этом квадранте ровно четверть круга и ровно четверть квадрата, то соотношение промахов и попаданий будет таким же, как если бы мы бросали песчинки в целый круг и целый квадрат.

Чтобы проверить, попадает ли песчинка в круг, используем формулу длины гипотенузы: x² + Y² = 1 (так как гипотенуза — это радиус окружности):

Если длина гипотенузы меньше единицы — точка попадает в круг. В итоге мы посчитаем и общее количество точек, и точек, которые попали в круг. Потом мы разделим одно на другое, умножим результат на 4 и получим приближённое значение числа π.

Алгоритм на языке Python, читайте комментарии, чтобы лучше разобраться в происходящем:

На методах Монте-Карло основано много полезного:

моделирование облучения твёрдых тел ионами в физике;
моделирование поведения разреженных газов
исследования поведения разных тел при столкновении
алгоритмы оптимизации и нахождения кратчайшего пути решения
решение сложных интегралов (или когда их очень много)
предсказание астрономических наблюдений
поиск в дереве в различных алгоритмах
алгоритмы работы некоторых функций квантового компьютера
моделирование состояния приближённой физической среды

Без них изучать современный мир и совершать новые открытия было бы сложнее.

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

#Метод Монте-Карло

Метод Монте-Карло — общее название группы численных методов для решения прикладных задач при помощи моделирования случайных величин.

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

Простейший случай использование метода Монте-Карло — определение площади под графиком функции. Для этого необходимо ограничить функцию фигурой, чья площадь известна или легко вычисляема (S), затем «набросать» в эту фигуру некоторое количество точек (N) и подсчитать, сколько точек попало внутрь графика (I). Площадь области, ограниченной графиком функции и осями координат будет равна S*(I/N).

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

Принято считать, что метод Монте-Карло появился в году. Сотрудники Лос-Аламосской национальной лаборатории Станислав Улам, Джон фон Нейман и Николас Метрополис предположили, что можно использовать связь между случайными процессами и дифференциальными уравнениями «в обратную сторону». Однажды Улам задумался, какова вероятность того, что раскладываемый им карточный пасьянс удачно разрешится. Но вместо того, чтобы справиться с этой задачкой с помощью комбинаторики, он провел эксперимент большое количество раз и, подсчитав число успешных исходов, верно оценил вероятность.

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

Изображение: Becarlson/Wikimedia Commons