4. Статистическое моделирование

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

Основа - метод статистических испытаний Монте-Карло, который базируется на использовании случайных чисел, то есть возможных значений некоторой случайной величины с заданным распределением вероятностей. Статистическое моделирование представляет собой метод получения с помощью ЭВМ статистических данных о процессах, происходящих в моделируемой системе.

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

2 области применения: 1) изучение стохастических систем; 2) решение детерминированных задач.

Результат статистического моделирования - серия частных значений искомых величин или функций, их статистическая обработка. Если количество реализаций N  , результаты устойчивы и достаточно точны.

Теоретическая основа метода статистического моделирования является пре дельнее теоремы теории вероятностей. Их значение - гарантируют высокое качество статистических оценок при числе испытаний N  . Часто приемлемые результаты могут быть получены при достаточно небольших N.

Неравенство Чебышева. Для неотрицательной случайной величины X и любого K>0 выполняется неравенство:

P(X>=K)=<M(X)/K

Теорема Бернулли. Если проводится N независимых испытаний, в каждом из которых некоторое событие А осуществляется с вероятностью p, то относительная частота появления события m/N при N   сходится по вероятности к p, т.е. при любом >0

, где m - число положительных исходов испытания.

Теорема Пуассона.

, где p_i - вероятность осуществления события А в i-м испытании.

Обобщенная теорема Чебышева.

, X_i - i-ая случайная величина

Теорема Маркова. Обобщенная теорема Чебышева справедлива и для зависимых случайных величин, если

Центральная предельная теорема. Если X₁ , X₂,..., X_n - независимые одинаково распределенные случайные величины, имеющие математическое ожидание M(X_i)=a и дисперсию ², то при N   закон распределения суммы неограниченно приближается к нормальному:

Приведем примеры применения методов статистического моделирования.

Пример 1. Входное воздействие - , воздействие внешней среды - - случайные величины с известными функциями распределения.

Необходимо определить математическое ожидание величины y:

Схема алгоритма (ген. - генерация):

Пример 2. Необходимо найти площадь фигуры:

Пример 3. Проводится s=10 независимых выстрелов по мишени, причем вероятность попадания при одном выстреле задана и равна p. Требуется оценить вероятность того, что число попаданий в мишень будет четным.

Аналитическое решение этой задачи:

Схема алгоритма (статистическое моделирование):

Генерация последовательности случайных чисел

Существует три способа генерации случайных чисел:

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

2. Табличные - случайные числа оформлены в виде таблицы в оперативной памяти или на внешнем носителе. При этом способе запас чисел ограничен, вычислительные ресурсы используются неэффективно. Используется редко.

3. Программный (алгоритмический) - случайные числа формируются с помощью специальных программ. Каждое случайное число вычисляется с помощью соответствующей программы по мере возникновения потребностей при моделировании системы на ЭВМ. Этот способ наиболее распространен.

Программная имитация случайных воздействий сводится к генерированию некоторых стандартных (базовых) процессов и к их последующему функциональному преобразованию. Чаще всего в качестве базовой последовательности используют независимые случайные величины, равномерно распределенные на интервале (0,1).

Непрерывная случайная величина имеет равномерное распределение в интервале (a,b), если ее функции плотности и распределения соответственно примут вид

Для получения случайных чисел на ЭВМ используются алгоритмы, поэтому такие последовтельности, являющиеся по сути детерминированными, называются псевдослучайными. ЭВМ оперирует n-разрядными числами, поэтому поэтому на ЭВМ вместо непрерывной совокупности равномерных случайных чисел интервала (0,1) используют дискретную последовательность 2ⁿ случайных чисел того же интервала - закон распределения такой дискретной последовательности называется квазиравномерны распределением.

Требования к идеальному генератору случайных чисел:

1. Последовательность должна состоять из квазиравномернло распределенных чисел.

2. Числа должны быть независимыми.

3. Последовательности случайных чисел должны быть воспроизводимыми.

4. Последовательности должны иметь неповторяющиеся числа.

5. Последовательности должны получаться с минимальными затратами вычислительных ресурсов.

Наибольшее применение в практике моделирования на ЭВМ для генерации последовательностей псевдослучайных числе находят алгоритмы вида:

