Теоретическая часть. 
Метод Монте-Карло

Сущность метода Монте-Карло и моделирование случайных величин

Некоторые сведения теории вероятностей Предположим, что нам необходимо вычислить площадь плоской фигуры. Это может быть произвольная фигура, заданная графически или аналитически (связная или состоящая из нескольких частей), рис. 1.1.

Рис. 1.1.

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

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

Непрерывная случайная величина определяется заданием интервала, содержащего возможные значения этой величины, и функции, которая называется плотностью вероятностей случайной величины (плотностью распределения). Физический смысл следующий: пусть — произвольный интервал, такой что, тогда вероятность того, что окажется в интервале, равна интегралу.

(1.1).

Множество значений может быть любым интервалом (возможен случай). Однако плотность должна удовлетворять двум условиям:

1) плотность положительна:

; (1.2).

2) интеграл от плотности по всему интервалу равен 1:

(1.3).

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

(1.4).

Дисперсией непрерывной случайной величины называется число:

.

Нормальной случайной величиной называется случайная величина, определённая на всей оси и имеющая плотность.

(1.5),.

где — числовые параметры.

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

.

называемой обычно интегралом вероятностей.

Согласно (1.1),.

.

В интеграле сделаем замену переменной, тогда получим ;

.

где .

Отсюда следует, что Также .

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

Выбрав, , найдём. Следовательно,.

(1.6).

Вероятность настолько близка к 1, что иногда последнюю формулу интерпретируют так: при одном испытании практически невозможно получить значение, отличающееся от больше чем на .

Проводя большое количество опытов, и получая большое количество случайных величин можно воспользоваться центральной предельной теоремой теории вероятностей. Эта теорема впервые была сформулирована П. Лапласом. Обобщением этой теоремы занимались многие выдающиеся математики, в том числе П. Л. Чебышёв, А. А. Марков, А. М. Ляпунов. Её доказательство достаточно сложно.

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

Обозначим.

Сумму всех этих величин обозначим через .

Используя соотношения.

получаем:

Рассмотрим теперь нормальную случайную величину с такими же параметрами:

.

В центральной предельной теореме утверждается, что для любого интервала при больших.

Смысл этой теоремы в том, что сумма большого числа одинаковых случайных величин приближенно нормальна. На самом деле эта теорема справедлива при гораздо более широких условиях: все слагаемые не обязаны быть одинаковыми и независимыми; существенно только, чтобы отдельные слагаемые не играли большой роли в сумме. Эта теорема оправдывает часто встречающиеся нормальные случайные величины. В самом деле, когда встречается суммарное воздействие большого числа незначительных случайных факторов, результирующая случайная величина оказывается нормальной.

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

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

Последнее соотношение перепишем в виде:

(1.7).

Это соотношение даёт и метод расчёта, и оценку погрешности.

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

.

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

Таблицы случайных чисел используют предпочтительно при расчётах вручную. Определяющую роль в этом играют два факта: 1) при использовании ЭВМ легче и удобней воспользоваться генератором случайных чисел, получаемых тут же, чем загружать из памяти значения таблицы, которая к тому же, будет занимать там место. 2) При подсчёте вручную нет необходимости использовать ЭВМ, так как часто необходимо выяснить лишь порядок искомой величины.

Генераторы случайных чисел анализируют какой-либо процесс, доступный для них (шумы, скачки напряжения) и составляют последовательность из 0 и 1, из которых составляются числа с определёнными разрядами, однако такой метод получения случайных величин имеет свои недостатки. Во-первых, трудно проверить вырабатываемые числа. Проверки приходится делать периодически, так как из-за каких-либо неисправностей может возникнуть так называемый дрейф распределения (нули и единицы в каком-либо из разрядов станут появляться не одинаково часто). Во-вторых, обычно все расчёты на ЭВМ проводятся несколько раз, чтобы исключить возможность сбоя. Но воспроизвести те же самые случайные числа невозможно, если их только не запоминать по ходу счёта. А если запоминать, то снова появляется случай таблиц.

Таким образом, самым эффективным способом получения случайных чисел — это использование псевдослучайных чисел.

Числа, получаемые по какой-либо формуле и имитирующие значения случайной величины, называются псевдослучайными числами.

Первый алгоритм для получения псевдослучайных чисел был предложен Дж. Нейманом. Он называется методом середины квадратов.

Пусть задано 4-значное число. Возведём его квадрат. Получим 8-значное число. Выберем 4 средние цифры этого числа и положим. Далее и т. д.

Но этот алгоритм не оправдал себя, так как получается слишком много малых значений. Поэтому были разработаны другие алгоритмы. Наибольшее распространение получил алгоритм, называемый методом сравнений (Д. Лемер): определяется последовательность целых чисел, в которой начальное число задано, а все последующие числа вычисляются по одной и той же формуле.

при (1.8).

По числам вычисляются псевдослучайные числа.

(1.9).

Формула (1.8) означает, что число равно остатку, полученному при делении на, такой остаток называют наименьшим положительным вычетом по модулю Формулы (1.8), (1.9) легко реализовать на ЭВМ.

Достоинства метода псевдослучайных чисел довольно очевидны. Во-первых, на получение каждого числа затрачивается всего несколько простых операций, так что скорость генерирования случайных чисел имеет тот же порядок, что и скорость работы ЭВМ. Во-вторых, программа занимает не так много места в памяти. В-третьих, любое из чисел может быть легко воспроизведено. В-четвёртых, необходимо лишь один раз проверить «качество» такой последовательности, затем её можно много раз безбоязненно использовать при расчёте однотипных задач.

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

Значения любой случайной величины можно получить путём преобразования значений одной какой-либо случайной величины. Обычно роль такой случайной величины играет случайная величина, равномерно распределённая в (0, 1).

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

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

(1.10),.

т.е. выбрав очередное значение, надо решить уравнение (1.10) и найти очередное значение .

Может оказаться, что разрешить уравнение (1.10) относительно трудно, например, в случаях, когда интеграл от не выражается через элементарные функции или когда плотность задана графически. Предположим, что случайная величина определена на конечном интервале и плотность её ограничена .

Разыгрывать значение можно следующим образом:

1) выбираются два значения и случайной величины и строится случайная точка с координатами .

2) если точка лежит под кривой, то полагаем, если же точка лежит над кривой, то пара отбрасывается и выбирается новое значение.