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

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

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

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

Значение S
Вероятн. PS

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

Таблица 4.1

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

(4.6)

Эта статистика называется статистикой "хи - квадрат" наблюдаемых значений Y₂ … Y₁₂ при бросании игральных костей. Используя табл.4.1, получим:

.

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

,(4.7)

Так как

,

Y₁ + Y₂ +…+ Y_k = n, p₁ + p₂ +…+ p_k =1.

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

Таблица 4.2

	p = 99%	p = 95%	p = 75%	p = 50%	p = 25%	p = 5%	p = 1%
…
2,5583,9406,7379,34212,5518,3123,21
…

Здесь p - процентные точки c^{2 -} распределения; m = k - 1 - число степеней свободы, что на единицу меньше, чем число категорий. Внутри клеток таблицы стоят числа .

Предположим, что были сделаны три эксперимента с генерированием случайных последовательностей и получены числа:

, , .

Сравнивая эти величины со значениями таблицы 4.2 при 10 степенях свободы, мы видим, что ₁ гораздо больше, чем 23.21, а это может произойти только в 1% случаев. В связи с этим эксперимент 1 демонстрирует значительное отклонение от случайного поведения. ₂ показывает не лучшие свойства, так как результаты слишком близки к ожидаемым. Наконец, значение ₃ находится между 75 и 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 выбирается достаточно большим, но не настолько большим, чтобы критерий стал практически неприменим.

Критерий равномерности (критерий частот)

Первое требование, предъявляемое к последовательности (4.8) состоит в том, чтобы ее члены были числа, равномерно распределенные между 0 и 1. Существуют 2 способа проверить это:

. Использовать критерий Колмогорова-Смирнова [2].

. Использовать c²-критерий.

Для того чтобы применить c²-критерий, используется последовательность (4.10) вместо (4.8). Для каждого r, 0 £ r < d, подсчитывается число случаев, когда Y_j = r. Затем применим c^{2 -} критерий, принимая число категорий k = d, а вероятности p_S = 1/d для каждой категории. d - число, равное, например, 64 или 128.

Критерий серий

Более общее требование к последовательности состоит в том, чтобы пары последовательных чисел были равномерно распределены независимым образом. В критерии серий подсчитывается число случаев, когда пара (Y_2j, Y_2j+1) = (q, r) для 0 £ j < n.

Такая операция осуществляется для каждой пары целых чисел q и r, таких, что 0 £ q< r < d. Затем применяется c^{2 -} критерий к этим k = d² категориям, где 1/d² - вероятность отнесения пары чисел к каждой из категорий. При этом d выбирается таким образом, чтобы n>>k, например n ³ 5d².