19. [НМ48] Предложите критерий, аналогичный критерию Колмогорова-Смирнова, для применения к многомерным распределениям F{xi,... ,Хг) = Pr(Xi < xi,...,Xr < Xr). (Можете использовать такие процедуры, как, например, "критерий серий" (см. следующий раздел).)

20. [HM4I] Получите следующие члены асимптотического разложения для КС-распределения, продолжив (27).

21. [м4о] Хотя в разделе говорится, что КС-критерий может применяться только тогда, когда F{x) - непрерывная функция распределения, конечно, можно попытаться вычислить Ki и Кп , когда распределение имеет скачки. Проанализируйте возможное поведение АГ+ и Кп для различных разрывных распределений F{x). Сравните эффективность полученных статистических критериев с х-критерием на нескольких выборках случайных чисел.

22. [НМ.46] Исследуйте "подправленный" КС-критерий, предложенный в ответе к упр. 6.

23. [М22] (Т. Гонсалес (Т. Gonzalez), С. Сахни (S. Sahni) и В. Р. Франта (W. R. Pranta).) (а) Предположим, что максимальное значение в формуле (13) для КС-статистики Кп принимается для данного индекса j, когда [nF{Xj)] = к. Докажите, что F{Xj) = max {F{Xi) [nF(X<)J = к], (b) Напишите алгоритм для вычисления Кп и Кп за 0{п)

шагов (без сортировки).

► 24. [40] Проведите опыты с различными вероятностными распределениями {p,q,r) трех категорий, гдер+q+r = 1, вычисляя точное распределение х-статистики К для различных п и тем самым определяя, насколько точным является приближение х-распределения с двумя степенями свободы.

25. [НМ26] Предположим, что 1- = aijXj + щ для 1 < г < т, где Xi, ..., Хп -

независимые случайные величины со средним, равным нулю, и единичной дисперсией. Матрица А = (a<j) имеет ранг п.

a) Выразите ковариационную матрицу С = (cij), где dj = Е(У; - - т),ъ терминах матрицы А.

b) Докажите следующее: если С = (су) - любая матрица, такая, что ССС = С, то статистика

тп тп

= EE(-)«-w)co-

i=l 3 = 1

равна Xf + + Хп- [Следовательно, если Xj имеют нормальное распределение, W имеет х-распределение с п степенями свободы.]

Устойчивость среднего при бросании монеты определяется законом, ... который гарантирует, что вы не разоритесь сами, слишком много теряя, и не разорите своих оппонентов, слишком много выигрывая.

- ТОМ СТОППАРД (ТОМ STOPPARD), Розенкранц и Гилденстерн мертвы (1966)

3.3.2. Эмпирические критерии

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

способов применения; (b) теоретическое обоснование. (Читатель, не привыкший к математическим рассуждениям, может пропустить теоретические выкладки. С другой стороны, математически подготовленный читатель может найти приведенную теорию весьма интересной, даже если он никогда не собирается проверять генераторы случайных чисел, так как здесь вводятся некоторые понятия комбинаторики. Действительно, в этом разделе вводится несколько важных понятий, представляющих для нас интерес в связи с совершенно иными вопросами.) Каждый критерий применяется к последовательности

{Un) = Uo,Ui,U2,... (1)

действительных чисел, которые, как предполагается, независимы и равномерно распределены между О и 1. Некоторые из этих критериев предназначены непосредственно для целочисленных последовательностей, а не для последовательностей действительных чисел (1). В таком случае вместо нее используется вспомогательная последовательность

{Y„} = Yo,Yi,Y2,..., (2)

определенная правилом

Y„ = [dU„]. (3)

Это последовательность целых чисел, которые, как предполагается, независимы и одинаково распределены между О и d-1. (Иначе говоря, вероятность, что случайная величина примет значение к, к = О,... ,d - 1, равна 1/d. - Прим. ред.) Число d выбирается таким, чтобы его было удобно использовать в том либо ином смысле. Например, можно выбрать d = 64 = 2® на бинарном компьютере так, что F„ представляет шесть старших двоичных разрядов двоичного представления числа f7„. Значение d должно быть достаточно большим, чтобы критерий бьш значимым, но не настолько большим, чтобы критерий стал практически неприменимым.

