[См. статьи Дж. Л. Дуба и М. Д. Донскера (J. L. Doob and М. D. Donsker, Annals Math. Stat. 20 (1949), 393-403 и 23 (1952), 277-281). Их подход, вообще говоря, рассматривается как наиболее перспективный для изучения КС-критериев.]

7. Положим j = п в (13), чтобы увидеть, что никогда не может быть отрицательной и что максимальное значение, которое она может принимать, равно \/п. Аналогично, положив J = 1, можно произвести подобные наблюдения над К~ .

8. Новая КС-статистика была подсчитана для 20 наблюдений. Распределение использовалось как F{x), когда КС-статистика была подсчитана.

9. Идея ошибочна, так как все наблюдения должны быть независимыми. Между статистиками и К~, полученными из тех же данных, существует связь, поэтому каждую проверку нужно выполнять отдельно. (Большое значение одной из статистик приводит к малому значению другой.) Подобным образом данные на рис. 2 и 5, на которых показаны 15 результатов проверки, не являются 15-ю независимыми наблюдениями, поскольку критерий "максимум-5" не зависит от критерия "максимум-4". Три критерия каждого горизонтального ряда являются независимыми (так как они применялись к разным частям последовательности), но пять критериев в столбцах являются в некоторой степени коррелированными. В результате 95-процентные и другие вероятностные уровни, которые используются в одном критерии, нельзя применять к целой группе критериев, основанных на тех же данных. Мораль такова: генератор случайных чисел можно "проверять" с помощью нескольких критериев, таких как частотный критерий, критерий по максимуму и критерий монотонности, но набор данных, полученных после подсчета различных критериев, нельзя рассматривать как материал для новой проверки, поскольку сами критерии могут быть зависимыми. Статистики А+ и К~ следует рассматривать как два различных критерия. Хороший датчик случайных чисел выдержит проверку в обоих случаях.

10. Каждое У, и пр, дублируется, поэтому числитель (6) умножается на 4, а знаменатель- только на 2. В итоге новое значение V вдвое больше старого.

11. Эмпирическая функция распределения остается той же; значения и К~ умножаются на •У2.

12. Пусть Z, = (У, - nq,)/\/nql. Значение V равно п, умноженному на

-Ps + s/qs/nZf 1р,.

4 = 1

Это последнее выражение отделено от О, когда п возрастает (так как Zn* ограничено с вероятностью 1). Следовательно, Убудет возрастать и принимать совершенно невероятные значения при предположении, что вероятности равны р,.

Для КС-критерия предположим, что F{x) - предполагаемое распределение, а G(i) - истинное распределение, и пусть h = maxG(i) - F{x)\. Возьмем n достаточно большим, чтобы неравенство \Fn{x) - G{x)\ > /i/2 выполнялось с очень малой вероятностью; тогда F„(i) - F{x)\ будет невероятно большим для гипотетического распределения F{x).

13. ("max" на самом деле следовало бы заменить обозначением "sup", так как здесь имеется в виду наименьшая верхняя граница. Однако обозначение "max" использовалось, чтобы не смущать читателей, которые не знакомы с обозначением "sup".) Предположим для удобства, что Ао = -оо, Х„+х = +оо. Если Xj <х < Xj+x, то Fn{x) = j/n, поэтому max(F„(i) - F{x)) = j/n - F{Xj) и max(F(i) - Fn{x)) = F{Xj+x) - j/n на данном интервале. Когда j изменяется от О до п, рассматриваем все действительные значения х. Это

доказывает равенства

/f+ = V max U-F{Xj));

0<]<n\n J

