AOP_Tom2 (1021737), страница 8
Текст из файла (страница 8)
1 при и = 1с — 1. 'Если 1' меньше 1%-й точки или больше 99%-й точки, отбрасываем эти числа как недостаточно случайные. (Если быть более точными, то отбрасываем следующую гипотезу: вероятности того, что наблюдения относятся к категории з, равны р,. — Прим. ред.) Если 1" лежит между 1%- и 5%-й точками или между 95%- н 99%-й точками, то эти числа оподозрительны": если (интерполируя таблицу) 1' лежит между 5%- н 10%-0 точками или 90%- и 95%-й точками, числа можно считать "почти подозрительными". Проверка по Хз-критерию часто производится три раза (и более) с разными данными. Если по крайней мере два из трех результатов оказываются подозрительными, то числа рассматриваются как недостаточно случайные.
Например, на рис. 2 схематично показаны результаты применения пяти различных типов Хз-критерия для каждой из шести последовательностей случайных чисел. Каждой проверке подвергались три различных блока чисел последовательности. Генератор А — это метод Мак-Ларена-Марсалья (Мас1агеп-Магэаб)1а) (алгоритм 3.2.2М, примененный к последовательности в 3.2.2 — (13)). Генератор Š— это метод х=е х=1 х=1 (Ь) (а) (с) Рис.
8. Примеры функций распределения. Фибоначчи (Р1Ьопасс1), 3.2.2 — (5), а другие генераторы — это линейные конгруэнт- ные последовательности со следующими параметрами. Ха = О, а = 3141592653, с = 2718281829 гп = 2ээ Хо=О а 2т+1 с=1 гп 2зэ Хе —— 47594118, а = 23, с = О, гп = 10э + 1. Хэ = 314159265 а 21в + 1 с = 1, пз 2зь Генератор В: Генератор С: Генератор ЬЬ Генератор Е В. Критерий Колмогорова-Смирнова, Как мы уже видели, Хэ-критерий применяется в ситуациях, когда наблюдения могут относиться только к конечному числу категорий. Однако совершенно небесполезно рассматривать случайные аеличины, которые принимают бесконечное множество значений, такие как случайные дроби (случайные действительные числа между О и 1). Хоти только конечное множество Из рис. 2 заключаем, что (как следует из результатов проверки) генераторы А, В, 0 удовлетворительны, генератор С находится на границе и его следовало бы отбросить, генераторы В и Р, безусловно, неудовлетворительны.
Генератор Р имеет, конечно, низкий потенциал; генераторы С и В уже обсуждались в литературе, но их множители слишком малы. (Генератор 0 — оригинальный мультипликативный генератор, предложенный Лехмером. (ЬеЬшег) в 1948 году; генератор С вЂ” оригинальный линейный конгруэнтный генератор с с ф О, предложенный Ротенбергом (Во1епЬег8) в 1960 году.) Вместо терминов "подозрительный", "почти подозрительный" и т. д.
для описания результатов применения Х'-критерия можно, кстатли, использовать процедуру, обсуждаемую ниже в этом разделе. действительных чисел может быть представлено в компьютере, мы хотим, чтобы они вели себя подобно реальным числам в интервале [О .. 1). В теории вероятностей и математической статистике одни и те же обозначения используются, когда случайная величина принимает конечное либо бесконечное число значений. Чтобы задать распределение значений случайной величины Х, следует сделать это в терминах функции распределения Г(х), где Г(х) = Рг(Х < х) = вероятности, что (Х < х). На рис. 3 приведены три примера.
Сначала (рис. 3, (а)) представлена функция распределения случаиного двоичного разряда, когда Х принимает только значения 0 и 1, каждое с вероятностью г1. Затем (рис. 3, (Ь)) показана функция распределения равномерно распределенных случайных действитпельных чисел, лежащих между 0 и 1. Здесь вероятность того, что Х < х, просто равна х, когда 0 < х < 1. Например, вероятность, что Х < г, равна, естественно, г.
И наконец, на рис. 3, (с) представлено предельное распределение случайной величины $' в Хг-критерии (здесь приведен случай с 10 степенями свободы). Это распределение в другом виде приводилось в табл. 1. Заметим, что Г(х) всегда возрастает от 0 до 1, когда х возрастает от — со до +со. Если выполнить и независимых наблюдений случайной величины Х и получить значения Лм Хг,...,Х„, то можно будет построить эмпирическую функцию распределения Г„(х), где число Хм Хг,...,Х„, таких, что они < х Г„(х)— На рис. 4 показаны трн эмпирические функции распределения (они изображены зигзагообразными линиями, хотя, строго говоря, вертикальные линии не являются частью графика Г„(х)).
На них наложены графики предполагаемых настоящих функций распределения Г(х). Когда и становится больше, Г„(х) более точно приближает Г(х). Критерий Колмогорова-Смирнова (КС-критерий) может использоваться, когда функция Г(х) непрерывна (не имеет скачков).
Он основан на разности меэкду Г(х) и Г„(х). Плохой источник случайных чисел (автор имеет в виду источник случайных чисел, распределение которых не соответствует требуемому. — Прим. ред.) будет давать такую эмпирическую функцию, которая плохо приближает предполагаемую функцию распределения Г(х). На рис. 4, (Ь) приведен пример случайной величины, для которой почти все Л; расположены слишком высоко, а это приводит к тому, что эмпирическая функция распределения находится слишком низко.
На рис. 4, (с) приведен еще худший пример. Ясно, что такое большое расхождение между Г„(х) и Г(х) совершенно невероятно, и КС-критерий может только показать, насколько именно. Чтобы построить КС-критерий, образуем такие статистики: К~ = ~/и щах (Г„(х) — Г(х)); К„= фь щах (Г(х) — Г„(х)) . 5% 25%50% 75% 95% 99% (Ь) 5% 25%50% 75% 95% 99% (с) Рис. 4. Примеры эмпирических распределений. 5% 25%50% 75% 95% 99% Здесь К„определяет наибольшее из отклонений, когда Е„больше Е, а ʄ— Г„ меньше Е. Эти статистики для примеров, приведенных на рис.
4, таковы. Рис. 4, (Ь) Рис. 4, (с) 0.134 0.313 1.027 2.101 Рис. 4, (а) К20 0.492 Ь'2о 0 536 (12) (Замечание. Множитель 5/и, который появляется в формуле (11), на первый взгляд, сбивает с толку. В упр. 6 показано, что для фиксированного х стандартное отклонение ги(х) пропорционально 1/,/й; следовательно, множитель 5/й увеличивает статистики К„+ и К„таким образом, что это стандартное отклонение ие зависит от п.) Точно так же, как и для ~2-критерия, можно сравнить значения К„' и К„с процентной таблицей и определить, будут ли они значимо выше или ниже. Табл. 2 можно использовать одновременно для К,+, и К . Например, вероятность, что К20 < 0.7975, равна 75% (автор имеет в виду здесь и далее, что вероятность равна 0.75.— Прим.
ред.). Отличие от 7~2-критерия состоит в том, что в таблице представлены не просто приближенные значения, которые справедливы для достаточно больших п; табл. 2 дает точные значения (за исключением, конечно, ошибки округления), и КС-критерий может надежно использоваться для любого значения и. Формулы (11) в том виде, в котором они записаны, не совсем подходят для вычислений на компьютере, так как формально нужно находить максимум по бесконечному множеству значений х. Но, учитывая тот факт, что Е(х) возрастает, и Таблица 2 НЕКОТОРЫЕ ПРОЦЕНТНЫЕ ТОЧКИ РАСПРЕДЕЛЕНИЙ К» И К„ р = 95% О.
9500 р = 99% 0.9900 р=50% 0.5000 р=1% р = 5% р=25% р = 75% 0.2500 и=1 0.01000 0.05000 0.7500 О. 5176 0.7071 0.01400 0.06749 0 01699 0.07919 1.0980 1 2728 0.2929 1.1017 1.3589 0.3112 О. 5147 0.7539 0.01943 0.08789 1.1304 1.3777 0.5110 О. 7642 0.3202 1.1392 1.4024 0.02152 0.09471 0.5245 0.7674 0 3249 О.
7703 1.4144 0.02336 0.1002 0.02501 О 1048 1.1463 0.3272 О. 5319 1.4246 0.5364 0.7755 1.1537 0.3280 1.4327 0.02650 0.1086 1 1586 0.3280 0.5392 О. 7797 1.4388 0.02786 О.ПН9 О. 7825 1. 1624 0.3274 О. 5411 и =10 1.4440 0.02912 0.1147 0.03028 0.1172 1.1658 0.5426 О. 7845 0.3297 1.1688 и = 11 1.4484 0.3330 0.5439 О. 7863 0.3357 и = 12 0.03137 0.1193 1.4521 0.7880 1,1714 0.5453 1.4606 и = 15 1.1773 0.5500 0.7926 0.03424 0.1244 0.3412 и = 20 и= 30 0.03807 0.1298 0.04354 0.1351 0.7975 1.
1839 1 4698 0.3461 0.5547 1.4801 0.8036 1.1916 0.3509 0.5605 рв — -'и Нз+ 0(1/и), где рр — — 11п(1/(1 — р)) и > 30 0.07089 0.1601 0.3793 0.5887 0,8326 1.2239 1.5174 Дли ресширеиии этой таблицы воспользуйтесь формулами (25) и (26), в также ответом к упр. 20. К+ = з/и пзах ( — — Г(ХЗ)); 1 — 11 К„= з/и тпах (Г(ХЗ) — — ). Выбрать подходящее число наблюдений и немного легче для этога критерия, чем для Х~-критерия, хотя некоторые из рассуждений похожи. Егчи случайные то, что Ео(х) возрастают только в конечном множестве точек, можно предложить простую процедуру для подсчета статистик Ке и К,, Шаг 1. Получить независимые наблюдения Хм Хэ,..., Х„. Шаг 2.
Упорядочить наблюдения так, чтобы они располагались в порядке воз- растания (построить вариационный ряд); Хэ < Хз « Х„. (Эффективный алгоритм сортяровки приведен в главе 5. Но в этом случае сортировки можно иЗбежать,как показано в упр. 23.) Шаг 3. Нужные статистики сейчас задаются формулами величины Х действительно имеют вероятностное распределение С(х), в то время как предполагается, что они имеют распределение, определяемое функцией г (х), и должно быть сравнительно болыпим для того, чтобы отбросить гипотезу о равенстве С(х) = Е(х).
Для этого и должно быть настолько большим, чтобы ожидаемые эмпирические функции распределевия С„(х) и Г„(х) заметно различались. С другой стороны, болыпие значения и приводят к усреднению локального неслучайного поведения, и такое нежелательное поведение приводит к значительным неприятностям в большинстве компьютерных применений случайных чисел; это может служить причииой для выбора небольших значений и. Хороший компромисс будет достигнут, если взять и равным, скажем, 1 000 и вычислить достаточно много К,+еэе для различных частей случайной последовательности. Тем самым получим значения (14) Кйюо(1) ~Сове(2) Кроо(г). Затеи можно применить КС-критерий снова к эппьи результатам.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
