AOP_Tom2 (1021737), страница 13
Текст из файла (страница 13)
Значительно более простой и более практичный критерий монотонности приведен в упр. 14, так что читатель, интересующийся только проверкой генераторов случайных чисел, может пропустить несколько страниц И перейти к критерию "максимум-гь после выполнения этого упражнения. С другой стороны, с математической точки зрения поучительно увидеть, как можно изучить сложный критерий монотонности со взаимно независимыми сериями. Так что на некоторое время мы отклонимся в сторону. Пусть задана перестановка и элементов. Пусть Яр, — — 1, если положение 1 яиляется началом возрастающей серии длиной р или больше, и пусть Яр1 = О в других случаях. Например, .рассмотрим перестановку (9) с и = 10.
Легко видеть, что являющуюся мерой зависимости Вр и Вэ. Средние значения должны быть подсчнтаньг как среднее по множеству всех и! перестановок. Равенства (12) н (13) показывают, что можно выразить в терминах средних значений Ур,. и Яр, Ею, поэтому сначала получим следующий результат (предполагая, что 1 < у): 1 ч~-. р+ 5п если 1 < и — р + 1; и! — — (р+ 1)!' О в других случаях. (р+ 5п)д (р + 1)'(д + 1)" р + А1 р + д + 811 — если 1+ р = у < и — д + 1; О в других случаях. если (+ р < у < и — д+ 1; (14) Суммирование (2,) производится по всем возможным перестановкам.
Для иллюстрации вычислений рассмотрим наиболее трудный случай, когда 1+р = у < и — д+1, а 1 > 1. Величина Ер,Е равна либо нулю, либо единице, поэтому суммирование сводится к подсчету числа перестановок Уг5Гз... У„, для которых Ярг — — Ету = 1, т. е. всех таких перестановок, что (15) и; >и;« ° и;„- >Цр« . Ц„ Количество таких перестановок может быть подсчитано следующим образом. Существует ( "„,) возможностей выбора элементов для положения, изображенного ряд-~-1 в (15), существует )/р+ д~ /р+ д+1~ /р+ д+1~ (15) теап(Вр) = (и + 1)р/(р+ 1)! — (р — 1)/р!, 1 < р < и; сотаг(В„', В') = теап(В„'В') — теап(Вр) теап(В') — ЕрДе, — теап(В'„) теап(В,',) 1<51<и теап(В,')+ /(р,д,и), если р+ д < п, теап(В,') — теап(Вр) теав(В',), если р+ д > и, способов нх расположения в таком порядке, как в (15) (см.
упр. 13), и существует (и — р — д — 1)! способов упорядочения оставшихся элементов. Следовательно, выражение в (16) нужно умножить на ( ",,)(и — р — д — 1)! и разделить на и!, чтобы получить искомую формулу. Из соотношения (14) и несколько громоздких вычислений получим где ! = пгох(р, д), 8 = р + д и + (эг —  — 2)ро — 82 — ргдг + 1 (р + 1)!(4 + 1)! (19) Это выражение для ковариации, к сожалению, является довольно сложным, но без него нельзя обойтись. Из этих формул легко вычислить пгеап(Л„) = щеап(Л~„) — щевл(Л~ 1), сота!(Лр, Л ) = сотаг(Л~,Л~) — сота!(Л' 1, В~), сотаг(Лр, Ве) = сота!(ЛЩ Л~) — сота!(Вр, ВВ+! ).
(20) В работе Аппо!з Май. абак 16 (1944), 163-166, Я. Вольфовиц (д. %011о87!!2) помазал, что величины Л1, Лг, ..., Л! 1, Л! становятся нормально распределенными при и -4 оо со средним и ковариацией, приведенными выше. Отсюда следует, что имеет место такой критерий серий. Если задана последовательность из и случайных чисел, то нужно подсчитать число серий Лр длиной р для 1 < р < 8, а также число серий В,' длиной 1 или больше. Пусть 4.11 — — Л! — Щеап(Л!), ..., 4:21 1 = Я4 1 — теап(Я! !), (21) 6)! = Л! — и!сап(Л',).
ПостРоим матРицУ С коваРиаций Л', напРнмеР С!э —— сота!(Л1, Яз), в то вРемЯ как Сп — — сотаг(Я„В!). Когда 8 = 6, то (22) С = пС! + Сг, где 23 180 -7 Зба ги945728оо 21:!4697 5448643200 -ыатпе 2!794572800 1816214400 7264867600 10897286400 457784! †1229530 10897286400 21Т94572800 Эзб — 4ЗЗ 60480 -!з 5670 — 121 !8144О ВЗ !Эо -29 18О -и 210 -41 иове 91 25920 41 !ВЫ4 -7 360 28 !З гарба -989 20180 -Т!59 збгзза -ШО19 1вы4оа -1ЗОЗ 907200 -29 !Эо -305 4032 ЗГЭ 20160 2557 725ТО !оит 804800 413 64ВОО -5 ззб -Ебе 20160 5456З 907200 -г!зп 1814400 -62369 19958400 -ТТВЗ 99Т9200 — и 210 319 20160 -58747 907200 ГОТОЗ 804600 ЭЗ9471 ЩЫ84ОО ЗОЫТ 9979200 -433 60480 -7159 Э62880 †213 !Вы4оа 886657 39916800 -257699 239500800 -62611 239500800 — 41 12096 2557 725Тб ГОТОЗ бо4вао -2208ЗТ 4435209 1Щ6401 239500800 ЗВООВЭ 239500800 -15 5670 -1ООГВ 1814400 †623 19958400 — гзжое 239500800 29874ВП 9! 25920 1а!Тт бо48ао 2394Т1 19958400 П96401 2395ООВОО -139128839 -12! 181440 -!зоз ООТЭОО -7783 9979гоо -626П 239500800 — 14ОТ179 41 18144 41З 648оо ЗОИТ 9979200 Э60989 ЭЗВЭООВОО 457Т641 если и > 12.
Сейчас образуем матрицу А = (а; ), обратную к матрице С, и вычислим ~,1 г Щ,фа,э. Результат для больших п должен иметь приближенно гг-распределение с с степенями свободы. Матрица А, заданная ранее в (11), равняется матрице, обратной к Сы с точностью до пяти значащих цифр. Настоящая обратная матрица .4 равна и 'С, '— и Сг СгСг + и Сг 'СгСг СгСг ' —, и зто приводит к тому, что С, ~СгСг г очень приближенно равна -6С '.
Поэтому 1: - Я~С, 'Ц/(и — 6). Н. Критерий имаксимум-Фв. Обозначим 1гу = шах(Сгг,(/Оэ.ы...,У,гэ.г г) для 0 < г < и. Применим критерий Колмогорова-Смирнова к последовательности )ге, 1'~,..., Ъ'„г. Таким образом проверим гипотезу о том, что функция распределения равна Г(х) = х', О < х < 1. Можно также применить критерий Колмогорова- СмиРнова к последовательности )гэг, 'ггг,..., )г„' „пРовеРЯЯ гипотезУ о РавномеРном распределении.
Для обоснования критерия необходимо показать, что функция распределения 1~ равна Е(х) = х'. Вероятность того, что шах((/г „Уг,..., Уг) < х, равна вероятности того, что одновременно У1 < х, Уг < х, ..., Уг < х, которая, в свою очередь, равна произведению вероятностей Уь < х при й = 1,..., г, а именно — - хх... х = х'. 1. Критерий конфликтов. г~г-критерий можно применять только тогда, когда ненулевое число элементов ожидается в каждой категории.
Но существует критерий другого вида, который можно использовать, когда число категорий намного больше числа наблюдений. Этот критерий имеет отношение к рандомизации — важному методу информационного поиска; он будет рассматриваться в разделе 6.4, Предположим, что имеется т урн, и поместим в них наудачу и шаров, причем т намного больше и. Большинство шаров попадет в пустые урны, но если шар попадет в урну, в которой уже содержится хотя бы один шар, то будем говорить, что произошел "конфликт". Критерий конфликтов подсчитывает число конфликтов, и генератор удовлетворяет этому критерию, если не возникает слишком много или слишком мало конфликтов.
Для определенности предположим, что т = 2тв и и = 2г4. Тогда в среднем на 64 урны приходится только одни шар. Вероятность того, что в конкретную урну попадет ровно Й шаров, равна рь —— (~~)т ~(1 — т ')" ь, поэтому среднее число конфликтов в урне равно и (й — 1)рь = ~~„йрь — ~~',Рь = — — 1+ Рэ т ей! ь>о ь>г Так хак Ре = (1 — т г)" = 1 — ти г + (")т г — маленькое число, полУчим, что общее среднее число конфликтов во всех т урнах намного меньше пг/(2т) = 128.
(Истинное значение равно 127.33.) Критерий конфликтов можно использовать для того, чтобы оценивать генератор случайных чисел для строк больших размерностей. Например, когда т = 2гэ и и = 2г4, можно проверять 20-мерную случайность генератора случайных чисел, положив И = 2 и сформировав 20-мерный вектоР гг = (1гог,1гоу -г,,1гогеш) для О < г < и.
Мы храним таблицу из т = 2ю двоичных разрядов для определения конфликтов и один двоичный разряд для каждого возможного значения координаты вектора 1г; на компьютере с 32 двоичными разрядами в слове это дает 2ш слов. Сначала во все 2»е двоичных разрядов таблицы занесем 0; затем для каждого», если в соответствующий двоичный разряд уже занесена 1, регистрируем конфликт, в противном случае заносим в двоичный разряд 1. Этот критерий можно использовать для размерности 10 при д = 4 и т. д. Чтобы решить, проходит ли последовательность это испытание„можно использовать следующую таблицу процентных точек, когда т = 2зе и н = 2ы Конфликты < 101 108 119 126 134 145 153 С вероятностью .009 .043 .244 .476 .742 .946 .989 Для определения этих вероятностей используется та же теория, что и для покер- критерия (5); вероятность,что произойдет с конфликтов, равна вероятности того, что будут заняты и — с урн, а именно п»(тп — 1)... (тп — п+ с+ 1) / и щи 1н — с) Хотя и» и п очень большие, не составляет труда вычислить эти вероятности, используя следующий метод.
Алгоритм Б (Процентные точки длл критерия конфлнкпюв). Пусть заданы ш н и. Этот алгоритм определяет распределение числа конфликтов, происходящих, когда и шаров рассеиваются по и» урнам. Для вычислений используется вспомогательная таблица А[0], А[Ц, ..., А[п] чисел с плавающей запятой; фактически А[Я будет не равным 0 только для уе < / < Я и Я вЂ” /е будет иметь порядок, не больший, чем )ой и, поэтому их можно получить с использованием значительно меньшею объема памяти. 91. [Инициализация.] Присвоить А[Я +- 0 для 0 < у < и; затем присвоить А[Ц»- 1 н уе» вЂ” Я» — 1. Повторить шаг 82 ровно и — 1 раз и перейти к шагу 83. 92. [Корректировка вероятностей.] (Этот шаг соответствует бросанию шара в урну; А[Я вЂ” вероятность того, что заняты точно з урн.) Присвоить Я» — Я + 1. Затем для у» — Я, Я вЂ” 1, ..., /е (в таком порядке) присвоить А[,1]»- (з/т)А[Я + [(1+ 1/гп) (у/гп))А[у — Ц.
Если А[Я стало очень малым в результате вычислений, скажем, А[у] < 10 те, присвоить А[Я» — 0; в таком случае уменьшить Я на 1, если у = у», или увеличить /о на 1, если ~' =/о 93. [Вычисление ответа.] На этом шаге будет использоваться вспомогательная таблица (Тм Тз,..., Тнььь) = (.01, .05, .25, .50, .75, .95, .99, 1.00), содержащая точно определенные интересующие нас процентные точки. Присвоить р» — О, »» — 1 и ~' »- /е — 1. Выполнять следующие итерации, пока не будет достигнут 1 = стах: увеличить у на 1 и присвоить р» — р+ А[у]. Затем, если р > Тм выход и — / — 1 и 1 — р (имеется в виду, что с вероятностью 1 — р существует по крайней мере и — 2' — 1 конфликтов); иначе — увеличиваем 1 на 1 до тех пор, пока р < Тв 1 Л. Критерий промежутков между днями рождений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
