Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 26
Текст из файла (страница 26)
Пусть также Я„ы (У„+ У„+„) озодИ, где г выбрано наудачу между 0 и Л' — 1. Покажите, что (Я„) удовлетворяет Г-мерному критерию серий по крайней мере так же, как (У,), в следующем смысле, Пусть Р(хм... „х») н (И(зц..., я») — вероятности того, что бмерная строка (хм..., х») появляется в (Уь) и (Я„): 24. [НМ65] (Дж. Марсалья (О. Масеаб>(в).) Покажите, что критерий серий для и пересекающихся 1-мерных строк (Ус, Уз,, Ус), (Уз, Уз,..., Ус+>),, (У», У < >, ., Ус+»->) мо" жег быть осуществлен слелуюшнм образом.
Для калсдой цепочки а = ас ... а, с О < ас < д полсхкнм >>((о) равным числу случаев, когда и появляется как надцепочка У>, Уз,..., У», У»+>,...,У»+ с, и пусть Р(п) = Р(а>)... Р(а ) — вероятность того, что а появляетск в любом заданном положении. Разные цифры могут появляться с различными вероятностями Р(О), Р(1),..., Р(6 — 1). Подсчитаем статистику Уж-Š— -- Е— 1 >7(п) 1 >>>(а) и Р(о) и Р(п) ' Тогда У должно иметь >(з-распределение с сзс — с(с ' степенями свободы, когда и большое. [Указание. Используйте упр.
3.3.1-35.] 25. [М(6] Почему выполняется приближенное равенство С, 'С>С, ' ш -бС> ', где Сс и Сз — матрицы, определенные в (32)7 2б. [НМ60[ Пусть 5>с, 5(з, ..., 5> независимы и равномерно распределеыы в [О., 1) и пусть С(п < Ссз> « " 5>(,> — их значения после сортировки. Определите разности Я> »гс(з>-»гс(с>,..., Я -с = 5>(„>-С( и, Я = (>(с>+1-5(„> ирассортируйтеихЯ(м « ° . Я(„>, как в критерии промежутков между днями рождений. В следующих вычислениях удобно использовать обозначение х» в качестве сокращенной записи выражения х" [х > О[. в) Пусть даны любые действителъные числа в>, вз, ..., в„.
Докажите, что вероятность того что нера>сев<так Я» < в> н Яз В вз . ° . Я» ~ в» выполняются одновременно~ равна (1 — вс — вз — — в»)~ Ь) Докажите, следовательно, что наименьшая разыосгь Я(,> будет < в с вероятностью 1 — (1 — кв)" с) Какова функция распределения Рз(в) Рг(Я(з» < в) для 1 < /с < пу с() Вычислите среднее и днсперскю каждого Я(з>, ь 27. [НМ66] (Нтерпраеа»с»сме равности.) В обозначениях предыду»(его упражнения пока- жите, что числа Яс = пЯ(с р Яз = (и — 1)(Я(з> — Я(О)г .., Я„' = 1(Я(„> — Я(„,>) имеют то же самое совместное вероятиостиое распределение, что н первоначальные разности Я>, Я„н равномерно распределенных случайных величин.
Можно упорядочить их в виде Я(,> « . Я(„> и повторить зто преобразование, чтобы получить еще одно множество случайных разностей Я,,..., Я'„ы т, д. Каждое последующее множество разностей Я, (з> Я„может быть также проверено по критерию Колмогорова-Смирнова, где (з> К„с = ~1 шах (с — — Я, — - Я з (ю,, (з>> ><3<»'сп — 1 К„:> = »сп — 1 шзл (1Яс»+ "+ Я с (з (ю,> — 1Ъ >~~<»'с ' з п-1 Детально проверьте преобразование (Яс, '..., Я„) в (Я'„..., Яс„) для и 2 и и = 3.
Объясните, почему постоянное повторение зтого процесса в конечыом счете приведет к неудаче, если его применять к компьютерному генератору чисел с ограниченной точностью. (Один из методов сравнения генераторов случайных чисел оютоит в наблюдении, как долго они проживут при таких мучительных испытаниях.) 2й. [М66] Пусть Ь„,(т) — число и-мерных строк (ус,...,й») с О < уз < т, имеющих точно г равных разностей и в нулевьпс разностей. Таким образом, еероятыость того, что Н = г, в критерии промежутков меясду диямн рождений равна ~," Ь»г»(т)/т". Такзке пусть р (т) — число разбиений т на не более чем и частей (упр.
5.1.1-15). (а) Выразите Ь„еа(сп) в терминах разбиений. [Указание. Рассмотрите случай с малыми т и и.] (Ь) покажите, что существует простое соотношение между Ь,(го) и ьы-,к,»~- ю(тп) когда в > О. (с) Выведите точную формулу вероятности того, что разности равны. 29. [М85] Продолжая упр. 28, найдите простое выражение для производящих функций Ь~,(г) = ~~~»о Ь, е(н») з /гп, когда г ю О, 1 и 2. 30. [ля<41] Продолжая предыдущее упражнение, декан»нте, что если и» = из/а, то в-1 в/4 1.(гл) = ™(„1), (1 13пз 169а~ + 201баз — 1728а — 41472а з ) 288п 165888п» У = (о»У -) +о»1 -з+ +о»У -») шоб2 длк некоторого набора ап ..., а» с периодом длиной 2 — 1. Начнем со значений Уо = 1 » и У~ = . = У» ~ = О. Пусть Я„= (-1)""+~ = 2У вЂ” 1 — случайный знак.
Рассмотрим статистику Я, = Я, + Я +~ + + 3„» м где и — случайная точка в периоде. а) Докажите, что Е Я = и»/7»', где К = 2" — 1. Ь) Чему равно Е Я~,7 Предположите, что и» < йг. [Указание. См. упр, 3.2.2-16.] с) Чему равнялись бы ЕЯ и ЕЯ», будь Е действительно цчучайнымиу и) Предполагая, что н» < Х, докажите равенство ЕЯ = и» /Х -6В(Ж+ Ц/1»', где В = ~~~ [(У„~У»з...
У,„.»,)з = (УзчлУ»»г... У»»»-1)з](щ — 1). о<~<1<т ,зля фиксированного а при и -+ со. Найдите аналогичную формулу для 9 (т) — числа разбиений и» на и различных положительных частей. Выведите с точностью до 0(1/и) асимптотнческие вероятности того,что в критерии промежутков между днями рождений В равно О, 1 и 2. ъ 31. [МЖ] Рекуррентиое соотношение У„= (У„ы+У„»») щоб 2, описывающее млад~пий значимый разряд генератора Фибоначчи с запаздыванием 3.2.2-(7), как н второй младший значащий разряд $.2.2 — (7'), как нзвестио, имеет период длиной 2»» — 1; следовательно, каждая возможная не равная нулю конфигурация двоичных разрядов (У„, У + и, У„»»») появляется одинаково часто.
Тем не л»енес докажите, что если генерировать 79 последовательных двоичных разрядов У„,...,У„+за, начиная со случайной точки в периоде, вероятность, что там будет больше единиц, чем нулей, больше 61%. Есаи использовать такие двоичные разряды для определения "случайного блуждания", состоящего в том, что точка движется впрыю, когда двоичный разряд содержит 1, и влево, когда двоичный разряд содержит О, то в большинстве случаев будем заканчивать блуждание справа от нашей начальной точки. [Указание.
Найдите производящую функцию 2»» Рг(У» + ° . + У+те = Ь) з .] 33. [МЯО] Определите, верно ли следующее: если Х и У вЂ” независимые одинаково распределеншае случайные величины со средним 0 н если для нях более вероятно быть положительными, чем отрицательными, то Х + У более вероятно будет положительнмм, чем отрицательным. 33.
[»7М33] Найдите асимптотическое значение вероятности того, что Ь + 1 последовательнмх двоичных разрядов, генерируемых рекуррентным соотношением У„= (У„-~ + У -») щи 2, имеют болыпе единиц, чем нулей, когда Ь > 21 н длина периода втой рекуррентной последовательности равна 2» — 1. Предполагается, что Ь большое.
34. [НМ89] Объясните, как оценить среднее и дисперсию числа двухбуквенных комбинаций, не появляющихся последовательно в случайной строке длиной и в тн-буквенном алфавите, Предположим, что и» болыпое и и щ 2тиз. ь 35. [ЛМУ8] (Дж. Н. Линдхолм (Л. Н, 1,щсОю1ш), 1968.) Предположим, что случайные двоичные разряды (У») генерируются с помощью рекуррентного соотношения е) Оцените В в частном случае, рассмотренном э упр. 31: т = 79 и 11 = (1' -и + у~-и) юолт. ~З.З.З.
Теоретические критерии Несмотря на то что каждый генератор случайных чисел можно проверить с помощью критериев, приведенных в предмцущем разделе, всегда лучше иметь априорный критерий, а именно — теоретический результат, с помощью которого можно заранее сказать, насколько хороши будут проверки генератора. Такие теоретические результаты помогают понять методы генерирования намного лучше, чем эмпириче. ские методы проб и ошибок. В этом разделе мы подробнее пзучим линейные конгруэктные последовательности.
Если можно предугадать результаты определенных проверок заранее, прежде чем генерировать случайные числа, то имеется больше возможностей должным образом выбрать а„т и с. Развитие теории такого типа весьма сложно, хотя достигнут определенный прогресс. Получены пока далекие от общих результаты для статистических критериев, которые можно применять к велим.и периодам.
Тем не менее статистические критерии приобретают смысл, когда они применяются ко всему периоду; например, критерий равномерности будет давать отличные результаты н без этого требования, но критерий серий, критерий интервалов, критерий перестановок, максимумкритерпй и другие можно плодотворно проанализировать на всем периоде, Такие исследования будут определять глобальную '"'неслучайность" последовательности, т. е. неправильное поведение очень больших выборок. Теория, которая будет здесь рассматриваться, вполне всеобъемлюща, однако она ие исключает необходимости проверять локальные "неслучайности" методами, приведенными в разделе 3,3.2. Действительно, любая проверка с использованием только коротких последовательностей очень сложна.
,Известно лишь несколько теоретических результатов, касающихся поведения линейной конгруэнтной последовательности на промежутке, меньшем, чем целый период (онн обсуждаются в конце раздела 3,3.4; см. также упр. 18). Начнем с доказательства простого авриорввга закона для наименее сложного случая — для критерия перестанонок. Суть нашей первой теоремы состоит в том, что для последовательности с большим потенцпалом примерно в половине случаев выполняется неравенство Х„+г < Х„, Теорема Р.
Пусть а, с и т образуют линейную конгрузнтную последовательность с максимальным периодом. Пусть 6 = а — 1 и а — наибольший общий делитель т и 6. Вероятность того, что Л'а+г < Х„, равна -' + г, где г = (2(сшей а) — 4)/2т; следовательно, (г~ < фйт. Доказательство, Для доказательства этой теоремы используются методы, интересные сами по себе. Сначала определим (2) г(х) = (ах + с) шод т. Таким образом, Х'„1~ = г(Х„) и теорема сводится к подсчету количества целых х, таких, что 0 < х < т, а г(х) < х, поскольку такое число встречается где-то в периоде.
Необходимо показать, что зто число равно т (т + 2(с той М) — И) . (3) Функция Г(х — е(х))/гц1 равна 1, когда х > е(х), н 0 — в противном случае. Следовательно, искомое число, которое мы хотим подсчитать, можно записать следующим образом: (4) (Вспомним, что (-у) = -(у) н Ь = а-1.) Такие суммы можно подсчитать, используя методы из у1гр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
