Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 56
Текст из файла (страница 56)
Свой вклад в теорию внесли многие авторы — особенно Импаглиаззо (1шра818 азяо), Левин, Лаби (1пЬу) и Хастад (Наесай) [ЯТОС 21 (1989), 12-24; 22 (1990), 393- 404), которые показали, что псевдослучайные последовательности можно построить из любой однозначной функции. Однако такие результаты здесь не рассматриваются, так как они применяются, главным образом, в сложной абстрактной теории, а не в практическом генерировании случайных чисел.
Практическое применение теоретических работ к псевдослучайности впервые эмпирически исследовано в работе Р. 1 'Еспуег апд г(. Ргоп)х, Ргос. 11 )пгег Б?ши)абоп Сопб 22 (1989), 467-476. Если числа не случайны, го они пп крайней мере в полном беспорядке. — ДЖОРДЖ МАРСАЛЬЯ (ЙЕОйЕЕ МАРЕАЕ1 1А) (1984) УПРАЖНЕНИЯ 1. [10[ Может ля периодическая последовательность быть равнореспределенной? 2. [10) Рассмотрите периодическую двоичную последовательность 0,0, 1, 1, О, О, 1, 1, .... Она 1-, 2- илн 3-распределенная? 3. [Мйй) Постройте троичную периодическую З.распределенную последовательность. 4.
[НМЦ) Докажите, что Рг(Я(п) н Т(п)) + Рг(Я(а) нлн Т(п)) = Рг(Я(п) ) + Рг(Т(п) ) длв любых двух утверждений Я(п) и 2" (и), предполагая, что по крайней мере три из этих пределое существуют. Например, если последовательность 2-распределена, то можно найти, что Рг(и~ < Ц, < щ иля иг <??„+~ <»е) = »~ — м~ +»г — нг — (»~ — нг)(»т — кэ) 3. [НМ32) Пусть П„, = (21ММ" 01/3) пюд1. Чему равна Рг(Сь < 2~)? 6. [ЕМУ[ Пусть Я~(п), Яэ(п), ... — Еесконечнаа последовательность утверждений о совместных непересекающихся событиях, т, е, Я;(и) н Яг(п) не могут вмполняться одновременно, если 1?1?.
Предположим, что Рг(Я;(и)) существует для каждого у > 1. Покажите, что ЯЕ(Я)(п) выполняется для некоторого у > 1) > 2 .>д Рг(ЯГ(п)), и приведите пример, показывающий, что равенство может не выполняться. 7. [НМ2?) Пусть (Яо(п)) — семейство утеерэкдений, таких, что Рг(ЯЗ(п)) существует,зля всех 0? > 1. Предполаким, что для всех и > 0 Я;.(п) выпслнаетса дла точно одной пары целых чисел Еу. Если 2,3>,рг(ЯЕ(п)) = 1, то следует ли из этого, что "Рг(Я0 (и) выполняетсл для некоторого у > 1)" существует для всех 1 > 1 и равна Ез Рг(ЯЕ(п))? 3. [М13) Докажите (13). 9.
[НМ20] Докажите лемму Е. [Указание. Рассмотрите 2 .,(у;„— а)~,[ ь 10. [НМ32) Где в доказательстве теоремы С используется тот факт, что ш делит «? 11. [М?0) Применяя теорему С, докажите, что если последовательность ((?н) оо-распределена, то она яеляетса подпосладовательностью ((?ги). 12. [Над) Покажите, что й-распределенная последовательность удовлетворяет критерию "максимум-й" в следующем смысле: Рг(и < шах((?„, (? .~~,...,??»44-~) <») = » -в~. и 13. [ИЮ7] Покажите, что оо-распределенная [О., 1)-последовательность проходит критерий интервалов в следующем смысле: если 0 < а < )9 < 1 и р ж )7 — а, пусть /(0) = 0 и для и > 1 пусть /(и) — наименьшее целое число ш > /(» — 1), такое, что а < (),, < /), тогда Рг(/(п) — /(и — 1) = л) = р(1-р)" 14.
[7)МИ] Покажите, что со-распределенная последовательность проходит критерий мо- нотонности в следующем смысле: если /(0) = 0 и если для и > 1 /(и) — наименьшее целое число щ > /(и — 1), такое, что (7,» ) > П, тогда Рг(/(и) — /(и - Ц = й) = гй/(й+ 1) ! - 2(й+ Ц/(й+ г) !. ь = !(шапрг(!» » "»»» и й = )ип !п1~!(~). » ~»» а) Чем являются Х и ы для последовательности Ван дер Корпута (»ав ()ег Сотри!) (29)? Ь) Покаи(ите, что 1„+„, > 1„для 1 < й < и, Используйте атот результат для доказа(() (л) тельства того, что Ж > 1/!в2.
с) Докал(иге, что ж < 1/!в4. [Указание. Для каждого и существуют такие числа а(, ..., аг, что !с» > ! + „для 1 < й < 2((. Кроме того, кал(дое целое числа 2, ..., и (Й) (»+а») появляется самое большее дважды в (аь..., ас» ).] (!) Покажите, что последовательность (И'„), определенная равенспюм !1'„= !9(2п+ 1) шо(! 1, удовлетворяет 1/!п2 > и(('~ > и!(") > 1/!в4 для всех и. Следовательно, она достигает оптимальных значений ь и й. !' 16, [ЛМЯО] Покажите, что оо-распределенная последовательность проходит критерий собирания купонов, в котором существует только два вида купонов, в следующем смысле: пусть Х(, Хм — оо-распределенная двоичная последовательность, Пусть /(0) = 0 и для и > 1 пусть /(и) — наименьшее целое число и( > /(и — 1).
такое, что (Х)(„, е„..., Х является множеством (0,1). Докажите, что Рг(/(и) — /(и — 1) = й) = 2' для )с > 2 (см. упр. 7), 16. [77МУО] Вмполняется ли критерий собирания купонов для оо-распределенных последовательностей, когда существует больше двух видов кулонов? (См.
предыдущее упражнение.) 17. [ЯМАЛО] Для любого заданного рационального числа г ч ранкл(ш (Ргап)(йп) доказал, что последовательность (г" шоб 1) не является 2-распределенной. Но существует ли рациональное число г, для которого зта последовательность равнораспределена? Б частности. раинораспределеиа ли последовательность при т = 1? [См. К. Ма)г!ег, Маг))сша(Жа 4 (1957), 122-124.] ь 16. [ВМйй] Докажите, что если (?о, П(, ° ..
х-распределена., то такой же будет последовательность $о, (((, ..., где !'' = [п1)„]/и. 29. [1»МУб] Рассмотрите модификацию определения ВА, требуя, чтобы подпоследовательность была татько 1-распределенной, а не оо-распределенной. Существует лн последовательность, удовлетворяющая атому более слабому определению, которая не будет оо-распределенной? (Действительно ли зто щцжделение более слабое?) ь 20. [НМЮб] (Н.
Г.де Брейн (М. С. ()еВгш)п)и П. Эрдеш (Р. Ег()бе).) Первые п точек любой «О .. 1)-последовательности (()„) с ()о ж 0 делят интервал [О .. 1) на и пцлынтервалов. Пусть этн подь)итервалы имщот длины !( ) > !»(~) > . > !( ). Очевидно, что !( ) > ( > !( ), поскольку !") + +!» ) = 1. Одним из способов измерения равномерности распределении (П,) является рассмотрение пределов 21. [НМ40] (Л.
Г. Рамшоу (1 . Н. ВапщЬан).) а) Продолжаем предыдущее упражнение. Будет ли последовательность (И'и) равнораспределенау Ь) Покажите, что (И'и) является только [О .. Ц-последовательностью. ддя которой выполняется ~, 1пн~ < 10(1+ к/и) всякий раз, как только 1 < й < и. с) Пусть (~п(1~,...,1п)) — любая последовательность непрерывных функций на множествах строк размерности и ((1м...,1„) [ 11 » 1п и 1~ + . +1 = 1), удовлетворяющая следуя)щим двум свойствам: если ~ ",1, >2 «,1,'для 1<О<я, то („(1м...,1п)>у (1[,...,1'„). [Примеры: п(~01; — п(пы1; 1~АЦ/1~И~; п(1~дм+ +1~"П).[ Пусть 7 = 1пп вар уп(1~Ц,...,1Ы1) и -и пп для последовательности (И'и).
Покажите, что уп(1~~1,...,11п1) < гп для всех и относительно (Ип), а также 1ппэпр уп(111, .,1~"~) > г относительно каждой другой [О .. Ц-последовательности. ь 22. [Н)ЮО[ (Герман Вейль (Негщапп Юеу)).) Покажите, что [О.. Ц-последовательность (Уп) я-распределена тогда и только тогда, когда 1нп — ~~~ ехр(2я((съем + ° +се(1 +ь-1)) = 0 1 о«л для каждого множества не всех равных нулю целых чисел см сг,, сь. 23. [жуй) (а) Покажите, что [О..Ц-последовательность (П,) Ь-распределена тогда и только тогда, когда все последовательности ((с~ В + сзУпщ + +сЮп+ь-~) щоб 1) 1рас пределены всякий раз, когда см см ..., сь — целые числа, не все равные нулю.
(Ь) Покажите, что Ь-ичная последовательность (Х„) й-распределена тогда и только тогда, когда все последовательности ((с1Хп +сзХ„+~ + +сьХ„+ь 1) щодЬ) 1-распределены всякий раз . когда см см ..., сь — целые числа с йсб(см..., сь) = 1. ь 24. [МИ] (Й. Г, Ван дер Корпут (Л. С. иап бег Сограс).) (а) Докажите, что [О .. Ц-последовательность (У ) равнораспределена всегда, когда последовательности ((У еь— Уп) щод 1) равнораспределены для всех Ь > О. (Ь) Следовательно, ((олпе + + а1п + оо) щоб Ц равнораспределена, когда О > 0 н ак — иррациональные числа, 25. [НМОО) Последовательность называется белой, если все сериальные коэффициенты корреляции равны нулю, т..е, если соотношение в следствии Я выполняется для всея Й > 1.
(Согласно следствию Я оо-распределенная последовательность является белой.) Покажите, что если [О .. Ц-последовательность равнорагпределена, то она белая тогда и только тогда, когда йщ ~~, ' (Н, — 1)((1,~,— '-,) =0 для всех й >1. 1 и ОФп о<з<п 26. [НМЯ4[ (Дж. Франклин (Л, РгапЫш).) Белая последовательность, определенная в предыдущем упражнении, может не быть случайной. Пусть Уо, Ум ...
— со-распределенная последовательность. Определим последовательность 1ге, К, ... следующим образом: Яп — 1,1тп) = (Угп-1,Узп)~ если (12п-1 (1зп) Е С, ()тп-Мвтп) = ((1гп,(1зп-1), если Кг -1,11зп) б б, где ст — множество ((,р) [* — -', <р< илия+ <3). Покажите, что (а) последовательность )те, $'а, ... равнораспределенная н белая, (Ь) Рг(1'„> Ът еа ) = ф. (Это Указывает на слабость кРитеРиЯ «еРиальной коРРелЯцни.) 27. [НЩЗ] Чему равно нанбслыпее возможное значение для Рг(И > К,+а) в равно- распределенной белой последовательности? (Д. Копперсмнт (П.
СоррегешйЬ) построил такую последовательность, для которой зто значение достигает -.) т ь 23. [НМ31] Воспользуйтесь последовательностью (11), чтобы построить 3-распределен- ную [О .. 1)-последовательность, для которой Рг(Уа > а ) = йа, 20 [НМУ(] Пусть Хо, Ха..... — (2Й)-распределенная двоичная последовательность. По- кажите, что Рг(Ха =О) < 2+ ( ь )/2ы. а 30. [МЯУ] Постройте (20)-распределенную двоичную последовательность, для которой Рг(Ха„ж О) = — + ~ )/2ы. (Таким образом., неравенство в предыдущем упражнении является наилучшим.) 31. [МЗО] Покажите, что существуют [О ..
1)-последовательности, удовлетворяющие апре. делению Вб, однако я„/и > 1 дчя всех я > О, где ат„— число у < и, для которых Уч < а (Это можно рассматривать как неслучайное свойство последовательности.) 32. [ЛЩ] Задана (Х ) 'случайная" Ь-ичввя последовательность, удовлетворяющая определению Вб, и Н вЂ” 'исчисляемое правило подпоследовательности, точно задающее бесконечную подпоследовательность (Х„)Н.
Покажите, что последняя подпоследовательность не только 1-распределена, но и "случайна" согласно определению Вл. ЗЗ. [НМЗЗ] Пусть (У,„) и (Ьты ) — бесконечные непересекающиеся подпоследовательности последовательности (У ). (Иначе говоря, го < га < га < и 'ее < эа < аа < возрастающие последовательности целых чисел и г„те эч для любых т, и.) Предположим, что (1ты) — комбинированная подпоследовательность, такая, что ге < Фа < га < ° ., и положим (1„) = (а;,) О (э„).
Покажите, что если Рг(Ь,„Е А) = Рг(Ьы б А) = Р, то Рг(Ьты б А) =Р. ь 34. [М35] Определите правила подпоследовательностей йа, йа, аса, ..., такие, что с этими правилами можно использовать алгоритм Ж, чтобы задать эффективный алгоритм построения [О .. 1)-последовательности, удовлетворяющей определению В1. ь Зб.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
