Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 65
Текст из файла (страница 65)
Для него случайные блуждания длиной 445 имеют 64% шансов закончиться справа от начальной точки. Это смещение пропадет только тогда, когда длина блужданий возрастет до половины периода (после чего, конечно, нули станут более вероятны, хотя в полком периоде будет недоставать одного нуля). 0.7 0.6 0.5 0.4 0.3 пт = 0 256 51 2 768 1024 1280 1536 1792 2047 Вероятности, что число 1 превосходит число О в свучайных наборах из ш чисел, когда У„м Ув-з 9 1'в и.
Техника отбрасывания Лювгера (ВйзсЬег) может использоватьсн для того, чтобы избежать смещения в сторону единиц (см, окончание раздела 3,2.2), Например, со смещениями 55 и 24 отклонений от случвйкости в наблюдениях за случайными блужданиями длиной 1001 нет, если генери1ювать числа группами по 165 и использовать только первые 55 чисел. 32. Нет, если они принимают значения (-1 — 2с, с — 2с, 1 — 2с) с соответствующими 2 2 вероятностями (1-с, с, -'). Тогда Х+1' ) 0 с вероятностью (1+с) < -', если с достаточно мало, (Таким образом, два игрока в гольф могут быть в среднем одинаково сильными, но один из них может с большей вероятностью выиграть один раунд, тогда как другой с большей вероятностью выиграет два раунда.
См. работу Т. М, Кавера (Т. М. Сотег, Ащег, Ясасмс1с)ал 43 (1989), 277-278), в которой обсуждаются подобные феномены.) ЗЗ. ПО СущЕСтну, НужНО раССМОтрстЬ (ЗЫ~' '11т]('+з)" Н(-'ХХЗ-)'/(1 — «). ПуСтЬ Гн = я — 21, и = 1 и требуемые коэффициенты равны у„'— ,. у св~ы —,,"',, где д(х) = нт1п(1хзс ) + ~, з.з п1в(-'хзс ) — (штз»= — ') 1вз. Удобно (и разумно) интегриронать вдоль пути з = е'", где с = 4/(нз+ Зп) и и = -1+ 0 для — оо < 1 < оо, Получим д(г'") = — си/2+ и/2+ сзснз + свсзиз + ., где св = с~тт~д(Ц/М = О(1), а также 1/(1 — есв) = =,„~ + 1 — Взсн/2!— Вынеся множители нз подынтегрального выражения и используя тот факт, что + /'~.' е" гт Яв = ф и з— ', /;,.' с' Гзизв 8н = (-1)" (2к — 1)(2к — 3)...
(1)К2хк, получаем асимптотическую формулу -'+ (2х) Ы~н(та+ Зн) ззт+ 0((из+ Зп) зтз), Если ш+Зп четно, то справедлива та же асимптотическая формула, поскольку мы даем одну половину коэффициента при 3~ "3"Рг единицам, а вторую — нулям. (этот коэффициент равен ( — )' . О(( -3п)-312).) 34. Число строк длиной и, не содержащих заданные двухбуквенные подстроки или пары подстрок, -- это коэффициенты при 2" в соответствующей производящей функции. Они могут быть записаны ввиде сееет" +0(1), где с и т мохгно разложить по степеням е = 1/еп. Слз чай 1 2 3 б б Исключение Производящая функция (1+3)/р(3) 1/(1 -газ+32) (1 +3)/(р(в)+ ') (1 + )/(р(3)+ '+3") , (1+ )/(1 +2 2 3) 1/(1-тз+232) т Е +Е 24 +'' З 34 Е 24 + 2 З 4 22+23 34+, — 24 +Š— 74 + 2 3 4 -24 +Е -бе + г 3 4 -24 -бе + 2 4 с 1+ег -243+ 1+42+344+...
1+2 г 4з+ 1+24 — 24 +. 1+242 — 2ез+ 1+24 +1244+. -. оа аЬ аа, ЬЬ аа, Ьс аЬ, Ьс оЬ, с41 (Здесь а, Ь, с, б обозначают буквы н р(з) = 1 — (из — 1)(з + 32). Оказывается, что эффект исключении (аЬ,Ьа) или (аа,аЬ) эквивалентен исключению (аа,ЬЬ); исключение (аЬ,ас) эквивалентно исключению (аь,с«1).) пусть 5429 — коэффициент при 3" в случае,г и пусть Х вЂ” общее число двухбуквенных комбинаций, которые не появляются, Тогда ЕХ = (т501+ тай)/т" и Е Х' = (тВ»ц ~ + тй(ЮГ' + ОВ»щ~) + 2т~А" + ВЙ ~ + Мю) + тзбещ)/т".
33. (а) ЕЯ, = 37 42~ 'Е. 'Е„+1 - -Ж ЕЕ гкал 4Я„4., = дг ЕЕ 41 = тулу (ь) пусть б* = о4»" ' + . + а». Определим линейную функцию /, как и в первом ответе к УпР. 3.2.2.16. Тогда 1< ж /(б"), а отсюда следУет, что У +, + уе+г = /(» ) + /(б"е') щ /(б"43 + б"+1) = /(Е"а) (по людулю 2), где а не равно нулю, когда 3 ~ у (по 2~ ~, Я„' Я„) <я — т(т — 1)/44". ( ) Е~ ",' „' Я„~, = ~ 1 ' ЕЕ<~, — — 0 и Е(~, 'Я ~,)' = ~ е ~'~„;"„~ ЕЕ + 3~4г = с г=е ео +1+2 а«4«, (ел»е Ие<геэг) = еп, когда каждое ж, действительно случайно.
Таким образом, среднее и дисперсия Я очень близки к истинным значениям, когда из С ЕЧГ. (4() Е Вз = »7 ' Г»=э' те =о' Е™:о' Е» оо Е 4.»Ее»ЕЕ ег. Если любые Ь, 4 и У равны, сумма по и равна 1; следовательно, Ф-1 ее = —,1 —. ~ б т 3 е„,е д ). о<»«1<я =е Так же, как и в (Ь), покажем, что сумма по и равна 1, если б" + б'+ б' Ф 0; иначе она равна — 1е'. Таким образом, Еб~, = пзз-бВ(13'+1)/г»', где В = 2 „,.
(б»+б'+бг =О) = 2 3«<1<, (1+ б + б' = 0) (т — у) Наконец заметим, что 1+ С = бг тогда н только тогда, когда /(34+') = /Кз+') для 0 < 1 < ь. предполагаем, что О < 4 < у < 1у. (е) Для 4 = 31 и / =- 35 появляются только ненулевые члены; значит, В = 79 — 35 = 24. (Следующий ненулевой член появится, когда з = б2 и у = 110.) В настоящей случайной ситуации Е Яэ должно быть равно О, так что значение Е Ягзэ ж — 144 определенно говорит о неслучайности. Любопытно, что это значение отрицательное, хотя в упр.
31 показано, что Вщ обычно лололснтельное. Значение Ягз стремится быть основательно отрицательным, когда оно оказывается ниже О. Дипмратврра. 1ЕЯЕ 2гавз. 1Т-14 (1968), 569-576. М. Ма»вищо1о авб У. Кит!се„АСМ Тгапа Мо<)е1!пб аит( Соптр. %щий 2 (1992), 179-194; 4 (1994), 254-266. М. Мацумото и Й. Курнта утверждают, что генераторы с троичным основанием не удовлетворяют таким критериям, проверяющим распределения, люке когда смещение достаточно большое. См. также работу АСМ Тгапз. Мот)е1тлб алт( Сощр.
Яппий 6 (1996), 99-106, в которой они демонстрируют длинную подпоследовательность низкой плотности. РАЗДЕЛ 3,3.3 1. 9((к/9)) + 19 — 1»95(к/9). 2. См. упр. 1.2.4-38 н 1.2.4-39(а, Ь, 8). 3. ((к)) = -2 „>! — „т„зщ2кпк, ряд сходится для всех к. (Представление в (24) моткно рассматривать как "конечнмй" ряд Фурье в случае, когда к рационально.) 4. 4 , ж 2'» 5. Заметим, что неравенство Х .»! < Х„ имеет вероятность 8 + », где )т) < 4/(2 10 ) < 1/(2 ° 5»).
Следовательно, кансдмй генератор с потенциалом 10 приемлем с точки зрения теоремы Р. б. Промежуточный результат: Е к»(к) 1 пт с к' — — = — о(а, пт, с) + — — — — —. та пт 12 ' ' 4 2т 2вт' »5*<» 6. (а) Используйте индукцию и формулу ~(Ь/+с)) (~Ь/+с — 1)) 1 1 (Ь/+с) 1 (Ьу+с — 1) (Ь) Используйтетотфакт, что — (( — )) = -(( — — — /) = (( — /) — — +-5( — ). 7. Положите т = Ь, и = й, й = 2 во второй формуле упр.
1.2.4-45! ~(-";-((~кН-":-((-':))- )- (-:-((-":И ="— »<! <»»<!<в Суммы в левой части упрощаются, а после стандартных преобразований получим Ь Ьт й 1 Ь Ь 1 Ьтй — Ьй — — + — + — + — — -о(Ь, й,0) — -а(й, Ь, О) + — <т(1, й,0) = Ь"й — Ьй. 2 бй 12 4 6 ' ' 6 ' ' 12 Так как !т(1,й,0) = (й — 1)(й — 2)/й, зто приводит к закону взаимности.
8. См. работу Вийе Магй. У. 21 (1954), 391-397. 9. Начните с интересного тождества г-! р ! )йр/г)(йд/г)+ <1 )йд/р)(йг/р) +~ (йг/д)(йр/д( =(р-1)(д- Ц(г — 1), для дока»аз!в!встав которого можно применить простой геометрический метод, предполагая, что р .1. д, д 1 г и г 2.
р. См. работу У. Дитера (Г Втесег, АЬЬ. ша»Ь, Ящп. Сптг. На!пЬигб 21 (1957), 109-125). 10. Очевидно, что из (8) следует равенство !т(й — Ь, й, с) = -о(Ь,Ь, -с). Заменим у на й — у в определении (16), чтобы доказать равенство !т(Ь, й, с) = о (Ь, й, -с). 11. (а) ~~с (( — ))(( — )) = ~ (( — ))(( — )); используем (10) длясуммио<с<зь о<с<с о<с<о рования по с 12' Так как (( о )) принимает те же значения, что и ((со)) в другом порядке, неравенство Коши влечет неравенство сг(Ь,й,с) < о(Ьсй,0)т и а(1,Ь,О) может быть легко просумми- рована непосредственно (см. упр.
7). о«с<о если ЬЬ' ш 1 (по молулю й). 14. (2зз — 3 2ш + 5)/(2го — 1) 2 зз, Весьма удовлетворительное глобальное значение вопреки локальной неслучайности! 16. Замените сз в (19) иа (с))с). 16. По нилукции можно доказать, что тождество, приведенное в указании, эквивалентно сп! = р,т,с.! + р„спс,+з для 1 < г < й (См, также упр. 4,3.3-32.) Теперь заменим с, иа 2,'„«„с Ь„ш,.~! и сравним коэффициенты при Ь,Ь в обеих частях тождества, которое необходимо доказать. Эозсочанве. Для всех показателей е > 1 аналогичные сообралсения дают с 'с' — с' с 1 ь (с - с.
(-1)" " = — ' Е (-1) "Ь,ь:-5' ')рз, с<1<с ш! шсс. ! пс! !<!5! ' с! — сзо! 17. В этом алгоритме выполняются равенства й = ш-, Ь = со!+!, с = сс, р = рс-с, р' = р! з, з = (-1)'+! лля 1 = 1, 2,,, с + 1. Р1. [Инициализация.) Присвоить А с — О, В с — Ь, р+- 1, р' +- О, з +- 1, Р2.
(Деление.) Присвоить а +- (й/Ь), Ь +- (с/Ь), г с- с шос1 Ь. (Теперь а = ас, Ь = Ь, и г = с!.!.!.) РЗ. (Накапливание.) Присвоить А +- А+ (а -6Ь)з, В с- В+6Ьр(с+ г)з. Если г ф 0 или с = О, присвоить А+- А — Зз. Если Ь = 1, присвоить В+- В+рз. (Здесь вычитаем Зе(шс+с, сс) и такске принимаем во внимание члены 2„(-1)с сы/т! я!у+!,) Р4. (Подготовка к следующей итерации.] Присвоить с +- г, з +- -з; присвоить г сй — аЬ, й +- Ь, Ь +- г; присвоить г +- ар+ р, р' +- р, р +- г. Если Ь > О, возвратиться к шагу Р2. По окончании работы этого алгоритма р будет равно истинному значению йо вели- чины й, так что требуемый ответ — А + В/р.
Окончательное значение р' будет равно Ь', если з < О, иначе р' будет равна йо — Ь', Хорошо было бы, чтобы В благодаря подходящей корректировке А не выходило из области 0 < В < йо. Поэтому используются только операции с обычной точностью (с двойной точностью выполняются умножение и деление), если йо — - число, заданное с обычной точностью. 16. Можно намек шльно увидеть, что формула Б(1с,й,с,з) =2.„1, (Нй) — ((у — з)/й))(((Ьу+с)/й)) определена для всех з > 0 не только тогда, когда й > з. Записав (у/й) — ((У вЂ” з)/й) = —,', -Ь ((1 — ')) — (Я)) + 13;о — 1о(с=„-'-) и выполнив суммирование, получим Я(Ь,й,с,з) = — ((-)) + — а(Ь,й,йз+с) — — сг(й,й,с) + -((-)) — -(( — ))., где со = стоб «(.
Общая сумма будет составлять около -', когда В малб и когда все дроби а/гл, (а~ пюс) гл)/т, (аЬ пюб т)/т, Ь/т, (а' — 1)/т, (а'(а' — 1) пюд т)/т, ((аИ) пюб ел)/т имеют малые частичные отношения. (Заметим, что а' — 1 щ — 6+ Ь вЂ”, как в упр. 3.2.1.3-7.) 21. Сначала заметим, что основной интеграл точно разлагаегся следующим образом: Г" ' 1 «1 В пх и — В е„= /«х(ах+В)дх ж — ~- — -+-«1, если х„= —; аз~3 2 2 а Г' Го 1 В а — 1 Вз о= / х[ах+В)Их=во+о«+ ° +о, «+/ (ах+В)дх= — — — + — + —. -8«а За 2а 4а 2а П, у С=(.-(-',)з)/(,-'-(«)') =(1-ОВ+ОВ')/.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
