Теоретической основой метода Монте-Карло являются предельные теоремы теории вероятностей. Они гарантируют высокое качество статистических оценок при весьма большом числе испытаний. Метод статистических испытаний применим для исследования как стохастических, так и детерминированных систем. Практическая реализация метода Монте-Карло невозможна без использования компьютера.
1.2. Построение и тестирование датчиков базовой случайной величины
Базовой случайной величиной (БСВ) в статистическом моделировании называют непрерывную случайную величину z, равномерно распределенную на интервале (0 < t < 1). Её плотность распределения вероятностей (п. р. в.) задаётся формулой
ft=1, 0≤t≤1 (1.1)
Математическое ожидание (м. о.) M(z) и дисперсия D(z) базовой случайной величины z имеют следующие значения:
Mz=12, Dz=112
Нетрудно определить и начальный момент k — го порядка:
Mzk=11+k
БСВ моделируются на ЭВМ с помощью программных датчиков БСВ. Датчик БСВ — это программа, выдающая по запросу одно случайное значение БСВ z е{0 < t < 1}. Путём многократного обращения к датчику БСВ получают выборку независимых случайных значений z1, z2, z3, … , zn.
Программный датчик БСВ обычно вычисляет значения zb z2, z3, … по какой-либо рекуррентной формуле вида
zi+1=fzi (1.2)
при заданном стартовом значении z0.
Заданное значение z0 полностью определяет всю последовательность z1, z2, z3, … , поэтому величину z на выходе датчика БСВ называют псевдослучайной величиной. В практическом применении датчиков БСВ статистические свойства псевдослучайной последовательности чисел в широких пределах идентичны свойствам «чисто случайной» последовательности.
Путём преобразования БСВ можно получать модельные реализации многих других случайных объектов, включая любые непрерывные или дискретные случайные величины (как простые, так и многомерные), случайные события, случайные процессы, графы, схемы и т. д. Поэтому БСВ z называют базовой случайной величиной.
Рассмотрим для примера мультипликативный конгруэнтный метод. Этот датчик БСВ однозначно задаётся двумя параметрами: модулем m и множителем к. Обычно эти параметры представляют собой достаточно большие целые числа.
Проводим моделирование по формуле:
Ai=kAi-1mod m, zi=Aim, (1.3)
где zi — очередное значение БСВ (0 < z < 1); m — модуль (большое число); k- множитель (большое целое число). А0 — заданное начальное значение (целое);mod — операция вычисления остатка.
Датчик дает периодическую псевдослучайную последовательность z1, z2, z3, … с длиной периода T < m — 1. Чтобы длина периода T была максимальной, модуль m берут близким к максимальному представимому в компьютере целому числу. Для упрощения операций деления и вычисления остатков в двоичных ЭВМ часто берут m=2k. Рекомендуется также брать достаточно большой множитель k, причем взаимно простой с m.
Обозначим равномерное распределение вероятностей на интервале (0, 1) через R[0,1]. Тогда утверждение, что БСВ z имеет распределение R[0,1], можно кратко записать в виде z ~ R[0,1].
С помощью статистических тестов проверяют два свойства датчика БСВ, делающих его точной моделью идеальной математической БСВ: во-первых, проверяют равномерность распределения чисел, выдаваемых датчиком на интервале (0, 1), и, во-вторых, их статистическую независимость. При этом последовательность псевдослучайных чисел z на выходе датчика рассматривают как статистическую выборку.
Проверка равномерности распределения БСВ сводится к построению эмпирических вероятностных характеристик (моментов и распределений) случайной величины (с. в.) z по выборке z1, z2, z3, … , zn и их сравнению с теоретическими характеристиками распределения R[0,1]. В силу закона больших чисел с ростом длины выборки n эмпирические характеристики должны приближаться к теоретическим. При этом, поскольку компьютер позволяет легко получать выборки весьма большой длины, такое сближение эмпирических и теоретических характеристик можно наблюдать непосредственно, без использования специальных статистических тестов.
В настоящее время, как правило, любые языки программирования и пакеты моделирования содержат встроенные датчики БСВ и необходимость в самостоятельной разработке или тестировании датчиков возникает редко.
Простейшую проверку статистической независимости БСВ можно осуществить, оценивая линейную корреляцию между числами zi и zi+s, отстоящими друг от друга в псевдослучайной последовательности на фиксированный шаг s > 1.
Рассмотрим теоретическое определение коэффициента корреляции двух произвольных с. в. х и у. Коэффициент корреляции определяется для них формулой
Rx,y=M(x∙y)-Mx∙MyDx∙Dy (1.4)
Если х ~ R[0,1] и y ~ R[0,1], то M(x) = M(y) = 1/2 и D(x) = D(y) =1/12, и формула принимает следующий вид:
Rx,y=12Mx∙y-3 (1.5)
Условимся рассматривать в выборке всякую пару чисел (zi, zi+s) как реализацию пары с. в. (x, у). Тогда во всей выборке имеем следующие n-s реализаций пары (x, y):
z1,z1+s ,…,zn-s,zn
По этим реализациям можно рассчитать оценку R коэффициента корреляции R(x,y). Формулу для вычисления оценки R можно вывести из равенства (1.5) следующим образом. Заменяя в (1.5) справа м. о. M(xy) соответствующим эмпирическим м. о. (средним арифметическим выборочных значений), а слева обозначение R(x,y) коэффициента корреляции обозначением R его оценки, получаем:
R=12n-si=1n-szi,zi+s-3
