вместо каждого t-ro члена. Но когда он применил х-критерий в случае одинаковых распределений к величинам Vf, получились чрезмерно высокие значения статистики V, которые увеличивались при возрастании t. Почему так произошло?

17. [МЯЗ] Даны любые числа 1/о,..., t/„ -1, Vo,..., Vn -1 Пусть их средние значения равны

0<к<п 0<к<п

а) Пусть Uk = - й, Vl = Vk - v. Покажите, что коэффициент корреляции С, определенный в (24), равен

0<к<п I у 0<fc<n у 4<к<п

b) Пусть с = NjD, где N и D - числитель и знаменатель выражения из п. (а). Покажите, что < D, отсюда -1 < С < 1. Получите формулы для разности - . [Указание. См. упр. 1.2.3-30.]

c) Если С = ±1, покажите, что aUk + fiVk = т, О < к < п, для некоторых не всех равных нулю постоянных а, 0 и т.

18. [МЯО] (а) Покажите, что, если п = 2, сериальный коэффициент корреляции (23) всегда равен -1 (если знаменатель не равен нулю). (Ь) Аналогично покажите, что, когда п = 3, сериальный коэффициент корреляции всегда равен - . (с) Покажите, что знаменатель в (23) равен нулю тогда и только тогда, когда Uo = Ui = • • =

19. [МЗО] (Дж. П. Батлер (J. Р. Butler).) Пусть Uo, ..., Un-i - независимые одинаково распределенные случайные величины. Докажите, что ожидаемое значение сериального коэффициента корреляции (23), среднее по всем случаям с ненулевым знаменателем, равно -1/(п-1).

20. [НМ41] Продолжая предыдущее упражнение, докажите, что дисперсия (23) равна пУ{п - 1)*(гг - 2) - nE{{Uo - Ui)yD)/2{n - 2), где D - знаменатель из (23), а Е - ожидаемое значение по всем случаям, когда D фО. Чему равно асимптотическое значение E((t/o - Ui)*/D), когда каждое Uj равномерно распределено?

21. [19] Какие значения / будут вычислены алгоритмом Р, если применить его к перестановкам (1,2,9,8,5,3,6,7,0,4)?

22. [18] Для какой перестановки {0,1,2,3,4,5, б, 7,8,9} алгоритм Р выдаст значение / = 1024?

23. [М22] Пусть (Уп) и (У1) - последовательности целых чисел, имеющие периоды длиной А и А соответственно с О < У„,У < d. Пусть также Zn = {Уп + Уп+г) modd, где г выбрано наудачу между О и А - 1. Покажите, что (Zn) удовлетворяет t-мерному критерию серий по крайней мере так же, как (Уп), в следующем смысле. Пусть P{xi,... ,Xt) и Q{xi, ...,Xt) - вероятности того, что t-мерная строка (xi,..., Xt) появляется в (У„) и {Zn):

Р{хг,.. ,xt)=jYl К"- • • -"+-0 = (ь ... ,Х()];

п=0 Л-1Л-1

Q{xi,...,Xt) = -£Yl [{Zn,...,Zn+i-l) = {Xl,...,Xt)]. n=0 г=0

Тогда {Q{xu...,xt)-d-) < {P{xu---,xt)-d-)\

{"l....."l) (il.....xt)

24. [НМ35] (Дж. Марсалья (G. Marsaglia).) Покажите, что критерий серий для п пересекающихся «-мерных строк {Yi,Y2,...,Yt), (У2, Уз, •. ,Yi+i), (Уп, Уп+i, • • •, Уг+п-О может быть осуществлен следующим образом. Для каждой цепочки а = ai ... От с О < а; < d положим N{a) равным числу случаев, когда а появляется как подцепочка У1, Уг,..., Уп, Уп+1,..., У„+т-1, и пусть Р(а) = P(oi)... P(am) - вероятность того, что а появляется в любом заданном положении. Разные цифры могут появляться с различными вероятностями Р(0), Р(1), ..., P{d - 1). Подсчитаем статистику

1ЛГИ 1 у> ЛГ(а) п.А Р(а) п.

Тогда V должно иметь -распределение с - степенями свободы, когда п большое. [Указание. Используйте упр. 3.3.1-25.]

25. [М46] Почему выполняется приближенное равенство CidCi яа -6Cf S где Ci и Сг - матрицы, определенные в (22)?

26. [НМЗО] Пусть Ui,U2, ... ,Un независимы и равномерно распределены в [О .. 1) и пусть < U(2) < • • < U(n) - их значения после сортировки. Определите разности Si =

U(2)-U(i), Sn-i = Щп)-Щп-1), Sn = t/(i)+l-[/(„) и рассортируйте их 5(i) < • • • < 5(„), как в критерии промежутков между днями рождений. В следующих вычислениях удобно использовать обозначение х" в качестве сокращенной записи выражения х"[х >0].

a) Пусть даны любые действительные числа si, S2, , Sn- Докажите, что вероятность того, что неравенства Si > 81 и S2 > 82, , Sn > 8„ выполняются одновременно, равна (1 - «1 - S2-----вп)+~.

b) Докажите, следовательно, что наименьшая разность S(i) будет < s с вероятностью

1-(1-п5);-1.

c) Какова функция распределения Fk(s) - Рг(5() < s) для \ <к <п1 А) Вычислите среднее и дисперсию каждого S(k)-

