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

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

1.1 Законы распределения случайных чисел

Характеристики распределения случайных чисел.

Вероятность представляет собой количественную меру шансов происшествия или правдоподобия события.

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

При графическом представлении к-либо испытаний (измерений) значения измеряемой величины располагаются по оси x, а частот появления событий располагаются по оси y. Полученный график распределения вероятностей называется функцией плотности вероятностей (плотности распределения вероятностей) f(x).

Функция распределения вероятностей F(x) является интегралом функции плотности вероятностей.

Площадь, находящаяся под кривой функции плотности, всегда равна единице. Площадь, расположенная под частью кривой функции плотности вероятности p того, что случайное измерение xi лежит в интервале между значениями x и x+dx: P(x< xi < x+dx).

Вероятность того, что СВ xi не превышает x, равна значению соответствующей ординаты: P(xi <= x).

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

Характеристики функции плотности вероятности.

Математическое ожидание СВ xi определяется средгим значением функции плотности вероятности:

, .

Дисперсия характеризует разброс относительно математического ожидания:

, .

Таблица

Классификация распределения вероятностей

Класс	Непрерывные	Дискретные
Распределения одной СВ (одномерные)	Равномерное Треугольное Нормальное (гауссово) Экспоненциальное и др.	Биноминальное (Бернулли) Пуассона и др.
Распределения двух СВ (двумерные)	Равномерное Нормальное Круговое и др.	Биноминальное Пуассоновское и др.
Распределения многих СВ (многомерные)	Равномерное Нормальное Сферическое и др.	Биноминальное Пуассоновское и др.

Равномерное (прямоугольное) распределение

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

Функция плотности: f(x)=1, 0 <=x <=1,

функция распределения вероятностей: F(x)=x, 0 <=x <=1.

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

, .

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

Нормальное распределение

В технике и природе наиболее распространенное распределение СЧ - гауссовское или нормальное. Это распределение наиболее часто применяется при моделировании на ЭВМ.

Плотность вероятности нормального распределения записывается следующим образом:

где - дисперсия СВ, - математическое ожидание СВ x.

Функция распределения вероятностей: .

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

При конечном числе n измерений (или наблюдений) математическое ожидание и дисперсия могут быть определены:

, .

Экспоненциальное распределение

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

Функция плотности распределения определяется формулой:

при .

Функция распределения вероятностей: , .

Математическое ожидание и дисперсия соответственно равны:

и .

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

Биноминальное распределение

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

Вероятность s удачных исходов в n реализациях некоторого эксперимента равна

Функция распределения вероятностей записывается в виде

Математическое ожидание и дисперсия соответственно равны

, , где - вероятность неблагоприятного исхода.

Распределение Пуассона

Одним из частных случаев биноминального распределения является Пуассоновское распределение (если предположить, что в биноминальном распределении при очень большом числе независимых испытаний n стремится к бесконечности, а p стремится к нулю, причем произведение np остается постоянным):

Функция распределения вероятностей: , где - вероятность того, что при среднем числе благоприятных исходоа np случайное число их будет не менее m.

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

и .

Распределение Пуассона описывает редкие события, такие как, количество аварий на железной дороге, аварий автомобилей и самолетов, происшедших за отрезок времени; число вызовов, пришедших на телефонный коммутатор за единицу времени; поступление заказов на станцию техобслуживания или в торговую точку; прибытие или отъезд путешественников из некоторого пункта и др.

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

Для моделирования случайной величины необходимо знать ее закон распределения. Наиболее общим способом получения последовательности случайных чисел, распределенных по произвольному закону, является способ, в основе которого лежит их формирование из исходной последовательности случайных чисел, распределенных в интервале [0,1] по равномерному закону.

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

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

Недостатки данного способа получения случайных чисел следующие:

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

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

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

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

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

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

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

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

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

1.3 Методы получения последовательностей равномерно распределенных псевдослучайных чисел

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

xi+1=Ф(xi),

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

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

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

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

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

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

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

Метод серединных квадратов

Пусть имеется 2n-разрядное число, меньшее 1

хi = 0, a1 a2 ¼ a2n.

Возведем его в квадрат

хi2 = 0, b1 b2 ¼ b4n,

а затем отберем средние 2n разрядов, которые и будут являться очередным числом псевдослучайной последовательности

хi+1 = 0, bn+1 bn+2 ¼ b3n.

Этому методу соответствует рекуррентное соотношение

хi+1 = FRAC[ 10-2n INT[ 103n хi2 ] ],

где FRAC[ × ] и INT[ × ] означают соответственно дробную и целую часть числа в квадратных скобках.

Недостаток метода - наличие корреляции между числами последовательности, а в ряде случаев случайность вообще может отсутствовать. Кроме того, при некоторых i* может наблюдаться вырождение последовательности, т.е. хi = 0 при i ³ i*.

Пример. x0 = 0,2152 , (x0)2=0,04631104 , x1 = 0,6311 , (x1)2=0,39828721, x2=0,8287 и т.д.

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

x0 = 0,4500 , (x0)2=0,20250000, x1 = 0,2500 , (x1)2=0,06250000, x2=0,2500 и т.д.

Метод середины произведения

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

хi-1 = 0, a1 a2 ¼ a2n,

