величины Xj действительно имеют вероятностное распределение G(x), в то время как предполагается, что они имеют распределение, определяемое функцией F{x), п должно быть сравнительно большим для того, чтобы отбросить гипотезу о равенстве G{x) = F{x). Для этого п должно быть настолько большим, чтобы ожидаемые эмпирические функции распределения G„(a;) и Fn{x) заметно различались. С другой стороны, большие значения п приводят к усреднению локального неслучайного поведения, и такое нежелательное поведение приводит к значительным неприятностям в большинстве компьютерных применений случайных чисел; это может служить причиной для выбора небольших значений п. Хороший компромисс будет достигнут, если взять п равным, скажем, 1 ООО и вычислить достаточно много Kqqo для различных частей случайной последовательности. Тем самым получим значения

Гооо(1), Гооо(2), Л-ГоооИ- (14)

Затем можно применить КС-критерий снова к этим результатам. Пусть сейчас F{x) - это функция распределения случайной величины Kqqq. Найдем эмпирическую функцию распределения Fr{x) для наблюдений случайной величины в (14). К счастью, функция F{x) в этом случае имеет очень простой вид. Для больших п, таких, как п = 1000, функция распределения примерно равна

Fooix) = I - е-\ х>0. (15)

Данное замечание применимо к К~, поскольку и К~ имеют одно и то же ожидаемое поведение. Можно использовать КС-критерий следующим образом: сначала критерий применяется несколько раз при умеренно больших п, а затем наблюдения объединяют и снова применяют КС-критерий. Это позволяет обнаружить как локальные, так и глобальные отклонения от гипотетического распределения.

Например, автор провел следующий простой эксперимент во время написания этой главы. Критерий "максимум-5", описанный в следующем разделе, был применен к множеству 1 ООО равномерно распределенных чисел. Было выполнено 200 наблюдений Xi, Х2, Х200, которые, как предполагалось, имели функцию распределения F{x) = х при О < а; < 1. Наблюдения были разделены на 20 групп по 10 наблюдений в каждой, и статистика Kq была вычислена для каждой группы. По 20 значениям К:, полученным таким образом, построена эмпирическая функция, показанная на рис. 4. Гладкая кривая, изображенная на каждом из рис. 4, - это истинная функция распределения статистики Kq. На рис. 4, (а) изображено эмпирическое распределение Kq, полученное из последовательности

У„+1 = (3141592653У„ + 2718281829) mod 2 f/„ = У„/2

и это распределение удовлетворительно приближает истинную функцию распределения, т. е. последовательность можно считать случайной. На рис. 4, (Ь) приведена такая же эмпирическая функция распределения, построенная по последовательности Фибоначчи. Эта последовательность имеет глобально неслучайное поведение, т. е. можно показать, используя критерий "максимум-5", что наблюдения Х„ не имеют на самом деле распределения F{x) = х. На рис. 4, (с) изображена эмпирическая функция распределения, полученная с использованием заведомо плохой, с малым потенциалом, линейной конгруэнтной последовательности Уп+i = ((2* -f 1)У„ -I-1) mod 2, Un = Уп/2. Результаты применения КС-критерия к этой

эмпирической функции приведены в (12). Используя табл. 2 для п = 20, получаем, что значения и ддя рис. 4, (Ь) почти подозрительны (они лежат около 5- и 88-процентного уровней), но не совсем плохи для того, чтобы отбросить их полностью. Значение /20 Р- 4, (с), конечно, не подходит, поэтому критерий "максимум-5" показывает явную несостоятельность этого генератора случайных чисел.

Можно было бы ожидать, что КС-критерию в этом эксперименте труднее замечать "глобальные неслучайности", чем локальные, так как основные наблюдения для рис. 4 были сделаны только по 10 раз. Если взять 20 групп по 1 ООО чисел в каждой, то на рис. 4, (Ь) будет показано намного более значимое отклонение. Чтобы проиллюстрировать это, единственный КС-критерий был применен ко всем 200 наблюдениям, которые привели к появлению рис. 4. Были получены следующие результаты.

Рис. 4, (а) Рис. 4, (Ь) Рис. 4, (с) К+оо 0.477 1.537 2.819 (16)

К200 0-817 0.194 0.058

"Глобальная неслучайность" генератора Фибоначчи здесь проявляется вполне определенно.

Теперь можно окончательно описать критерий Колмогорова-Смирнова. Дано п независимых наблюдений Xi, Х„ из некоторого распределения, заданного непрерывной функцией распределения F{x). Иначе говоря, F{x) должна быть функцией, похожей на функции, которые показаны на рис. 3, (Ь) и 3, (с), и не имеющей таких скачков, как скачки функции на рис. 3, (а). Затем процедура, описанная перед формулой (13), применяется к этим наблюдениям, и получаются статистики К+ и К- Они должны быть распределены в соответствии с табл. 2.

