Методы проверки качества псевдослучайных чисел с равномерным законом распределения

Пусть имеется h - случайная величина, о законе распределения которой выдвигается некоторая гипотеза, Х - множество возможных значений h. Разобьем Х на m попарно непересекающихся множеств Х₁, Х₂, ¼ ,Х_m, таких, что

P { h ÎХ_j } = p_j > 0 при j = 1, 2, ¼, m,

p₁ + p₂ + ¼ p_m = P { hÎХ } = 1.

Выберем N независимых значений h₁, h₂, ¼ ,h_N и обозначим через ν_j количество значений h ÎХ_j. Очевидно, что математическое ожидание ν_j равно Np_j, т.е. М[ν_j] = Np_j.

В качестве меры отклонения всех ν_j от Np_j выбирается величина

(7)

При достаточно большом N величина хорошо подчиняется закону распределения с ( m - 1) степенью свободы:

P { < } , (8)

где - плотность распределения с (m - 1) степенью свободы. Для распределения составлены специальные таблицы, приведенные в приложении А.

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

2.1.1. Тесты проверки ²случайности²

На практике обычно применяют два теста проверки ²случайности²: тест проверки серий и тест проверки частот и пар.

Тест проверки серий предусматривает разбиение случайных цифр в исследуемой последовательности на элементы двух родов - первого и второго.

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

Например, если в последовательности цифр

e₁, e₂, ¼,e_k e_{k + 1}, e_{k + 2}, ¼ ,e_{k +} e_{k + + 1}, e_{k+ +2}, ¼ ,e_s

серия 1-го серия 2-го серия 1-го

рода длины k рода длины рода длины s - k -

e₁ ¹ e₂ ¹ ¼ ¹ e_k ¹ e_{k + 1}, e_{k + 1} = e_{k + 2} = ¼ = e_{k +} и e_{k +} ¹ e_{k + + 1} ¹ ¼ ¹ e_s, то цифры e₁, e₂, ¼ ,e_k образуют серию первого рода длины k, цифры e_{k + 1}, e_{k + 2}, ¼ ,e_{k +} образуют серию второго рода длины и цифры e_{k + + 1}, e_{k+ + 2}, ¼ ,e_s также образуют серию первого рода длины s - k - . Иногда для удобства элементы серий первого рода обозначают знаками ²-² (минус), а второго рода - знаками ²+² (плюс).

В практике встречается другая разновидность теста проверки серий, когда к элементам серий первого рода относят числа, меньшие 0.5, а к элементам серий второго рода - не меньшие 0.5.

При достаточно большом объеме выборки e₁, e₂, ¼,e_N ( практически при N ³ 20 ) и уровне значимости α = 0.05 нижний предел общего числа серий равен:

(12)

а нижний предел числа серий элементов первого и второго родов равен:

(13)

Максимальная длина серий не должна быть больше, чем

(14)