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

Поскольку при использовании детерминированных алгоритмов получаемая последовательность чисел является псевдослучайной, возникает вопрос: насколько они близки по своему поведению к случайным? Для ответа на него предложено великое множество самых разнообразных тестов - методов статистических испытаний. Сущность каждого теста заключается в сравнении различных числовых характеристик, вычисленных на основе последовательности случайных чисел от ДСЧ, и соответствующих характеристик, рассчитанных для теоретической последовательности случайных величин, равномерно распределенных в интервале [0,1]. Среди наиболее часто используемых тестов можно отметить следующие:

1. Частотные тесты. Для сравнения близости распределения полученного набора чисел от ДСЧ к равномерному распределению используют либо критерий хи-квадрат, либо критерий Колмогорова-Смирнова.

В этом случае весь диапазон чисел [0,1] разбивается на интервалы. Тогда для случайной величины U, равномерно распределенной в этом интервале, вероятность попадания в каждый из k интервалов равна 1/к, а частота = N/k, где N - число опытов.

Проверка состоит в следующем. При помощи ДСЧ вырабатывается достаточно большое количество случайных чисел. Подсчитывается ожидаемая частота попадания в каждый из к интервалов - , а также наблюдаемая частота . Статистика хи-квадрат определяется выражением

.

Если , то наблюдаемые и теоретически предсказанные значения частот точно совпадают. Если , то расчетные значения сравниваются с табличными значениями. Значения табулированы для различных чисел степеней свободы , где к - число интервалов, m - число параметров распределения, определяемых из опыта; и уровней доверительной вероятности . Если расчетная величина оказывается больше табличной, то между наблюдаемым и теоретическим распределением имеется значительное расхождение.

2. Интервальный тест. В этом тесте производится подсчет знаков, появляющихся между повторами каких-либо цифр. Результаты сравнения с теоретически ожидаемыми с помощью критерия хи-квадрат.

3. Спектральный тест. На основе применения анализа Фурье измеряется статистическая независимость соседних групп чисел. Характеризуется как наиболее чувствительный тест.

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

Дата добавления: 2014-01-11