Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 62
Текст из файла (страница 62)
Вероятность, что Ху < я, равна Г(х), поэтому имеем биномнальное распределение, обсуждавшееся в разделе 1.2.10. Ь"„(х) = э/и с вероятностью (,") Г(х)»(1 - Е(х))" '; сред» »(*); »* — „»»!*!!»-г»*!!! ц .»»».!»-»!»)М, Это указывает на то, что немного лучшей статистикой была бы г:=Л (».(*)-»!*)у ~РЙ7(»-»»г!» -ь»С»с»» см. упр, 22. Можно вычислить среднее и стандартное отклонения ддя Р„(р) — Е (х) при х < р и получить ковариацию ме»кду г"„(х) и гь(у). Используя данные факты, можно показать, что при больших и функция Р (х) ведет себя, как броуновское движение, и методы нз этого раздела теории вероятностей можно использовать для ее изучения. (См.
статьи Дж. Л. Дуба и М. Д. Доискера (3. Е. 11ооб апд М. О, 11опз)гег, Алла)з Маей, Бсаа 20 (1949), 393 — 403 и 23 (1952), 277-281). Их подход, вообще говоря, рассматривается как наиболее перспективный для изучения КС-критериев.) 7, Положим у = и в (13), чтобы увядеть, что К„" никогда не может быть отрицательной и что максимальное значение, которое она может принимать, равно т7й. Аналогично, положив у = 1, можно произвести подобные наблюдения над К„. 8, Новая КС-статистика была подсчитана для 20 наблюдений. Распределение К е использовалось как г"(х), когда КС-статистика была подсчитана.
9. Идея ошибочна, так как все наблюдения должны быть независимы»»и. Между статистиками К„+ и К„, полученными из тех же данных, существует связь, поэтому каждую проверку нужно выполнять отдельно, (Большое значение одной из статистик приводит к малому значению другой.) Подобным образом данные на рис. 2 и 5, на которых показаны 15 результатов проверки, не являются 15-ю независимыми наблюдениями, поскольку критерий "максимум-$" ие зависит от критерия "максимум-4". Три критерия каждого горизонтального ряда являются независимыми (так как они применялись к разным частям последовательности)„но пять критериев в столбцах являются в некоторой степени коррелированными, В результате 95-процентные и другие вероятностные уровни, которые используются в одном критерии, нельзя применять к целой группе критериев, основанных иа тех же данных.
Мораль такова: генератор случайных чисел можно 'проверять"' с помощью нескольких критериев, таких как частотный критерий, критерий по максимуму и критерий монотонности, но набор данных, полученных после подсчета различных критериев, нельзя рассматривать как материал для новой проверки, поскольку сами критерии могут быть зависимыми. Статистики К„" и К„следует рассматривать как два различных критерия. Хороший датчик случайных чисел выдержит проверку в обоих случаях. 10.
Каждое 1', н пр, дублируется, поэтому чиглитель (6) умножается на 4, а знамена- тель — только на 2. В итоге новое значение г' вдвое больше старого. 11. Эмпирическая функция распределения остается той же; значения К„" и К„умножа- ются на ~Г2. 12. Пусть В, = ٠— п4,)/ь~~,, Значение Ъ' равно и, умноженному на ~(9» Р» + ~/Дз7ВЯ») /Р» Это последнее выражение отделено от О, когда и возрастает (так как У,п ьм ограничено с вероятностью 1). Следовательно, $гбудет возрастать и принимать совершенно невероятные значения при предположении, что вероятности равны р».
Для КС-критерия предположим, что Р(к) — предполагаемое распределение, а С(к)— истинное распределение, и пусть Л ж шах)С(к) — Р(к)!. Возьмем и достаточно большим, чтобы неравенство )Е (к) — С(к)! > 57'2 выполнялось с очень малой вероятностью; тогда )га(к) — У'(к)( будет невероятно большим для гипотетического распределения Г(к). 13. (»шах» иа самом деле следовало бы заменить обозначением "зир", так как здесь имеетсв в виду наименьшая верхняя граница.
Однако обозначение "шах" использовалось, чтобы не смущать читателей, которые не знакомы с обозначением»зцр".) Предположим для удобства, что Хо -со, Х»+» =+со. Если Х < к С Л ем то Р»(к) =Цп, поэтому шах(гь(х) — Г(к)),у/и — г"(Ху) и шах(г (к) — Р„(к)) = Г(Х».»») — у/и на данном интервале. Когда у изменяется от 0 до и, рассматриваем все действительные значение к, Это доказывает равенства К'~ = чгй шак ~~- — Р(Х,)); К ~/й шел (Г(Хт) — ~ — ), Данные равенства эквивалентны (13), так как добавочный член под знаком максимума не положителен и изменен в соответствии с упр. 7.
14. Логарифм левой части требуемого равенства можно записать как 2,1 1-й 1;!в~1+ — '~+ — !п(2хп)--~~ !пр,--,~~ !в~1+ — ~+Он, ,/йр, 2 н эта величина (с использованием разложения 1п(1 + Я~/!/пр,) и того, что 2 ~, 2, ~/йу, = О), примет вид 1с э 1 — и 1 /1~ 2, + — !п(2кп) — — !п(р~... рь) + О ( — ) . ~Ф' 1$. Соответствующий якобиан легко вычнслитгс (!) вынеся множитель гь ! из опреде- лителя, (й) разложив полученный определитель по алгебраическим дополнениям строки, содержащей "'соэд~ — э!пВ~ 0 ...
0" (каждый детерминант алгебраического дополнения может быть вычислен по индукции) и (й!) вспомнив, что яп~ А + сов~ д~ = 1. 16. / екр~ — — +..)ои=ре ' +О~ — ~+ ( екр(- — + ..)4п, е Последний интеграл равен Если все это собрать вместе, то будет получено Если положить хЯ = хр н записать г-"' -и ! е ~эна=р, э~2к -ы х+1 = -, Ч(-,-) ~ГЯ =р, где !/2 = х+х42хх+р, можно найти р, а именно — р = 2~(1+аз)+О(1/~/х ), что согласуется с анализом, приведенным выше. Поэтому решение имеет вид ! = и+ 2~/йх + -"хт — э + О(!ай ). 17. (а) Сделать замену переменньпсх <- х +й (Ь) Иидукция по и; по определению Р е(х — Ф) = / Р1„ме(х„— !) Ы„. (с) Левая часть равна ьэ.с Гьмеэ гь гэ геэ М,, ( Ыхь~п умноженному на ! Ыхь 1,!хь, 4х, В й+, Ф с (с!) Из (Ь) и (с) получим Рьь(х) ы'у": (хэ.! и) Инслнтель (г — !)" (х+1-г)" ' ' г! (и — г)! в (24) равен Р„1,!(н).
18. Можно предположить, что Е(х) = х для 0 < к < 1, как отмечено в выражении (24) раздела. Если О < Хл « . Х < 1, то пусть 21 = 1 — Х»л „. Справедливы неравенства 0 < Ял « . Я„ < 1, и К„'", определенное для Х»,...,Л , равно К„, определенному для 2»,..., 2„. Эти симметричные соотношения дают взаимно однозначное соответствие между множествами с одним и тем же числом элементов, для которых К,+, и К„попадают в одну и ту же область.
20. НапРимеР, член поРЯдка 0(1/и) Равен -(эз" — 1э~)/н+0(п ~г~). Полное Разложение было получено Х, А. Поверье (Н. А. 1.аннет!ег, Хе!сэс)п!й йг )табшсйе!л!!сЬЬе!йпйеопе нос! гегввпс(се СеЫеге 2 (1963), 61-63). 23. Пусть гл — некоторое число > и, (а) Если !тг'(Х;)) = (тЕ(Х1Ц и л > у, то л/гл — г'(Л,) > у/и — Р(Х»), (Ь) Начните с а» = 1.0, Ь» = 0.0 и с» = О для 0 < ус < т. Затем для каждого наблюдения Х! выполните такие операпни: присвойте У +- Р(Х»), Ь +- (т ), а»»- ппп(а», У), Ь» +- шах(Ь», 1'), с» +- с» + 1. (Предположим, что Р(Х») < 1, поэтому Ь < т.) Затем присвойте у »- О, г+ »- г +- 0 и для й = О, 1, ..., т — 1 (в таком порядке) поступайте следующии образом, каким бы ни было с» > 0: присвойте »- шах(г,໠— у/и), 3»- /+ с», г»»- шах(г», у/и — Ь»).
Окончательно присвойте К+»- ь/й г", К +- л/йг . Требуемое время равно О(т+ и), и точное значение и должно быть известно заранее. (Если оценка (Ь + 1)/пл использована для а» и Ь» так, что только значения с» действительно вычислены для каждого й, получим оценки для К„+ и К„в пРеделах т л/й/т, даже когда т < и.) (АСМ Тгалэ, Маей. Яо/свите 3 (1977), 60-64.) 26. (а) Так как сп = Е(2",», ал»Х» 2,", адЛ~) = 2», аа,аз», то С = А.4 .
(Ъ) Рассмотрим сингулярное разложение А = 1/)11г', где У и К вЂ” ортогональные матрицы размера гл х т и и х и и 0 — матрица размера гл х и с членами А» = (л = Ясг,; сингулярные значения аг все положительны. (См., например, работу Голуба и Ван Лаана (Со!пЬ апб Уал 1 пап, Магпх Сошрисшюлэ (1996), 62.6.3.) Если ССС = С, то ЯВЬ' = Я, где Я = 0)У~ и В = (/~С(/. Таким образом, эб м (!=Да!, где лгы считаем, что п„»л . = а~ и 0 н эо = 2»,эмЬыэб = олагЬ1. Следовательно, Ьо = [Ь=Я/а,, если э »,У < и, и получим, что Р В!1 — это еднничная матрица размера и х гл. Пусть Р = т (У! — дп,)"~ — д ) и Х = (Лм..,,Х„)з. Из этого следует, что !Р и 1'тС1" = Х А'САХ = Хт)ТУ'ВПР Х = ХтХ РАЗДЕЛ 3.3.2 1, Наблюдения в З!г-критерии должны быть независимыми. Во второй последовательности соседние наблюдения, очевидно, зависимы, так как вторая компонента одной пары равна первой компоненте следующей пары.
2. Образуйте 1-мерную строку (1'»,..., 1'л»г,) для 0 < у < и и подсчитайте, сколько рэз эти строки совпадают с любымя заданными. Примените 1»-критерий с Ь = ср и вероятностью причисления к каждой категории 1ф'. Количество наблюдений и должно быть равно по крайней мере Ьд'. 3. Вероятность того, что точно у значений проверенм, а именно — вероятность того, что Сг-л является и-и элементом, лежащим в области а < Ц ~ < ф, как легко видеть, равна Ее можно вычислить, подсчитав люэможные комбинации из остальных и - 1 элементов и определив вероятность такой схемы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
