Исследование качества генераторов случайных чисел

1.4. Исследование качества ГСЧ, сформированного по линейному конгруэнтному методу

Формирование случайных (псевдослучайных) чисел по линейному конгруэнтному методу основывается на следующем рекуррентном соотношении:

где:

$$R_{k+1}$$ — вновь формируемое число;

$$a$$ — множитель (мультипликативная константа);

$$R_{k}$$ — предыдущее число ( $$R_{0}$$ — назначаемое число);

$$c$$ — приращение (инкремент);

$$mod$$ — модуль, бинарная операция для обозначения остатка от деления двух чисел;

$$M$$ — целочисленная константа [19]. Для $$n$$ -разрядных целых чисел $$M=2^{n}$$. В самом простом случае принимается, что $$c=0$$ Массив случайных чисел $${x_{i}}$$ из интервала $$(0,1)$$ будет формироваться следующим образом:

где $$R_{i}$$ — числа, определяемые по формуле (5.1).

В стандартной процедуре реализации линейного конгруэнтного метода (5.1) принимается, что $$a,c,M$$ — целые положительные числа. Приведем определение конгруэнтности двух чисел $$X$$ и $$Y$$: два числа $$Y$$ и $$Х$$ конгруэнтны (сравнимы) по модулю числа $$M$$, если они дают одинаковые остатки при делении на этот модуль $$M$$. Таким образом, по формуле (5.1) число $$R_{k+1}$$ будет конгруэнтно по модулю $$M$$ числу $$(aR_{k}+c)$$.

При выборе чисел $$a,c,M$$ придерживаются следующих правил:

В качестве множителя $$a$$ рекомендуется принимать первообразный корень по модулю $$М$$. Приведем следующее классическое определение.

Первообразный корень по модулю $$М$$ — натуральное число $$g$$, такое, что наименьшее положительное число $$k$$, для которого разность $$g^{k}-1$$ делится на $$М$$ (без остатка), совпадает с $$\varphi(M)$$, где $$\varphi(M)$$ — число натуральных чисел, меньших $$М$$ и взаимно простых с $$М$$.

Например, при $$М = 7$$ первообразным корнем по модулю 7 является число 3. Действительно, $$\varphi(M)=6$$, т. е. количеству чисел ряда $$1, 2, 3, 4, 5, 6$$, каждое из которых взаимно просто с числом 7.

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

Числа $$3^{1} – 1 = 2,\mbox{ }3^{2} – 1 = 8,\mbox{ }3^{3} – 1 = 26,\mbox{ }3^{4} – 1 = 80,\mbox{ }3^{5} – 1 = 242$$ не делятся на 7 без остатка, и лишь $$3^{6} – 1 = 728$$ делится на 7 (частное от деления равно 104).

В системе MATLAB формирование простых чисел производится с помощью функции $$primes$$ (см. $$help\mbox{ }primes$$ ). Для проверки, являются ли два числа взаимно простыми, можно применить функцию $$gcd$$, которая определяет наибольший общий делитель для двух чисел.

В самом простом случае принимается, что $$c=0$$ При этом можно использовать следующие рекомендации по выбору параметров генератора:

Пример формирования модуля $$M$$ в командном окне MATLAB:

>> N = 7*10^6;
>> m = primes(N);
>> M = m(end)
M =
     6999997

Задание 4

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

По критерию Колмогорова–Смирнова (КС-критерию) осуществляется проверка простой статистической гипотезы $$Н_{0}$$ (нулевой гипотезы) о том, что функция распределения $$F(x)$$ случайной величины $$Х$$ совпадает с некоторой известной функцией $$F_{0}(x)$$ при некотором уровне значимости $$\alpha$$. КС-критерием можно пользоваться уже при объеме выборки $$n \ge 20$$.

В системе MATLAB КС-критерий реализован функцией $$kstest$$.

Рассмотрим пример использования функции $$kstest$$ для проверки гипотезы о том, что функция распределения $$(F)$$ выборки, сформированной с помощью функции $$rand$$, соответствует функции распределения $$(F0)$$ экспоненциального закона с параметром 1 той же самой выборки.

Программное решение примера в командном окне MATLAB:

>> x = rand(25,1); F0 = expcdf(x,1);
>> H = kstest(x,[x,F0])
H =
     1

Полученный результат $$Н = 1$$ означает, что нулевая гипотеза отвергается, т. е. выборочная функция равномерного распределения $$(F)$$ в интервале $$[0; 1]$$ имеет значительные расхождения с предполагаемой функцией экспоненциального распределения $$(F0)$$ с уровнем значимости $$\alpha$$ = 0.05 (по умолчанию). Если закладывается другой уровень значимости, отличный от 0.05, то тогда он должен быть введен в функцию $$kstest$$. На том же примере это будет выглядеть так (с уровнем значимости 0.012):

