Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 63
Текст из файла (страница 63)
Производящая функция равна С(э) (рэ/(1 — (1 — р)э))", что имеет смысл, так как данное распределение является и-кратной 11. [1[2[9 8 б 3[6[7 0[4[. 12. Алгоритм 11 (Донные длл крнтерпл менотонностпи). К1. [Инициализация.] Присвоить у +- -1 и присвоить СООИТ[1[ +- СООИТ[2] +- +- СООИТ[6] +- О, Также присвоить (/„з- Ь."„1 для удобства по завершении работы алгоритма. 212.
[Присвоить г значение О.] Присвоить г +- О. ВЗ. [Будет ли (/з < ~ ~12] Увеличить г н / на 1. Если (,1 < (тьм повторить этот шэг. В4, [Регистрации длины.[ Если г > 6, увеличить СООИТ[6] на 1, иначе увеличить СООИТК иа 1. Кб. [Коневу] Если у < и — 1, вернуться к шагу К2. $ 13. Существует (р+д+1)(р~~) способов получении (Л 1 >< (Л < - < сзтр-~ < >б.+р < . < К+р+р-ь Вычтите (Р+т~') способов, в которых (Л 1 < 1/н в вычтите (Р+[+') рь! способов, в которых (/,,р 1 < Ктр.
Затем добавьте 1 длв способа, когда выполняются оба неравенства К 1 < У; и (/вьр 1 < Ц~.р, так как этот способ вычиталсв дважды. (Это частный случай принципа включения-исключения, который подробно рассматривается в разлеле 1.3.3.) 14. Серия длиной г встречается с веровтностью 1/г! — 1/(г + 1)Ь если предположить, что Ц различны. Поэтому используем р, = 1/г! — 1/(г+ 1)! длв г < 1 и р~ = 1/ — длв серий длиной > б 16, Это всегда верно длв Р(Л ), когда Р непрерывна и Л имеет распределение Р (см. жмечанне, следующее за формулой 3.3.1-(23)).
16. (а) Зп = шах(2~п О,УС+ПО ы). Если Я и м занесено в памвть, то достаточно просто преобразовать этот массив в множество Яп без использования дополнительной памвти. (Ь) В его "улучшении" каждое К, должно на самом деле иметь требуемое распределение, но наблюдении не явлвютсв независимымн при больших значениях 1гь. Действительно, когда (/1 — относительнО большая величина, то все Яп, л Пн ..., 20-нык будут равны (/1, так что возможен эффект повторении тех же данных 1 раз (У будет умножаться на 1, как в упр. 3.3.1-10).
17. (Ь) Согласно тождеству Бине (Вшет) разность равна 2,'о<ь«„(Цр'„— У,Тгь)~, » поэтому она неотрицательна, (с) Поэтому, если )р~ = Х~, получим (/ь1' — П'Ъ~ = О для всех пар у, Е (Угсюда следует, что матрица ((/о (/[ . (/ -) ) имеет ранг < 2, поэтому ее строки линейно зависимы. (Более элементарное доказательство можно получить, если учесть тот факт, что равенство По)' -У,' 'ге = О длк 1 < у < и влечет существование постоянных а, 6, таких, что аб"„' + ~П~' = 0 для всех у при условии, что Ц н Ъ~ — не нули; последний случай может быть исключен в результате перенумерации.) 18. (а) Числитель равен -((/е — (/1 ) э, знаменатель равен (По — 1Г1 )~ (Ь) Числитель в этом случае равен -(Пег + (/7+ (/тэ — (/о(/1 — (/~сгэ — ПэПе), а знаменатель — 2(Пот + .
— (гтПо), (с) Знаменатель всегда равен ~" ., „Я -Пь)э, что следует из упр. 1.2,3-30 или 1.2,3-31. 19. Сформулированный результат на свмом деле имеет место длв любого симметричного совместного распределеник (/о, ..., (/„~ (распределение не меняется при перестановхах). Пустая~ ж По+' +П -маг = По+" +Пэ м Х= Ьо~П1+ . +П -тК,-1+(/р-16оиП= пЯт — Ю~т. Также пусть Е/(Пе,, .., П ~) обозначает ожидаемое значение /(Пе,..., (/„-1) при условии, что 11 эе О.
Так как Р— симметричная функция, Е/((/о,...,(/н-1) = Е /((г' (о),..., У,„(„0) для всех перестановок р из (О,..., л — 1). Следовательно, Е 5з/В = лЕЦ)/В, ЕЯ/В = п(л — 1)Е(1)о(/(/В)+г(ЕПоз/В и ЕХ/В = лЕ(УоП)/В). Это влечет равенство 1 = Е (лЯз — з) )/В = -(и — Ц Е(пХ вЂ” л) )/В. (Строго говоря, Е Яз/В н Е Я('/В могут быть бесконечными„гюзтому необходимо позаботиться о том, чтобы можно было работать только с линейными комбинациями ожидаемых величин, которые, как известно, существуют.) 20. Пусть Еш), Езп, Еш, Ез) и Е» означают соотеегственно величины Е((/оУ) УгУз/Вз), Е(САП(Уг/Вз) ЕЯ~о(Г(/В~) Е(У~о(/г/В~) Е(((оо/В~) Тогда вмполняется Е9зз/Вз л(л — 1)Ею+ лЕ4, Е(ЕзЕ /В ) = л(л — 1)(л — 2)Ем) + л(л — 1)Ею + 2л(л — 1)Ез( + лЕы Е3(/В =л(л-1)(л — 2)(л-3)Е(ш+бг((л-1)(л-2)Ез))+Зл(л-1)Езз+4л(л-1)Ез(+лЕ4, ЕЛз/Вз = л(л-3)Е,)„+2лЕм)+лЕзз, Е(ХЯ/В~) = й(л — 2)(л — З)Еш)+бз)(л-2)Езп+ 2пЕш + 2лЕм, Е((Со — П) )~/В~) = 6Еы — 8Ез( + 2Е4, откуда следует первый результат.
Пусть 4 = а((!пг!)/л))гз, М = аз/2+ 1/3 н т = [1/4]. Если разделить область распределения на гл равиовероятных частей, то можно показать, что в каждой части содержится число точек, равное числу, лежал»ему между по(1-б) и г(8(1+о) с вероятностью > 1 — О(л ~). Для этого нужно испольэовать неравенства для хвктов 1.2.10-(24) и (25), Следовательно, если распределение равномерно, В = —,' пз(1+ О(д)), по крайней мере д')я этих вероятностей. Если В ие из втой области, то 0 < (Уо — (г()о/Вз < 1. Так Е((П (7 )4) /) /~( )~4 1 ) Е((1 фп-"(1+ О(4)) + О( — ). Замечание.
Пусть 7)) — числитель в (23). В. Дж. Диксон (%. 3. Ебхоп) доказал, что когда все переменные кмеют нормальное распределение, сокидаемое значение величины е" и+ли)Ш равно (! — зз — ! )' (! — ! + (! — 2))-4!) " + О( ). Дифференцируя по ш и интегрируя по з, ои нашел момезггы Е((з/В)з» ' = ( — -')"/(л — 1)1, Е((»)/В)з» .= (+-')"/(л+ -')»! когда л > 21.
В частности, дисперсия в этом случае точно равна 1/(л+ 1) — 1/(л — 1)з, [.4плаЬ о/МаЗЬ. угас. 16 (1944), 119-144.] 21. Последовательные значения с, г = з — 1 иа шаге Р2 равны 2, 3, 7, 6, 4, 2, 2, 1, О; следовательно, / = 886862. 22. 1024 =6!+2 3(+2 4(+2 3!+2 2!+О 1!, поэтому нужно, чтобы последовательные значения о — 1 на шаге Р2 были равны О, О, О, 1! 2, 2, 2, 2, О. Если теперь идти в обратном направлении, то получится перестановка (9, б, 5, 2, 3, 4, О, 1, 7, 8). 23, Пусть Р (х),...,х() = », 2 „:о [(У„',..., У„'»( () = (х),..., х()]. Тогда Ц(х(,..., х() = ~~1 Р'(у(,, у,)Р((х) — уз) шо»1(1, ..., (х! — у() шод»)) (ю," .п) или, более компактно, Ц(х) =- 2 Р'(у)Р(х — у).
Следовательно, используя общее неравенство (ЕХ)з < ЕХз. получим т4 М(х) — г ')з = Е (Е Р'(у)(Р(х — у) — (1 ()) < 2.,2.„~ '(у)(Р(*-у)- 1-')'=2:„Р(у)2:.(Р(х)-4-')'=2:.(Р( )-4-')'. [С . р б у С. Магза81(а, Сошр. Ясг1 апг( Язаз(зо)сз( Яушр, оп зйе 1лзегГасе 16 (1984), 5-6. Результат интересен только тогда, когда ((' < 2Л, так как каждое Р(х) кратно 1/Л.] 24. Запишите Л ) а и а; Л для первых Л и последних Л элементов цепочки а. Пусть К(а,б) = [а =/)]/Р(а) и пусть б — это матрица (з( и о(( с элементами г з = К(а,6)— К(З вЂ” 1: а, З вЂ” 1: )г).
ПуСтЬ С вЂ” КОаарнацнапиая Матрнца СпуЧайНЫХ ВЕЛИЧИН гз'(а) дпя [а[ = З, деленная на л. Эти величины подчинены ограничению ) о К(ао) = 2, )У(па) для каждой из (1) ' цепочек а, но все другие линейные ограничения вытекают нз этого (см. теорему 2.3.4.2С). Поэтому С имеет ранг»1'-4' ' и согласно упр. 3.3.1-25 достаточно показать, что ССС = С, Нетрудно проверить, что с„э ««Р(аб) 2 ищ, Т»(п„З), где Т»(п, Д) — член, соответствующий пересечению, которое может произойти, если наложить ф на а и сдвинуть ее на й позиций вправо: 1гК(1+ 5, и,;У: 1+5) — 1, если Ь < О; : 1 — Ь, 1 — Ь: 3) - 1, есл Ь > О. Например, если»(= 2, С = 5, а м 01101 и Д = 10101, то выполняется с э = Р(0) Р(1) х (Р(01) '+ Р(101) '+Р(1) ' -9). Элемент пб ССС поэтому равен Р(пф), умноженному на 1-1 ~ Р(Уа6) ~~~ ~ Т»(п,7а)(К(п,Ь) — 1)Т~(ГЬ„З). м~=»-»,»=э 1»щ» щс» Если заданы Ь и 1, то произведение Т»(п,.го)(К(а, 6) — 1)Т~(.~6, В) разлвгаетсв на восемь членов„к каждому из которых добавляется ш1, до умножения на Р(таЬ), а затем выполняется суммирование по всем уаЬ.
Например, сумма Р(уаЬ)К(2: и, уа: 2)К(а, Ь) х К(3: гЬ, ф: 3), когда и = а»...а», В = Ь, ...Ь„т = с,...с»» и Г > 5, равна сумме Р(с4... с» э), которая равна 1. Если Г = 4, та же сумма должна равняться К(ам (и), но не должна входить в сумму Р(уаЬ)К(2; а, уа: 2)(-1)К(3: ОЬ, В: 3). Поэтому результат равен нулю, если только не выполняется неравенство Ь < О < 1; в противном случае исключаются К(1: (у: и), (б: 1): 1)-К(»-1: (у: а), ф: 1+1); 1-1), где 1 = щ(в(с+5, 1-1) н у ж юах(О, Ь + 1).
Сумма по Ь и 1 прибавляется к с«э. 25. Эмпирическая проверка показывает, что на самом деле, когда (22) обобщено для произвольного 1, отношение соответствующих элементов С, ' и С»"'С»С, ' очень близко к -С прн Г > 5. Например, когда 1 = б, все зти соотношения лежат между -б.039 и -б.111; когда Г = 20, то все они лежат между -20.039 и -20,045.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