Сравним критерии КС и х- Вначале заметим, что критерий КС можно использовать совместно с х-критерием, чтобы получить лучшую процедуру, чем метод, который, между прочим, упоминался при окончательном описании х-критерия. (Это означает, что существует лучший способ, чем выполнение трех проверок и определение количества "подозрительных".) Предположим, что уже сделано, скажем, 10 независимых х-проверок различных частей случайной последовательности и получены значения Vi, V2,..., Vio- Это не совсем хороший метод определения, сколько значений v подозрительны в большей или меньшей степени. Данная процедура будет работать в крайних случаях, и очень большие или очень малые значения могут означать, что последовательность имеет также много локальных "неслучайностей". Но лучший общий метод состоит в составлении эмпирической функции этих 10 значений и ее сравнении с истинным распределением, полученным, из табл. 1. Эмпирическое распределение дает ясную картину результатов использования критерия х- И действительно статистики /fJo и K{q могут быть определены из эмпирических х-значений, таким образом указывая на успех или неудачу проверки. Имея только 10 значений или целых 100, это легко проверить вручную с помощью графических методов. Если значений v много, понадобится программа для вычисления х-распределения на компьютере. Заметим, что все 20 наблюдений на рис. 4, (с) находятся между 5- и 95-процентным уровнями, поэтому

не нужно рассматривать любое из них, как подозрительное, индивидуально. Однако совместно эмпирические распределения показывают, что эти наблюдения не проходят проверку. Важная разница между КС-критерием и х-критерием состоит в том, что КС-критерий применяется к распределению, заданному функцией F{x), которая не имеет скачков, в то время как х-критерий применяется к распределениям, имеющим только скачки (поскольку все наблюдения делятся на к категорий). Таким образом, эти два критерия предназначены для разных видов распределений. Однако критерий х можно применять даже тогда, когда F{x) непрерывна, если разделить область определения F{x) на fc частей и не обращать внимания на то, как случайные величины распределены в каждой из них. Например, чтобы проверить, можно ли рассматривать величины Ui, U2, Un как значения случайной величины, имеющей равномерное распределение между нулем и единицей, нужно проверить гипотезу, что эта случайная величина имеет распределение F{x) = х при О < X < I. Для этого естественно использовать КС-критерий. Но можно разделить интервал между нулем и единицей на fc = 100 равных частей, подсчитать, сколько значений Uk попадет в каждую часть, и применить х-критерий с 99 степенями свободы. Сейчас существует много теоретических результатов сравнения эффективности КС-критерия с х-критерием. Автор нашел несколько примеров, в которых КС-критерий более чувствителен к неслучайности, чем х-критерий. С другой стороны, в некоторых примерах х-критерий дал более значимые результаты. Если, например, 100 категорий, о которых говорилось выше, пронумеровать числами О, 1, ..., 99 и если отклонение от ожидаемых величин положительно по сравнению с числами от О до 49 и отрицательно по сравнению с числами от 50 до 99, то эмпирическая функция распределения будет больше отличаться от F{x), чем показывает значение х- Но если отклонение от ожидаемых величин положительно по сравнению с О, 2,..., 98 и отрицательно по сравнению с 1, 3,..., 99, то эмпирическая функция распределения будет примыкать к F{x) намного теснее. Различные виды отклонений измеряются по-разному, х-критерий был применен к 200 наблюдениям, что привело к ситуации, изображенной на рис. 4 (с fc = 10). Соответствующие значения V были равны 9.4, 17.7 и 39.3, поэтому в частном случае они хорошо сопоставлялись со значениями КС-критерия, приведенными в (16). Так как х критерий по своей сути менее точный и требует сравнительно больших значений п, то КС-критерий имеет некоторые преимущества, когда проверяются непрерывные распределения.

Следующий пример также интересен. Наблюдения, изображенные на рис. 2, - это х-сттистики, которые основаны на п = 200 наблюдениях критерия "максимум-Г для 1 < t < 5 с областью значений, разделенной на 10 равновероятных частей. КС-статистики Лгоо и 200 могут быть вычислены по тому же множеству в 200 наблюдений, и результаты могут быть табулированы так же, как на рис. 2 (можно показать, какие КС-значения выходят за 99-процентный уровень, и т. д.). Результаты для такого случая показаны на рис. 5. Заметим, что генератор D (оригинальный метод Лехмера) выглядит очень плохо на рис. 5, в то время как Х-критерий, примененный к тем же данным, наоборот, на рис. 2 выглядит хорошо. Генератор Е (метод Фибоначчи) на рис. 5 выглядит неплохо. Хорошие генераторы А и В проходят все испытания удовлетворительно. Причина расхождений между рис. 2 и 5 состоит, в том, что (а) число наблюдений 200 на самом деле не достаточно