Частотный тест

Частотный тест позволяет выяснить, сколько чисел попало в интервал (m_r – σ _r; m_r + σ _r), то есть (0.5 – 0.2887; 0.5 + 0.2887) или, в конечном итоге, (0.2113; 0.7887). Так как 0.7887 – 0.2113 = 0.5774, заключаем, что в хорошем ГСЧ в этот интервал должно попадать около 57.7% из всех выпавших случайных чисел (см. рис. 22.9).

Рис. 22.9. Частотная диаграмма идеального ГСЧ в случае проверки его на частотный тест

Также необходимо учитывать, что количество чисел, попавших в интервал (0; 0.5), должно быть примерно равно количеству чисел, попавших в интервал (0.5; 1).

3) Проверка по критерию «хи-квадрат»

Критерий «хи-квадрат» (χ ²-критерий) — это один из самых известных статистических критериев; он является основным методом, используемым в сочетании с другими критериями. Критерий «хи-квадрат» был предложен в 1900 году Карлом Пирсоном. Его замечательная работа рассматривается как фундамент современной математической статистики.

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

Частотная диаграмма эталонного ГСЧ представлена на рис. 22.10. Так как закон распределения эталонного ГСЧ равномерный, то (теоретическая) вероятность p_i попадания чисел в i -ый интервал (всего этих интервалов k) равна p_i = 1/ k. И, таким образом, в каждый из k интервалов попадет ровно по p_i · N чисел (N — общее количество сгенерированных чисел).

Рис. 22.10. Частотная диаграмма эталонного ГСЧ

Реальный ГСЧ будет выдавать числа, распределенные (причем, не обязательно равномерно!) по k интервалам и в каждый интервал попадет по n_i чисел (в сумме n ₁ + n ₂ + … + n_k = N). Как же нам определить, насколько испытываемый ГСЧ хорош и близок к эталонному? Вполне логично рассмотреть квадраты разностей между полученным количеством чисел n_i и «эталонным» p_i · N. Сложим их, и в результате получим:

χ ²_эксп. = (n ₁ – p ₁ · N)² + (n ₂ – p ₂ · N)² + … + (n_k – p_k · N)².

Из этой формулы следует, что чем меньше разность в каждом из слагаемых (а значит, и чем меньше значение χ ²_эксп.), тем сильнее закон распределения случайных чисел, генерируемых реальным ГСЧ, тяготеет к равномерному.

В предыдущем выражении каждому из слагаемых приписывается одинаковый вес (равный 1), что на самом деле может не соответствовать действительности; поэтому для статистики «хи-квадрат» необходимо провести нормировку каждого i -го слагаемого, поделив его на p_i · N:

Наконец, запишем полученное выражение более компактно и упростим его:

Мы получили значение критерия «хи-квадрат» для экспериментальных данных.

В табл. 22.2 приведены теоретические значения «хи-квадрат» (χ ²_теор.), где ν = N – 1 — это число степеней свободы, p — это доверительная вероятность, задаваемая пользователем, который указывает, насколько ГСЧ должен удовлетворять требованиям равномерного распределения, или p — это вероятность того, что экспериментальное значение χ ²_эксп. будет меньше табулированного (теоретического) χ ²_теор. или равно ему.

Приемлемым считают p от 10% до 90%.

Если χ ²_эксп. много больше χ ²_теор. (то есть p — велико), то генератор не удовлетворяет требованию равномерного распределения, так как наблюдаемые значения n_i слишком далеко уходят от теоретических p_i · N и не могут рассматриваться как случайные. Другими словами, устанавливается такой большой доверительный интервал, что ограничения на числа становятся очень нежесткими, требования к числам — слабыми. При этом будет наблюдаться очень большая абсолютная погрешность.

Еще Д. Кнут в своей книге «Искусство программирования» заметил, что иметь χ ²_эксп. маленьким тоже, в общем-то, нехорошо, хотя это и кажется, на первый взгляд, замечательно с точки зрения равномерности. Действительно, возьмите ряд чисел 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, … — они идеальны с точки зрения равномерности, и χ ²_эксп. будет практически нулевым, но вряд ли вы их признаете случайными.

Если χ ²_эксп. много меньше χ ²_теор. (то есть p — мало), то генератор не удовлетворяет требованию случайного равномерного распределения, так как наблюдаемые значения n_i слишком близки к теоретическим p_i · N и не могут рассматриваться как случайные.

А вот если χ ²_эксп. лежит в некотором диапазоне, между двумя значениями χ ²_теор., которые соответствуют, например, p = 25% и p = 50%, то можно считать, что значения случайных чисел, порождаемые датчиком, вполне являются случайными.

При этом дополнительно надо иметь в виду, что все значения p_i · N должны быть достаточно большими, например больше 5 (выяснено эмпирическим путем). Только тогда (при достаточно большой статистической выборке) условия проведения эксперимента можно считать удовлетворительными.

Итак, процедура проверки имеет следующий вид.

1. Диапазон от 0 до 1 разбивается на k равных интервалов.
2. Запускается ГСЧ N раз (N должно быть велико, например, N / k > 5).
3. Определяется количество случайных чисел, попавших в каждый интервал: n_i, i = 1, …, k.
4. Вычисляется экспериментальное значение χ ²_эксп. по следующей формуле:

где p_i = 1/ k — теоретическая вероятность попадания чисел в k -ый интервал.

1. Путем сравнения экспериментально полученного значения χ ²_эксп. с теоретическим χ ²_теор. (из табл. 22.2) делается вывод о пригодности генератора для использования. Для этого: а) входим в табл. 22.2 (строка = количество экспериментов – 1); б) сравниваем вычисленное χ ²_эксп. с χ ²_теор., встречающимися в строке. При этом возможно три случая.

Первый случай: χ ²_эксп. много больше любого χ ²_теор. в строке — гипотеза о случайности равномерного генератора не выполняется (разброс чисел слишком велик, чтобы быть случайным).

Второй случай: χ ²_эксп. много меньше любого χ ²_теор. в строке — гипотеза о случайности равномерного генератора не выполняется (разброс чисел слишком мал, чтобы быть случайным).

Третий случай: χ ²_эксп. лежит между значениями χ ²_теор. двух рядом стоящих столбцов — гипотеза о случайности равномерного генератора выполняется с вероятностью p (то есть в p случаях из 100).

Заметим, что чем ближе получается p к значению 50%, тем лучше.