хi = 0, b1 b2 ¼ b2n,

то для получения числа хi+1 необходимо перемножить хi-1 и хi

хi-1 × хi = 0, c1 c2 ¼ c4n,

а затем отобрать средние 2n цифр этого произведения

хi+1 = 0, cn+1 cn+2 ¼ c3n.

Данному методу соответствует рекуррентное соотношение

хi+1 = FRAC[ 10-2n INT[ 103n хi × хi-1 ] ]

при заданных двух начальных числах х0 и х1.

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

Мультипликативный метод

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

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

1984 º 4 (mod 10), 5008 º 8 (mod 103).

Конгруэнтные процедуры являются чисто детерминированными, т.к. описываются в виде рекуррентного соотношения, когда функция (1) имеет вид:

Хi = lХi + m ( mod M ),

где Хi, l, m, M - неотрицательные целые числа.

Раскрывая (2) получим

Хi = li Х0 + ( li - 1) m / ( l - 1 )( mod M ).

Если задано начальное значение Х0, множитель l и аддитивная константа m, то (5) однозначно определяет последовательность целых чисел { Хi }, составленную из остатков от деления на М, членов последовательности

{ li×Х0 + m ( li - 1 ) / ( l - 1 )}.

Таким образом, для любого i ³ 1 справедливо неравенство Хi < M. По целым числам последовательности {Хi} можно построить последовательность {хi} = {Хi / M} рациональных чисел из единичного интервала (0, 1).

Мультипликативный метод задает последовательность неотрицательных целых чисел {Хi}, не превосходящих М, по формуле

Хi+1= l Хi ( mod M ),

т.е. это частный случай (4) при m = 0.

Для машинной реализации наиболее удобна версия М = pg, где p - число цифр в системе счисления, принятой в ЭВМ, а g - число бит в машинном слове.

Алгоритм построения последовательности для двоичной машины М = 2g сводится к выполнению следующих операций:

выбрать в качестве Х0 произвольное нечетное число;
вычислить коэффициент l = 8t ± 3, где t - любое целое положительное число;
найти произведение l Х0, содержащее не более 2g значащих разрядов;
взять g младших разрядов в качестве первого числа последовательности Х1, а остальные отбросить;
определить дробь х1 = Х1 / 2g из интервала ( 0, 1 );
присвоить Х0 = Х1;
вернуться к пункту 3.

Пример:

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

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

Получение равномерно распределенных чисел в заданном диапазоне

Используя датчик случайной величины X с равномерным распределением в интервале от 0 до 1, с помощью очевидного преобразования можно получить случайную величину у с равномерным распределением в интервале от а до с:

Проверка стохастической последовательности равномерно распределенных чисел

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

1) Частотный критерий:

Берется N случайных чисел и подсчитывается m чисел, заключенных в пределах , т.е. в диапазоне от 0,2113 до 0,7887. Если отношение , то принимается, что случайные величины распределены приблизительно равномерно.

2) Вычисление математического ожидания и дисперсии:

Считается, что случайные числа распределены равномерно, если:

и , где N – количество сгенерированных случайных чисел.

1.4 Методы получения последовательностей неравномерно распределенных псевдослучайных чисел

Алгоритмы получения ряда чисел, распределенных по нормальному закону

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

Алгоритм 1. Нормальные случайные числа могут быть получены из N равномерно распределенных чисел при достаточном условии и использовании соотношения:

где - случайные величины с равномерной плотностью распределения вероятности в интервале от 0 до 1.

Математическое ожидание и дисперсия полученной таким образом случайной последовательности соответственно равны m = N / 2, s2 = N / 12.

Алгоритм 2. Метод отбраковки.

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

то нормальное случайное число определим формулой

где b – постоянная.

Может быть указан еще один метод отбраковки: если два равномерных случайных числа и удовлетворяют неравенству

то нормальное случайное число вычисляется с помощью соотношения

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

, .

Алгоритм получения ряда чисел, распределенных по закону Пуассона

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

Число N-1 представляет собой случайную переменную s, принадлежащей совокупности, распределенной по закону Пуассона с математическим ожиданием np. Если неравенству удовлетворяет первое из равномерно распределенных случайных чисел, то s=0.

Проверка соответствия последовательности M случайных величин пуассоновскому распределению с данными n и p осуществляется с помощью проверки удовлетворения величин равенствам

, .

Моделирование случайных величин, распределенных по экспоненциальному закону

Экспоненциально распроеделенные случайные числа получаются на основе последовательности равномерно распределенных величин, в соответствии с соотношением:

Проверка соответствия последовательности M случайных величин экспоненциальному распределению с интенсивностью осуществляется с помощью соотношения

Моделирование случайных величин, распределенных по биноминальному закону

Для небольших значений n образуем n равномерно распределенных случайных чисел . Случайная биноминальная величина равняется количеству равномерно распределенных случайных чисел, не превосходящих по величине p.

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

, где и .

Случайная биноминальная величина равняется в этом случае чмслу итераций N, которые нужно выполнить для того, чтобы неравенство удовлетворилось.

Покажем, как может быть проверена случайность последовательности M чисел, полученных для заданных n и p. Эти числа случайны, если удовлетворены условия:

, .