AOP_Tom2 (1021737), страница 16
Текст из файла (страница 16)
Квик считал, что есе Я, должны иметь одно и то же распределение, поэтому критерий будет даже сильнее, если использовать каждое Яп, 0 < 2 < и, вместо каждого (-го члена. Но когда он применил Хз-критерий в случае одинаковых РаспРеделений к величинам Уус, полУчились чРезмеРно высокие значениЯ статистики У, которые увеличивались цри возрастании К Почему так произошло? 17.
[МЯЯ] Даны любые числа Пе,,,., сс'„с, Ус,..., У !. Пусть их средние значении раним 1 б= — ~ ~Ц„ и 0<с<ч о<а< а) Пусть (с! = (с'„— О, Ъ'„' = Уь — О. Покажите, что коэффициент корреляции С, определенный в (24), равен Ь) Пусть С = с((Р, где Ас и Р— числитель и знаменатель выражения из п. (а). Покажите, что ст'~ < Р~, отсюда -1 < С < 1. Получите формулы для разности Р— )с'~. [Указание. См.
упр. 1.2.3-30.] с) Если С = Л1, покажите, что а(с!+)?У! = т, 0 < Л < и, для некоторых не всех равных нулю постоянных о, Я и г. 18. [МЯО] (а) Покажите, что, если и = 2, серивльиый коэффициент коррелиции (23) всегда равен -1 (если знаменатель не равен нулю). (Ь) Аналогична покажите, что, когда и = 3, серивльный коэффициент корреляции всегда равен — 2. (с) Покажите, что ! знаменатель в (23) равен нулю тогда и только тогда, когда (?е = сс'! = = П -!.
19. [МЯО] (Дж. П. Батлер (3. Р. Вв(1ег).) Пусть 1)о, ..., (?„! — независимые одинаково распределенные случайные величины. Докажите, что ожидаемое значение серивльиаго коэффициента корреляции (23), среднее по всем случаям с ненулевым знаменателем, равно -1/(и — 1).
20. [НМ41] Продолжая предыдущее упражнение, докажите, что дисперсия (23) равна п~)с(п — 1) (и — 2) — пз Е((По — 1)!)с/Р!)/2(п — 2), где Р— зкаменатель из (23), а Е— ожидаемое значение по всем случаям, когда Р ф О, Чему равно асимптотическое значение Е(((?а — 1(!)~/Р~), когда каждое сс) равномерно распределено? 21.
[1Я] Какие значения у будут вычислены алгоритмом Р, если применить его к перестановкам (1,2,9,8,5,3,б,7,0,4)? 22. [)Я] Для какой перестановки (0,1,2,3,4,5,8,7,8,9) алгоритм Р выдаст значение у = 1024? 23. [МЯЯ] Пусть (У„) и (У„') — последовательности целых чисел, имеющие периоды длиной Л и Л' соответственно с О < У„, У„' < сс. Пусть также Я„ж (У„+ У„'т„) шос(с(, где г выбрано наудачу между 0 и Л' — 1. Покажите, что (Я ) удовлетворяет бмерному критерию серий по крайней мере так же, как (У„), в следующем смысле. Пусть Р(хс,...,хс) и (4(х),... с хс) — веРоатности того, что ьмеРнаЯ стРока (хс,..., х,) поЯвлЯетсЯ в (У ) и (Я ): 1 х-! Р(хс,,хс) = — ~~~ [(У,...,У.ьс-!) =(хс,...,хс)]; Л =о 1 х-! А' — ! ()(хс,...,хс) = —, ~ „", [(Яь,,Яч+с-!) = (хс,...,хс)[.
=0 с=е 'согда» (г)(хс,...,хс) — 4 с)з < ~ (Р(х,.",*с) — 4 с)'- (Ьс,с..,ьС) (* с, , с . М с ) 24. [НМУ5] (Дж. Марсалья (С. Магваб!)а).) Покажите, что критерий серий для и пересекающихся 1-мерных строк (умУц..., 1)), (Уц Ув,...,у)+1),, (Ъ«, У«+),,1с+ -)) может быть осуществлен следующим образом. Для каждой цепочки а = а)... а„, с О < а«6 положим )1)(а) равным числу случаев, когда а появляется как надцепочка Уц1ц..., У, У +),, 1«+ «-), и пусть Р(а) = Р(а))... Р(а ) — вероятность того, что и появляется в любом заданном положении.
Разные цифры могут появляться с различными вероятностями Р(0), Р(1), ..., Р(6 — 1). Подсчитаем статистику 1 Х(п) 1 Ж(а) и Р(п) и Р(п) Тогда У должно иметь |~-распределение с 6) — )() ' степенями свободы, когда и большое. [Указание. Используйте упр. 3.3.1 — 25.] 25. [М46] Почему выполняется приближенное равенство С) 'СвС) ' )и — ОС) ', где С) и Св — матрицы, определенные в (22)? 26. [НМЯО] Пусть 5)), (?в.....
() независимы и равномерно распределены в [О .. 1) и пусть с)о) < ())в) « Сг«) — их значения после сортировки. Определите разности Я) = <))в) — б<ц,..., Я ) = Сы) — 5)! ц, Я = 5)0)+1 — (?! ) ирассортируйтеихЯСО « ЯШ), как в критерии промежутков между днями рождений. В следующих вычислениях удобно использовать обозначение х+ в качестве сокращенной записи выражения х" [х > 0]. а) Пусть даны любые действительные числа в), вв, ..., в„.
Докажите, что вероятность того, что неравенства Я) > в1 и Яз > вв, ..., Я„> в выполняются одновременно, равна (1 — в1 — вв — — в„)" Ь) Докажите, следовательно, что наименьшая разность Ясц будет < в с вероятностью 1 — (1 — ив)+ 1. с) Какова функция распределения Гв(в) = Рг(ЯЫ) < в) для 1 < )с < и? )() Вычислите среднее и дисперсию каждого Я)в). )' 22. [НМ26] (Нтернраеанные разности,) В обозначениях предыдущего упражнения покажите, что числа Б[ = ибсц, зв = (и — 1)(Я)в) — Я)ц),..., з'„= ЦЯ1„) — Я)„ц) имеют то же самое совместное вероятностное распределение, что и первоначальные разности Ю), Я„ и равномерно распределенных случайных величин.
Можно упорядочить их в виде Я[ц « Я[„) и повторить это преобразование, чтобы получить еще одно множество случайных разностей Я),..., Я„и т. д. Каждое последующее множество разностей Я) «« )в) Я«может быть также проверено по критерию Колмогорова-Смирнова, где гв) К„) = ~~и — 1 п)ах ~ — — Я) — — Я + / 2 оц )в)1 6,<.~ -1 ' / К„:, = й:1 (Н, '+" +Н. ' — — ). Г Ш,„1 — 11 )<)< ' ) и — 1 Детально проверьте преобразование (Я), .'.., Я«) в (Я(„..., Я«) для и = 2 и и и 3.
Объясните,почему постоянное повторение этого процесса в конечном счете приведет к неудаче, если его применять к компьютерному генератору чисел с ограниченной точностью. (Один из методов сравнения генераторов случайных чисел состоит в наблюдении, как долго они проживут при таких мучительных испытаниях.) 26. [МЯ6] Пусть Ь«„,(и)) — число и-мерных строк (у),..., у„) с 0 < у, < )и, имеющих точно г равных разностей и в нулевых разностей.
Таким образом, вероятность того, что Й = г, в критерии промежутков между днями рождений равна 2„'е Ь«„(т)/т". Также пусть р (т) — число разбиений т на не более чем и частей (упр. 5.1.1-15). (а) Выразите Ь„ое(ти) в терминах разбиений. [Указание. Рассмотрите случай с малыми т и и.] (Ь) Покажите, что существует простое соотношение межлу Ь„„,(т) н Ьш,ц,+г- >е(т), когда з > О, (с) Выведите точную формулу вероятности того, что разности равны.
29. [М35] Продолжая упр. 28, найдите простое выражение для производящих функций Ь„,(г) = ~ >р Ь,е(гп)г /т, когда г = О, 1 и 2. ЗО. [НМ41) Продолжая предыдущее упражнение, докажите, что если гп = пг/а, то т" 'е Ы Г 13а 169а~+ 2016аг — 1728аг — 41472а г ) +О(п ) (( — Ц> '1 288 165888пг для фиксированного а прн и — > оо.
Найдите аналогичную формулу для 9„(т) — числа разбиений т на и раэлачяих положительных частей, Выведите с точностью до 0(1/и) асимптотические вероятности тога, что в критерии промежутков между днями рождений Нравно0,1 и2. 31 [МИ) Рекуррентное соотношение Уь ж (1'„гг+У ы) шоб2, описывающее младший значимый разряд генератора Фибоначчи с запаздыванием 3.2.2 — (7), как и второй младший значащий разряд 3.2.2-(7'), как известно, имеет период длиной 2г' — 1; следовательно, каждая возможная не равная нулю конфигурация двоичных разрядов (У, У +и..., У еы) появляется одинаково часто. Тем не менее докажите, что если генерировать 79 последовательных двоичных разрядов У„,..., У„еге, начиная со случайной точки в периоде, вероятность, что там будет больше единиц, чем нулей, больше 51%. Если использовать такие двоичные разряды для определения 'случайного блуждания", состоящего в том, что точка движется вправо, когда двоичный разряд содержит 1, и влево, когда двоичный разряд содержит О, то в большинстве случаев будем заканчивать блуждание справа от нашей начальной точки.
[Указаное. Найдите производящую функцию 2 г е Рг(У + + У+ге=5)г .) 32. [МЗО) Определите, верно ли следующее: если Х и 1' — независимые одинаково распределенные случайные величины со средним О и если для них более вероятно быть положительными, чеи отрицательнымн, то Х + У более вероятно будет положительным, чем отрицательным. ЗЗ. [НИЗ) Найдите асимптотическое значение вероятности того. что Ь + 1 последовательных двоичных разрядов, генерируемых рекуррентным соотношением У„= (У„-г + У э) шоб 2, имеют больше единиц, чем нулей, когда Ь > 21 и длина периода этой рекуррентной последовательности равна 2" — 1.
Предполагается, что Ь болыпое. 34. [Нар[ Объясните, как оценить среднее и дисперсию числа двухбуквенных комбинаций, не появляющихся последовательно в случайной строке длиной и в пг-буквенном алфавите. Предположим, что т большое и и ш 2т . г ь Зб. [НМЯЯ) (Дж. Н. Линдхолм (3. Н. Ь|пйЬоЬп), 1968.) Предположим, что случайные двоичные разряды (У„) генерируются с помощью рекуррентного соотношения У =(агУ г+агУ,-г+ . +аьУ„-э)шод2 для некоторого набора а„,, аг с периодом длиной 2 — 1. Начнем со значений Уе = 1 ь и Уг = = Уь ~ = О. Пусть Я = (-1)»" ' = 21'„— 1 — случайный знак.
Рассмотрим статистику Я = Я + Я ег +. + Я е ы где и — случайная точка в периоде. а) Докажите, что Е Я = т/гУ, где Н = 2 — 1. Ь) Чему равно Е Яг? Предположите, что т < Н, [Указание. См, упр. 3 2.2-16.) с) Чему равнялись бы ЕЯ и ЕЯ~, будь Яг действительна случайными? 6) Предполагая, что т < /т', докажите равенство Е Я~ = т~/?у — 6В(?Ь'+ 1)/Х, где [(Уьыу'+г .. К+в-г)г = (Уг+Л1+г Уг+г-г)г[ (т — 3) . е«'г< и е) Оцените В в частном случае, рассмотренном в упр. 31: т = 79 и У = (К,-м + 1я ы) шоб 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
