Основные критерии проверки случайных наблюдений

 

Статистические критерии [5] отвечают на вопрос: достаточно ли случайной будет последовательность. Если критерии T ₁, T ₂, …, T_n подтверждают, что последовательность ведет себя случайным образом, это еще не означает, вообще говоря, что проверка с помощью T_{n +1} –го критерия будет успешной. Однако каждая успешная проверка дает все больше и больше уверенности в случайности последовательности. Обычно к последовательности применяется несколько статистических критериев, и если она удовлетворяет этим критериям, то последовательность считается случайной.

Различают два вида критериев: эмпирические и теоретические. Эмпирические критерии основаны на использовании определенных статистик. Теоретические критерии

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

Рассмотрим критерий «хи - квадрат» (c²-критерий) [5]. Он является основным методом, используемым в сочетании с другими критериями. Прежде чем рассматривать идею в целом, проанализируем частный пример применения c²-критерия к бросанию игральной кости.

Используем 2 игральные кости, каждая из которых независимо допускает выпадение значений 1, 2, …, 6 с равной вероятностью. В следующей таблице дана вероятность получения определенной суммы S при одном бросании игральных костей:

 

Значение S	2	3	4	5	6	7	8	9	10	11	12
Вероятность PS

 

 

   Имеем всего 36 возможных результатов бросания. Рассмотрим результаты бросания. Например, величина 4 может быть получена тремя способами: 1 + 3, 2 + 2, 3 + 1. Это составляет . Аналогично определяются оставшиеся P_S. Если бросать игральную кость n раз, то в среднем мы должны получить величину S примерно n × P_S раз, но это не совсем так. Например, при 144 бросаниях результаты следующие:

 

Таблица 4.1

Величина S	2	3	4	5	6	7	8	9	10	11	12
Наблюдаемое число, YS	2	4	10	12	22	29	21	15	14	9	6
Ожидаемое число, n pS	4	8	12	16	20	24	20	16	12	8	4

 

Заметим, что во всех случаях наблюдаемое число отличалось от ожидаемого. Введем в рассмотрение число :

 

              (4.6)

 

Эта статистика называется статистикой «хи - квадрат» наблюдаемых значений Y ₂ … Y ₁₂ при бросании игральных костей. Для данных выше приведенной таблицы получим

 

.

 

Формулу (4.6) перепишем следующим образом:

 

.

 

, учитывая факт, что Y ₁ + Y ₂ +…+ Y_k = n,
p ₁ + p ₂ +…+ p_k =1, можно записать

 

                            (4.7)

 

Чтобы воспользоваться c²-статистикой проводят несколько экспериментов, затем вычисляют числа . Далее используют известные таблицы c²-распределения имеющие вид:

Таблица 4.2

	p = 99 %	p = 9 5%	p = 75%	p = 50%	p = 25%	p = 5%	p = 1%
…
	2,558	3,940	6,737	9,342	12,55	18,31	23,21
…

 

Здесь p — процентные точки c²-распределения; v = k – 1 — число степеней свободы, что на единицу меньше, чем число категорий. (Интуитивно это означает, что Y ₁, Y ₂, … Y_k, Y ₂, … Y_k не являются полностью независимыми, т.к. формула (6.1) показывает, что Y_k может быть вычислено, если Y ₁, … Y_{k -1} известны.)

Предположим, что были сделаны три эксперимента с генерированием случайных последовательностей и получены , , . Сравнивая эти величины со значениями таблицы 2 при 10 степенях свободы, мы видим, что ₁ гораздо больше;  будет больше 23.21 только в 1% случаев. В связи с этим эксперимент 1 демонстрирует значительное отклонение от случайного поведения. ₂ показывает не лучшие свойства, так как результаты слишком близки к ожидаемым. Наконец, значение ₃ находится между 25 и 50-процентной точками. Таким образом, наблюдение является удовлетворительно случайным по отношению к этому критерию.

Отметим, таблица 4.2 — это только приближенные значения c²-распределения, которое является предельным распределением случайной величины  формулы (4.7). Поэтому табличные значения близки к реальным только при больших n. Насколько большими должны быть n? Эмпирическое правило гласит: нужно взять n настолько большим, чтобы все значения n p_S были больше или равны пяти.

 

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

 

Эмпирические критерии традиционно применяются для проверки, будет ли последовательность случайной. Каждый критерий применяется к последовательности

 

{ U_n } = U ₀, U ₁, U ₂, …                               (4.8)

 

действительных чисел, которые предполагаются независимыми и равномерно распределенными в интервале (0,1).

Если критерии используются для целочисленных последовательностей, то используется вспомогательная последовательность

 

{ Y_n } = Y ₀, Y ₁, Y ₂, …,                             (4.9)

 

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

Y_n = [ d × U_n ]                                    (4.10)

 

Это последовательность целых чисел, распределенных в интервале (0, d –1). Число d выбирается таким образом, чтобы сделать все Y_i — целыми. Обычно d выбирается достаточно большим, чтобы критерий был значимым, но не настолько большим, чтобы критерий стал практически неприменим.