Оба рассмотренных генератора основаны на получении последовательности целых чисел, причем каждое следующее число полностью определяется предыдущим числом (и параметрами генератора, которые в процессе счета не изменяются). Поэтому очевидно, что при большом количестве запусков генератора числа в последовательности после какого-то шага начнут повторяться. Очевидно, что из целых чисел, лежащих в диапазоне от 0 до (M-1), можно в лучшем случае сформировать последовательность, не содержащую повторов, длиной не более M.
Периодом генератора называют количество неповторяющихся чисел, которые генератор может сформировать при заданных параметрах и "затравке". Обычно период генератора получается меньше M. Генератор может считаться достаточно хорошим, если он обеспечивает период последовательности более M/4 для большинства "затравок".
При экспериментальном определении периода последовательности следует учитывать, что число-"затравка" может не повторяться никогда, как и несколько последовательно получаемых из нее чисел (апериодическая часть последовательности). Тем не менее, каждая "затравка" задает то или иное подмножество из M целых чисел, которые будут циклически перебираться генератором.
Примером последовательности с апериодической частью, может служить последовательность, получаемая с помощью мультипликативного датчика с параметрами:
M = 77841; a = 273; b = 374; x0 = 7;
При указанных параметрах генератор выдает три апериодических числа: 2285, 1451, 7292 — после чего, начиная с числа 45065, идет периодическая часть последовательности с периодом всего-навсего 93 числа. Распределение этих 93 чисел оказывается почти идеально равномерным, и по критерию Пирсона вероятность подтверждения гипотезы получается равной 100%, однако такую последовательность никак нельзя назвать "хорошей".
Для определения периода генератора необходимо зафиксировать одно из целых чисел, полученных в результате работы процедуры генератора, и подсчитать количество вызовов процедуры генератора до того момента, когда в результате получится то же целое число, сгенерировав, таким образом, не менее M чисел. Если при генерации M чисел повторений не обнаружено, — значит, зафиксированное число относится к апериодической части псевдослучайной последовательности и следует взять другое, более "позднее" число для проверки повторения. Следует заметить, что апериодическая часть в подавляющем большинстве случаев все же состоит из единственного числа-"затравки" или отсутствует вовсе.
Проводить проверку повторения вещественных чисел из диапазона [0,1) не следует.
Пример анализа последовательности случайных чисел.
В качестве примера для анализа рассмотрим последовательность из 25 чисел, получаемых с помощью мультипликативного датчика со следующими параметрами: M=1000, a=47, b=1. В качестве x0 возьмем 1 (табл. 5.1).
О периоде. Прежде всего, в полученной последовательности есть одна отрадная особенность: числа не повторяются (период больше 25). С другой стороны, если проанализировать получаемую последовательность целых чисел xi, можно видеть, что все они заканчиваются только на 8, 7, 0 и 1. Таким образом, из 10 возможных последних цифр используются лишь 4, поэтому из 1000 возможных чисел получится не более 400 неповторяющихся чисел с
Таблица5.1
xi
ui
ui2
0,048
0,002
0,257
0,066
0,080
0,006
0,761
0,579
0,768
0,590
0,097
0,009
0,560
0,314
0,321
0,103
0,088
0,008
0,137
0,019
0,440
0,194
0,681
0,464
0,008
0,000
0,377
0,142
0,720
0,518
0,841
0,707
0,528
0,279
0,817
0,667
0,400
0,160
0,801
0,642
0,648
0,420
0,457
0,209
0,480
0,230
0,561
0,315
0,368
0,135
такими последними цифрами. На самом деле период этой последовательности равен 200 для большинства "затравок", включая нашу единицу, но для некоторых затравок он составит 40 или даже всего 8 неповторяющихся чисел.
Математическое ожидание. Для случайной величины X, равномерно распределенной на интервале от A до B, мат.ожидание вычисляется по формуле:
,
следовательно, для равномерного распределения от 0 до 1 MX=0.5.
Оценка мат. ожидания (выборочное среднее) для выборки объемом N чисел xi вычисляется по формуле.
Для нашей выборки =0.450 .
Дисперсия. Для случайной величины X , равномерно распределенной на интервале от A до B, дисперсия вычисляется по формуле , что в случае ррсч[0,1) дает DX=0.083. Для оценки дисперсии (вычисления выборочной дисперсии) по выборке используют формулу .
(Следует использовать оценку мат. ожидания, а не теоретически рассчитанное мат. ожидание.)
Для нашей последовательности из 25 чисел выборочная дисперсия составляет 0.0816.
Для реальных выборок объемом несколько тысяч значений ошибка, как правило, не должна превышать 1%.
Критерий Пирсона. Критерий Пирсона позволяет оценить вероятность того, что данная выборка является выборкой значений случайной величины (СВ) с заданным законом распределения. Теоретическое обоснование этого критерия изучается в рамках курса "Теория вероятности и мат. статистика".
Для применения критерия Пирсона интервал возможных значений СВ разбивается на L равных отрезков. Для каждого отрезка подсчитывается Gi — количество попаданий в него чисел из выборки, а также Pi — ожидаемое количество попаданий в случае, если СВ имеет заданное распределение. Подсчитанные значения Gi позволяет построить гистограмму, по которой можно визуально оценить соответствие заданного распределения и полученного. Затем рассчитывается коэффициент хи-квадрат: , после чего по таблице распределения хи-квадрат для полученного коэффициента и (L-1) степени свободы находят вероятность истинности гипотезы о том, что исследуемая выборка имеет заданный закон распределения.
Так как объем нашей выборки невелик, воспользуемся всего лишь пятью интервалами. Для реальных задач рекомендуется брать 20 - 50 интервалов. Получаемая гистограмма выглядит следующим образом:
При расчете получаем 1.2, и по таблице распределения хи-квадрат с четырьмя степенями свободы определяем, что вероятность того, что наша выборка соответствует равномерному распределению на интервале от 0 до 1, составляет ~87%. Хорошо это или плохо? Это хороший результат. Принято считать хорошими значения вероятности от 70 до 95%. Если получено меньшее значение, то велика вероятность, что заданное распределение не получено. Если вероятность более 95%, то велика вероятность того, что выборка не случайная. Наглядный пример такой ситуации: если по методу мультипликативного датчика построить генератор, взяв a=1, b=1, M=1000, и произвести 999 испытаний, то гистограмма идеально совпадет с ожидаемой и критерий Пирсона даст вероятность 100%. Однако, очевидно, что получаемая последовательность (арифметическая прогрессия) никак не может считаться случайной.
,
=0.450 .
, что в случае ррсч[0,1) дает DX=0.083. Для оценки дисперсии (вычисления выборочной дисперсии) по выборке используют формулу 
.
0.0816.
, после чего по таблице распределения хи-квадрат для полученного коэффициента и (L-1) степени свободы находят вероятность истинности гипотезы о том, что исследуемая выборка имеет заданный закон распределения.
получаем 1.2, и по таблице распределения хи-квадрат с четырьмя степенями свободы определяем, что вероятность того, что наша выборка соответствует равномерному распределению на интервале от 0 до 1, составляет ~87%. Хорошо это или плохо? Это хороший результат. Принято считать хорошими значения вероятности от 70 до 95%. Если получено меньшее значение, то велика вероятность, что заданное распределение не получено. Если вероятность более 95%, то велика вероятность того, что выборка не случайная. Наглядный пример такой ситуации: если по методу мультипликативного датчика построить генератор, взяв a=1, b=1, M=1000, и произвести 999 испытаний, то гистограмма идеально совпадет с ожидаемой и критерий Пирсона даст вероятность 100%. Однако, очевидно, что получаемая последовательность (арифметическая прогрессия) никак не может считаться случайной.