сверткой того же распределения при п = 1. Следовательно, среднее и дисперсия пропорциональны п. Сейчас можно легко найти достаточное для проверки число Uj и его характеристики (min п, ave (среднее) п/р, max оо, dev (стандартное отклонение) у/п{\ -р)/р)-Более детальное обсуждение этого вероятностного распределения, когда п = 1, приводится в ответе к упр. 3.4.1-17 (см. также значительно более общие результаты в упр. 2.3.4.2-26).

4. Вероятность интервала длиной > г равна вероятности того, что г последовательных Uj лежат вне заданной области, а именно (1 - рУ Вероятность того, что длина интервала г точно равна вероятности того, что длина интервала > г минус вероятность, что длина интервала > (г -Ь 1).

5. Поскольку Л стремится к бесконечности, п (с вероятностью 1) также стремится к бесконечности, поэтому данный критерий точно такой же, как критерий интервалов, описанный в разделе, если исключить длины очень больших интервалов. И критерий интервалов данного раздела, определенно, имеет асимптотически х-распределение, поскольку длина каждого интервала не зависит от длин других интервалов. [Замечание. Вполне завершенное доказательство этого результата приведено в работе Е. Бофингер и В. Дж. Бо-фингер (Е. Bofinger and V. J. Bofinger Annals Math. Stat. 32 (1961), 524-534). Эта работа заслуживает внимания, потому что в ней обсуждается несколько интересных вариантов критерия интервалов. Авторы показали, например, что величина

0<г<(

не приближается к ;:-распределению, хотя эта статистика (другие авторы относили ее к "строгим" критериям) ранее считалась более "сильным" критерием, поскольку Np равно ожидаемому значению п.]

7. 5, 3, 5, 6, 5, 5, 4.

8. См. упр. 10 с w = d.

9. (Замените d на w на шагах Cl и С4.) Тогда получим

d{d- l).d-w + l) d

{Yr - {Np)pry (Np)pr

=--U-1

для w <r <t\

d\ (\\t-\\ 1 ft-l-iN

10. Как и в упр. 3, на самом деле нужно рассмотреть только случай для п - \. Производящая функция для вероятности того, что множество купонов имеет длину г, выглядит следующим образом:

" = (dE{I l}() =" T)j-\d-{l-l))j-

Это следует из предыдущего упражнения и формулы 1.2.9-(28). Среднее и дисперсию легко подсчитать, используя теорему 1.2.10А и упр. 3.4.1-17. Найдем, что

среднее(С) = ш -f - l) + ... + ij = (Я - Я „) = р;

дисперсия(С) = й(Я<> - Hlj - d(Hi - Щ-) = <т\

Число проверенных Uj для набора множеств купонов повторяется п раз, поэтому его характеристики равны (min wn, ave (среднее) рп, шах оо, dev (стандартное отклонение) crv).

11. 1298536704.

12. Алгоритм R {Данные для критерия монотонности).

R1. [Инициализация.] Присвоить j i--1 и присвоить COUNT[l] 4- C0UNT[2] •(-•••«-

C0UNT[6] 4- 0. Также присвоить Un Un-i для удобства по завершении работы алгоритма.

R2. [Присвоить г значение 0.] Присвоить г 4- 0.

R3. [Будет ли Uj < Uj+i7] Увеличить г и j на 1. Если Uj < Uj+i, повторить этот шаг.

R4. [Регистрация длины.] Если г > 6, увеличить C0UNT[6] на 1, иначе увеличить COUNT[r] на 1.

R5. [Конец?] Если j < п - 1, вернуться к шагу R2.

13. Существует {р + q + 1)(р) способов получения Ui-i Ui < < Ui+p-i Ui+p < ••• < Ui+p+q-i. Вычтите Cpl) способов, в которых Ui-i < Ui, и вычтите Cl*) Способов, в которых Ui+p-i < Ui+p. Затем добавьте 1 для способа, когда выполняются оба неравенства Ui-i < Ui и Ui+p-i < Ui+p, так как этот способ вычитался дважды. (Это частный случай принципа включения-исключения, который подробно рассматривается в разделе 1.3.3.)