K- = V, max (f{Xj) -

Данные равенства эквивалентны (13), так как добавочный член под знаком максимума не положителен и изменен в соответствии с упр. 7.

14. Логарифм левой части требуемого равенства можно записать как

-D.b(i+).ii„(2™,-l:i.p.-l;,„(,.-)+o(i),

и эта величина (с использованием разложения 1п(1 + Zs/y/nps) и того, что Z,\fnpl = 0), примет вид

- Е + 1"(2,гп) - \ 1п(р:... р.) + О (-) .

15. Соответствующий якобиан легко вычислить: (i) вынеся множитель г"~ из определителя, (ii) разложив полученный определитель по алгебраическим дополнениям строки, содержащей "cos Q\ - sin Q\ О ... О" (каждый детерминант алгебраического дополнения может быть вычислен по индукции) и (iii) вспомнив, что sin в\ Л- cos в\ = \.

16. /"exp(-g + ..)du=у.-+(;) + C<-i+• • )

Последний интеграл равен

Если все это собрать вместе, то будет получено

Г(х + 1) -v/2y "+v 3) + 0(J-

Если положить г%/ = Хр и записать

met/2 = x+zV2x+y, можно найти у, а именно - у = (l-f 2)-f 0(l/v/i), что согласуется

с анализом, приведенным выше. Поэтому решение имеет вид t = и + 2у/йг + - + 0{1/).

17. (а) Сделать замену переменных Xj 4- Xj + t. j,

(b) Индукция по n; по определению Рпо{х - t) = P(„ i)o(i„ - t) dx„.

(c) Левая часть равна

/ di„ ... / dxk+i, умноженному на / dxk / dxjt-i ... / dii.

Jn Jfc-(-l Jt Jt Jt

(d) Из (b) и (с) получим Pn)fc(x) =У2 ~ \a: + t - n). Числитель

- r! (n - г)!

в(24)равенР„<](")-

18. Можно предположить, что F{x) = х для О < i < 1, как отмечено в выражении (24) раздела. Если О < Xi < • • • < Х„ < 1, то пусть Zj = 1 - Xn+i-j- Справедливы неравенства О < Zi < < Z„ < 1, и К:, определенное для Xi,...,Xn, равно К~, определенному для Zi,..., Zn. Эти симметричные соотношения дают взаимно однозначное соответствие между множествами с одним и тем же числом элементов, для которых и К попадают в одну и ту же область.

20. Например, член порядка 0(1/п) равен -(!« - s)/n + 0(n~). Полное разложение было получено X. А. Ловерье (Н. А. Lauwerier, Zeitschrift fiir Wahrscheinlichkeitstheorie und verwandte Gebiete 2 (1963), 61-68).

23. Пусть m - некоторое число > п. (a) Если [TnF(A,)J = [mF(Xj)\ и i > j, то i/n - FiXi) > j/n - F{Xj). (b) Начните с Uk = 1.0, bk = 0.0 и Cfc = 0 для 0 < A; < m. Затем для каждого наблюдения Xj выполните такие операции: присвойте Y 4- F{Xj), к 4- L"iFj, йк 4- тш(ад,К), bk 4- max(6jt,F), с* 4- cjt + 1. (Предположим, что F{Xj) < 1, поэтому к < т.) Затем присвойте j 4- О, г"*" 4- г~ 4- О и для к = О, 1, m-1 (в таком порядке) поступайте следующим образом, каким бы ни было cjt > 0: присвойте г~ 4- max(r",afc - j/n), j 4- j + cjt, r"*" 4- max(r+, j/n - bk). Окончательно присвойте 4- л/пг*, К~ 4- л/пг~. Требуемое время равно O(m-l-n), и точное значение п должно быть известно заранее. (Если оценка {к + \)/т использована для Uk и bk так, что только значения cjt действительно вычислены для каждого /г, получим оценки для Кп и Ай в пределах \\fn/m, даже когда т < п.) [АСМ Trans. Math. Software 3 (1977), 60-64.]

25. (а) Так как dj = E(Y:"k=, UikXk ЕГ=1 <Jii) = ELi ikajk, то С = AA".

(b) Рассмотрим сингулярное разложение А = UDV, где U и V - ортогональные матрицы размера тХтипхпиВ - матрица размера m х п с членами dij = [i =j]crj; сингулярные значения ctj все положительны. [См., например, работу Голуба и Ван Лоана (Golub and Van Loan, Matrix Computations (1996), §2.5.3.] Если CCC = C, то SBS = S, где S = DD и В = UCU. Таким образом, Sij = [i = j]crj, где мы считаем, что (T„+i = • • = om = О и Sij = = crfajbij. Следовательно, bij = [i = j]/crj, если

hj n, и получим, что DBD - это единичная матрица размера пхп. Пусть У = {Yi - x,...,Ym - .т)" и X = (А:,...,А„). Из этого след>-ет, что W = FCF = ХАСАХ = XVDBDVX = АА.

РАЗДЕЛ 3.3.2

1. Наблюдения в х-критерии должны быть независимыми. Во второй последовательности соседние наблюдения, очевидно, зависимы, так как вторая компонента одной пары равна первой компоненте следующей пары.

2. Образуйте t-мерную строку {Yjt,... ,Yjt+t-i) для О < j < п и подсчитайте, сколько раз эти строки совпадают с любыми заданными. Примените х-критерий с А; = d и вероятностью причисления к каждой категории 1/d. Количество наблюдений п должно быть равно по крайней мере 5d.

3. Вероятность того, что точно j значений проверены, а именно - вероятность того, что 17,-1 является п-м элементом, лежащим в области а < Uj-i < 0, как легко видеть, равна

q:;)p"(i-p)-".

Ее можно вычислить, подсчитав возможные комбинации из остальных п - 1 элементов и определив вероятность такой схемы. Производящая функция равна G{z) = {pz/{l - (1 -p)z))", что имеет смысл, так как данное распределение является п-кратной