Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 19
Текст из файла (страница 19)
Например, автор провел следующий простой эксперимент во время написания этой главы. Критерий "максимум-5", описанный в следующем разделе, был применен к множеству 1 000 равномерно распределенных чисел. Было выполнено 200 наблюдений Хы Хэ, ..., Хтээ, которые, как предполагалось, имели функцию распределения Е(х) = хэ при О < х < 1. Наблюдения были разделены на 20 групп по 10 наблюдений в кажлрй, н статистика К+э была вычислена для каждой группы. По 20 значениям К э, полученным таким образом, построена эмпирическая функция, показанная на рис.
4. Гладкая кривая, изображенная на каждом из рис. 4,— это истинная функция распределения статистики К+э. На рис. 4, (а) изображено эмпирическое распределение К;э, полученное из последовательности У~+~ = (314159265ЗУ„+ 2718281829) шоб 2~~, К, = У„/2ээ и это распределение удовлетворнтельно приближает истинную функцию распределения, т. е. последовательность можно считать случайной. На рис. 4, (Ь) приведена такая же эмпирическая функция распределения, построенная по последовательности Фибоначчи. Эта последовательность имеет элобаэьяо неслучайное поведение, т. е. можно показать, используя критерий "максимум-5", что наблюдения Х„не имеют на сэмом деле распределения Е(х) = хэ. На рнс. 4, (с) изображена эмпирическая функция распределения, полученная с использованием заведомо плохой, с малым потенциалом, линейной конгруэнтной последовательности У„ч1 ((2'э+ 1)У„+ 1) пюб 2зэ, У„= 1;,/2эь.
Результаты применения КС-критерия к этой эмпирической функции приведены в (12). Используя табл. 2 для и = 20, получаем, что значения Кзе и Кээ для рис. 4, (Ь) почти подозрительны (они лежат около 5- и 88-процентного уровней), но не совсем плохи для того, чтобы отбросить их полностью. Значение Кзе для рис. 4, (с), конечно, не подходит, поэтому критерий "максимум-5' показывает явную несостоятельность этого генератора случайных чвсел. Можно было бы ожидать, что КС-критерню в этом эксперименте труднее замечать "глобальные неслучайности", чем локальные, так как основные наблюдения для рис. 4 были сделаны только по 10 раз. Если взять 20 групп по 1 000 чисел в каждой, то на рис.
4, (Ь) будет показано намного более значимое отклонение. Чтобы проиллюстрировать это, единсгпееянмй КС-критерий был применен ко всем 200 наблюдениям, которые привели к появлению рис. 4. Были получены следующие результаты. Рис. 4, (а) Кюэе 0.477 К го 0.817 Рис. 4, (Ь) Рис. 4, (с) 1,537 2.819 0.194 0.058 (16) "Глобальная неслучайность" генератора Фнбоначчи здесь проявляется вполне опре- деленно. Теперь можно окончательно описать критерий Колмогорова-Смирнова. Дано и независимых на6аюдеиив Хм ..., Х„из некоторого распределения, заданного непрерывной функцией распределения Р(я). Иначе говоря, Р(к) должна быть функцией, похожей на функции, которые показаны на рис.
3, (Ъ) и 3, (с), и не имеющей таких скачков, как скачки функции на рис. 3, (а), Затем процедура, описанная перед формулой (13), применяется к этим наблюдениям, и получаются статистики Кэ и К„. Они должны быть распределены в соответствии с табл. 2. Сравним критерии КС и Хт. Вначале заметим, что критерий КС можно использовать совместно с;~т-критерием, чтобы получить лучшую процедуру, чем метод, который, между прочим, упоминался при окончательном описании Х~-критерия. (Это означает, что существует лучший способ, чем выполнение трех проверок и определение количества "подозрительных".) Предположим, что уже сделано, скажем, 10 независимых х -проверок различных частей случайной последовательности и получены значения Ры 1т„...
1ш. Это не совсем хороший метод определения, сколько значений 1' подозрительны в большей или меньшей степени. Данная процедура будет работать в крайних случаях, и очень большие или очень малые значения могут означать, что последовательность имеет также много локальных "неслучайностей".
Но лучший общий метод состоит в составлении эмпирической функции этих 10 значений и ее сравнении с истинным распределением, полученным, из табл. 1. Эмпирическое распределение дает ясную картину результатов использованиЯ кРитеРиЯ Хэ. И действительно статистики К7э и К,е могУт быть определены из эмпирических Х -значений, таким образом указывая на успех нли неудачу проверки. Имея только 10 значений или целых 100, это легко проверить вручную с помощью графических методов.
Если значений Ъ' много, понадобится программа для вычисления ~ге-распределения на компьютере. Заметим, что все 20 наблюдеэшй на рнс. 4, (с) находятся между 5- и 95-процентным уровнями, поэтому не нужно рассматривать любое нз ннх, кэк подозрительное, индивидуально. Однако совместно эмянрические распределения показывают, что эти наблюдения не проходят проверку.
Важная разница между КС-критерием и,гт-критерием состоит в том, что КС-критерий применяется к распределенню, заданному функцией Г(х), которая не имеет скачков, в то время как Хт-критерий применяется к распределениям, имеющим только скачки (поскольку все наблюдения делятся на к категорий), Таким образом, эти два критерия предназначены для разных видов распределений. Однако крнтернй хэ можно применять даже тогда, когда Е(х) непрерывна, если разделпть область определения Р(х) на Й частей и не обращать внимания на то, как случайные величины распределены в каждой из ннх. Например, чтобы проверить, можно ли рассматривать величины Ум Уэ, ..., У„как значения случайной величины, имеющей равномерное распределение между нулем и единицей, нужно проверить гипотезу, что эта случайная величина имеет распределение г'(х) = х при О < х < 1.
Для этого естественно использовать КС-критерий. Но можно разделить интервал между нулем и единицей на к = 100 равных частей, подсчитать, сколько значений У» попадет в каждую часть, н применить Хэ-критерий с 99 степенями свободы. Сейчас существует много теоретических результатов сравнения эффективности КС-крнтерия с Хэ-критерием. Автор нашел несколько примеров, в которых КС-критерий более чувствителен к неслучайности, чем уэ-критерий. С другой стороны, в некоторых примерах ~~э-критерий дал более значимые результаты.
Если, например, 100 категорий, о которых говорилось выше, пронумеровать числами О, 1, ..., 99 и если отклонение от ожидаемых величин положительно по сравнению с числами от О до 49 и отрнцательно по сравнению с числами от 50 до 99, то эмпирическая функция распределения будет больше отличаться от Р(х), чем показывает значение ~э.
Но если отклонение от ожидаемых величин положительно по сравнению с О, 2,, 98 и отрицательно по сравнению с 1, 3,..., 99, то эмпирическая функция распределения будет примыкать к Р(х) намного теснее. Различные виды отклонений измеряются по-разному. хэ-критерий был применен к 200 наблюдениям, что привело к ситуации, изображенной на рнс.
4 (с к = 10). Соответствующие значения $' были равны 9.4, 17.7 и 39.3, поэтому в частном случае они хорошо сопоставлялись со значениями КС-критерия, приведенными в (16). Так как Х~- критерий по своей сути менее точный и требует сравнительно больших значений п, то КС-крнтернй имеет некоторые преимушества, когда проверяются непрерывные распределения. Следующий пример также интересен.
Наблюдения, изображенные на рис. 2,— это Хэ-стртистики, которые основаны на п = 200 наблюдениях критерия "максимум- 1" для 1 < 1 < 5 с областью значений, разделенной на 10 равновероятных частей. КС-статистики Кэ~ээ и Ктеэ могут быть вычислены по тому же множеству в 200 наблюдений, н результаты могут быть табулированы так же, как на рнс. 2 (можно показать, какне КС-значения выходят за 99-процентный уровень, н т. д.). Результаты для такого случая показаны на рнс.
5. Заметим, что генератор Р (оригинальный метод Лехмера) выглядит очень плохо на рнс. 5, в то время как Х~-критерий, примененный к тем же данным, наоборот, на рнс. 2 выглядит хорошо. Генератор Е (метод Фнбоначчн) на рнс. 5 выглядит неплохо. Хорошие генераторы А и В проходят все испытания удовлетворительно. Причина расхождений между рис.
2 н 5 состоят, в том, что (а) число наблюдений 200 на самом деле не достаточно Группы лля К+ в с в е р Группы ллп Кп В с в Е р Рнс. 5. Кс-крнтернн, примененные к тем же данным, которые пралставлены на рис, 2. большое для строгой проверки н (Ь) слова "отбросить", "подозрительные", "почти подозрительные", упорядочнвающне критерий, сами выглядят подозрнтельно. (Несправедливо обвинять Лехмера, что он использовал "плохой" генератор случайных чисел в 40-х годах, так как он применял зтот генератор П совершенно правильно.
Компьютер ЕХ1АС бьи машиной параллельноко действия, н программы заносились в нее штепсельным коммутатором. Лехмер сделал так, что его сумматоры постоянно умножали собственное содержимое на 23 (по модулю 10е + 1), поставляя новые значения каждые несколько мнкросекунд. Поскольку множитель 23 очень мзл н известно, что каждое значение, полученное таким образом, также зависит от предыдущего значения, его нельзя рассматривать в качестве достаточно случайного.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
