Советов Б.Я., Яковлев С.А. Моделирование систем (2001) (1186219), страница 31
Текст из файла (страница 31)
На практике длину последовательности 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—\.
Иначе говоря, надо найти, при какихусловиях равенствоXtmX9 (mod M)(4.14)справедливо при минимальном значении •s=Af—1.Можно записать [см. (4.11)], что Xt+,^X Xi(modM),место припоэтому (4.14) имеетx'=l(modM)(4.15)(здесь существенно, что Х0 взаимно просто с М).По условию требуется, что наименьший показатель степени s=Pu(A), удовлетворяющий (4.15) и называемый показателем А по модулю М, был равен. Л/— 1. Длялюбого простого модуля М существует ср (М— 1) значений X (первообразных корней),удовлетворяющих уравнению (4.15) при Рм(Л)=<р(Ж0> где q>{M) —функция Эйлера,определяемая как число натуральных чисел т^М, взаимно простых с М. Дляпростого модуля М имеем q> (M)=М—\.Таким образом, доказано существование многих А, при которых повторениеэлементов последовательности {х,} наступит на (А/— 1)-м числе д.'л/-ь т.
е.L=P=M—\, что и требовалось доказать.Для алгоритмов получения последовательностей чисел {х,} общего вида (4.10) экспериментальная проверка является сложной(из-за наличия больших Р и L), а расчетные соотношения в явномвиде не получены. Поэтому в таких случаях целесообразно провеститеоретическую оценку длины отрезка апериодичности последовательности L. Для этого воспользуемся элементарной вероятностноймоделью, рассмотренной в следующем примере [4, 36, 37].Пример 4.6. Пусть имеется конечное множество, содержащее Л' различных чисел.Проведем последовательность независимых опытов, в каждом из которых из этогомножества извлекается и записываетсяодно число.
Вероятность извлечения любогочисла в каждом из опытов равна 1/N, так как выборка чисел проводится с возвратом.Обозначим через L случайную величину номер опыта, в котором впервые будетснова извлечено уже записанное ранее число Можно доказать, что в данной вероятностной модели для любого х > 0 имеем128—lim Р{Ь/^Ы<х} = 1-е— x*I2JV-oOТак как математическое ожидание случайной величины с такой функцией распределения равно у/п/2, то при N-»oo получим M[L] = y/nN/2. Такая оценка длиныотрезка апериодичности «груба», но полезна на практике для предварительногоопределения L с целью дальнейшего уточнения экспериментальным путем.Рассмотрим некоторые особенности статистической проверкистохастичности псевдослучайных последовательностей. Для такойпроверки могут быть использованы различные статистические критерии оценки, например критерии Колмогорова, Пирсона и т.
д. Нов практике моделирования чаще всего пользуются более простымиприближенными способами проверки [29, 37].Для проверки равномерности базовой последовательности случайных чисел xt, f=l, N, можно воспользоваться такими оценками:(1/N) £ x,= l/2,(l/JV) £ *? = l/3.i=li= lДля проверки таблиц случайных цифр обычно применяют различные тесты, в каждом из которых цифры классифицируются понекоторому признаку и эмпирические частоты сравниваются с ихматематическими ожиданиями с помощью критерия Пирсона [29,46].Для проверки аппаратных генераторов случайных чисел можноиспользовать те же приемы, что и для проверки последовательностей псевдослучайных чисел, полученных программным способом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
