Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 21
Текст из файла (страница 21)
При интегрировании справедливо равенство Вхь(0 = г Ыг Вд. Для болев общего и-мерного простраьщтва можно положить х» ««гь!пдю ..ыпд»»соьд», 1 < 2< и, н х«««гь(вд»...ашд Покажите, что в этом случае Вх1 Вяз... Вх«««]г" ' ьш" ь д~ ...ьш В ь Вг 401... 00«-1 [. ь 16. [НМВВ] Обобщите теорему 1.2,11.3А, чтобы найти зяачение у(. + 1, х+ /Б+ 0)[»(х+ ц для балыках х и фиксированных В, ь. Опустите члены ответа, н»бьющие порядок 0(1/х).
Используйте этот результат, чтобы найти приближенное решение ь уравнения у~-", -') /г(-') р для больших и и фиксированных р, таким образом получив асимптотические формулы, приведенные в табл. 1. [Уха»анас, См. упр. 1.2.11.3-8.] 17. [НМдб] Пусть Ь вЂ” фиксированное число. Длв 0 < й < и положим г« г« г«»«ь г«»«1 Г ь Р„»(х) =/ Вх„/ Вх„, ... ~ Ых»+» / Вх» ... / Вхп «-~-г »+1, ь а по апределенша пусть Рьь(х) = 1.
Докажите следующие соотношения. Г«+' Г«" Г«»«ь г«»«ь Г * Г « «1 »,1 ь ! Ь) Р«( )=( +1)"У .— (, +1)"-'У( — Ц.. (й — ь)» с) Р«»(х) — Р„р, ю(х) ж —, Рщ юь(х - 2), если 1 < й < и. 0) Кроме того, получите общую формулу для Р„»(х) и примените ег к вычнстению (24), 18. [М20) Найдите "простое«объяснение, почему Н„имеет то же распределение, что и Н«. 19. [И!788[ Предложите критерий, аналогичный критерию Колмогорова-Смирнова, для применения к многомерным распределениям г(х!,...,х,) = Рг(Л! < х!,...,Л, < х ). (Можете использовать такие процелуры, как, например, "критеркй серий'* (см.
следующий раздел) . ) 29. [ИЦ1) Получите слелуюшие члены асимптотического разложения для КС-распреде. пения. продолжив (27). 21. [М40) Хотя в разделе говорится, что КС-критерий может применяться только тогда, когда г"(х) — непрерывная функция распределения, конечно, можно попытаться вычислить К+ и К... когда распределение имеет скачки, Проанализируйте воз!!ожное поведение К,+, и К„для различных разрывных распределений Р(х).
Сравните эффективность полученных статистических критеряев с т -критерием иа нескольких выборках случайных чисел. 22. [НМбб] Исследуйте "подправленный" КС-критерий, предложенный в ответе к упр. 6. 23. [М88) (Т. Гонсалес (Т. Совза(ез), С, Сахни (Б. ЯаЬш) и В. Р.
франта (%. 11, ггалеа).) (а) Г1релпологким, что максимальное значение в формуле (13) для КС-статистики Кь принимается для данного индекса !, когда [пЕ(Х1)) = и Докажите, что г"(Ху) шах (Е'(Х!) [ [пР(Х!)) = к). (Ь) Напишите алгоритм для вычисления Ке и К,, зв О(п) шагов (без сортировки). ь 24. [40) Проведите опыты с различными вероятностными распределениями (р, о, г) трех категорий „где р+в+г = 1, вычисляя точное распределение тз-статистики 1: для различных и и тем самым определяя, насколько точным является приближение Х -распределения с 2 двумя степенями свобошк. 2$.
[гциеб) Предположим, что П = 2 ", аоХ1 + и! для 1 < ! < пь, где Х!,, Л;,— независимые случайные величины со средним, равным нулю, н единичной дисперсией. Матрица А = (ао) имеет ранг и. а) Выразите ковариационную матрицу С = (сб), где с З = Е(1! — Р!)% — Рт ) в терминах матрицы А. Ь) Докажите следуюшее: если С = (сц) — любая матрица, такая, что ССС = С, то статистика И' — ~~ (У, — Р!)(1', — Р!)со ! !1=! равна Л!э + + Хэ. [Следовательно, если Ху имеют нормальное распределение, И' имеет Хз-распределение с и степенями свободы.) устойчивость среднего ппи бросании монеты определяется законом... который гарантирует, что вы не Разоритесь свми, слишком много теряя, и не Разорите своих оппонентов, слишком много выигрывая.
— ТОМ СТОППАРД (ТОМ БТОРРАВО), Розенкранц и Гилденстерн мертвы (1966) 3.3.2. Эмпирические критерии В этом разделе рассматриваются одиннадцать специфических критериев, которые традиционно применяются для проверки, будет ли последовательность случайной. Обсуждение каждого критерия разбивается на две части: (а) "краткое" описание способов применения; (Ь) теоретическое обоснование. (Читатель, ие привыкший к математическим рассуждениям, может пропустить теоретические выкладки. С другой стороны, математически подготовленный читатель может найти приведенную теорию весьма интересной, даже если он никогда не собирается проверять генераторы случайных чисел, так как здесь вводятся некоторые понятна комбинаторики. Действительно, в этом разделе вводится несколько важных понятий, представляющих для нвс интерес в связи с совершенно иными вопросами.) Каждый критерий применяется к последовательности (Е~ь) = уо,(ум(Гз " действительных чисел, которые, как предполагается, независимы и равномерно распределены между 0 и 1.
Некоторые из этих критериев предназначены непосредственно для целочисленных последовательностей, а не для последовательностей действительных чисел (1). В таком случае вместо нее используется вспомогательная последовательность (Уь) = Уе У1 1з (2) определенная правилом У„= (сК7„). (3) Это последовательность целых чисел, которые, как предполагается, независимы и одинаково распределены между 0 и д-1. (Иначе говоря, вероятность, что случайная величина примет значение й, й = О,...,д — 1, равна 1/д.
— 1Урпм. ряд.) Число д выбирается таким, чтобы его было удобно использовать в том либо ином смысле, Например, можно выбрать д = 64 = 2е на бинарном компьютере так, что 1; представляет шесть старших двоичных разрядов двоичного представления числа бГ„. Значение д должно быть достаточно большим, чтобы критерий был значимым, но не настолько большим, чтобы критерий стал практически неприменимым. Введенные выше обозначения бг„, У„н д будут использоваться в этом разделе, хотя значение д будет, вероятно, изменяться в различных критериях. А. Критерий равномерности (критерий частот).
Первое требование, предьявляемое к последовательности (1), состоит в том, что ее члены — это числа, равномерно распределенные между 0 и 1. Существует два способа проверить это. (а) Использовать критерий Колмогорова-Смирнова с Г(в) = я для 0 < в < 1. (Ь) Использовать последовательность (2) вместо (1), где д — подходящее число, например 100 на десятичном либо 64 или 123 — на бинарном компьютере. Дли каждого т, 0 < г < г(, подсчитаем число случаев, когда У = г для О < у < и, а затем применим Гз-критерий, принимая й = д и вероятности р, = 1/д для каждой категории. Описание и обоснование этих критериев приведено в разделе 3.3.1. В. Критерий серий.
Более общее требование к последовательности состоит в том, чтобы пары последовательных чисел были равномерно распределены независимым образом. В конечном счете Солнце восходит так же часто, как и заходит, но это не делает его движение случайным. В критерии серий просто подсчитываем число случаев, когда пара (Уэу, Уэу+1) = (д,г) для О < у < п.
Такая операция осуществляется для каждой пары целых чисел (д,г)„таких, что О < в,г < М. Затем применяем Тг-критерий к этим й = ог категориям, где 1/пг — вероятность отнесения пары чисел к каждой из категорий, Как и для критерия равномерности, М вЂ” подходящее число, но оно должно быть немного меньшим, чем значении, предложенные выше, так как значимый х -критерий должен иметь и сравнительно большим по сравнению с й (скажем, по крайней мере п > бвг).
Ясно, что можно обобщить этот критерий для троек, четверок и т, д, вместо пар (см. упр. 2). Тогда значение г( необходимо существенно уменьшить для того, чтобы число категорий не получилось слишком большим. Поэтому ири рассмотрении четверок н больп;их серий чисел используются менее точные критерии, такие как покер-критерий и максимум-критерий, описанные ниже. Заметим, что 2п чисел последовательности (2) использовались в этом критерии для того, чтобы сделать и наблюдений.
Было бы ошибкой применять критерий серий к парам (1е,У1), (Ум)г), ..., (1' НУ ). Может лн читатель сказать, почему? Но можно применять критерий серий еще и к парам (Угт~.ОУгу+г), ожидая, что наша последовательность удовлетворит этим двум проверкам. Однако нужно помнить, что эти проверки на самом деле взаимозависимы. С другой стороны, Джордж Марсалья (Сеогйе Магэая)(а) доказал, что если использовать пары (Уе, Уг), (У1 Уг),, (У НУ,) и применить обычный тг-критерий для вычисления обеих статистик (1г для критерия серий и Ъ~ — для критерия частот по 1в,..., 1' 1) с тем же значением г(, то случайная величина 1г — Уг будет иметь хг-распределение с М(с( — 1) степенями свободы, когда и достаточна большое (см. упр.
24). С. Критерий интервалов. Этот критерий используется для проверки длины "интервалов" между появлением П на определенном отрезке. Если а и д — два действительных числа, таких, что О < а < ф < 1, то рассмотрим длины подпослеаовательностей бэ, У.+м ..., У +„в которых П,~.„лежит между а и 3, а другие Ь', не лежат между этими числами. (Эту подпослеловательность, состоящую из г + 1 числа, будем называть интервалом длиной г.) Алгоритм С (Данные длл крипгерил пнпгеввалвв). Следующий алгоритм (рис. 6), примененный к последовательности (1) для любых значений а н ф, подсчитывает число интервалов длиной О, 1, ..., $ — 1 н число интервалов длиной > 1, пока не получится и интервалов.
С1. (Инициализация.] Присвоить у <- -1, в +- О и присвоить СООМТ(г] <- О для О < г < г. С2. (Присвоение г значения О.] Присвоить г <- О. СЗ. ]а < Пг < (г?] Увеличить ( на 1. Если Пу > а и Ь~ < ф, то перейти к шагу СЬ. С4. (Увеличение г.] Увеличить г на единицу и возвратиться к шагу СЗ. Сб. (Регистрация длины интервала.) (Интервал длиной г только что найден.) Есзи г > $, то увеличить СООМТ(г] на 1, иначе — увеличить ОООМТ(г] на 1. Сб. (Найдены лн и интервалов?) Увеличить в на 1. Если в < и, то вернуться к шагу С2. $ Рис, 6. Сбор данных для критерия интервалов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
