15. Пусть для s,t > О

Pst - Pr(Xn-2t-3 =Xn-2t~2 фХп-2Ь-1 Ф Ф Хп-\ И Хп = • • • = Xn+s Ф Xn+s + l)

= 2-2.-3.

для t > о пусть qt = PT{Xn-2t-2 = Xn-2t-i Ф Ф Xn-i) = 2~~. Согласно упр. 7 Рг(Хп не начало множества купонов) = Et>o5t = §> ¥х{Хп начало множества купонов длиной s + 2) = Et>oP«* ~ 5 2~~. Поступим, как в упр. 13.

16. (Решение Р. П. Стенли (R. Р. Stanley).) Всякий раз, когда появляется подпоследовательность 5 = (Ь - 1), (Ь - 2), ..., 1, О, О, 1, ..., (Ь - 2), (Ь - 1), множество купонов должно закончиться в правой части S, так как некоторое множество купонов находится полностью в первой половине S. Вычислим вероятность того, что множество купонов начинается с позиции п, используя вероятность, что последнее предшествующее появление S произошло на позиции п - 1, п - 2 и т. д., как в упр. 15.

18. Поступите, как в доказательстве теоремы А, чтобы вычислить Рг и Рг.

19. (Решение Т. Герцога (Т. Herzog).) Да. Например, примените упр. 33 к последовательности (t/[„/2j), когда {Un) удовлетворяет определению R4 (или даже его слабой версии).

20. (а) 2 и . (Когда п возрастает, разделяем In пополам).

(b) Каждая новая точка разделяет один интервал на две части. Допустим, р равно max2l((n + fe);i!)j. Тогда 1 = ELi < ИГЛ nl < EVo р/(" + fe) = р1п2 + 0(l/n). Так что для бесконечного множества тп выполняется mlm > 1/1п2 -Ь 0(1/т).

(c) Чтобы проверить указание, предположим, что Z.* выбирается из интервала с конечными точками Um и Um, и положим ак = max(m - п,т - п, 1). Тогда, если р = min"=„+i mZ<r\ 1 = Elli 4п > Elli р/(" + «О > 2pELi V(" + к); следовательно, 2р < 1/(Я2„ - Нп) = 1/\п2 + 0{1/п).

(d) Мы получим {li\ /1")) = (Ig nil, ig п±2,..., ig так как (n + 1)-я точка всегда делит наибольший интервал на интервалы длиной Ig и Ig . [Indagationes Math. 11 (1949), 14-17.]

21. (а) Нет! Мы получим PF(FF„ < 5) limsup„ i/([2"-i/l)/[2"-i/l = 2 - л/2 и Рг(Ж„ < 5) < liminf„ .«,i/(2")/2" = л/2 - 1, поскольку i/([2"-/l) = i/(2") = ELo(2+-2*)+0(n).

(b,c) См. Indagationes Math. 40 (1978), 527-541.

22. Если последовательность fe-распределена, то предел равен нулю согласно теореме В и значению интеграла. Обратно, заметим, что если f{xi,. ..,Хк) разлагается в абсолютно сходящийся ряд Фурье

f{xi,...,Xk)= Е a(ci,... ,cfc)exp(27rj(cixi + • • •+cjtXfc)),

-oo<ci.....cj,<oo

TO мы получим limN-ioo T,o<n<N f{Un,-- .,Un+k-i) = a(0,... ,0) +6r, где

бг< E \a{cu...,Ck)\,

max{ci.....\ck\)>r

так что бг можно сделать произвольно малым. Следовательно, предел равен

а(0,...,0)=/ • / f{xi,...,Xk)dxi...dxk Jo Jo

и (8) выполняется для всех достаточно гладких функций /. Осталось доказать, что функцию в (9) можно аппроксимировать гладкими функциями с любой требуемой точностью.

23. (а) Немедленно следует из упр. 22. (Ь) Аналогичным путем используйте дискретное преобразование Фурье; см. D. Е. Knuth, АММ 75 (1968), 260-264.

24. (а) Пусть с - любое не равное нулю целое число. Покажем согласно упр. 22, что

1 - N

О при N оо.

Это выполняется потому, что если К - любое положительное целое число, то получим Ек=о Т.п=о 6""+ = к Zo е*" + 0{К). Следовательно, по неравенству Коши

N-lK-l

n=0 Jfc=0

fc=0

(b) Когда d = 1, to из упр. 22 следует, что ((ащ-Ьао) mod 1) равнораспределена тогда и только тогда, когда ах - иррациональное число. При d > 1 можно воспользоваться (а) и индукцией по d. [Acta Math. 56 (1931), 373-456. Результат в (b) ранее был получен более сложным методом Г. Вэйлом (Н. Weyl, Nachr. Gesellschaft der Wiss. Gottingen, Math.-Phys. Kl. (1914), 234-244). С помощью подобных аргументов доказывается, что полиномиальная последовательность равнораспределена, если по крайней мере один из коэффициентов Qd, ..., qi - иррациональное число.]

25. Если последовательность равнораспределена, то знаменатель в следствии S приближается к , а числитель - к значению, полученному в этом упражнении.

26. См. Math. Сотр. 17 (1963), 50-54. [Рассмотрим также следующий пример А. Дж. Во-термена (А. G. Waterman): пусть {Un) - равнораспределенная [О .. 1)-последовательность и {Х„) - оо-распределенная двоичная последовательность. Пусть Vn = или 1 - fv/S] соответственно, когда А„ равно О или 1. Тогда (V„) равнораспределена и белая, однако Pr(Vn = Vn+i) = \. Пусть Wn - (Уп - en)modl, где {tn) - любая убывающая монотонно к О последовательность, тогда (Wn) равнораспределена и белая, однако

Рг(Жп < Wn + x) = 1.]

28. Пусть {Un) оо-распределена. Рассмотрите последовательность {\{Хп + Un))- Она 3-распределена, если использовать тот факт, что ([/„) (16, 3)-распределена.

29. Если X = xiX2...xt - любое двоичное число, то можно рассмотреть число ix{n) случаев, когда Хр ... Ap+t-i = х, где 1 < р < п и р четное. Аналогично пусть v°{n) - число случаев, когда р нечетное. Пусть v{n) + {п) = Vx{n). Тогда

где Ui в этих суммах имеют 2к нижних индексов, 2к - 1 из которых - звездочки (обозначающие, что по ним суммируют - каждая сумма берется по 2"" комбинаций нулей и единиц), и где "й" означает приближенное равенство (за исключением ощибки самое больщее 2к вследствие условий на концах). Поэтому находим, что

2ки{п) = 1 (Е.о.....(п) + • • + Е ......о(п)) - + О (i) ,

где X = х\... Х2к содержит г(ж) нулей на нечетных позициях и s{x) нулей на четных позициях. Согласно (2А;)-распределенности величина в скобках стремится к fe(2*~)/2" = к/2. Оставшаяся сумма, очевидно, максимальна, если v{n) = Vx{n), когда г(ж) > s{x), а Jxin) = О, когда г(ж) < s{x). Так что максимум правой части равен

l-„Ej-..C)C)A»»b4";)A-

0<з<г<к

Сейчас Рг(Х2п = 0) < limsup„ i/o(2n)/n. Таким образом, доказательство завершено. Заметим, что получено

е(;) С)= .->.»(";).

е(П(;)-*)-»"--»(":)-

30. Постройте диграф с 2* вершинами, обозначенными {Ехх... X2k-i) и {Oxi... X2k-i), где каждое Xj равно либо О, либо 1. Пусть 1 + f(xi,X2,... ,Х2к) - ориентированные ребра из {Exi ... X2k-i) к {0x2 Х2к), а 1 - f{xi,X2,..., Х2к) - ориентированные ребра, ведущие из {Охх. ..X2k-i) к {Ех2 Х2к), где f(xi,X2, . ,Х2к) = sign(xi - жг + жз - Ж4 + • • - Жг*). Мы обнаружим, что каждая вершина имеет столько же ребер, ведущих к ней, сколько ребер, ведущих от нее. Например, {Ехх . . Х2к-\) имеет 1 - /(О, Ж1,..., X2k-i) + 1 - /(1,Ж1,... ,Ж2*; 1) ведущих к ней ребер, 1 + f{xi,... ,Ж2*:-1,0) + 1 + /(ж1,... ,Ж2-1,1) ребер, ведущих от нее, и f(x,xx,...,X2k-\) = -/(жь ..., Ж2*-1,ж). Опустим все вершины, не имеющие путей, ведущих к ним либо исходящих из них, т. е. {Ехх .. .X2k-i), если /(0,Ж1,... ,Ж2*-1) = +1, или {0хх...Х2к-\), если /(1,Ж1,...,Ж2*-1) = -1. Полученный ориентированный граф является связным, так как мы можем добраться из любой вершины к (.Б 1010...1) и из этой точки - к любой требуемой вершине. Согласно теореме 2.3.4.2G существует циклический путь, проходящий через каждое ребро длиной 2*"", и можно предположить, что он начинается в вершине (£00... 0). Построим циклическую последовательность с Хх = = Х2к-\ = О и Xn+2k-i = Х2к, если п-е ребро - это путь из (.Бж1... Ж2*:-1) к {0x2...Х2к) ИЛИ ИЗ {Охх... Х2к-\) К {Ех2...Х2к). Например, граф для к = 2 показан на рис. А-5; ребра циклического пути пронумерованы от 1 до 32 и циклическая последовательность имеет вид

(00001000110010101001101110111110)(00001...).

Заметим, что в этой последовательности Рг(Х2п = ) - хё Очевидно, что последовательность (2А;)-распределена, так как каждая строка размерности (2fe) Ж1Ж2... Х2к появляется

1 + /(Ж1, . . . , Ж2к) + 1 - /(Ж1, . . . , Ж20 = 2

раз за цикл. Тот факт, что Рг(А2п = 0) имеет требуемое значение, вытекает из факта, что при этом построении достигается максимальное значение правой части равенства в доказательстве предыдущего упражнения.