Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 17
Текст из файла (страница 17)
Поэтому нужно считать, что число степеней свободы равно Й вЂ” 1. Эти аргументы не строги, но они подтверждаются теоретически.) Если в таблице выбрать число х, стоящее на юй строке и в столбце р, то "вероятность того, что значение Ъ' а (8) будет меныпе либо равно х, приближенно равна р, если и достаточно велика". Например, 95-процентное значение в строке 10 равно 18.31; значения, такие, что Г > 18.31, будут появляться приблизительно в 5% случаев. Допустим, что наш эксперимент с бросанием игральных костей был промоделироваи на компьютере с помощью некоторой последовательности чисел, предположительно случайных, со следующими результатами. Значениеэ= 2 3 4 5 б 7 8 9 10 11 12 Эксперимент 1, г', = 4 10 10 13 20 18 18 11 13 14 13 (9) Эксперимент 2, 1; = 3 7 11 15 19 24 21 17 13 9 5 Можно подсчитать ул-статистику в первом случае, $~~ = 29 ьэе, и во втором случае, 1з = 1;$.
Сравнивая эти величины со значениями таблиши при 10 степенях свободы, мы видим, что 1"~ намного больше„1' будет больше 23.21 только в 1% случаев! (Используя более полные таблицы, можно обнаружить, что 1' будет так же велико, квк и 1'м только в 0.1% случаев.) Поэтому эксперимент 1 демонстрирует значительное отклонение от случайного поведения. (Автор часто употребляет термин "отклонение от случайного поведения*' и подобные ему термины в том смысле, что наблюдаемые реализации случайной величины маловероятны прн предполагаемом распределении этой случайной величины.
— Прим. ред.) С другой стороны, $~з достаточно малб, так как наблюдаемые значения У, в эксперименте 2 достаточно близки к ожидаемым значениям пр, в (2), Из Хт-таблицы на самом деле ясно, что 1'в слишкам малб. Наблюдаемые значения настолько близки к ожидаемым, что нельзя рассматривать результаты как случайные! (В самом деле, если воспользоваться другими таблицами, можно увидеть, что такие маленькие значения Г встречаются только в 0.03% случаев, когда имеем ~з-распределение с 10 степенями свободы.) Наконец, значение $ = 74~э, полученное в (5), также Таблица 1 НЕКОТОРЫЕ ПРОПЕНТНЫЕ ТОЧКИ ХЯ-РАСПРЕДЕЛЕНИЯ ряк 1% р = 99% р=5% р=25% р= 50% р = 75% р = 95% О.ОООР6 0.00393 0.1015 1.323 3.841 0.4549 0.02010 0.1026 9.210 0.5754 2.773 5.991 0.1148 11.34 0.3518 1.213 7.815 и=4 0.2971 13.28 0.7107 1.923 5.385 1.1455 0.5543 Н.07 15.09 4.351 и=6 12.59 16.81 0.8721 7.841 1;239 2.167 18.48 4.255 и=а 1.646 20.09 2.733 5.071 10.22 7.344 2.088 16.92 21.67 5.899 8.343 11.39 и=10 2.558 23.21 3.940 18.31 9.342 24.72 и= 11 3.0$3 7.584 13.70 и = 12 3.571 5.226 26.22 8.438 11.34 14.85 21.03 11.04 и = 1о о.229 7.261 14.34 18.25 8.260 и = 20 37.57 15.45 23,83 31.41 18.49 14.95 43.77 24,48 76,1о 29.71 и = 50 42.94 56.33 67.50 и+ уйиикг+ -,'я' — 1, + 0(1/,/й) и> 30 -2.33 -1.64 —.674 0.00 0.674 1 64 Другие змачеммя мшкио имети в кмиге Непдьоо)г ог Мкгйешкг)се1 Ропснояе, вышедшей под ре- дпкпией йе Абрамовича (йе Аьгкпюиия) и и.
А. стегум (1. А. агейпп) (гчеяь1пйгоп, В.сл 0,9, Оогегпшепг Рнпппй,ОКке, 1964); ткбл. 26.6. См. также (22) и упр. 16. может быть проверено по табл. 1. Око находится между 25- и 50-процентной точками, поэтому рассматривать это значение как значимо большое либо значимо малое нельзя. Таким образом, наблюдения в (2) являются удовлетворительна случайными па отйошению к этому критерию. (Имеется в виду, что данные не опровергают гипотезу о распределении этой случайной величины. — Прим.
ред.) В некоторой степени замечательно, что для использования таблиц не имеет значения, чему равны и и вероятность р,. Только число и = й — 1 влияет на результаты. Следует отметить, однако, что значения табл. 1 — это только приближенные значения: дело в том, что в ней приведены зпачеппя ут-распределения, которое является предельным распределением случайной величины )г в формуле (6). Поэтому табличные значения близки к реальным только при больших и. Насколько болыпими должны быть п? Эмпирическое правило гласит: нужно взять и настолько большим, чтобы все значения величин пр, были больше или равны пяти.
Однако лучше брать существенно большие и, чтобы получить более надежный критерий. В приведенном выше примере и = 144, прз равнялось только 4 и эмпирическое правило было нарушено. Это объясняется только тем, что автору просто надоело бросать игральные кости; это привело к тому, что значения табл.
1 оказались менее подходящими. Эксперимент, проведенный на компьютере при и = 1000 или 10 000, или даже 100 000, был бы намного лучше рассмотренного нами. Мы могли также объединить данные при э = 2 н в = 12; этот критерий имел бы только 9 степеней свободы, но аппроксимация Хз была бы более точной. Можно пояснить, насколько груба аппроксимация, если рассмотреть случай только двух категорий, имеющих вероятности р~ и рз.
Предположим, р~ = 1 и рз = з. В соответствии со сформулированным эмпирическим правилом необходимо провести более двадцати наблюдений, и. > 20, чтобы иметь удовлетворительную точность. Давайте это проверим. Когда и = 20, возможные значения $~ будут такими: (У~ — 5)т/5+ (5 — 1'~)з/15 = Дгт для -5 < г < 15. Теперь посмотрим, насколько точно в первой строке (» = 1) табл. 1 описывается распределение Г ~~-распределение непрерывно, в то время как распределение 1' имеет довольно большие скачки, поэтому нужно сделать несколько замечаний, прежде чем представить точное распределение, Если различные возможные исходы эксперимента приводят к величинам 1'е < Ъ~ < ° < 1"„с соответствующими вероятностями яе, хм ..., х„, то предположим, что заданная вероятность р попадает в интервал хэ+ ° ° +к~-~ < р < во+" + ну з +хз.
Найдем такУю "пРоцентнУю точкУ" х, где $' меньше х с веРоЯтностью < р и 1т больше х с вероятностью < 1 — р. Нетрудно видеть, что существует только одно такое число, а именно — х = 1",. В нашем примере лдя и = 20 и и = 1 оказывается, что процентные точки для точного распределения, соответственно аппроксимации в табл.
1 для р ж 1%, 5%, 25%, 50%, 75%, 95% н 99%, равны О, О, .27, .27, 1.07, 4.27, 6.67 (с точностью до двух десятичных знаков). Например, процентная точка для р = 95% равна 4.27„тогда как приближенное значение в табл. 1 равно 3.641, что существенно меньше. Поэтому, если пользоваться таблицей, следует отнести значение Г = 4.27 за 95%-й уровень, на самом же деле вероятность того, что Ъ' > 4.27, болыпе 6.5%. Когда и = 21, ситуацю1 меняется мало, поскольку средние значения прг = 5.25 и прт = 15.75 могут никогда не достигаться точно. Процентные точки для и = 21 равны ,02, .02,,14, .40, 1.29, 3.57, 5.73.
Можно было бы ожидать, что значения из табл. 1 дадут лучшее приближение прн и = оО, но соответствующая таблица, оказывается, в некоторых аспектах еще больше отличается от табл. 1, чем при п = 20: .03, .03, .03, .67, 1.31, 3.23, 6. Приведем значения при и = 300: О, О, .07, .44, 1.44, 4, 6.42. Даже в этом случае, когда пр, > 75 для каждой категории, значения в табл. 1 хороши только относительно одной значащей цифры.
Вопрос о правильном выборе п достаточно сложен. Если игральные кости действительно несимметричны, то это будет проявляться все больше н больше прн л в с О Е р Обозначение Диапазон й Указание Отбросить Подозрительный Почти подозрительный 0-1%, 99-100% 1-0%, 90-99% 0-10%, 90 — 99% Рис. 2. Ъказании "значимости" отклонении Хз-критерия при Ь = 90 (см. также рис. 5). возрастании и (см.
упр. 12). Но при больших значениях и имеет место тенденция к сглаживанию локального неслучайного поведения, когда блока чисел со строгим смещением следуют за блоками чисел с противоположным смещением. При реальном бросании игральных костей сглаживания локального неслучайного поведения можно не опасаться, так как одни и те же игральные кости используются во время всего эксперимента, но последовательность случайных чисел, генерируемых компьютером„может очень часто демонстрировать такие аномалии, Возможно, х~- критерий следовало бы применять для нескольких разных значений и.
Во всяком случае, значения и должны быть по возможности большими. Теперь можно окончательно описать %1-критерий следующим образом. Выполняется достаточно большое число и независимых наблюдений. (Важно избегать использования Хз-критерия при зависимых наблюдениях. См., например, унр. 10, в котором рассмотрен случай, когда одна половина наблюдений зависит от другой.) Подсчитываем число наблюдений, относящихся к каждой из /с категорий, и величину 'т', приведенную в формулах (б) и (5).
Затем Ъ' сравниваем с числами из табл. 1 при и = Й вЂ” 1. Если Ъ' меньше 1%-й точки нли больше 99% й точки, отбрасываем зтн числа как недостаточно случайные. (Если быть более точными, то отбрасываем следующую гипотезу: вероятности того, что наблюдения относятся к категории з, равны р,. — Прим. ред.) Если 1' лежит между 1%- и 5%-й точками или между 95%- и 99%-й точками, то зти числа "подозрительны"; если (интерполируя таблицу) Г лежит между 5%- и 10%-й точками или 90%- и 95%-й точками, числа можно считать "почти подозрительными". Проверка яо уз-критерию часто производится три раза (и более) с разными данными.
Если по крайней мере два из трех результатов оказываются подозрительными, то числа рассматриваются как недостаточно случайные. Например, на рис. 2 схематично показаны результаты применения пяти различных типов ~з-критерия для иезидой из шести последовательностей случайных чисел. Каждой проверке подвергались три различных блока чисел последовательности. Генератор А — это метод Мак-Ларена-Марсалья (Мас1,агап-Магзай!!а) (алгоритм 3.2.2М, примененный к последовательности в 3.2.2-(13)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