14. Серия длиной г встречается с вероятностью 1/г! - 1/(г -I-1)!, если предположить, что Uj различны. Поэтому используем рг = 1/г! - 1/(г + 1)! для г < t и pt = 1/t! - для серий длиной > (.

15. Это всегда верно для F{X), когда F непрерывна и X имеет распределение F (см. замечание, следующее за формулой 3.3.1-(23)).

16. (а) Zjt = max(Zj(f i), Zy+i)(f i)). Если Zjt-i) занесено в память, то достаточно просто преобразовать этот массив в множество Zjt без использования дополнительной памяти. (Ь) В его "улучшении" каждое Vk должно на самом деле иметь требуемое распределение, но наблюдения не являются независимыми при больших значениях Vk. Действительно, когда Uj - относительно большая величина, то все Zjt, ..., Zj-t+i)t будут равны Uj, так что возможен эффект повторения тех же данных ( раз (У будет умножаться на t, как в упр. 3.3.1-10).

17. (Ь) Согласно тождеству Вине (Binet) разность равна I3o<it<j<n(t ~ UjVk), и поэтому она неотрицательна, (с) Поэтому, если D" = N, получим UkVj - UjVl = О для всех пар j, к. Осюда следует, что матрица

[и;, и[ ... ип-Л \vi Vi ... v:, j

имеет ранг < 2, поэтому ее строки линейно зависимы. (Более элементарное доказательство можно получить, если учесть тот факт, что равенство UqVJ -UjVq = О для 1 < j < п влечет существование постоянных а, /3, таких, что aUj + PVJ = О для всех j при условии, что Uq и Vq - не нули; последний случай может быть исключен в результате перенумерации.)

18. (а) Числитель равен-(f/o - I/i), знаменатель равен (f/o - I/i). (b) Числитель в этом

случае равен -{Uq + U? + Ul - UoUi - U1U2 - U2U0), а знаменатель - 2{Uo +----I/2I/0).

(с) Знаменатель всегда равен ylo<j<k<nii ~i)> что следует из упр. 1.2.3-30 или 1.2.3-31.

19. Сформулированный результат на самом деле имеет место для любого симметричного совместного распределения Uo, ..., Un-i (распределение не меняется при перестановках). Пусть Si = Uo + --- + Un-i,S2=-Ui + --- + U-i,X = UoUi + --- + Un-2Un-i+Un-iUoHD = nS2 - S\. Также пусть Е/(I/o,...,Лг-О обозначает ожидаемое значение f{Uo,. . ,Un-i) при условии, что D ф 0. Так как D - симметричная функция, Е f{Uo, . ,Un-i) =

[/р(0),..., I/p(„ i)) для всех перестановок р из {О,..., п - 1}. Следовательно, Е S2ID = JllD, Esf/D = п{п - l)E{UoUi/D) + nEUg/D и EX/D = nE{UoUi/D). Это влечет

E/(I/p, nEUl

равенство 1 = E {7182 - Sf)/D = -(n - 1) E (nX - SD/D. (Строго говоря, E 52/D и E ЗЦО могут быть бесконечными, поэтому необходимо позаботиться о том, чтобы можно было работать только с линейными комбинациями ожидаемых величин, которые, как известно, существуют.)

20. Пусть Ецп, E2U, Е22, Е31 и Е4, означают соответственно величины E{UqUiU2UzID"), EiUiUiU2/D), E{USU/D), E{UiUi/D), E{U/D). Тогда выполняется ESJ/D = n(n - 1)£22 + nEi, E(S2S?/D) = n(n - l)(n - 2)E2u + n{n - 1)£22 + 2n(n - 1)£з1 + ПЕ4, ESt/D = п(п-1){п-2){п-3)Еии+6п{п--1){п-2)Е2и+Щп-1)Е22+4п{п-1)Ез1+пЕ4, EXD = п{п-3)Еии+2пЕ2п+пЕ22, E{XS!/D) = h(n - 2)(n - 3)£;im+5n(n-2)£;2n + 2n£22 + 2п£з1, E{{Uo - Ui)yD) = 6E22 - 8E31 + 2E4, откуда следует первый результат.

Пусть S = a((lnn)/n)3, М = а/2 + 1/3 и m = TVl Если разделить область распределения на m равновероятных частей, то можно показать, что в каждой части содержится число точек, равное числу, лежащему между nS(l-S) и nS{l+S) с вероятностью > 1 - 0{п~). Для этого нужно использовать неравенства для хвостов 1.2.10-(24) и (25). Следовательно, если распределение равномерно, D = jn(l + 0(S)), по крайней мере для этих вероятностей. Если D не из этой области, то О < (С/о - Ui)*/D < 1. Так как Е((1/о - I/i)") = /J(x - y)Uxdy = , можно получить, что E{{Uo - Ui/D) = f n-(l + 0(<J)) + 0(n~).

Замечание. Пусть N - числитель в (23). В. Дж. Диксон (W. J. Dixon) доказал, что когда все переменные имеют нормальное распределение, ожидаемое значение величины

(1 - 2г - 2«;)/(1 - 2г + - 2zy - 4w У" + 0(«;").

Дифференцируя по w и интегрируя по г, он нашел моменты E(iV/Z))*~ = {-У/(п- У,

E(iV/D)* =: {+У/{п + У, когда п > 2А;. В частности, дисперсия в этом случае точно равна 1/(п + 1) - 1/(п - 1) [Annals of Math. Stat. 15 (1944), 119-144.]

21. Последовательные значения c-i = s - 1 на шаге Р2 равны 2, 3, 7, 6, 4, 2, 2, 1, 0; следовательно, / = 886862.

22. 1024 = 6! + 2 5! + 2 4! + 2 3! + 2 • 2! + О • 1!, поэтому нужно, чтобы последовательные значения s - 1 на шаге Р2 были равны О, О, О, 1, 2, 2, 2, 2, 0. Если теперь идти в обратном направлении, то получится перестановка (9,6,5, 2, 3,4, 0,1,7, 8).

23. Пусть Pixu- ,xt) = ir En-oiCn, ,Y;+t-i) = (xi,.. .,xt)]. Тогда

Q{xi,...,xt)= P{yi,...,yt)P{{xi-yi)modd, ...,{xt-yt)inodd)

(bi.....vt)

или, более компактно, Q{x) = P{y)P{x - у). Следовательно, используя общее нера-венство (EXf < EX получим EAQi) У Е.(Е„ Р(у)(Р( - у) - d")) <

Е,P{y){p{x-y)-d-r = Е„Piy)i:APi)-d-r = ЕЛР(х)-а-Г. [См.работу

G. Marsaglia, Сошр. Sci. and Statistics: Symp. on tiie Interface 16 (1984), 5-6. Результат интересен только тогда, когда d < 2А, так как каждое Р{х) кратно 1/А.]

24. Запишите к : а и а : к для первых к и последних к элементов цепочки а. Пусть K{a,j3) = [а = /3]/Р(а) и пусть С - это матрица d х d с элементами Cq = К{а,0) - K{t - 1 : а, t - 1 : /3). Пусть С - ковариационная матрица случайных величин N{a) для \а\ = t, деленная на п. Эти величины подчинены ограничению Еа=о (-*) ~ Еа=о (*-) для каждой из d~ цепочек а, но все другие линейные ограничения вытекают из этого