МЕТОД МОНТЕ-КАРЛО
- Способ исследования поведения вероятностных систем экономических, технических и т.п. в условиях, когда неизвестны в полной мере внутренние взаимодействия в этих системах.
Создателями метода статистических испытаний (метода Монте-Карло) считают американских математиков Д. Неймана и С. Улама. В 1944 году, в связи с работами по созданию атомной бомбы Нейман предложил широко использовать аппарат теории вероятностей для решения прикладных задач с помощью ЭВМ. Данный метод был назван так в честь города в округе Монако, из-за рулетки, простейшего генератора случайных чисел.
Первоначально метод Монте-Карло использовался главным образом для решения задач нейтронной физики, где традиционные численные методы оказались мало пригодными. Далее его влияние распространилось на широкий класс задач статистической физики, очень разных по своему содержанию. К разделам науки, где все в большей мере используется метод Монте-Карло, следует отнести задачи теории массового обслуживания, задачи теории игр и математической экономики, задачи теории передачи сообщений при наличии помех и ряд других.
Метод Монте-Карло (или метод статистических испытаний) можно определить как метод моделирования случайной величины с целью вычисления характеристик их распределений. Суть состоит в том, что результат испытаний зависит от некоторой случайной величины, распределенной по заданному закону. Поэтому результат каждого отдельного испытания носит случайный характер. (Как правило, составляется программа для осуществления одного случайного испытания.) Проведя серию испытаний, получают выборку. Полученные статистические данные обрабатываются и представляются в виде численных оценок интересующих исследователя величин (характеристик системы).
Т.е. испытание повторяется N раз, причем каждый опыт не зависит от остальных, и результаты всех опытов усредняются. Это значит, что число испытаний должно быть достаточно велико, поэтому метод существенно опирается на возможности компьютера.
Теоретической основой метода Монте-Карло являются предельные теоремы теории вероятностей. Они гарантируют высокое качество статистических оценок при весьма большом числе испытаний. Метод статистических испытаний применим для исследования как стохастических, так и детерминированных систем. Практическая реализация метода Монте-Карло невозможна без использования компьютера.
Можно проиллюстрировать метод статистических испытаний на простейшем примере: вычисление числа π как отношение площади 1/4 круга к площади всей картинки путем разбрасывания случайным образом точек по всему рисунку. Затем считается отношение попавших в круг точек ко всем точкам, и по этому отношению приблизительно определяется отношение площадей. Увеличением числа вбрасываемых точек можно более точно определить площадь круга, но это так же ведет и к увеличению времени вычислений.
Точность вычислений очень сильно зависит от качества используемого генератора псевдослучайных чисел. Другими словами, точность тем выше, чем более равномерно случайные точки распределяются по единичному квадрату.
p»4Sкр/Sкв (1)
Подсчитаем число точек внутри квадрата и внутри четверти круга. Очевидно, что их отношение будет приближенно равно отношению площадей этих фигур , так как попадание капель в различные места чертежа равновероятно. Пусть Nкр - число капель в круге,Nкв –число капель в квадрате , тогда
p»4Nкр/Nкв
(2)
|
|
|
Каждому точке поставим в соответствие два случайных числа, характеризующих его положение вдоль осей Ох и Оу (см. рис. 2). Если окажется, что для точки (хi,уi) выполняется неравенство хi2+уi2>1, то, значит, она лежит вне круга. Если хi2 +уi2 Ј 1, то точка лежит внутри круга.
Для подсчета значения p
воспользуемся формулой (2). Ошибка вычислений по этому методу, как правило
пропорциональна 
,
где D – некоторая постоянная, а N – число испытаний. В этом примере 
.
Из этой формулы видно, что для того, чтобы уменьшить ошибку в 10 раз, т.е.
получить ещё один верный десятичный знак, нужно увеличить N, т.е. объём работы,
в 100 раз (см. таблицу с результатами испытаний).
ИМИТАЦИЯ СЛУЧАЙНЫХ ВЕЛИЧИН И ПРОЦЕССОВ
Моделирование случайных элементов в системах является одной из самых главных, базовых задач математического моделирования.
Любая случайная величина или процесс X может моделироваться следующим образом:
Базовый датчик выдает независимые равномерно распределенные случайные величины:
непрерывные в [0,1);
дискретные в 
Типы базовых датчиков:
физические (любой физический шум) – не используются, т.к. характеристики нестабильны и реализацию повторить нельзя;
псевдослучайные – строятся на основе детерминированного алгоритма, но полученные результаты неотличимы от случайных.
Псевдослучайные базовые датчики строятся по модели 
при
заданном 
Требования к базовым датчикам и их проверка
Периодом T и длиной отрезка апериодичности датчика называются наименьшие из величин, удовлетворяющие
Чем больше T и L, тем лучше датчик (особенно L).
Как определить их:
Берем V – достаточно большое число (обычно 
Генерируем 
и
проверяем 
,запоминая.
Генерируем 
и
проверяем 
.
Если нет для 
,
то 
и
.
Иначе запоминаем 
,
для которого 
,
и находим следующий 
,
для которого 
(если
нужно, генерируются дополнительные величины). Тогда 
Генерируем 
и
и
ищем первое совпадение 
.
Тогда 
Должно быть 
для
Проверка:
Берем 
и
генерируем 
Находим 
и
разбиваем отрезок [0,1) на k равных частей (длиной 
)
Для каждого числа 
определяем,
в какой интервал оно попало:
и заполняем массив 
:
По значениям этого массива строим гистограмму (для наглядности).
Используем критерий 
.
Выбираем уровень значимости 
(обычно
5%), а число степеней свободы 
.
В таблицах находим
значение 
и
проверяем: если 
,то
«данные эксперимента не противоречат гипотезе о равномерности случайных чисел»,
иначе – «противоречат».
Генерируем 
Вычисляем 
,
(можно
и больше).
Вычисляем 
Проверяем для всех k
Если да, то «данные эксперимента не противоречат гипотезе о
равномерности случайных чисел», иначе – «противоречат». Здесь –
уровень значимости, а 
берется
из таблиц 
4. Простейшие проверки
Подходят для любой непрерывной случайной величины.
Математическое ожидание: 
Дисперсия:
Мультипликативный конгруэнтный метод (метод вычетов)
В основе лежит следующее рекуррентное соотношение:
–
множитель, M – модуль, 
–
стартовое значение. Рекомендуемые значения для 64-разрядной сетки:
Тогда период 
Для 32-разрядной:
Тогда период 
p – порядок, стартовые значения: 
.
Период 
Частный случай. Датчик Терпугова.
function Rand (var y: Integer): Double;
const b=843314861;
c=453816693;
m2=1073741824; {M/2}
begin
{$O-,$R-} {Optimization- & Range Check-}
y:=y*b+c;
if y<0 then y:=(y+m2)+m2;
Result:=Double(y)*0.4656613E-09;
end;
Причем 
тогда
и только тогда, когда 
Существуют и другие методы моделирования базовых датчиков.
Пусть имеется некоторое случайное событие А, наступающее с
вероятностью р(А). Тогда 
(
– числа, генерируемые базовым датчиком). Следовательно, генератор 1 случайного
события:
,где
Полная группа попарно несовместимых событий 
.
Пусть 
Идея:
ГЕНЕРАЦИЯ ДИСКРЕТНЫХ СЛУЧАЙНЫХ ВЕЛИЧИН
Пусть имеется дискретная случайная величина с рядом распределения.
|
x |
|
|
... |
|
|
p |
|
|
... |
|
,
Т.о. задача сводится к генерации полной группы попарно
несовместимых событий. Т.е., если наступило 
,
.
Программная реализация
Специальные методы генерации некоторых дискретных случайных величин
|
x |
0 |
1 |
... |
n |
|
p |
|
|
... |
|
Тогда
Док-во.
x
удовлетворяет равномерному распределению.
x = 0,1,2,... до 
Док-во.
Отрицательное биномиальное распределение.
х=0,1,2,... до
Параметры: 
,
и 
Для 
это
распределение совпадает с геометрическим, поэтому можно представить 
,
где 
-
независимые случайные величины, распределенные по геометрическому закону. Т.о.
(базовый датчик должен выдать r чисел для генерации одного х).
(теорема
об опытах – вероятность наступления m событий A в n опытах).
Введем 
(функция
Хэвисайда).
Тогда
наступило
1 события 
сумма
дает кол-во событий наступивших в n опытах 
биномиальное
распределение).