>> x = rand(25,1); F0 = expcdf(x,1);
>> H = kstest(x,[x,F0],0.012)
H =
     1

По-прежнему нулевая гипотеза отвергается.

Рассмотрим пример использования функции $$kstest$$ для проверки гипотезы о том, что функция распределения выборки, сформированной с помощью $$rand$$, соответствует функции распределения равномерного закона из интервала $$[0; 1]$$ той же самой выборки.

Решение примера в командном окне MATLAB:

>> x = rand(25,1); F0 = unifcdf(x,0,1);
>> H = kstest(x,[x,F0])
H =
     0

Нулевая гипотеза о равномерном распределении выборки принимается.

Задание 5

3. Исследование качества ГСЧ по критерию независимости случайных чисел с помощью нормированной автокорреляционной функции

Корреляционная функция называется автокорреляционной, если производится статистический анализ одного случайного процесса (или одной выборки случайных чисел).

Нормированной корреляционной функцией называется отношение центрированной корреляционной функции к дисперсии случайного процесса [4].

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

$$n_{1} – m$$,

где:

$$n_{1}$$ — случайное число;

$$m = 0.5$$ — теоретическое математическое ожидание равномерного распределения.

Для определения корреляционной функции по результатам опыта выбирается достаточно большой объем выборки, чтобы можно было в широком диапазоне формировать разницу между двумя соседними значениями случайных чисел. Эту разницу для непрерывного времени обычно обозначают через $$\tau$$ и тогда корреляционная функция обозначается как $$R(\tau)$$. Если объем выборки составляет N, то диапазон вычисления корреляционной функции будет определяться как $$N – \tau$$. Величина $$\tau$$ задает область определения корреляционной функции. Например, $$\tau$$ может меняться от 0 до 6-8. При этом $$N$$ должно быть много больше 6 или 8. Область суммирования принимает значения от 1 (первое случайное число выборки) до $$N – \tau$$.

После этого корреляционная функция вычисляется по следующей экспериментальной формуле:

где $$n_{j}$$ — случайное число из заданной выборки случайных чисел.

Расчет по приведенной формуле: если взято какое-либо случайное число, то другое случайное число отстоит от первого на величину $$\tau$$.

Обозначим нормированную корреляционную функцию как $$\widetilde{R}$$. Центрированную корреляционную функцию обозначим через $$R^{\circ}$$. Тогда нормированная корреляционная функция будет определяться в виде отношения

где $$s$$ — дисперсия данной выборки случайных чисел.

Вычисление $$R^{\circ}$$ можно выполнять по приведенной экспериментальной формуле (5.3), если в ней применяются центрированные случайные числа.

ГСЧ считается хорошим, если при $$\tau$$, не равным нулю, модуль нормированной корреляционной функции меньше 0.1, т. е. $$|\widetilde{R}|< 0.1$$.

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

Программный код решения примера:

clear,clc
%% Ввод параметров в интерактивном режиме
V1 = inputdlg({'Введите число больше 10.......................................',...
    'Сдвиг больше 1'},'Корреляционная функция',1,{'800','6'});

%% Преобразование к числам с плавающей точкой
V2 = str2num(char(V1));
% Гарантированное выделение целой части
V = fix(V2(1));
z = fix(V2(2));
% Формирование выборки случайных чисел
N = rand(V,1); 
%% Центрирование выборки случайных чисел относительно математического ожидания
Nc = N - 0.5;

%% Расчет автокорреляционной функции
sum1 = Nc(1:(V-z));
sum2 = Nc((1+z):V);
Rc = sum(sum1.*sum2)/(V-z);
s = var(N);
Rn = (Rc/s);
%% Проверка качества случайных чисел
if abs(Rn) < 0.1
   fprintf('\n\t ГСЧ выcокого качеcтва\n')
else
   fprintf('\n\t ГСЧ низкого качеcтва\n')
end
%% Интерактивное сообщение
helpdlg('Смотрите результаты в командном окне','Корреляционная функция')

В программе по умолчанию исследуется объем выборки величиной 800 со сдвигом между числами, равным 6.

Задание 6

Компьютер № 1: N = 410;     Компьютер № 2: N = 520;
Компьютер № 3: N = 630;     Компьютер № 4: N = 740;
Компьютер № 5: N = 850;     Компьютер № 6: N = 960;
Компьютер № 7: N = 1070;   Компьютер № 8: N = 1180;
Компьютер № 9: N = 1190;   Компьютер № 10: N = 1210.

Контрольные вопросы