AOP_Tom2 (1021737), страница 173
Текст из файла (страница 173)
д, Анализ становится все более и более сложным с удлинением блужданий. Интуитивно ясно, что преобладание единиц на первых 79 шавках будет продолжаться столько, сколько числовые подпосэедовательности умеренно колеблются между О и 1. Сопутствующая диаграмма показывает результаты более простого случая, а именно— использования генератора 1'„= (1'„г + У и) шос1 2, который можно легко проанализировать. Для него случайные блуждания длиной 445 имеют б4% шансов закончиться справа от начальной точки. Это смещение пропадет только тогда, когда длина блужданий возрастет до половины периода (после чего, конечно, нули станут более вероятны, хотя в полном периоде будет недоставать одного нуля).
0.7 0.6 0.5 0.4 0.3 т = 0 256 51 2 768 1024 1280 1536 1792 2047 Вероятноств, что чксло 1 превосходят число 0 в случайных наборах вз гп чисел, когда 1' = 1' — г 6 1' — и Техника отбрасывания Люшера (ВйэсЬег) может использоваться для того, чтобы избежать смещения в сторону единиц (см. окончание раздела 3.2.2). Например, со смещениями 55 и 24 отклонений от случайности в наблюдениях за случайными блужданиями длиной 1001 нет, если генерировать числа группами по 165 и использовать только первые 55 чисел.
32. Нет, если они принимают значения ( — 1 — 2с, с — 2с, 1 — 2е) с соответствующими 2 г вероятностями (-' — с, с, -'). Тогда Х+ г' > 0 с вероятностью (-'+е) < -', если с достаточно малб. [Таким образом, два игрока в гольф могут быть в среднем одинаково сильными, но один из них может с большей вероятностью выиграть один раунд, тогда как другой с большей вероятностью выиграет два раунда.
См, работу Т. 51. Кавера (Т. М. Согег, Ашег. ВгаВэг!с1ал 43 (1989), 277 — 278), в которой обсуждаются подобные феномены.] 33. По существу, нужно рассмотреть [гме' ПГг](1тгл)" г (-'гэз-)'/(1 — г). Пусть т = й — 21, и = 1 и требуемые коэффициенты равны — ', у еэ01 ~*,1, где д(г) = ел1п(-'хгэ) + 1 з'г п1п(-'-ф-) — ("'+з" ') !пг. Удобно (и разумно) интегрировать вдоль пути г = е'", где ег = 4/(т + Зп) и и = — 1 + Н для — со < Г < оо, Получим д(е'") = — ео/2-~- иг/2+ свао~ + сэагиг +, где сь = е~д~д(1)/lс! = 0(1), а также 1/(1 — е'") = =' + -' — Вгао/2!— Вынеся множители из подынтегрального выражения и используя тот факт, что — е" Ш ~„' = -' и — ', 1,"+' е" 7гп~" ди = ( — 1)" (2)г — 1)(2Й вЂ” 3)...
(1)з/2я, получаем асимптотическую формулу -' + (2х) ьып(ш+ Зп) эш + 0((гп+ Зп) зш). Если т+ Зп четно, то справедлива та же асимптотическав формула, поскольку мы даем одну половину КОэффнцИЕНта Прн 2<~4~"Ооз ЕдИНИцаМ, а ВтОруЮ вЂ” НуЛяМ. (ЭтОт КОЭффИцИЕНт раВЕН (,< '.,)' '+О((-- -Г"') ) 34. Число строк длиной и, не содержащих заданные двухбуквенные подстроки нли пары подстрок, — это коэффициенты при 2" в соответствующей производящей функции. Они зюгут быть записаны в виде се"'т" +0(1), где с и т можно разложить по степеням е = 1/пь Случай 1 2 3 4 5 б Исключение Производящая функции (1«- )/р( ) 1/(1 — тз+22) (1+ 3) /(р(2 ) + 22) (1+ )/(р(~)+~'+~') (1-<-2) /(1- тз+ 222 — 2 3) 1/(1- поз+22 ) 2" — е +е — — е +' 2 3 3 4 2 — Š— зс + 2 З 4 — 24 +22 — Ве + 2 3 4 — 2е +е — 7е + -2ез+ез -644+ -2е -бе + 4 с 1+е — 2е +'' 1+ез+Зе'+ 1+ 2< — 4ез+ 1+222 — 223+ 1+222 — 2ез+ 1+22 +122 + аа аЬ аа, ЬЬ аа, Ьс аЬ, Ьс аЬ, со( (Здесь а, Ь, с, 6 обозначают буквы и р(з) = 1 — (оп — 1)(2 + 22).
Оказывается, что эффект исключения (аЬ,Ьа) или (аа, аЬ) эквивалентен исключению (аа, ЬЬ); исключение (аЬ,ас) эквивалентно исключению (аЬ,со().) Пусть Бе<21 .-- коэффициент при 3" в случае 7 и пусть Х вЂ” общее число двухбуквенньох комбинаций, которые не появляются. Тогда ЕХ = (тоПО «- тзБ< ~)/т" и ЕЛ = (тяз< 1 «- опе(В<~о + 654<В) + 2опз(В<4< + 5<~< + В<~О) + тз В<еО)/т". н-о зз = — „~ — -+4 у' т'г...з.„г„.,). 3 1 < з з 0<з<о<о<т =е Так же, как и в (Ь), покажем что сумма по п равна 1, если С" «-5*+ 52 ОЕ 0; иначе она рав- на — Х. Таким образом. Ея~ = поз — 6В(оо<+1)/оо, где В = е„ойз<«(ь" + ь'+ зо =0) = е е<,«[1+6 + <~ =0) (оп — 7). Наконец заметим, что 1+ б' = бо тогда и только тогда, когда /(б'е~) = /(бо« ~) для 0 < 1 < Й.
Предполагаем, что 0 < о < 2 < <т. (е) Для < = 31 и / = 55 появляются только ненулевые члены; значит, В = 79 — 55 = 24. (Следующий ненулевой член появится, когда о = 62 и / = 110.) В настоящей случайной ситуации Е Я~, должно быть равно О, так что значение Е Я<33 — 144 определенно говорит о неслучайности Любопытно, что это значение отрицательное, хотя в упр.
31 показано, что Воз обычно полозосиопело нее. Значение Воз стремится быть основательно агряцазельным, когда оно оказывается ниже О, 36. (а) Еч, — Л,~ — Е -оŠ— о~ )У Е вЂ” оЕ ' — аВ <У- Š— 1 /Д. (<2) Пусть 3 = аоб ' + + аз. Определим линейную функцию /, как и в первом ответе к УпР. 3.2.2-16 Тогда У„= /(4"), а отсюда следУет, что 1~,~., + Е «.о — — /(с" ы) + /(с" ') = /(б" е' + б"+о) = /(б'а) (по модулю 2), где о не равно нулю, когда < ф / (по 2 Ее«р«, ., Е'„:е ~ ) = по — оп(оп — 1)/Х. (с)Е~'":е'У~«,— — ~, о'ЕЕео=ОиЕ(~, е'Я,.о) =~",.'„'~ ~',"„'Ег„«.,г„., = ез"'о Е т .оо + те„о« <, (Е т «-,)(Е Я «.„) = еп, когда каждое Я„действительно глучайно, Таким образом, среднее и дисперсия В очень близки к истинным значениям, когда гл « ооо.
(6) Е оз '= оо' ' 2 „„' 2 ",' ' 2 ~ „' 2 '~ е Я„„ЕЯ„е,Я„ео. Если любые Ь, 3 и у равны, сумма по и равна 1, следовательно, Литература. 1ЕЕЕ 71 апэ. 1Т-14 (1968), 569-576. М. Масеиптосо апс1 У. Кщтса, АСМ Тгатш. Мос1е!тпб алс1 Сотр. 56ти1. 2 (1992), 179-194; 4 (1994), 254-266. М. Мацумото н Й. Курита утверждают, что генераторы с троичным основанием не удовлетворяют таким критериям, проверяющим распределения, даже когда смещение достаточно большое. См. также работу АСМ Тгапе. Мос1е!тпб апд Сотр.
56ти!. 6 (1996), 99-106, в которой они демонстрируют длинную подпоследовательность низкой плотности РАЗДЕЛ З.З.З ри /р)) + 19 Ьдб(,/„) 2. См. упр. 1.24-38 и 1.2.4 — 39(а, Ь, 6). 3. ((х)) = — ~„„>, — „' сйп 2ттих, ряд сходится для всех х. (Представление в (24) можно рассматривать как "конечный" ряд Фурье в случае, когда х рационально.) 4. с1~ = 2'а 5. Заметим, что неравенство Х„ес ( Х имеет вероятность -'+ е, где )с( < с)/(2 10т ) < 1/(2 5э).
Следовательно, киаксйсй генератор с потенциалом 10 приемлем с точки зрения теоремы Р. 6. Промежуточный результат: Х. х а(х) 1 т с х — — = — ст(п, ти, с) + — — — —— та т 12 ' ' 4 2ит 2т а«* 6. (а) Используйте индукцию и формулу ((ЬЗ+с)) ((ЬЗ+с — 1)) 1 1 (Ьу+ с) 1 (Ьу+с — 1) (Ь) Используйте тот факт, что — (( — )) = — (( — — — )) = (( — )) — — +-д( — ). 7. Положите т = Ь, и = Ь, lс = 2 во второй формуле упр.
1.2.4-45: е(7-сс7к)(7-сс-"/))-~)" е(7-сй)) ~) = а<с<с а<с<а Суммы в левой части упрощаются, а после стандартных преобразований получим Ьз Ь 1 Ь 1с — ЬЬ вЂ” — + — + — + — — -а(Ь, Ь, О) — — п(Ь, Ь, О) + — п(1, Ь, О) = 5~Ь вЂ” ЬЬ. 2 6Ь 12 4 б ' ' 6 ' ' 12 Так как п(1,Й,О) = (Ь вЂ” 1)(Ь вЂ” 2)/Ь, это приводит к закону взаимности. 8. См. работу 77ийе МасЬ. Х 21 (1954), 391 †3. О. Начните с интересного тождества р — с — с у (Ьр/г) (Ьч/г) + ',7,(Ь9/р! (Ь /р) + Е(Ьт/Ч) (Ьр/Ч) = (р -1)(Ч - 1Н - 1), для доказательства которого можно применить простой геометрический метод, предполагая, что р .1.
9, д .1 г и г Л. р. См. работу У. Дитера (Г П(есег, АЬЬ. тасЬ. Еет. Пптф Наспбигб 21 (1957), 109-125). 10. Очевидно, что из (8) следует равенство ст(Ь вЂ” Ь, Ь, с) = — п(Ь, Ь, — с). Заменим т на Ь вЂ” у в определении (16), чтобы доказать равенство ст(Ь, Ь, с) = п(Ь, Ь, -с), 11. (а) Х ~(( — )) (( с)) = ) (( )) (( )); используем (10) для суммно«зь е«з о<1<э рования по 1 (Ь) (( И )) = И И )) + 23( ~„+'); сейчас суммируем. 12.
Так как (( ~+'-)) принимает те же значения, что и (Я)) в другом порядке, неравенство Каши влечет неравенство п(И, И, с) < п(И, И, 0)з и п(1, И, 0) может быть легко просумми- рована непосредственно (см. упр, 7). 13. п(И,И,с) ч- = — ~Х,, + -(сшобlс) — б(( — ]), И,'с о<1<« если ИИ ш 1 (по модулю И). 14.
(2«е — 3 . 2«е + 5)Д2«е — Ц ж 2 зз. Весьма удовлетворительное глобальное значение вопреки локальной неслучайности! 10. Замените с в (19) на (с](с]. 16. По индукции можно доказать, что тождество, приведенное в указании, эквивалентно ш1 = Р ш <-~ + Р -1гп е«для 1 < г < И (См. также упр. 4.5.3-32,) Теперь заменим с, на ~„'<„<, Ь,гп е1 и сравним коэффициенты при Ь,Ь1 в обеих частях тождества, которое необходимо доказать. Замечание. Для всех показателей е > 1 аналогичные соображеник дают (-ц'"' " = — ~ (-ц'-'ь,(" "")р,, т,ш,тг т1 ' с, — с;~1 "' э ! 1 г 17.
В этом алгоритме выполняются равенства И = ш;, И = ш,ем с = сз, р = р«м р рз-«, е = ( — цэ+' для 2 = 1, 2, ..., С + 1. 131. ]Инициализация.] Присвоить А+- О, В с — И, р+- 1, р' +- О, «е- 1 132. ]Деление.] Присвоить а +- (И/И], Ь < — (с/И], г е- с глоб И. (Теперь а = ам Ь = Ь, и г = с,еь) ПЗ. ]Накапливание.] Присвоить А е- А+(а — ОЬ)«, В е- В+ОЬР(с+г)«. Если г ~ О или с = О, присвоить А г- А — 3«. Если И = 1, присвоить В +- В+ре, (Здесь вычитаем Зе(т,~.це~) и также принимаем во внимание члены 1 (-Цг ю/гпзт, гп) О4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
