AOP_Tom2 (1021737), страница 12
Текст из файла (страница 12)
24). С. Критерий интервалов. Этот критерий используется для проверки длины "интервалов" между появлением Г на определенном отрезке. Если а и 1) — два действительных числа, таких, что О < о < ф < 1, то рассмотрим длины подпоследовательностей??, 1?.„ь,, ..., П+,. в которых (? ., лежит между а и Д, а другие (?, не лежат между этими числами. (Эту подпоследоваыльность, состоящую из г + 1 числа, будем называть интервалом длиной г.) Алгоритм С (Данные для кригнерия интервалое). Следующий алгоритм (рис. 6), примененный к последовательности (1) для любых значений а и Д, подсчитывает число интервалов длиной О, 1, ..., С вЂ” 1 и число интервалов длиной > Г, пока не получится и интервалов.
С1.(Инициализация.] Присвоить ? <- — 1, в <- О и присвоить СООйТ(г] < — О для О<с<6 С2. ]Присвоение т значения О.] Присвоить г +- О. СЗ. (о < с?1 <,У?] Увеличить у на 1. Если (?, > а и 1?, < Д, то перейтн к шагу С5. С4. (Увеличение г.] Увеличить г на единицу и возвратиться к шагу СЗ. С5. ]Регистрация длины интервала.] (Интервал длиной г только что найден.) Если т > 1, то увеличить СООИТ]1] иа 1, иначе — увеличить СООйТ]г] на 1. Сб. (Найдены лн и интервалов?] Увеличить э на 1.
Если в < и, то вернуться к шагу С2. 1 Рис. 6. Сбор данных для критерия интервалов. (Алгоритмы для критериев собирания купонов н монотонности подобны этому.) После реализации алгоритма С аз-критерий применяется при 6 = 1+ 1 к значениям СООМТ[0], СООЯТ[1], ..., СООМТ[С] с использованием следующих вероятностей: р, = р(1 — р)' для 0 < г < 1 — 1; р~ = (1 — р)'. (4) Здесь р = 0 — ц — вероятность того, что а < Пу < О.
Значения п и г выбираются, как обычно, чтобы ожидаемое значение С00яТ[г] равнялось 5 или больше (желательно больше) . Критерий интервалов часто применяется при а = 0 или д = 1 для того, чтобы на шаге 63 обойтись без одного сравнения. Особые случаи (а, О) = (О, -') и (-'„1) иногда называются "отклонение выше среднего" и 'отклонение ниже среднего' ссютветственно. Вероятности в (4) получить легко, и мы это оставляем читателю. Заметим, что для критерия интервалов, описанного выше, необходимо получить и интервалов определенной длины.
Однако таких интервалов в количесшве и может не оказаться. Если последовательность (б'„) недостаточно случайна, то алгоритм П может не закон ~иться. Поэтому можно предложить другой критерий интервалов, требуюпгий фиксированное число значений П (см. упр. 5). Р. Покер-критерий (критерий разбиений). "Классический" покер-критерий рассматривает и групп по пять последовательных целых чисел (1эы 1'эу ы1ээеэ, Тат+э:1эуе4) для О < у < и и проверяет, какие из следующих семи комбинаций соответствуют таким пятеркам чисел (порядок не имеет значения). т -критерий основан на подсчете числа пятерок в каждой категории.
Уместно рассмотреть какую-нибудь упрощенную версию этого критерия, для которой можно использовать более простые программы. Хорошим компромиссом Все числа разные: Одна пара: Две пары; Три числа одного вида: Полный набор: Четыре числа одного вида: Пять чисел одного вида: аЬсНе ааЬсд ааЬЬс аааЬс аао6Ь аааа6 ааааа будет критерий, использующий более простой подсчет различных значений в мно- жестве пятерок.
В этом случае можно выделить только пять категорий: 5 значений = все разные; 4 значения = одна лара; 3 значения = две пары или три числа одного вида; 2 значения = полный набор или четыре числа одного вида; 1 значение = пять чисел одного вида.
При такой схеме упрощаются подсчеты и критерий остается почти таким же хорошим. В общем случае можно рассматривать и групп и последовательных чисел и подсчитывать число групп из и чисел с т различными числами. Затем применяется у -критерий, в котором используются вероятности того, что в группе т различных г чисел Н(г~ — 1)... (И вЂ” т+ 1) ()г1 Рг= ь д' г (5) (Числа Стирлинга („") определены в разделе 1.2.6 и могут быть подсчитаны по приведенным в нем формулам.) Так как вероятности р, очень малы, когда т = 1 или 2, следует, вообще говоря, перед применением гг -критерия объединить нескольг ко категорий, имеющих малые вероятности, в одну. Чтобы получить формулу для р„, следует подсчитать, сколько Н~ групп из )с чисел, расположенных между 0 и а' — 1, имеют точно т различных элементов, и разделить это число на Ы".
Так как И(й — 1)... (Н вЂ” г+1) — это число упорядоченных наборов из т элементов множества, содержащего д элементов, достаточно показать, что 1 „1 — зто число способов разбиения множеотва из й элементов на точно т частей. Поэтому в упр. 1.2.6-64 завершается доказательство равенства (5). Е.
Критерий собирания купонов. Следующий критерий соотносится с покер- критерием, так как критерий интервалов соотносится с критерием частот. Используется последовательность Еа, 1м... и находятся длины отрезков 11„.м 11+а~ .: 1г+ содержащие "полный набор' целых чисел от 0 до Ы вЂ” 1. Алгоритм С описывает эту процедуру.
Алгоритм С (Данные для критерия собирания куаоное). Если дана последовательность целых чисел 1а, Уп..., таких, что 0 < уг < Н, то алгоритм подсчитывает длины п последовательных "собравших купоны" отрезков. После реализации алгоритма СООИТ[т] - — это число отрезков длиной т для И < т < Ф, а СОБйТ[с] — это число отрезков длиной > К С1.[Инициализация.] Присвоить ~' ~ — — 1, а г- 0 и присвоить СООМТ[г] < — 0 для Н<т<й С2. [Присвоить а и т значение 0.] Присвоить о ( — т ~- 0 и присвоить ОССОйЯ[к] < — 0 для О < /с < д.
СЗ. [Следующее наблюдение.) Увеличить г и у на 1. Если ОССОАБ[1' ] ф О, повторить этот шаг. Р1. [Инициализация.] Присвоить г ь — 1, 7 < — О. (В этом алгоритме всегда будет выполняться неравенство 0 < з < й/г!.) Р2. [Найти максимум.] Найти максимум (Ц,...,(7,). Если (7, — это максимум, присвоить з Ф- г 7+ э — 1. РЗ. [Замена.] Заменить 17„ьэ П,.
Р4. [Уменьшить г.] Уменьшить г на 1. Если г > 1, то вернуться к шагу Р2. 1 Последовательность (Пм..., (7~) будет расположена в порядке возрастания, когда алгоритм остановит работу. Чтобы доказать, что функция 7 единственным образом харакгперизуетсл начальным порядком (б'ы..., Ц), заметим, что алгоритм Р может быть обращен. Для т = 2, 3, ..., с присвоить э ь — 7' шой г, 7" ь- Д~г] и заменить [7, ь+ о~;ы У = (... (с~ 1 х (1 — 1) + с~ з) х (1 — 2) + .
+ сз) х 2+ сь =(С вЂ” 1)!сф 1+(1 — 2)!с~ з+. +21сз+1)см (7) где "цифры" с; — это целые числа, удовлетворяющие неравенствам 0<с.<у для 1<у<6 В алгоритме Р с„1 — — е — 1, когда шаг Р2 выполнен для заданного значения г. (8) С. Критерий монотонности. В последовательности можно проверять распределение восходяпзих и нисходящих серий. Имеется в виду проверка распределений длин монотонных частей заданной последовательности (отрезки возрастания или убывания) . В качестве примера точного определения серии рассмотрим последовательность цифр "1298536704". Проводя вертикальные линии слева, справа, а также между Х и Х ь1 всякий раз, когда Х, > Ху+ы получим [1 2 9[8]5[3 6 7[0 4[.
(9) Таким образом выделяются восходящие серии: сначала — серия длиной 3, затем — — две серии длиной 1, затем — снова серия длиной 3 и, наконец, серия длиной 2. В алгоритме из упр. 12 показано, как табулировать длину восходящей серии. Мы не будем применять Хз-критерий к подсчету серий, как в критерии интервалов и критерии собирания купонов (которые во многих других отношениях Легко видеть, что это разрушит эффект шагов Р2 — Р4. Следовательно, не существует двух перестановок, которые могут иметь одно и то же значение 7, и алгоритм Р обоснован.
Главной идеей, которая лежит в основе алгоритма Р, является представление со смешанным основанием, называемым "факторивльной числовой системой": каждое целое число на отрезке О < 7" < ~! может быть единственным образом записано в виде подобны этому критерию), поскольку смежные интервалы нб являются независимыми. Длинные серии имеют тенденцию следовать за короткими и наоборот. Такого отсутствия независимости достаточно, чтобы применение 1С2-критерия было неправомочным. Вместо этого можно подсчитать следующую статистику для случая, когда длины серий определены так, как в упр.
12: (СОЧТЯ вЂ” п61)(СООМТ[у] — п6 ) аб, 1 1<С1<б (10) где и — длина последовательности и матрицы коэффициентов А = (ао)1<сэ<б и В = (6,)1<1<5 заданы в следующем виде; 1 б 5 24 11 125 15 120 25 504Е 1 54б 4529.4 9044.9 13568 18091 9044.9 18097 27139 36187 13568 27139 40721 54281 18091 36187 54281 72414 22615 45234 67852 90470 27892 55789 83685 111580 22615 27892 45234 55789 67852 83685 90470 111580 113262 139476 139476 172860 г„= г21 = г21 = г„= 2'„= г„= г„= Я„= г„= г„= 1, а все оСтальные <ч1 равны нулю.
В этих обозначениях Я„'=г„+г„2+" +г,„ представляет собой число серий длиной > р и (12) 71р = Я' — Я'„„1 (13) является числом серий, длина которых точно равна р. Наша цель — подсчитать среднее значение (шеап) Вр, а также ковариацпю (сораг) сораг()Тр, 774) = шеап((Лр — шеап(йр)) ()24 — шеап(144)) ), (Значения аб, приведенные здесь, только приблизительны; точные значения могут быть получены из формул, приведенных ниже.) Статистика 1' в (10) должна иметь 252-распределение с шестью, а не пятью, степенями свободы, когда п большое. Значение п должно, скажем, равняться 4 000 или больше. Тот же критерий можно применить к нисходящей серии.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
