->3. а<

Нет>

/G6. Найдены лиЛ . п интервалов?

> G4. Увеличение г

G5. Регистрация длины интервала

Рис. 6. Сбор данных для критерия интервалов. (Алгоритмы для критериев собирания купонов и монотонности подобны этому.)

После реализации алгоритма G х-критерий применяется при /г = i + 1 к значениям C0UNT[0], C0UNT[1], ..., C0UNT[«] с использованием следующих вероятностей:

Vr=v{l-vY ДЛяО<г<«-1; vt = {l-pf.

Здесь р = - а - вероятность того, что а <Uj < /3. Значения nut выбираются, как обычно, чтобы ожидаемое значение COUNT[r] равнялось 5 или больше (желательно больше).

Критерий интервалов часто применяется при а = О или /3 = 1 для того, чтобы на шаге 03 обойтись без одного сравнения. Особые случаи (а,) = (О, ) и (,1) иногда называются "отклонение выше среднего" и "отклонение ниже среднего" соответственно.

Вероятности в (4) получить легко, и мы это оставляем читателю. Заметим, что для критерия интервалов, описанного выше, необходимо получить п интервалов определенной длины. Однако таких интервалов в количестве п может не оказаться. Если последовательность (f/„) недостаточно случайна, то алгоритм G может не закончиться. Поэтому можно предложить другой критерий интервалов, требующий фиксированное число значений Uj (см. упр. 5).

D. Покер-критерий (критерий разбиений). "Классический" покер-критерий рассматривает п групп по пять последовательных целых чисел {Yzj,Yzj+\,Yzj+2, Ysj+z,Ysj+i} для О < j < п и проверяет, какие из следующих семи комбинаций соответствуют таким пятеркам чисел (порядок не имеет значения).

X -критерий основан на подсчете числа пятерок в каждой категории.

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

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

5 значений = все разные; 4 значения = одна пара;

3 значения = две пары или три числа одного вида;

2 значения = полный набор или четыре числа одного вида;

1 значение = пять чисел одного вида.

При такой схеме упрощаются подсчеты и критерий остается почти таким же хорошим.

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

d{d-l)...{d-r + l) fk-

Р = ---\г

(Числа Стирлинга {*} определены в разделе 1.2.6 и могут быть подсчитаны по приведенным в нем формулам.) Так как вероятности рг очень малы, когда г = 1 или 2, следует, вообще говоря, перед применением х-критерия объединить несколько категорий, имеющих малые вероятности, в одну.

Чтобы получить формулу для Рг, следует подсчитать, сколько групп из к чисел, расположенных между О и d - 1, имеют точно г различных элементов, и разделить это число на d. Так как d{d-1)... (d-г +1) - это число упорядоченных наборов из г элементов множества, содержащего d элементов, достаточно показать, что {*} - это число способов разбиения множества из к элементов на точно г частей. Поэтому в упр. 1.2.6-64 завершается доказательство равенства (5).

Е. Критерий собирания купонов. Следующий критерий соотносится с покер-критерием, так как критерий интервалов соотносится с критерием частот. Используется последовательность Уо, Yi, .. .и находятся длины отрезков Yj+i, Yj+2, Yj+r, содержащие "полный набор" целых чисел от О до d - 1. Алгоритм С описывает эту процедуру.

Алгоритм С (Данные для критерия собирания купонов). Если дана последовательность целых чисел Yo,Yi, таких, что О < Yj < d, то алгоритм подсчитывает длины п последовательных "собравших купоны" отрезков. После реализации алгоритма СОШТ[г] - это число отрезков длиной г для d < г < it, а COUNT[it] - это число отрезков длиной > t.

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

С2. [Присвоить q и г значение 0.] Присвоить g -f- г -f- О и присвоить OCCURS[A;] О для О < к < d.

СЗ. [Следующее наблюдение.] Увеличить г uj на, 1. Если OCCURS[}] / О, повторить этот шаг.

С4. [Полное множество?] Присвоить OCCURS[y] -f-ln-f- + l. (В наблюдаемой подпоследовательности содержится q различных значений; если q = d, то множество полное.) Если q < d, возвратиться к шагу СЗ.

С5. [Регистрация длины.) Если г > t, увеличить COUNT[i] на 1, иначе - увеличить СОгаТ[г] на 1.

Сб. [п найдено?] Увеличить s на 1. Если s < п, возвратиться к шагу С2.

Пример использования этого алгоритма приведен в упр. 7. Представим себе мальчика, который собирает купоны d видов, равномерно распределенные по его сверткам с завтраком. Он ест завтраки до тех пор, пока не получит по крайней мере по одному купону каждого типа.

После того как алгоритм С вычислит п длин, нужно применить х-критерий к COUNT[d], COUNT[d + 1], COUNT[<] ck = t- d+l. Соответствующие вероятности равны

Чтобы найти их, просто заметим, что если qr равна вероятности того, что подпоследовательность длиной г не полна, то

согласно (5), т. е. это вероятность того, что набор из г элементов не имеет d различных значений. Поэтому (6) следует из соотношений pt = qt-i и

Рг = 9г-1 - 9г для d<r <t.

В упр. 9 и 10, а также в работах Джорджа Пойа (Полна) (George Р61уа, Zeitschrift fur angewandte Math, und Mech. 10 (1930), 96-97) и Германа фо1 Шеллинга (Hermann von Schelling, AMM 61 (1954), 306-311) приведены формулы, возникающие в связи с обобщением критерия собирания купонов.

F. Критерий перестановок. Разделим последовательность на выходе на п групп по t элементов в каждой, т. е. {Ujt,Ujt+i,... ,Ujt+t-i) для О < j < п. Элементы в каждой группе можно упорядочивать tl различными способами. Подсчитывается число групп с любым возможным порядком и применяется х-критерий с к = tl возможными категориями и вероятностью 1/tl для каждой категории.

Например, если t - S, существует шесть возможных категорий, а именно Uzj < U3J+1 < U3J+2, или f/sj < U3J+2 < U3J+1, или или U3J+2 < U3J+1 < U3J. В этом критерии предполагается, что Ue не могут быть равны между собой, т. е. вероятность того, что Us = Uj при S ф j равна нулю.

Чтобы реализовать этот критерий на компьютере, удобно использовать следующий сам по себе интересный алгоритм.

Алгоритм Р {Анализ перестановок). Если задана последовательность различных элементов {Ui,Щ), вычислим целое число f{Ui,..., Ut), такое, что

0<f{Ui,...,Ut)<tl

и f{Ui, ...,Ut) = f{Vi,...,Vt) тогда и только тогда, когда {Ui,... ,Ut) и {Vi,... ,Vt) имеют тот же относительный порядок.