Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 64
Текст из файла (страница 64)
Этот феномен требует объяснения. 20. (а) Вектор (л»,..., Я ) является равномерно распределенной точкой в (и — 1)-мерном многограннике, определенном неравенствами Я» > О, ..., Я«> 0 на гиперплоскости Я~ + + Я„««1. Легко доказать по индукции, что (1 э! эз ' ' ' э«)~. М~ [ бгю [ 41, ~[1 — с~ — "— г«-~>э«]= (и — 1).' Чтобы получить вероятности, разделим этот интеграл на его значение в частном случае, когда э» = .. = э« = О [см.
работу Бруно де Финетти (Вгвпо де г1лесп', Сэо»ла)е В»його Вабало г(еяй Ассизи' 2 г (1954), 151-173)]. (Ь) Вероятность того, что $01 > э, равна вероитности 5» > э, ..., Я > э. (с) Вероятность того, что $1», > э, равна вероятности, что по крайней мере Й— 1 из Я~ будет < э. Следовательно, 1 — Г»(э) = С»(э) + . + С»»(э), где С,(э)— зто вероятность, что точио,у разностей < э.
Из соображений симметрии Сэ(э) равно ("), умноженному на вероятность того, что Я» < э, ..., Я < э, Я~+» > э, ..., 5«> э, и зта вероятность равна Рг(5» < э,...,бэ ~ < э,ьэ > О,ь)+» > э,,Я«> э)— рг(9~ < э,...,б»» < э,Я» > э,...,Я«> э). Повторное применение (а) показывает, что С~(э) = (~ ) Е~ (]) (-1)1 '(1 — (и - 1)э)". '; следовательно, В частности, наибольшая разность 91»» имеет распределение (Между прочим, подобнаи величина х" '(и — 1)'. 'Г (х '), оказывается, является плотностью распределения суммы 1»1-»- . +4»» Равномерно распределенных случайных величин.) (41) Из формул Ез' = г)ь (1 — Г(4))з' 'сьь и ) ь" (1 — Йь)~ ' 144 = 5 ' 'и '("+,") находим Е 9<4» — — и '(Н» — Н„ь) и с помощью алгебры получаем Еэ»гь = и '(и+ 1) х (нс㻠— нс»ь+ (и„— н„ь)2).
поэтому дисперсия Ясь» равна и '(и+1) 1(н»ы» — нс㻄— (Н Н )21) (Распределение Гь(з) впервые было найдено В. А, Витвортом (%. А. %51сногзЬ), который «формулировал вопрос о распределении Я»ь» как проблему 557 в СЬоссе авс( СЬапсе (СашЬгсЫйе, 1867) и дал ее решение в 17СС Ехегсйеь т СЬо»се оп с( Су овсе (СашЬг»са, 1897) .
Витворт также нашел элегантный метод подсчета математического ожидания любого полинома от функции Сь(ь) = Гь(з) — Гь»1(ь). Этот результат был опубликован в буклете, озаглавленном ТЬе Ехрессайап ог Рагсз (СашЬгЫбе, 1898), и включен в пятое издание СЬасе апс) Суапсе (1901). Упрощенные выражения для среднего, дисперсии н некоторых более общих статистик разностей были найдены Бартонам и Дэвидом (см.
рабату Вагсои авс( 1»атсЫ, Х Науа( Ясас. Яос, В18 (195б), 79-94). Обзор методов, которыми статистики традиционно анализируют разности как ключи к возможным смещениям данных, приведен в работе Р. Пайка (В. Ру1се, Х Коув1 асяс, Бос. В97 (19б5), 395-449).] 97. Рассмотрим многогранник в гиперплоскости 91 + .. + 5 = 1, определенный неравенствами 91 > О, ..., Я» > О. Он состоит из и» кангруэнтных падмногогранников, определенных упорядочением $1 (предполагается, что 92 различны), и операцией сортировки является от и» к одному складывание больших многогранников из подмногогранников, в которых 91 < . < Я . Преобразование, которое переводит (541»,..., ЯС„») в Щ,..., Я,), является взаимно однозначным отображением, разлагающим дифференциальные объемы на п» частей. Оно образует вершины (-„',,-'), (О,— „',,...,-„-~.), ..., (0,...,0,1) падмногогранников в соответствующих вершинах (1,0,...,0), (0,1,0,...,О), ..., (О,...,0,1); линейное растяжение и исгсажение полностью приспособлены к процессу.
(Евклидова расстояние между вершинами (О,..., О, -',... „1) и (О,..., О, -'„,..., ~5) в падмногограннике равно )7' ' — »с 1)112; преобразование образует регулярный симплекс, в котором все и вершин находятся на расстоянии 42.) Поведение итерированных разностей (о, о, 1) легче понять, если проверить детали графически при и = 3. В этом случае многогранник является простым равносторон- х(х УС2 2О ЕО ним треугольником, точки которого вы- 22 02 ражены в барицеитрических координатах 21 01 (х,у,г), х + у + з = 1. На приведен- ы Ос ном рисунке иллюстрируются два первых гь аь уровня рекурсивного разбиения этого гре- зь 14 угольника. Каждый из б подтреугаль- у >х ников помечен двузначным кодом ру, где зо зз ЬЬ 4Ь 12 ю зг ьз 4З и р соответствует подходящей перестановке, когда (х,у,з) = (51,92.
Яз) рассортироваьэ 44 44 41 4О ны в вике (Я»с», Ясг», Есз»), а д соответствует перестановке следующей стадии, когда 91„ , <у (о,),о) + (зь — Ь) + (зьз1 — Ь) + + (з„— и + 1) = т — (") — Ь. Следовательно, Ь„!(з) = 1«гь! (и — 1)!(Яь !(зь — з") зЫ/(1 — з)... (1 — з"). Аналогично можно показать, что «""', -(~„Е ь'- "!« '- ' '! ь ~ «*"- "!«*'-*' '!) (" ') х (1 ) (1 зЯ)' Можио получить Ьз, (з) для произвольных г из формулы Ь„,(з)ю' (з Ь,зз) (з -1 Ь,з )/,„~ь! /„„ь„, и!(и — 1)! з" а с! ...с !(1 — )...(1 — з") ьз"-1/ ''' ~з«/ ОЗ!! „.,Ь„! й 1 гдесь = 1+Ьь+ЬьЬь !+. +Ьь...Ьзй! = 1+Ььсь-!.
(Частный случайдля ю = 1 интересен, поскольку левая честь суммируется до (1 — з) "/и() ЗО. Это хорошая задача для метода перевала (см. работу Н. Г. де Брейна (М. С. !(е Вгп«)п« Азуп!ргоь«с Месйодз 1п Ала(узм (Хогг(1-НойаЫ, 196Ц, С)«ар!от Ц. Справедливо равенство р„(т) = — ' у е««1з*, где /(з) = -!и!пз — ~"„" !п(1 — зь). Пусть р = и/т и д = !/й/т; интегрирование по пути з = е "+' дает р„(т) = —,/' ехр(/(е >ео!))«й. Ъдобио использовать равенство з г! д(зе') = ~ ' —,,д!д(з)+ / —,д"+'у(зе' )ди, ,\! Я где у = у(з) — любая аналитическая функиия и д — оператор Щ. Когда функция д'у вычислена в точке е*, результат будет таким же, как и тогда, когда у(е') диффереицируетгя / раз но з. Этот принцип приводит к получеиию формулы д'/(е з) = -т(/=1]+ —, +(-1)! ~~ — Ь'р' ' 1.
1! р' Ь=.1 1> « из другого удобного равенства, Таким образом, получена асимпготическая формуладвя псдыитегральиого выражения ехр/(е >+'и) =ехр(~~~" 1 '—.;1-д!/(е ')/ =-е ' «з+!«' 'ехр(!с!1 — сзьз-!сззз+" ), «1>О ., - !ззма ь«««з«" «з*«!«+«««.-'« *., ° . ', = з«.-'! для / > 8. Вынеся за скобки константу, получим — — р~ — ~~ — Ьр~ б з-е б / в! 2я 2з. и! р "с-"з ~, 1. й Ь 1!>1 что приводит к интегралу, подыитегрвльное выражение которого является зкспонеипиальио малым, когда ф > и'. Можно пренебречь большими зиачеииями й поскольку разложение иа элементарные дроби показывает, что цодыитегральиое выражение имеет порядок 0((т/и) "~~).
Ни один из других корней единицы не появляется более и,'2 раз как полюс знаменателя, Следовательно, было допущено существование "тяжелых хвостов» «см. СМасЬ, 39.4«и выполнено интегрирование по всем 1. Формулы /'ы е ' ггг" 41 = О 1)(/ 3) -(1)ъ/йх я«у — четное) и и! = (и/е)»ъг2хпехр( —,' ц ' + О(п )) достаточны для завершения вычислений. С д (гп) = р,(гл — ("г ')) вместо р (гп) вычисления производятся таким же образом, но с сп возрастающим, как 1а(п~~~ — и ыг), и с дополнительным множителем ехр( — р("+')), Получаем пг" 'г.""Г / 13аг 169о~ — 201баз 1728аг + 41472о -з ) кб (и — 1)! (, 288 п 165888пг что совпалает с формулой для р„(гп), но а заменено на -а.
Действительно, если определить р„(гп) = г„(2гп + ("~')) и 9»(т) = г „(2пг — (""')), производящая функция гс (г) = 2 г„(г~) = П,(г "— г ) ' удовлетворит равенству )1„(1/з) = (-1)"В (г). Отсюда следует формула двойственности г„(-ш) = ( — 1)" 'г»(пз) в том смысле, что уравнение превратится в равенство, когда г (пг) вырагкается через полипом по пг и корни единицы, Поэтому можно сказать, что 9»(т) = р„(-гп). В общем случае интерпретацию такой двойственности можно найти в работе Дж. Пойа (см. С.
Рб!уа, Ма!5. Ушсзсйг)гг 29 (1928), 549-640, 544). (Дополнительно см. работу Дж. Шекерса (С. Бге)епее, геиагчег1у Х 51асЬ. Ох/огд 2 (1951), 85-108; 4 (1953), 96-111.) Точное значение 9»(гп), когда пг = 2гз и и = 512, равно 7.08069 34695 90264 094... х 1О'м~; наша аппроксимация дает оценку 7.080693501 х 10'м~. Вероятность того, что критерий дней рождения обнаружит Я = 0 разностей, равна Ь.оэ(гл)/гл» = и!(и — 1)!гл' »д»(гп) м е »Ы + О(п"г) согласно упр. 28, поскольку вклад от Ь ег(т) равен - г— „е Ы = 0(п '). Включение многкнтеля д (з) = ~,",:,'(з ~ — 1) в подмнтегральное выражение д,(гп) дает тот же эффект, что и умножение результата на "-+ 0(п '), поскольку 9„(е»ео ) = (")р + 0(~зрг) + ЫО(игб) — $1~0(п~д~) + Подобным же образом зкстрамножитель ~ гсг~, „(з '-1)(г ь-1), по существу, умножает на -'и'рг = -'а~ и добавляет О(п ').
Другие вклады в вероятность того, что Я = 2, имеют порядок 0(п '). Таким же образом найдем, что вероятность получения г равных разностей равна е "Ы(а/4)"/г! + 0(п ')„т. е. число равных разностей приближенно имеет распределение Пуассона. Более сложные члены возникают, если осуществить разложение до порядка 0(п ), 31. 79 даои*гных разрядов содержат 24 множества троек (У»,1'»+ам)'»+зг), (1'» ц 1'»+зг, К»зв),, (1'»+гг,)'»+ге,)'»+ге), плюс 7 дополнительных разрядов 1'»»г4,...,У+ге.
Последний двоичный разряд с равной вероятностью является 0 или 1, но в каждой группе троек с вероятностью зг двоичные разряды имеют вид (О, 0,0) и с вероятностью з они будут иметь вид (0,1,1). Поэтому производящая функции для суммы двоичных разрядов равна /(г) = ('тгд)г(-'-ф-)г» (это полипом 55-й степени). (Данная форлгула не точна! строго говоря, она имеет вид (2ы/(г) — 1)/(2»з — 1), поскольку все 0-случаи исключены.) Коэффициенты 2"г/(з) легко подсчитать на вычислительной машине, и, следовательно, можно найти, что вероятность того, что единиц больше, чем нулей, равна 18509401282464000/(2»з — 1) 0.51374.
Замечание. Это упражнение основано на открытии Ваттулайнена, Ала-Нисснла и Канкаала (см. работу 1гаыи1ывел, А!а-%ез!1а, апг! Кавказ)а, Р)гуэ(се) Йет1егг Беыегэ 73 (1994), 2513-2516), состоящего в том, что генератор Фибоиаччи с запаздыванием не удовлетворяет более сложному критерию двумерного случайного блуждания. Заметим, что и последовательность Уг, 1'г„»г, ... не удовлетворяет этому критерию, поскольку она описывается тем же рекуррентным соотношением. Смещение в сторону единиц распростра- няется на подпоследовательности, которые состоят из четных элементов, генерируемых последовательностью Х„= (Х -зз х Х ~-зв) пюд 2', ей присуща тенденция иметь больше случаев (...
10)з, чем (... 00)з в двоичной записи. Нет ничего магического в числе 79 в этом критерии, Эксперименты показывают, что значимые отклонения в сторону единиц присущи также случайным блужданиям длиной 101, 1001 или 10001. Но бюрмвльное доназательство этого, вероятно, будет трудным, в вб ° ч ~ в р РЧ *)" (~)' миозкнтели (1+ 2зз+ 5зз+ 5з~+ 10зз+ 8зв+ зт)/32 (1+ 2зз+ 7зз+ 7з4+ 15зз+ 25зв+ 29зт+ 28зз + 13зв + з'в)/128 и т. д. Анализ становится все более и более сложным с удлинением блужданий. Интуитивно ясно, что преобладание единиц на первых 79 шагах будет продолжаться столько, сколько числовые подпоследовательности умеренно колеблются между 0 н 1, Сопутствующая диаграмма показывает результаты более простого случая, а именно— использования генератора Ув = ()'„з + У» и) щоб 2, который можно легко проанализировать.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
