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

Эффективность статистического моделирования систем на ЭВМ и достоверность получаемых результатов существенным образом зависят от качества исходных (базовых) последовательностей псевдослучайных чисел, которые являются основой для получения стохастических воздействий на элементы моделируемой системы. Поэтому, прежде чем приступать к реализации моделирующих алгоритмов на ЭВМ, необходимо убедиться в том, что исходная последовательность псевдослучайных чисел удовлетворяет предъявляемым к ней требованиям, так как в противном случае даже при наличии абсолютно правильного алгоритма моделирования процесса функционирования системы 5 по результатам моделирования нельзя достоверно судить о характеристиках системы [29, 37].

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

Проверка равномерности последовательностей псевдослучайных квазиравномерно распределенных чисел (х_;) может быть выполнена по гистограмме с использованием косвенных признаков [4, 26]. Суть проверки по гистограмме сводится к следующему. Выдвигается гипотеза о равномерности распределения чисел в интервале (О,.

1). Затем интервал (0, 1) разбивается на т равных частей, тогда при генерации последовательности {х,} каждое из чисел х с вероятностью 1/т,/=" 1, т, попадает в один из подинтервалов. Всего в каждый у-й подинтервал попадает чисел последовательности {х,}, 1*1, Л^т, причем /*/*? Щ Относительная частота попадания случайных чисел последовательности {х/} в каждый из подинтервалов будет равна Ду/У. Вид соответствующей гистограммы для примера показан на рис. 4.11, а, где пунктирная линия соответствует теоретическому значению рр а сплошная — экспериментальному Лум Очевидно, что если числа х, принадлежат псевдослучайной квазиравномерно распределенной последовательности, то при достаточно больших N экспериментальная гистограмма (ломаная линия на рис. 4.11, а) приблизится к теоретической прямой 1/т.

Оценка степени приближения, т. е. равномерности последовательности {х*}, может быть проведена с использованием критериев согласия. На практике обычно принимается т-20-*-50, #=(10²-М0³)/и.

Суп. проверки равномерности по косвенным признакам сводится к следующему. Генерируемая последовательность чисел {х^ разбивается на две последовательности:

Рис. 4.11. Проверка равномерности последовательности.

Затем проводится следующий эксперимент. Если выполняется условие.

то фиксируется наступление некоторого события и в счетчик событий добавляется единица. После ЛГ/2 опытов, когда генерировано N чисто, в счетчике будет некоторое чисто к^N/2.

Геометрически условие (4.13) означает, что точка (лг_И-ь хгд, П, находятся внутри четверти круга радиусом г= 1, что иллюстрируется рис. 4.11, б. В общем случае точка (х^-ь хъ) всегда попадает внутрь единичного квадрата. Тогда теоретически вероятность попадания этой точки в четверть круга.

Если числа последовательности {*/} равномерны, то в силу закона больших чисел теории вероятностей при больших N относительная частота 2к/И-*п/А.

Проверка стохастичности последовательностей псевдослучайных чисел {х,•} наиболее часто проводится методами комбинаций и серий (7, 11, 25]. Сущность метода комбинаций сводится к определению закона распределения длин участков между единицами (нулями) или закона распределения (появления) чиста единиц (нулей) в п- разрядном двоичном числе Х₁. На практике длину последовательности N берут достаточно большой и проверяют все п разрядов или только / старших разрядов числа Х₁.

Теоретически закон появления; единиц в / разрядах двоичного числа Х₍ описывается, исходя из независимости отдельных разрядов биномиальным законом распределения:

где Р (/, I) — вероятность появления) единиц в / разрядах чиста Х (, р (1)=*р (0)" *0,5 — вероятность появления единицы (нуля) в любом разряде чиста Х{, С[=/!/[/!/(/—;)!].

Тогда при фиксированной длине выборки N теоретически ожидаемое чисто появления случайных чисел Х₍ с У единицами в проверяемых / разрядах будет равно я_/-Л'С'Л|).

Посте нахождения теоретических и экспериментальных вероятностей Р (/, 0 или чисел лу при различных значениях /<�л гипотеза о стохастичности проверяется с использованием критериев согласия [7, И, 18, 21].

При анализе стохастичности постедовательности чисел {*,} методом серии последовательность разбивается на элементы первого и второго рода (а и Ь), т. е.

где 0<�р<.

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

После разбиения последовательности {х,} на серии первого и второго рода будем иметь, например, последовательность вида.

Так как случайные числа а и Ь в данной последовательности независимы и принадлежат последовательности {*,}, равномерно распределенной на интервале (0, 1), то теоретическая вероятность появления серии длиной / в последовательности длиной / в N опытах (под опытом здесь понимается генерация числа дг, и проверка условия Х (<�р) определится формулой Бернулли:

В случае экспериментальной проверки оцениваются частоты появления серий длиной / В результате получаются теоретическая и экспериментальная зависимости Р(/, /). сходимость которых проверяется по известным критериям согласия, причем проверку целесообразно проводить при различных значениях р, 0<�р< и /.

Проверка независимости элементов последовательности псевдослучайных квазиравномерно распределенных чисел проводится на основе вычисления корреляционного момента [4].

Случайные величины ? и // называются независимыми, если закон распределения каждой из них не зависит от того, какое значение приняла другая. Таким образом, независимость элементов последовательности {*,} может быть проверена путем введения в рассмотрение последовательности {>у} = {*/+*}, где т — величина сдвига последовательностей.

В общем случае корреляционный момент дискретных случайных величин? и г/ с возможными значениями х, и yj определяется по формуле.

где ру — вероятность того, что ({, т}) примет значение (х₍, уу).

Корреляционный момент характеризует рассеивание случайных величин? и г и их зависимость. Если случайные числа независимы, то К (_Ч—0. Коэффициент корреляции.

где о_х-о_у — средние квадратические отклонения величин? и у.

При проведении оценок коэффициента корреляции на ЭВМ удобно для вычисления использовать следующее выражение:

где.

При вычислениях сначала рационально определить суммы:

При любом т^О для достаточно больших N с доверительной вероятностью р справедливо соотношение.

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