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

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

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

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

Рис. 9.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:

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

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

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

Таблица 9.2. Некоторые процентные точки χ2-распределения

p = 1% p = 5% p = 25% p = 50% p = 75% p = 95% p = 99% ν = 1 0.00016 0.00393 0.1015 0.4549 1.323 3.841 6.635 ν = 2 0.02010 0.1026 0.5754 1.386 2.773 5.991 9.210 ν = 3 0.1148 0.3518 1.213 2.366 4.108 7.815 11.34 ν = 4 0.2971 0.7107 1.923 3.357 5.385 9.488 13.28 ν = 5 0.5543 1.1455 2.675 4.351 6.626 11.07 15.09 ν = 6 0.8721 1.635 3.455 5.348 7.841 12.59 16.81 ν = 7 1.239 2.167 4.255 6.346 9.037 14.07 18.48 ν = 8 1.646 2.733 5.071 7.344 10.22 15.51 20.09 ν = 9 2.088 3.325 5.899 8.343 11.39 16.92 21.67 ν = 10 2.558 3.940 6.737 9.342 12.55 18.31 23.21 ν = 11 3.053 4.575 7.584 10.34 13.70 19.68 24.72 ν = 12 3.571 5.226 8.438 11.34 14.85 21.03 26.22 ν = 15 5.229 7.261 11.04 14.34 18.25 25.00 30.58 ν = 20 8.260 10.85 15.45 19.34 23.83 31.41 37.57 ν = 30 14.95 18.49 24.48 29.34 34.80 43.77 50.89 ν = 50 29.71 34.76 42.94 49.33 56.33 67.50 76.15 ν > 30 ν + sqrt(2ν) · xp + 2/3 · x2p – 2/3 + O(1/sqrt(ν)) xp = –2.33 –1.64 –0.674 0.00 0.674 1.64 2.33

Приемлемым считают 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%, тем лучше.