где t = max(p, q), s = p + q и

sil-pq)+pq

f{p,q,n) = (n+l)

(p+l)!(9+l)! is+1)1

s- 1

, {s-s-2)pq-s-pW + l (.Q.

(p+l)!(g+l)!

Это выражение для ковариации, к сожалению, является довольно сложным, но без него нельзя обойтись. Из этих формул легко вычислить

теап(Лр) = теап(Лр) - mean(it!p+i),

соуаг(Лр, л;) = соуаг(л;, л;) - соуаг(л;+1, л;),

соуаг(Лр, Rg) = covar(i?p,Щ) - covar(i?p, Щ+,).

(20)

В работе Annals Math. Stat. 15 (1944), 163-165, Я. Вольфовиц (J. Wolfowitz) показал, что величины R, R2, Rt i, Щ становятся нормально распределенными при п -> 00 со средним и ковариацией, приведенными выше. Отсюда следует, что имеет место такой критерий серий. Если задана последовательность из п случайных чисел, то нужно подсчитать число серий Rp длиной р для 1 < р < t, а также число серий Rf длиной t или больше. Пусть

Qi = Л1-теап(Л1), Qt-i = Rt-i - mean{Rt-i),

Qt = R[ -теап(Л;).

(21)

Построим матрицу С ковариации R[, например С13 = covar(i?i, Л3), в то время как Си = covar(it!i, Л(). Когда t = 6, то

С = nCi + С2,

(22)

Ci =

С2 =

если п > 12. Сейчас образуем матрицу А = (ау), обратную к матрице С, и вычислим X)i,j=i QiQjO-ij- Результат для больших п должен иметь приближенно -распределение с t степенями свободы.

Матрица Л, заданная ранее в (11), равняется матрице, обратной к Ci, с точностью до пяти значащих цифр. Настоящая обратная матрица А равна nCf -

n-CC2Ci + n-CrC2CiC2Cr----, и это приводит к тому, что СС2СГ

очень приближенно равна -6С~. Поэтому V « QCQ/{n - 6).

H. Критерий "максимум-f". Обозначим Vj = max{Utj,Utj+i, ,Utj+t-i) для О < j < п. Применим критерий Колмогорова-Смирнова к последовательности Vq, Vi, ..., Vn-i- Таким образом проверим гипотезу о том, что функция распределения Vj равна F{x) = , О < х < 1. Можно также применить критерий Колмогорова-Смирнова к последовательности Vq, V, ..., Vi, проверяя гипотезу о равномерном распределении.

Для обоснования критерия необходимо показать, что функция распределения Vj равна F{x) = ж*. Вероятность того, что max(C/i, С/г,..., Ut) < х, равна вероятности того, что одновременно Ui < х, U2 < х, ..., Ut < х, которая, в свою очередь, равна произведению вероятностей Uk < х при к = l,...,t, а именно - хх... х = х*.

I. Критерий конфликтов, х-критерий можно применять только тогда, когда ненулевое число элементов ожидается в каждой категории. Но существует критерий другого вида, который можно использовать, когда число категорий намного больше числа наблюдений. Этот критерий имеет отношение к рандомизации - важному методу информационного поиска; он будет рассматриваться в разделе 6.4.

Предположим, что имеется т урн, и поместим в них наудачу п шаров, причем т намного больше п. Большинство шаров попадет в пустые урны, но если шар попадет в урну, в которой уже содержится хотя бы один шар, то будем говорить, что произошел "конфликт". Критерий конфликтов подс*[итьшает число конфликтов, и генератор удовлетворяет этому критерию, если не возникает слишком много или слишком мало конфликтов.

Для определенности предположим, что т = 2 и п = 2. Тогда в среднем на 64 урны лриходится только один шар. Вероятность того, что в конкретную урну попадет ровно к шаров, равна рк = (")т"*(1 - т")""*, поэтому среднее число конфликтов в урне равно

Y{k - 1)рк = A;pfc - Y,Pk = £ - 1 +Ро.

к>1 к>0 к>1

Так как ро = (1 - т")" = 1 - nm~ -I- {)т~ -- маленькое число, получим, что общее среднее число конфликтов во всех т урнах намного меньше n/(2m) = 128. (Истинное значение равно » 127.33.)

Критерий конфликтов можно использовать для того, чтобы оценивать генератор случайных чисел для строк больших размерностей. Например, когда т = 2° и п = 2, можно проверять 20-мерную случайность генератора случайных чисел, положив d = 2 и сформировав 20-мерный вектор Vj = (Уго;, Узо+Х! • •, 20+19) для О < j <п. Мы храним таблицу из m = 2° двоичных разрядов для определения конфликтов и один двоичный разряд для каждого возможного значения координаты вектора Vj-, на компьютере с 32 двоичными разрядами в слове это дает 2 слов.

Сначала во все 2 двоичных разрядов таблицы занесем 0; затем для каждого Vj, если в соответствующий двоичный разряд уже занесена 1, регистрируем конфликт, в противном случае заносим в двоичный разряд 1. Этот критерий можно использовать для размерности 10 при d = 4 и т. д.

Чтобы решить, проходит ли последовательность это испытание, можно использовать следующую таблицу процентных точек, когда т = 2° и п = 2

Конфликты < 101 108 119 126 134 145 153

С вероятностью .009 .043 .244 .476 .742 .946 .989

Для определения этих вероятностей используется та же теория, что и для покер-критерия (5); вероятность, что произойдет с конфликтов, равна вероятности того, что будут заняты п - с урн, а именно

т{т - 1).. .{т - п +с +1) ( п \ т" In - с/

Хотя тип очень большие, не составляет труда вычислить эти вероятности, используя следующий метод.

Алгоритм S {Процентные точки для критерия конфликтов). Пусть заданы тип. Этот алгоритм определяет распределение числа конфликтов, происходящих, когда п шаров рассеиваются по т урнам. Для вычислений используется вспомогательная таблица А[0], А[1], А[п] чисел с плавающей запятой; фактически A[j] будет не равным О только для jo < j < ji и ji - jo будет иметь порядок, не больший, чем logn, поэтому их можно получить с использованием значительно меньшего объема памяти.

51. [Инициализация.] Присвоить A[j] •(- О для О < j < п; затем присвоить А[1] <г- 1 и jo <- ji 1. Повторить шаг S2 ровно п - 1 раз и перейти к шагу S3.

52. [Корректировка вероятностей.] (Этот шаг соответствует бросанию шара в урну; A[j] - вероятность того, что заняты точное урн.) Присвоить ji <- j\ +1. Затем для j ji, ji - 1, ..., jo (в таком порядке) присвоить A[j] {Цт)А[]] -\- ((1 + 1/т) - {j/m))A[j - 1]. Если A[j] стало очень малым в результате вычислений, скажем, A[j] < 10~°, присвоить A[j] 0; в таком случае уменьшить ji на 1, если j = fi, или увеличить jo на 1, если j = jo-

53. [Вычисление ответа.] На этом шаге будет использоваться вспомогательная таблица (ГьГг,... ,rtmax) = (.01, .05, .25, .50, .75, .95, .99, 1.00), содержащая точно определенные интересующие нас процентные точки. Присвоить р i- О, t i- 1 и j jo - 1. Выполнять следующие итерации, пока не будет достигнут t = tmax: увеличить j на 1 и присвоить р <- р + A[j]. Затем, если р > Tt, выход п - j - 1 и 1 - р (имеется в виду, что с вероятностью 1 - р существует по крайней мере п - j - 1 конфликтов); иначе - увеличиваем i на 1 до тех пор, пока p<Tt. \

J. Критерий промежутков между днями рождений. Джордж Марсалья в 1984 году ввел новый критерий. Поместим п шаров в т урн, как и в критерии конфликтов, но под урнами подразумеваем дни года, а под шарами - дни рождения. Предположим, что (Fi,..., Yn) - это дни рождения, где О < Уд, < т. Расположим их в порядке неубывания У(1) < • • < F(„), определим п "промежутков" Si - У(2) -У(1), ..., 5„ 1 = Y(n) - (n-i), Sn = У(1) Л-т- У(„) и, наконец, расположим промежутки