Введенные выше обозначения t/„, г» и d будут использоваться в этом разделе, хотя значение d будет, вероятно, изменяться в различных критериях.

A. Критерий равномерности (критерий частот). Первое требование, предъявляемое к последовательности (1), состоит в том, что ее члены - это числа, равномерно распределенные между О и 1. Существует два способа проверить это.

(a) Использовать критерий Колмогорова-Смирнова с F(x) = х для О < х < 1.

(b) Использовать последовательность (2) вместо (1), где d - подходящее число, например 100 на десятичном либо 64 или 128 - на бинарном компьютере. Для каждого г, О < г < d, подсчитаем число случаев, когда Yj = г для О < j < п, а затем применим х-критерий, принимая А; = d и вероятности ps = 1/d для каждой категории.

Описание и обоснование этих критериев приведено в разделе 3.3.1.

B. Критерий серий. Более общее требование к последовательности состоит в том, чтобы пары последовательных чисел были равномерно распределены независимым образом. В конечном счете Солнце восходит так же часто, как и заходит, но это не делает его движение случайным.

В критерии серий просто подсчитываем число случаев, когда пара {Y2j,Y2j+i) = {q,r) для О < j < п. Такая операция осуществляется для кгьждой пары целых

чисел {q,r), таких, что О < q,r < d. Затем применяем х-критерий к этим к = d категориям, где - вероятность отнесения пары чисел к каждой из категорий. Как и для критерия равномерности, d - подходящее число, но оно должно быть немного меньшим, чем Значения, предложенные выше, так как значимый Х-критерий должен иметь п сравнительно большим по сравнению с к (скажем, по крайней мере п > bd").

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

Заметим, что 2п чисел последовательности (2) использовались в этом критерии для того, чтобы Сделать п наблюдений. Было бы ошибкой применять критерий серий к парам (Уо,У1), (Fi,!), (У„ 1,У„). Может ли читатель сказать, почему? Но можно применить критерий серий еще и к парам {Y2j+\,Y2j+2), ожидая, что наша последовательность удовлетворит этим двум проверкам. Однако нужно помнить, что эти проверки на самом деле взаимозависимы. С другой стороны, Джордж Марсалья (George Marsaglia) доказал, что если использовать пары (Уо,У1), (УьУг), (Уп-1,Уп) и применить обычный х-критерий для вычисления обеих статистик (Vj ддя критерия серий и 14 - для критерия частот по Уо,...,У„ 1) с тем же значением d, то случайная величина Уг - К будет иметь Х-распределение с d{d - 1) степенями свободы, когда п достаточно большое (см. упр. 24).

С. Критерий интервалов. Этот критерий используется для проверки длины "интервалов" между появлением Uj на определенном отрезке. Если а vi - два действительных числа, таких, что 0<а<;5<1, то рассмотрим длины подпоследовательностей Uj, Uj+i, Uj+r, в которых Uj+r лежит между q и /9, а другие Us не лежат между этими числами. (Эту подпоследовательность, состоящую из г -1-1 числа, будем называть интервалом длиной г.)

Алгоритм G (Данные для критерия интервалов). Следующий алгоритм (рис. 6), примененный к последовательности (1) для любых значений а и 13, подсчитывает число интервалов длиной О, 1, 1 и число интервалов длиной > (, пока не

получится п интервалов.

G1. [Инициализация.] Присвоить j i--1, s <- О и присвоить COUNT[r] <- О для

0<г <t.

G2. [Присвоение г значения 0.] Присвоить г <- 0.

G3. [а <Uj < /37] Увеличить j на 1. Если Uj > а и Uj < /3, то перейти к шагу G5.

G4. [Увеличение г.] Увеличить г на единицу и возвратиться к шагу G3.

G5. [Регистрация длины интервала.] (Интервал длиной г только что найден.) Если г >t,To увеличить COUNT[(] на 1, иначе - увеличить СОШТ[г] на 1.

G6. [Найдены ли п интервалов?] Увеличить «на 1. Если s < п, то вернуться к шагу G2. I