Советов Б.Я., Яковлев С.А. Моделирование систем (3-е изд., 2001) (1186218), страница 30
Текст из файла (страница 30)
Поэтому всеприменяемые генераторы случайных чисел должны перед моделированием системы пройти тщательное предварительное тестирование,которое представляет собой комплекс проверок по различным статистическим критериям, включая в качестве основных проверки(тесты) на равномерность, стохастичность и независимость. Рассмотрим возможные методы проведения таких проверок, наиболеечасто используемые в практике статистического моделированиясистем.Проверка равномерности последовательностей псевдослучайных квазиравномерно распределенных чисел {*,-} может быть выполнена по гистограмме с использованием косвенных признаков [4, 26].
Суть проверки по гистограмме сводится к следующему. Выдвигается гипотеза о равномерности распределения чисел в интервале (О,1). Затем интервал (0, 1) разбивается на т равных частей, тогда при генерациипоследовательности {х,} каждое из чисел х с вероятностью pj= l/m,j= 1, т, попадаетв один из подынтервалов. Всего в каждый J-й подынтервал попадает Nj чиселЯ1последовательности {х(}, «=1, N, причем N— £ Nj.
Относительная частота попадания случайных чисел последовательности {*/} в каждый из подынтервалов будетравна Nj/N. Вид соответствующей гистограммы для примера показан на рис. 4.11, а,где пунктирная линия соответствует теоретическому значению pj, а сплошная —экспериментальному Nj/N. Очевидно, что если числа х, принадлежат псевдослучайной квазиравномерно распределенной последовательности, то при достаточно больших N экспериментальная гистограмма (ломаная линия на рис.
4.11, а) приблизитсяк теоретической прямой 11т.Оценка степени приближения, т. е. равномерности последовательности {xt},может быть проведена с использованием критериев согласия. На практике обычнопринимается л?=20-^50, N=(\02 + \03)m.Суть проверки равномерности по косвенным признакам сводится к следующему.Генерируемая последовательность чисел {х,} разбивается на две последовательности:а)1/тРис. 4.11. Проверка равномерности последовательности124xl>*Ji -fji —ix2i-l>•** **. x6, .... x2l; / - 1 , N.Затем проводится следующий эксперимент. Бели выполняется условиех1_у+xl<l, i-TTN,(4.13)то фиксируется наступление некоторого события и в счетчик событий добавляетсяединица.
После Я/2 опытов, когда генерировано N число, в счетчике будет некотороечисло k^N/2.Геометрически условие (4.13) означает, что точка (ха-ь хгд> '""1. ^> находитсявнутри четверти круга радиусом г = 1 , что иллюстрируется рис. 4.11, б. В общемслучае точка ( х а - ь ха) всегда попадает внутрь единичного квадрата. Тогда теоретически вероятность попадания этой точки в четверть кругаРх ="Si / 4 хруп/Здмщраи=(я^/4)/(1 • 1)=Я/4.Если числа последовательности {*/} равномерны, то в силу закона большихчисел теории вероятностей при больших N относительная частота 2kjN-ni/4.Проверка стохастичности последовательностей псевдослучайных чисел {*/} наиболее часто проводится методами комбинаций и серий [7,11, 25].
Сущность методакомбинаций сводится к определению закона распределения длин участков междуединицами (нулями) или закона распределения (появления) числа единиц (нулей) в празрядном двоичном числе Xt. На практике длину последовательности N берутдостаточно большой и проверяют все и разрядов или только I старших разрядовчисла Х\.Теоретически закон появления у единиц в / разрядах двоичного числа Xt описывается исходя из независимости отдельных разрядов биномиальным законом распределения:где Р (/, 0 — вероятность появления У единиц в / разрядах числа Хс,р{\)~р (0)—0,5 —вероятность появления единицы (нуля) в любом разряде числа Х{, Ц=/!/[/!/(/—j)!].Тогда при фиксированной длине выборки N теоретически ожидаемое числопоявления случайных чисел Xi с j единицами в проверяемых I разрядах будет равно|*-ЛГС!Л1).После нахождения теоретических и экспериментальных вероятностей P(j, I) иличисел rij при различных значениях 1^п гипотеза о стохастичности проверяетсяс использованием критериев согласия [7, 11, 18, 21].При анализе стохастичности последовательности чисел {х(} методом серий последовательность разбивается на элементы первого и второго рода (а и Ь), т.
е.(а, если Х[<р;xHi.(б в противном случае,гдеО<р<.Серией называется любой отрезок последовательности, состоящий из идущихдруг за другом элементов одного и того же рода, причем число элементов в отрезке(а или Ь) называется длиной серии.После разбиения последовательности {*,} на серии первого и второго рода будемиметь, например, последовательность вида...aabbbbaaabaaaabbbab... .Так как случайные числа а и Ь в данной последовательности независимы и принадлежат последовательности {*,}, равномерно распределенной на интервале (0, 1),125то теоретическая вероятность появления серии длиной ] в последовательности длиной I в N опытах (под опытом здесь понимается генерация числа х, и проверкаусловия х, <р) определится формулой Бернулли:Р(/, /)=<У (1-р)'~';=0Г1 '=М.В случае экспериментальной проверки оцениваются частоты появления серийдлиной/ В результате получаются теоретическая и экспериментальная зависимостиP(j, I), сходимость которых проверяется по известным критериям согласия, причемпроверку целесообразно проводить при различных значениях р , 0 <р< 1 и /.Проверка независимости элементов последовательности псевдослучайных квазиравномерно распределенных чисел проводится на основе вычисления корреляционного момента [4].Случайные величины { и г\ называются независимыми, если закон распределениякаждой из них не зависит от того, какое значение приняла другая.
Таким образом,независимость элементов последовательности {xt} может быть проверена путемвведения в рассмотрение последовательности {yj\ — {•*,+,}, где т — величина сдвигапоследовательностей.В общем случае корреляционный момент дискретных случайных величин( и у\ с возможными значениями х, и yj определяется по формуле**,=! X (х,-м[ящ-мтрФIJгде ру — вероятность того, что (f, 7) примет значение (ху, yj).Корреляционный момент характеризует рассеивание случайных величин{ и »; и их зависимость. Если случайные числа независимы, то К^=0. Коэффициенткорреляциигде ах—Оу — средние квадратические отклонения величин £ и г\.При проведении оценок коэффициента корреляции на ЭВМ удобно для вычисления использовать следующее выражение:1 ""*12 J JC ' JC| + t_ 7TT7iN-x £(ЛГ-т)»N-%2-N-1Х|XZJI+Is/.D[x,]Z>[x)+Jгде1D[x]=—"~T/N_t1V2T *, - - Ц ( У X.) ,1 V,1При вычислениях сначала рационально определить суммы:2^ хн 2*i * ' + « Ai -^'^i+i> 2^ х>' 2-1I126IГIIxi+vПри любом т^О для достаточно больших N с доверительнойвероятностью /? справедливо соотношениеiPftWlWViV.Если найденное эмпирическое значение р^(т) находится в указанных пределах, то с вероятностью /? можно утверждать, чтополученная последовательность чисел {х(} удовлетворяет гипотезекорреляционной независимости.Характеристики качества генераторов.
При статистическом моделировании системы S с использованием программных генераторовпсевдослучайных квазиравномерных последовательностей важнымихарактеристиками качества генератора является длина периодаР и длина отрезка апериодичности L. Длина отрезка апериодичностиL псевдослучайной последовательности {х,}, заданной уравнениемXi+i=XXi+n(modM),x^XJM,есть наибольшее целое число, такое, что при 04J<i^L событиеP{x,=Xj} не имеет места. Это означает, что все числа xt в пределахотрезка апериодичности не повторяются.Очевидно, что использование при моделировании систем последовательности чисел {*,}, длина которой больше отрезка апериодичности L, может привести к повторению испытаний в тех жеусловиях, что и раньше, т. е.
увеличение числа реализаций не даетновых статистических результатов.Способ экспериментального определения длины периодаР и длины отрезка апериодичности L сводится к следующему [29].Запускается программа генерации последовательности {х,} с начальным значением х0 и генерируется V чисел х,. вВ большинствепрактических случаев можно полагать К==(1 -=-5)10 .
Генерируютсячисла последовательности{х,} и фиксируется число xv.Затем программа запускается повторно с начальным числом х0 и при генерации очередного числа проверяется истинность событияР'{х,=ху}. Если это событие истинно:т о i"=i1 и i=i2(h < h < Р).вычисляетсядлина периода последовате 01 г зльности P=i2 — iv ПроводитРис. 4 12. Экспериментальное определениеся запуск программы генерадлины периода и длины отрезка апериодичции с начальными числаминости:х0 и хР. При этом фиксируа — вариант 1,6 — вариант 2127ется минимальный номер i=i3, при котором истинно событиеР" {х, = хР+1}, и вычисляется длина отрезка апериодичности L=i3 +Р(рис.
4.12, а). Если Р' оказывается истинным лишь для i= V,TOL>V(рис. 4.12, б).В некоторых случаях достаточно громоздкий эксперимент поопределению длин периода и отрезка апериодичности можно заменить аналитическим расчетом, как это показано в следующем примере.Пример 4.5. Необходимо показать, что в последовательности чисел {х,}, описываемой уравнениемXl+i=XX,(modM),X,xt= —,при простом модуле М можно так выбрать коэффициент Я, что при любом Х0,взаимно простом с М, длина отрезка апериодичности, совпадающая в этом случаес длиной периода Р, будет L=P=M—\.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
