Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 18
Текст из файла (страница 18)
Генератор Š— это метод э=е э=- э=1 1 х О э й э 1 1 (ь) (а) Рис. 3. Примеры функций распределения. Фибоначчи (Р)Ьопасс1), 3,2.2-(5), а другие генераторы — это линейные конгруэнт- ные последовательности со следующими параметрами. Хо = О, а = 314И92653, с = 2718281829, Хо=О, о=2 +1, с=1, т=2эо. Хо = 47594118, а = 23, с = О, Ло = 314И9263, а = 2'э + 1, с Генератор В Генератор С Генератор 0 Генератор Е Гбэ+ 1 =1, т=2ы.
В. Критерий Колмогорова-Смирнова. Как мы уже видели, Хэ-критерий применяется в ситуациях, когда наблюдения могут относиться только к конечному числу категорий. Однако совершенно небесполезно рассматривать случайные величины, которые принимают бесконечное множество значений, такие как случайные дроби (случайные действительные числа между О и 1). Хотя только конечное множество Из рис. 2 заключаем, что (как следует из результатов проверки) генераторы А, В, Р удовлетворительны, генератор С находится на границе и его следовало бы отбросить, генераторы Е и Р, безусловно, неудовлетворительны.
Генератор Г имеет, конечно, низкий потенциал; генераторы С и 0 уже обсуждались в литературе, но их множители слишком малы. (Генератор 0 — оригинальный мультипликативный генератор, предложенный Лехмером- (ЬеЬгпег) в 1948 году; генератор С вЂ” оригинальный линейный конгруэнтный генератор с с Ф О, предложенный Ротенбергом (ВосепЬегй) в 1960 году.) Вместо терминов "подозрительный", "почти подозрительный" и т. д. для описания результатов применения Хз-критерия можно, кспюти,.
использовать процедуру, обсуждаемую ниже в этом разделе. действительных чисел может быть представлено в компьютере, мы хотим, чтобы они вели себя подобно реальным числам в интервале [О .. 1). В теории вероятностей и математической статистике одни и те же обозначения используются, когда случайная величина принимает конечное либо бесконечное число значений. Чтобы задать распределение значений случайной величины Х, следует сделать это в терминах функции распределения Р(х), где Р(х) = Рг(Х < х) = вероятности, что (Х < х). На рис. 3 приведены три примера. Сначала (рис. 3, (а)) представлена функция распределения слрчайнога дваичнога разряда, когда Х принимает только значения 0 и 1, каждое с вероятностью 1.
Затем (рис, 3, (Ь) ) показана функция распределения равномерно распределенных случайных дейс|пви1пельнмх чисел, лежащих между 0 и 1. Здесь вероятность того, что Х < х, просто равна х, когда О < х < 1. Например, вероятность, что Х < ~3, равна, естественно, 3. И наконец, на рис. 3, (с) представлено предельное распределение случайной величины у в Хэ-критерии (здесь приведен случай с 10 степенями свободы). Это распределение в другом виде приводилось в табл.
1. Заметим, что Р(х) всегда возрастает от 0 до 1, когда х возрастает от — со до +со. Если выполнить и независимых наблюдений случайной величины Х и получить значения Хм Хз, ...,Х„, то можно будет построить эмаирическрю функцию распределения Р„(х), где число ХмХэ,...,Х„, таких, что они < х Р„(х)— и (10) К„' = ~/й шах (Р„(х) — Р(х)); К„= ~/й шах (Р(х) — Р„(х)) .
На рис. 4 показаны трн эмпирические функции распределения (они изображены зигзагообразными линиями, хотя, строго говоря, вертикальные линии не являются частью графика Р„(х)). На них наложены графики предполагаемых настоящих функций распределения Р(х). Когда и становится больше, Р„(х) более точно приближает Р(х). Критерий Колмогорова-Смирнова (КС-критерий) может использоваться, когда функция Р(х) непрерывна (не имеет скачков). Он основан на разнвстни мехсдр Р(х) и Р (х). Плохой источник случайных чисел (автор имеет в виду источник случайных чисел, распределение которых не соответствует требуемому. — Дрим.
ред.) будет давать такую эмпирическую функцию, которая плохо приближает предполагаемую функцию распределения Р(х). На рис. 4, (Ь) приведен пример случайной величины, для которой почти все Х; расположены слишком высоко, а это приводит к тому, что эмпирическая функция распределения находится слишком низко. На рис, 4, (с) приведен еще худший пример.
Ясно, что такое большое расхождение между Р (х) и Р(х) совершенно невероятно, и КС-критерий может только показать, насколько именно. Чтобы построить КС-критерий, образуем такие статистики: $% $$%$0% 7$% 9$% 9$% (ь) Рнс. 4. Примеры змпирических распределения. $% $$%$0% 7$% $$% $9% Здесь К+ определяет наибольшее из отклонений, когда Е„больше Г, а ʄ— гч меньше Е Эти статистики для примеров, приведенных на рис. 4, таковы. Рис. 4, (а) Рис, 4, (Ь) Рис. 4, (с) Кз+е 0.492 0,134 0,313 Кте 0.536 1.027 2.101 (12) (Замечение.
Множитель чгй, который появляется в формуле (11), на первый взгляд, сбивает с талку. В упр. 6 показано, что для фиксированного я стандартное отклонение Е„(я) пропорционально 1/$/й; следовательно, множитель ~~й увеличивает статистики К+ и К„- таким образом, что зто стандартное отклонение не зависит от и.) Точно так же, как и для 1т-критерия, можно сравнить значения К+ и К„с процентной таблицей и определить, будут ли они значимо выше или ниже. Табл.
2 можно использовать одновременно для К+ и К„-. Например, вероятность, что Кзе < 0,7975, равна 75% (автор имеет в виду здесь и далее, что вероятность равна 0.75.— Прим. ред.). Отличие от Хт-критерия состоит в том, что в таблице представлены ие просто приближенные значения, которые справедливы для достаточно больших и; табл. 2 дает точные значения (за исключением, конечно, ошибки округления), и КС-критерий может надежно использоваться для любого значения и. Формулы (1Ц в том виде, в котором они записаны, не совсем подходят для вычислений на компьютере, так как формально нужно находить максимум по бесконечному множеству значений я. Но, учитывая тот факт, что Г(я) возрастает, н Таблица 2 НЕКОТОРЫЕ ПРОЦЕНТНЫЕ ТОЧКИ РАСПРЕДЕЛЕНИЙ Кь+ И К„ р=75% р=95% )э =1% р=5% рж25% 0.9900 0.01000 0,05000 0.2500 0.7500 0.9500 0.5000 1.0980 1.2728 0.01400 0.06749 0.2929 0,01699 0.07919 О.ЗП2 0.5ПВ 0.7071 1.3589 0.7539 1.1017 0.5147 1.1304 1.3777 0.01943 0.08789 0,3202 0.7642 0.5ПО 0.7674 1.1392 1.4024 0.02152 0.09471 0.3249 0.5245 1.1463 1.4144 0.02336 0.1002 0.02501 0.1048 О.ПОЗ 0.3272 0.5319 0.7755 1.1537 и=7 0.3280 0.5364 1.1586 1.4327 0.02650 0,1086 0.3280 0,5392 0,7825 1.
1624 0.02786 О.П19 0.3274 0.54П 1.1658 1.4440 и = 10 0.02912 О.П47 0.3297 0.5426 0.7845 0.03028 0.7863 1.1688 1.4484 0.5439 0.1172 0.3330 п=П 1.4521 0.03137 О.ПОЗ 0.3357 0.5453 0.7880 1,1714 1.4606 1.1ТТЗ п = 15 0.03424 0.1244 0.3412 0.5500 0.7926 1.4698 О. 7975 1. 1839 и = 20 п = 30 0.03807 0,1298 0.04354 0.1351 0.3461 0.5547 1.1916 1.4801 0.8036 0.3509 0,5605 рр — -'и И~ + О(1/п), где ре - --'!в(1/(1 — р)) и > 30 0.07089 0,1601 0.3793 0.5887 0,8326 1.2239 1.5174 Дли ресширеиия этой таблицы еослольэуйтесь формуламя (25) и (26), а также отеетом к уир.
20. К+ = т/п щах ~- — Г(Х))); 1<1<я~в Т' — 11 К„= /й щах ~Р'(Х1) — — ). с<1<я ~ и Выбрать подходящее число наблюдений и немного легче для зтога критерия, чем для ТСт-критерия, хотя некоторые из рассуждений похожи. Если случайные то, что Г (я) возрастают только в конечном множестве точек, можно пре~псожить простую процедуру для подсчета статистик К+ и К„. Шаг 1. Получить независимые наблюдения ХО Хе,..., Х Шаг 2. Упорядочить наблюдения так, чтобы они располагались в порядке воз- растания (построить вариационный ряд): Хс < Хо « ° Хя. (Эффективный алгоритм сортировки приведен в главе 5. Но в этом случае сортировки можно иЪбежать, как показано в упр.
23.) Шаг 3. Иужные статистики сейчас знаются формулами величины Х действительно имеют вероятностное распределение с'(х), в то время как предполагается, что они имеют распределение, определяемое функцией Г(х), и должно быть сравнительно большим для того, чтобы отбросить гипотезу о равенстве С(х) = Е(х). Для этого и должно быть настолько большим, чтобы ожидаемые эмпирические функции распределения С„(х) и Е (х) заметно различались. С другой стороны, большие значения и приводят к усреднению локального неслучайного поведения, и такое нежелательное поведение приводит к значительным неприятностям в большинстве компьютерных применений случайных чисел; это может служить причиной для выбора небааьщих значений п.
Хороший компромисс будет достигнут, если взять п равным, скажем, 1 000 и вычислить достаточно много К~+сев для различных частей случайной последовательности. Тем самым получим значения (14) К1еое(1) К1эээ(2). К1эео(г). Затем можно применить КС-критерий снова к этим результатам. Пусть сейчас Р(х) — это функция распределения случайной величины К+ . Найдем эмпирическую функцию распределения Г„(х) для наблюдений случайной величины в (14). К счастью, функции Г(х) в этом случае имеет очень простой вид. Для больших щ таких, как я = 1000, функция распределения К+ примерно равна Е~(х) = 1 — е э', х > О.
(15) Данное замечание применимо к К„, поскольку К„' я К„имеют одно и то же ожидаемое поведение. Можно использовать КС-крятерий следующим образом: сначала критерий применяется несколько раз прн умеренно больших я, а затем наблкщеиня объединяют и снова применяют КС-критерий. Это позволяет обнаружить как локальные, так и глобальные отклонения от гнпотетического распрелачеипя.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
