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

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

Метод Монте – Карло используют:

• Для вычисления интегралов

• Для решения систем алгебраических уравнений высокого порядка

• Для исследования сложных систем: экономических, биологических, социальных.

Суть метода

Требуется найти значение а некоторой изучаемой величины. Для этого выбирается такая случайная величина X, что ее математическое ожидание M(X)=a.

Генерируется n значений случайной величины X, вычисляется их среднее арифметическое . В качестве оценки искомого числа а принимают .

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

Отыскание возможных значений случайной величины X (моделирование) называют разыгрыванием случайной величины.

Вычисление определенного интеграла методом статистических испытаний (методом Монте - Карло)

Вычислим методом статистических испытаний следующий интеграл

,

где функция y = f(x) непрерывна, и положительна на отрезке [a, b]

Из курса математики известно, что определенный интеграл равен площади криволинейной трапеции, ограниченной прямыми x = а, х = b, осью абсцисс и графиком функции y = f(x) (см. рис.1).

рис.1

В курсе теории вероятностей приводится несколько определений вероятности. По геометрическому определению в плоскости вероятность попадания в область d точки, брошенной в область D (d  D) равна отношению площадей, то есть

.

По статистическому определению вероятность наступления события приближенно равна отношению числа опытов m, в результате которых событие наступило, к общему числу всех опытов n, то есть

.

В геометрическом определении в качестве области d будем рассматривать криволинейную трапецию, в качестве D – прямоугольник {a ≤ x ≤ b, 0 ≤ y ≤ f(x)}. В статистическом определении в качестве проводимого опыта возьмем бросание точки в прямоугольник D, а в качестве события – попадание точки в область d. Получаем формулу

P = .

Отсюда формула

Тогда для решения задачи нужно провести достаточное количество опытов – n. Опыт заключается в случайном выборе точки (x_i, y_i) из D:

a ≤ x_i ≤ b, 0 ≤ y_i ≤ f(x).

Так же необходимо подсчитать количество опытов m, в которых точка (x_i, y_i) принадлежит криволинейной трапеции, то есть y_i ≤ f(x_i). Тогда интеграл можно вычислить по формуле

.

Результат вычисления интеграла будет тем точнее, чем больше опытов будет проведено.

Элементы теории случайных процессов

Случайным процессом X(t) называется процесс, значение которого при любом значении аргумента t является случайной величиной (чаще всего t – это время).

Примеры: движение молекул газа во времени, уровень воды в водохранилище.

Случайный процесс можно записать в виде функции двух переменных X(t,ω), где ω – элементарное событие.

Реализацией (траекторией) случайного процесса X(t,ω) называется неслучайная функция x(t), т. е. фиксируется ω.

Сечение случайного процесса X(t,ω) – это случайная величина, полученная при фиксировании t, т. е. X(t₀,ω) – это случайная величина.

Таким образом, случайный процесс X(t,ω) – это совокупность всех сечений при возможных значениях t, т. е. многомерная случайная величина (X(t₁); X(t₂); …; X(t_n)).

Математическое ожидание случайного процесса X(t,ω) – это неслучайная функция от t M[X(t)], которая при любом значении t равна значению математическому ожиданию соответствующего сечения. Оно характеризует среднюю траекторию всех возможных реализаций случайного процесса.

Дисперсия случайного процесса X(t,ω) – это неслучайная функция от t D[X(t)], которая при любом значении t равна значению дисперсии соответствующего сечения случайного процесса. Дисперсия характеризует разброс реализаций относительно средней траектории.

Среднее квадратическое отклонение случайного процесса X(t,ω) вычисляется как.

Теснота зависимости между двумя сечениями случайного процесса X(t,ω) характеризуется корреляционной функцией. Это неслучайная функция от двух переменных

Нормированная корреляционная функция

Говорят, что в физической системе происходит случайный процесс, если она с течением времени может под влиянием случайных факторов переходить из состояния в состояние.

Если система имеет счетное (в частном случае конечное) множество возможных состояний и переход из одного состояния в другое осуществляется скачком, случайный процесс называется дискретным, т. е. X(t) принимает дискретные значения.

Если число состояний бесконечно много и функция X(t) принимает любые значения из заданного промежутка, то случайный процесс называется непрерывным.

Если переходы системы из состояния в состояние возможны только в определенные моменты времени (аргумент t дискретный), то случайный процесс называется случайной последовательностью (процессом с дискретным временем).

Если переходы системы из состояния в состояние возможны в любой момент времени (аргумент t непрерывный), то случайный процесс называется процессом с непрерывным временем.

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

Марковский случайный процесс с дискретным числом состояний и с дискретным временем называется Марковской цепью.

Пусть p_ij(s) – условная вероятность того, что после s-ого испытания система будет находится в j-ом состоянии, если после (s-1)-ого испытания она находилась в i-ом состоянии.

Цепь Маркова называется однородной, если вероятность p_ij(s) не зависит от номера испытания s. Тогда p_ij называют переходной вероятностью, П=(p_ij) – матрицей переходов. Заметим, что для любого номера состояния i выполняется условие (k – число состояний).