Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 23
Текст из файла (страница 23)
Средние значения должны быть псдсчитаньг как среднее по множеству всех и! перестановок. Равенства (12) и (13) показывают, что можно выразить в терминах средних значений Яр, и Яр; Я„, поэтому сначала получим слелующнй результат (предполагая, что ( < 2): у ф+А1 1, если 1 < и — р+ 1; 0 в других случаях, (р+бр )Ч если ! + р < ( < и — д+ 1! (14) (р+ 1))(д+ 1)!' р+бц р+д+др1 О 1 т7 ~х'- в других случаях Суммирование ( ) производится по всем возможным перестановкам. Для иллюстрации вычислений рассмотрим наиболее трудный случай, когда !+р = у < и — у+1, а 1 > 1.
Величина Яр;Яру Равна либо нулю, либо единице, поэтому суммирование сводится к подсчету числа перестановок УгУз... 6'„, для которых Яр, = Ятз = 1, т. е. всех таких перестановок, что С; >(г;« "(1 >С; «" и; +-. (15) Еолнчество таких перестановок может быть подсчитано следующим образом.
Су- ществует ( +"+,) возможностей выбора элементов для положения, изображенного в (15), существует 1)(Р+й) (Р+й+1) ~Р+й+1) „ теап(Вр) = (и+ 1)р/(р+ 1)! — (р — 1)/р), 1 < р < и; сотаг(Вр, Вр) = теап(Вр В ) — теэлЯ,) теап(Вр) 1 —, ') Яр;Яэз — теап(Вр) теапЩ 1<изб<а теап(В!) + у(р, е, и), если р+ е < и, гпеап(В„') — теап(В') гпеап(В'), если р+ е > и, способов их расположения в таком порядке, как в (15) (см. упр. 13), и существует (и — р- у — 1)! способов упорядочения оставшихся элементов.
Следовательно, выражение в (16) нужно умножить на ( + +,) (и — р — е — 1)! и разделить на и(, чтобы получить искомую формулу. Из соотношения (14) н несколько громоздких вычислений получим где 1 = п1ах(р, д), В = р+ д и 1' (1- ро)+ рб 28 1 /6-1'1 ~(".)=(--)~, 1)( )1-( 1)'. ~ — !/ + (вз — 8 — 2)рб — 82 — рздз + 1 (р + 1)((0 + 1)' (19) Это выражение для ковариации, к сожалению, является довольно сложным, но без него нельзя обойтись.
Из этих формул легко вычислить шеап(Вр) = шеап(В') — шеап(В,',+,), сотаг(Вр, В' ) = сотаг(В', В' ) — сотаг(Вр+„В' ), сотаг(Вр, Вв) = сотаг(Вр, Вц) — сотаг(Вр, В'+,). В работе 4ппа»л Ма»!». б»аз. 16 (1944), 165-165, Я, Вольфовиц (Л. %0Иои»12) показал, что величины В„ВЗ, ..., В, „В,' становятся нормально распределенными прн и -4 оо со средним и ковариацией, приведенными выше. Отсюда следует, что имеет место такой критерий серий, Если задана последовательность из и случайных чисел, то нужно подсчитать число серий Вр длиной р для 1 < р < 1, а также число серий В, 'длиной 3 нли больше.
Пусть Ф =В»-п»сап(В1), ..., Ф ! =В! 1-шеап(В» 1), (2) ь»» = В» — и!еэл(В»). Построим матрицу С ковариацнй В,', например С!з = сотвг(В1, Вз), в то время как См = соъаг(ВТ,В»). Когда» = 6, то С = пС! + Сг, ЗЫ945728ОО 2!34697 $448843200 -!4ОТ»79 21794$Т229:Ю 1818214400 7 1 !05!»ТЗТ5564жю !229$305Т 5! 794457Боо 4577441 10697266аЮ зз !Зо =7 ЗВО -$ 336 6Ъ 4900 ЗВТО -121 131440 вз ТВО -29 Тбо -11 2!О -41 !2096 В1 25920 41 18144 =7 ЗВО .2543 20!60 -989 ЗОБ5 5621В -100гвз !выею -!зоз 9072ОО -29 150 4032 3!9 20!60 2857 72576 !ОПТ 604800 4!З 64800 -5 ЗЗВ -989 20165 -21311 15Г4 400 -61369 19958400 -ТТВЗ 9979200 -П З19 20155 -58747 ВОТНЮ !ЗТОЗ 604800 239471 19958400 ее4э% -ВЗЗ 55460 -7159 362885 ~21 1 1ВЬЫОО вв6651 ЗВЫЕВОО 257699 239500800 -626М 259500800 -41 12096 2557 72576 руз 04 -22083Т 4435200 1ЦЕЕ~1 239500600 360985 2ЗВЗООЕОΠ— 13 5675 -!оше !ВЫ»ОО -ВЗЗВВ Гвв58405 -257699 2595обеоб 29674911 91 25920 101 Т7 604555 ЗЗ947! !9956400 1196401 259500800 7264857600 -121 18!440 -шоз 957555 -ТТВЗ в979205 -425!3 239500805 41 !ВЫ» 4!з ВВВОО 99799555 зйоззе зжООВОО если л > 12.
Сейчас образуем матрицу А = (аи), обратную к матрице С, н вычислим ~,„, 9~ф~асо Результат для больших л должен иметь приближенно Ф «д-распределение с 1 стеленими свободы. Матрица А, заданная ранее в (11), равняется матрице, обратной к С«, с точностью до пяти значащих цифр. Настоящая обратная матрица А равна л 'С, ~— л «С, 'СзС, ' + л эС, 'СоС1 ~С«С, ' — ., и это приводит к тому, что С, 'С«С, ~ очень приближенно равна -6С «.
Поэтому К ж Я~С, '9/(л — 6), Н. Критерий нмаксимум-Фн. Обозначим 11 — — шах(ОО, Уц+ы ° ПО+1-1) оля О < у < и. Применим критерий Колмогорова-Смирнова к последовательности Ц, 1'м ..., 1'„м Таким образом проверим гипотезу о том, что функция распределения 1) равна Р(х) = х', 0 < х < 1. Можно также применить критерий Колмогорова- Смирнова к последовательности Я, $,..., Ъ'„' м проверяя гипотезу о равномерном распределении. Для обоснования критерия необходимо показать, что функция распределения $~~ равна Г(х) = х".
Вероятность того, что шах(УыУз,...,Ц) < х, равна вероятности того, что одновременно У«( х, Уз < х, ..., С«< х, которая, в сваю очередь, равна произведению вероятностей У«< х при й = 1,..., 1, а именно — хх... х = х'. 1. Критерий конфликтов. хз-критерий можно применять только тогда, когда ненулевое число элементов ожидается в каждой категории. Но существует критерий другого вида, который можно использовать, когда число категорий намного больше числа наблюдений, Этот критерий имеет отношение к рандомизации — важному методу информационного поиска: он будет рассматриваться в разделе 6.4. Предположим, что имеется т урн, и поместим в них наудачу л шаров, причем гл намного больше л.
Большинство шаров попадет в пустые урны, но если шар попадет в урну, в которой уже содержится хотя бы один шар, то будем говорить, что произошел "конфликт". Критерий конфликтов подсчитывает число конфликтов, и генератор удавлегваряет этому критерию, если не возникает слишком много или слишком мало конфликтов.
Для определенности предположим, что т = 2ю н л = 2'~. Тогда в среднем на 64 урны лрнходится только один шар. Вероятность того, что в конкретную урну попадет ровно Й шаров, равна р« = (,",)т «(1 — т ')" ", поэтому среднее число конфликтов в урне равно (й — 1)р« = ~~~ йр« — ~р« —— — — 1 + ро. «21 «>о «>« Так как ро = (1 — т «)" = 1 — лт ' + (")т т — маленькое число, получим, что общее среднее число конфликтов во всех т урнах намного меньше лз/(2т) = 128.
(Истинное значение равно 127.33.) Критерий конфликтов можно использовать для того, чтобы оценивать генератор случайных чисел для строк больших размерностей. Например, когда т = 2«о н л = 214, можно проверять 20-мерную случайность генератора случайных чисел, положив л' = 2 и сформировав 20-мерный вектор $1 = (1«о~,1зозм, ",1тоо+ш) для 0 < у ( л.
Мы храним таблицу из т = 2зо двоичных разрядов для определения конфликтов и один двоичный разряд для каждого возможного значения координаты вектора 1',; на компьютере с 32 двоичными разрядами в слове это дает 2гэ слов. Сначала во все 2то двоичных разрядов таблицы занесем 0; затем для каждого Ъ', если в соответствующий двоичный разряд уже занесена 1, регистрируем конфликт, в противном случае заносим в двоичный разряд 1. Этот критерий можно использовать для размерности 10 при 4 = 4 и т.
д. Чтобы решить, проходит ли последовательность зто испытание, можно использовать следующую таблицу процентных точек, когда т = 2то н и = 2ы Конфликты < 101 108 119 126 134 145 153 С вероятностью .009 .043 .244 .476 .742 .946 .989 Для определения зтих вероятностей используется та же теория, что и для покер- критерия (5); вероятность, что произойдет с конфликтов, равна вероятности того, что будут заняты и — с урн, а именно т(т — 1)...
(т — п+ с+ 1) / п ть ( 1 Хотя т н и очень большие, не составляет труда вычислить зги вероятности, используя следующий метод. Алгоритм 8 (Процентные пючки длл критерия конфликтное). Пусть заданы т н и. Этот алгоритм определяет распределение числа конфликтов, происходящих, когда п шаров рассеиваются по т урнам. Для вычислений используется вспомогательная таблица А[0], А[Ц, ..., А[п] чисел с плавающей запятой; фактически А[/] будет не равным 0 только для .уо <,у <,~~ и /и — уо будет иметь порядок, не больший, чем )ойп, позтому их можно получить с использованием значительно меньшего объема памяти. 81.
[Инициализация.] Присвоить АЩ +- 0 для 0 < у < и; затем присвоить А[Ц < — 1 и уо +- у~ +- 1. Повторить шаг 82 ровно п — 1 раз и перейти к шагу 83. 82. [Корректировка вероятностей.] (Этот шаг соответствует бросанию шара в урну; А[Я вЂ” вероятность того, что заняты точно / урн.) Присвоить /н е- Ь + 1. Затем для у +- уд,.(1 — 1, ..., 1о (в таком порядке) присвоить А[у] +- (1/т)АЦ+ ((1+ 1/т) О/т)]А[2 — Ц. Если А[у] стало очень малым в результате вычислений, скажем, А[у] < 10 ю, присвоить А[Я +- 0; в таком случае уменьшить /1 на 1, если т = З~, или увеличить 1о на 1, если 1 =,1о 83. [Вычисление отвега.] На атом шаге будет использоваться вспомогательная таблица (Тм Тп..., Т,мм,) = (.01, .05, .25, .50, .75, .95, .99, 1.00), содержащая точно определенные интересующие нас процентные точки.
Присвоить р ~- О, 1+- 1 н ,~' (- уо — 1. Выполнять следующие итерации, пока не будет достигнут 1 = гшах: увеличить ~ на 1 и присвоить р е- р+ А[Я. Затем, если р > Т„выход и — 7' — 1 и 1 — р (имеется в виду, что с вероятностью 1 — р существует по крайней мере п — 1' — 1 конфликтов); иначе — увеличиваем 1 на 1 до тех пор,. пока р < Ть ! Л.
Критерий промежутков между днями рождений. Джордж Марсалья в 1984 году ввел новый критерий. Поместим п шаров в т урн, как и в критерии конфликтов, но под урнами подразумеваем дни года, а под шарами — дни рождения. Предположим, что Щ,..., У„) — ото дни рождения, где 0 < 1ь < т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