► 27. [НМ26] [Итерированные разности.) В обозначениях предыдущего упражнения покажите, что числа Sl = п5(1), 52 = (п - 1)(5(2) - 5(i)),..., 5 = 1(5(„) - 5(„ i)) имеют то же самое совместное вероятностное распределение, что и первоначальные разности .., Sn п равномерно распределенных случайных величин. Можно упорядочить их в виде 5(1) < • • • < и повторить это преобразование, чтобы получить еще одно множество случайных разностей 5",..., 5J, и т. д. Каждое последующее множество разностей 5/*\..., 5п* может быть также проверено по критерию Колмогорова-Смирнова, где

<i-KЫтM-•---)•

«.-..=„»(5."4....<>-i)

Детально проверьте преобразование {Si,..., 5„) в (51,..., 5J,) для п = 2 и п = 3. Объясните, почему постоянное повторение этого процесса в конечном счете приведет к неудаче, если его применять к компьютерному генератору чисел с ограниченной точностью. (Один из методов сравнения генераторов случайных чисел состоит в наблюдении, как долго они проживут при таких мучительных испытаниях.)

28. [М26] Пусть Ьптз{т) - число п-мерных строк {yi,... ,Уп) с О < yj < т, имеющих точно г равных разностей и s нулевых разностей. Таким образом, вероятность того, что R = г, ъ критерии промежутков между днями рождений равна JIio "«(ш)/"»"-Также пусть р„{т) - число разбиений m на не более чем п частей (упр. 5.1.1-15). (а) Выразите ЬпОо{т) в терминах разбиений. [Указание. Рассмотрите случай с малыми m и п.]

(b) Покажите, что существует простое соотношение между bnr-s{m) и b(„ s)(r+i-s)o("i), когда S > 0. (с) Выведите точную формулу вероятности того, что разности равны.

29. [М35] Продолжая упр. 28, найдите простое выражение для производящих функций bnr(z) = I3m>o bnro{m)z"4m, когда г = О, 1 и 2.

30. [HMl] Продолжая предыдущее упражнение, докажите, что если т = rCja, то

, , т"-е° Л \Ъо? 169а + 2016а - 1728а - 41472Q -з\

"(")=;!(ГГТ)Т(1- +-1б5888;5-+(" )j

для фиксированного а при п -> оо. Найдите аналогичную формулу для gn(m) - числа разбиений m на п •различных положительных частей. Выведите с точностью до 0(\/п) асимптотические вероятности того, что в критерии промежутков между днями рождений R равно О, 1 и 2.

► 31. [М21] Рекуррентное соотношение Y„ = (Уп-24 -t-Vn-ss) mod 2, описывающее младший значимый разряд генератора Фибоначчи с запаздыванием 3.2.2-(7), как и второй младший значащий разряд 3.2.2-(7), как известно, имеет период длиной 2 - 1; следовательно, каждая возможная не равная нулю конфигурация двоичных разрядов {Y„,Yn-\-i,- . ,Уп+54) появляется одинаково часто. Тем не менее докажите, что если генерировать 79 последовательных двоичных разрядов Уп,..., Уп+78, начиная со случайной точки в периоде, вероятность, что там будет больше единиц, чем нулей, больше 51%. Если использовать такие двоичные разряды для определения "случайного блуждания", состоящего в том, что точка движется вправо, когда двоичный разряд содержит 1, и влево, когда двоичный разряд содержит О, то в большинстве случаев будем заканчивать блуждание справа от

нашей начальной точки. [Указание. Найдите производящую функцию IClloPC" -----

Уп+78 = А) г*.]

32. [М20] Определите, верно ли следующее: если X и У - независимые одинаково распределенные случайные величины со средним О и если для них более вероятно быть положительными, чем отрицательными, то X 4- У более вероятно будет положительным, чем отрицательным.

33. [НМ32] Найдите асимптотическое значение вероятности того, что к + I последовательных двоичных разрядов, генерируемых рекуррентным соотношением У„ = (Уп-( 4-Yn-k) mod 2, имеют больше единиц, чем нулей, когда А; > 2/ и длина периода этой рекуррентной последовательности равна 2* - 1. Предполагается, что А; большое.

34. [НМ29] Объясните, как оценить среднее и дисперсию числа двухбуквенных комбинаций, не появляющихся последовательно в случайной строке длиной п в т-буквенном алфавите. Предположим, что тп большое и п « 2т.

► 35. [НМ32] (Дж. Н. Линдхолм (J. Н. Lindholm), 1968.) Предположим, что случайные двоичные разряды (У„) генерируются с помощью рекуррентного соотношения

Уп = (aiYn-i 4- агУп-г 4- • • • 4- а*У„ к) mod 2

для некоторого набора ai, ..., с периодом длиной 2* - 1. Начнем со значений Уо = 1 и У = •.. = Yk-i = 0. Пусть Z„ = (-l)"" = 2Уп - 1 - случайный знак. Рассмотрим статистику Sm - Zn + Z„+i +----h Zn+m-1, где n - случайная точка в периоде.

a) Докажите, что Е Sm = m/N, где /V = 2* - 1.

b) Чему равно ES? Предположите, что тп < N. [Указание. См. упр. 3.2.2-16.]

c) Чему равнялись бы Е Sm и Е , будь Zj действительно случайными?

d) Предполагая, что тп < N, докажите равенство Е = m/N - 6B{N + l)/N, где

В= J2 [{Y+iYi+2...Y,+k-i)2 = {Yj+iYj+2...Yj+k-i)2]{m-j).

0<i<i<m