Существующие методы проверки качества генераторов случайных чисел.

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

m

Σ

j = 1

Проверка равномерности последовательностей псевдослучайных квазиравномерно распределенных чисел { х_i } может быть выполнена по гистограмме с использованием косвенных признаков. Суть проверки по гистограмме сводится к следующему. Выдвигается гипотеза о равномерности распределения чисел в интервале (0, 1). Затем интервал (0, 1) разбивается на m равных частей, тогда при генерации последовательности { х_i } каждое из чисел х с вероятностью p_j = 1/ m, j = 1, т, попадает в один из подынтервалов. Всего в каждый j -й подынтервал попадает N_j чисел последовательности { х_i }, i = 1, N, причем N = N_j. Относительная частота попадания случайных чисел последовательности { х_i } в каждый из подынтервалов будет равна N_j / N.

Оценка степени приближения, т. е. равномерности последовательности { х_i }, может быть проведена с использованием критериев согласия. На практике обычно принимается т = 20 ÷ 50, N = (10² ÷ 10³) m.

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

 

 

 

 

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

 

 

 

 

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

Геометрически условие (4.13) означает, что точка (х _{2 i - 1}, х _{2 i} ) = 1, N, находится внутри четверги круга радиусом r = 1, что иллюстрируется рис. 4.11, б. В общем случае точка (х _{2 i - 1}, х _{2 i} ) всегда попадает внутрь единичного квадрата. Тогда теоретически вероятность попадания этой точки в четверть круга

 

Если числа последовательности { х_i } равномерны, то в силу закона больших чисел теории вероятностей при больших N относительная частота 2 k / N → π/4.

Проверка стохастичности последовательностей псевдослучайных чисел { х_i } наиболее часто проводится методами комбинаций и серий. Сущность метода комбинаций сводится к определению закона распределения длин участков между единицами (нулями) или закона распределения (появления) числа единиц (нулей) в n -разрядном двоичном числе X_i. На практике длину последовательности N берут достаточно большой и проверяют все п разрядов или только l старших разрядов числа X_i.

Теоретически закон появления j единиц в l разрядах двоичного числа X_i описывается исходя из независимости отдельных разрядов биномиальным законом распределения:

 

 

где P (j, l) - вероятность появления j единиц в l разрядах числа Х_i; p (1) = p (0) = 0,5 - вероятность появления единицы (нуля) в любом разряде числа Х_i; C^j_l = l!/[ j!/(l - j)!].

Тогда при фиксированной длине выборки N теоретически ожидаемое число появления случайных чисел Х_i с j единицами в проверяемых l разрядах будет равно n_j = NC^j_l p^l (1).

После нахождения теоретических и экспериментальных вероятностей P (j, l) или чисел n_j при различных значениях l ≤ n гипотеза о стохастичности проверяется с использованием критериев согласия.

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

 

 

 

где 0 < р <.

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

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

...aabbbbaaabaaaabbbab....

Так как случайные числа а и b в данной последовательности независимы и принадлежат последовательности { х_i }, равномерно распределенной на интервале (0, 1), то теоретическая вероятность появления серии длиной j в последовательности длиной l в N опытах (под опытом здесь понимается генерация числа х_i и проверка условия х_i < p) определится формулой Бернулли:

 

 

 

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

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

Случайные величины ξ и η называются независимыми, если закон распределения каждой из них не зависит от того, какое значение приняла другая. Таким образом, независимость элементов последовательности { х_i } может быть проверена путем введения в рассмотрение последовательности { y_j } = { x_{i +τ}}, где τ - величина сдвига последовательностей.

В общем случае корреляционный момент дискретных случайных величин ξ и τ с возможными значениями х_i и y_j определяется по формуле

 

где p_ij - вероятность того, что (ξ, η) примет значение (х_i, y_j).

Корреляционный момент характеризует рассеивание случайных величин ξ и η и их зависимость. Если случайные числа независимы, то K _ξη = 0. Коэффициент корреляции

 

 

 

где σ_х—σ_y — средние квадратические отклонения величин ξ и η.

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

 

 

 

При любом τ ≠ 0 для достаточно больших N с доверительной вероятностью β справедливо соотношение

 

 

Если найденное эмпирическое значение Р ζητ (τ) находится в ука­занных пределах, то с вероятностью β можно утверждать, что полученная последовательность чисел {х,) удовлетворяет гипотезе корреляционной независимости.