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

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

Проверка равномерности может быть выполнена следующим образом. Интервал значений случайных чисел (0,1) разбивается на m частей. Тогда при генерации последовательности каждое из чисел x_i с вероятностью p_j=1/m должно попадать в один из подынтервалов. Всего в каждый подынтервал попадет N_j чисел (). Относительная частота попадания случайных чисел в каждый из подынтревалов буде равна N_j/N. Вид получаемой гистограммы представлен на рис.2. Очевидно, что последовательность тем равномернее, чем ближе ломаная линия к теоретическому значению p_j. Оценка данной степени приближения может быть проведена с использованием критериев согласия (Пирсона, Стьюдента, Фишера). При этом на практике обычно принимается m=20-50, N=(10²-10³)m.

Существо применения критерия Пирсона заключается в следующем: находят . По вычисленному значению и числу степеней свободы (r – число параметров теоретического закона распределения, для равномерного закона r=1) по таблице находят P. Если эта вероятность превышает некоторый уровень значимости , то гипотеза о равномерности принимается.

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

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

aaabbbbbbbaabbaabaaaabbbbbbbbb….

Для равномерно распределенной последовательности случайных чисел вероятность появления серии длиной j в последовательности длиной l определяется формулой Бернули:

При экспериментальной проверке оцениваются частоты появлений серий длиной j. В результате получают теоретическую и экспериментальную зависимости , сходимость которых проверяется по известным критериям согласия при различных значениях p и l.

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

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

,

где p_ij – вероятность того, что примет значение .

Для независимых случайных величин . При проведении оценок независимости используют понятие коэффициента корреляции – ,

где - средние квадратические отклонения величин .

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