x_i+1=Ф(x_i),

представляющие собой реккурентные соотношения первого порядка.

Пример. x₀ = 0,2152 , (x₀)²=0,04631104 , x₁ = 0,6311 , (x₁)²=0,39828721, x₂=0,8287 и т.д.

Недостаток подобных методов - наличие коррелляции между числами последовательности, а иногда случайность вообще отсутствует, например:

x₀ = 0,4500 , (x₀)²=0,20250000, x₁ = 0,2500 , (x₁)²=0,06250000, x₂=0,2500 и т.д.

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

Два целых числа  и  конгруэнтны (сравнимы) по модулю m, где m - целое число, тогда и только тогда, когда существует такое целое число k, что -=km.

19844 (mod 10), 50088 (mod 10³).

Большинство конгруэнтных процедур генерации случайных чисел основаны на следующей формуле:

где - неотрицательные целые числа.

По целым числам последовательности {X_i} можно построить последовательность {x_i}={X_i/M} рациональных чисел из единичного интервала (0,1).

Применяемые генераторы случайных чисел перед моделированием должны пройти тщательное предварительное тестирование на равномерность, стохастичность и независимость получаемых последовательностей случайных чисел.

Методы улучшения качества последовательностей случайных чисел:

1. Использование рекуррентных формул порядка r:

Но применение этого способа приводит к увеличению затрат вычислительных ресурсов на получение чисел.

2. Метод возмущений:

Моделирование случайных воздействий на системы

1. Необходимо реализовать случайное событие А, наступающее с заданной вероятностью p. Определим А как событие, состоящее в том, что выбранное значение x_i равномерно распределенной на интервале (0,1) случайной величины удовлетворяет неравенству:

x_i =<p.

Тогда вероятность события А будет Противоположное событие состоит в том, что x_i >p, его вероятность равна 1-р.

2. Рассмотрим группу событий. Пусть А₁, А₂ ,..., А_s - полная группа событий, наступающих с вероятностями p₁, p₂ ,..., p_s соответственно. Определим событие А_m как событие, состоящее в том, что выбранное значение x_i случайной величины удовлетворяет неравенству

,

где

Процедура моделирования испытаний в этом случае состоит в последовательном сравнении случайных чисел x_i со значениями l_r. Если условие выполняется, исходом испытания оказывается событие А_m .

3. Рассмотрим независимые события А и В с вероятностями наступления р_А и р_В. Возможными исходами совместных испытаний в этом случае будут события АВ, с вероятностями р_Ар_В, (1-р_А)р_В, р_А(1-р_В), (1-р_А)(1-р_В). Для моделирования совместных испытаний можно использовать два варианта процедуры:

• Последовательное выполнение процедуры, рассмотренной в п.1.

• Определение одного из исходов АВ, по жребию с соответствующими вероятностями, т.е. процедура, рассмотренная в п.2.

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

4. События А и В являются зависимыми и наступают с вероятностями p_А и p_В . Обозначим через p_А(В) условную вероятность наступления события В при условии, что событие А произошло. Алгоритм модели подобного случая может быть следующим:

Моделирование дискретных случайных величин

Дискретная случайная величина Y принимает значения y₁<= y₂<=… <= y_j<=… с вероятностями p₁, p₂, …, p_j,… составляющими дифференциальное распределение вероятностей

Y	y1	y2	…	yj	…
P	p1	p2	…	pj	…

При этом интегральная функция распределения

Длля получения дискретных случайных величин можно воспользоваться методом обратных функций: если X – равномерно распределенная на интервале (0,1) случайная величина, то искомую случайную величину получают при выполнении следующих действий:

Если x₁< p₁ , то Y= y₁ , иначе,

Если x₁< p₁ + p₂, то Y= y₂ , иначе,

…………………………………..

Если x₁< , то Y= y_m , иначе,

……………………………………

Дискретное распределение (общий случай). Предположим, что известны частоты а, выбора из N объектов на определенном интер­вале времени, i=1,..., N. Пример таких частот для N=7 представлен в табл. 1.3. Первая строка таблицы - это номер объекта, а вторая - частота его выбора. Требуется разработать программную функцию, которая должна возвращать значение номера объекта в соответствии

Таблица 1