2.15 Тест произвольные отклонения.

2.15.1 Цель теста

f Идея этого теста в том, что количество циклов, имеющих точно К входов на

совокупной сумме произвольной последовательности. Совокупная сумма произвольной последовательности, производное от частичных сумм после того, как на интервале (0,1) последовательность будет попадать в пределы (-!,+!). Цикл произвольной последовательности состоит из последовательности отрезков длин устройства принятого произвольно, что начинается и возвращается в начало. Цель этого теста в том, чтобы определить, что количество попаданий в конкретное состояние в пределах цикла отклоняется из которого одно попадание должно ожидаться для произвольной последовательности. Этот тест -действительно серия восьми тестов (и выводов), один тест и вывод для каждых состояний: -4, -3, -2, -1 и +1, +2, +3, +4.

2.15.2 Вызов функции

RandomExcursions(w), где:

n - это длина строки битов.

- последовательность битов сгенерированных функцией RNG или PRNG; это

существует как глобальная структура на момент функционального вызова;

2.15.3 Статический тест и распределение ссылок

x²(obs): Для данного состояния х, мера того как хорошо наблюдаемый номер состояния находиться в пределах цикла ожидаемое количество раз, исходя из предположения произвольности.

Распределение ссылки для статистического теста - это распределение x².

2.15.4 Описание теста

(1) Форма нормализованной последовательности для интервала (-1,+1) и X: нули и та входная последовательность (е) измененные в интервале от -1 до +1; X; = 2е; -1.

Например, если £=0110110101, тогда n - 10 и Х = -1, 1, 1,-1, 1, 1,-1, 1,-1, 1.

(2) Вычислите частичные суммы S, последовательно больших подпоследовательностей, каждая начинающаяся с X,.

Сформировать набор S = {Si}.

S1 =Х1

S2 =X1+X2

Для примера в этой секции,

(3) Сформировать новую последовательность 5" включая нули перед и после набора S. То есть, S'= 0,S1, S2, ... ,Sn,0.

Для примера в этой секции, S' = 0, -1, 0, I, 0, 1, 2, I, 2, I, 2, 0. Результирующий произвольный проход, показан ниже.

Пример произвольного прохода (S )

(4) J - это общее число нулевых пересечений в S', где нулевое пересечение является величиной нуля в S', что происходит после стартового нуля. J - также количество циклов в S , где цикл S' -подпоследовательность S, состоящая из случайных нулей, сопровождаемая нулевыми величинами, и заканчиваясь нулем. Заканчивающий нуль в одном цикле может быть начальным нулем в другом цикле. Количество циклов в S' - количество нулевых пересечений. Если J < 500, прекратите тест.

Для примера в этой секции, если S'= {0,-1,0 1,0, 1,2, 1,2, 1, 2, 0}, то J= 3 (есть нули в позициях 3, 5 и 12 для S'). Нулевые значения легко пронаблюдать на вышеуказанном графике. Для J = 3, есть 3 цикла, состоящих из {0,-1,0}, {0, 1,0} и {0, 1,2,1,2,1,2,0}.

(5) Для каждого цикла и для каждой не равной нулю величины х может иметь величины -4 <х < -1 и 1 <х < 4, вычислять частоту каждого х в пределах каждого цикла.

Для примера в этой секции, на этапе 3, первый цикл имеет один случай для -1, второй цикл имеет один случай для 1, и третий цикл имеет три случая каждый из 1 и 2. Это может быть представлено используя следующую таблицу.

		Циклы
Значение X	Цикл 1 (0,-1,0)	Цикл 2 (0,1,0)	Цикл З (0,1,2,1,2,1,2,0)
-4	0	0	0
-3	0	0	0
-2	0	0	0
-1	1	0	0
1	0	1	3
2	0	0	3
3	0	0	0
4	0	0	0

(6) Для каждых восьми состояний х, вычислите Vk(x) - общее число циклов в которых состояние х происходит точно k время среди всех циклов, для k = 0, 1,...,5

5 (для k = 5), все частоты > 5 сохранены в V₅ (х)). Отметьте, что (х) = J.

Для примера в этой секции,

V₀ (-l) = 2 (состояние -1 происходит точно 0 времени в двух циклах),

Vi(-l) = 1 (состояние -1 происходит только один раз в одном цикле), и

V2(-l) = Vз(-1) = V4(-l) = Vs5(-l) = 0 (состояние -1 происходит точно {2, 3,4, >5} времени в 0 циклах).

• Vо (1) = 1 (состояние 1 происходит точно О времени в одном цикле),

V1 (1) = 1 (состояние 1 происходит только один раз в одном цикле),

V3 (1) = 1 (состояние 1 происходит 3-й раза в одном цикле ), и

V2(l) = V4(1) =V5 (1) = 0 (состояние 1 происходит точно {2, 4, >5} времени в 0 циклах).

• Vo(2) = 2 (состояние 2 происходит точно 0 времени в 2-х циклах),

V1 (2) = 1 (состояние 2 происходит 3-й раза в одном цикле), и

V1 (2) = V2(2) = V4(2) = V5(2) = 0 (состояние 1 происходит точно

{1,2, 4, >5} времени в 0 циклах).

• Vo(-4) = 3 (состояние -4 происходит точно 0 времени в 3-х циклах), и

V1(-4) = V2(-4) = V3(-4)=V4(-4)=V5(-4) = 0 (состояние -4 происходит точно

{1, 2, 3, 4, >5} времени в 0 циклах).

И так далее....

Это может быть показано используя следующую таблицу:

х	Номера циклов
	0	1	2	3	4	5
-4	3	0	0	0	0	0
-3	3	0	0	0	0	0
-2	3	0	0	0	0	0
-1	2	1	0	0	0	0
1	1	1	0	1	0	0
2	2	0	0	1	0	0
3	3	0	0	0	0	0
4	3	0	0	0	0	0

- здесь - это вероятность, что состояние х

происходит k раз в произвольном распределении (смотри Секцию 3.15 для таблицы переменных). Величины для л^ (х) и их метод вычисления приведен в Разделе

3.15. Отметьте, что восемь x² статистики будут произведены (то есть, для х = -4, -3, -2,-1,1, 2, 3,4).

(8) Для каждого состояния, вычислите Р-value = igamc(5/2, x² (obs)/2). Восемь Р-

values будут произведены.

2.15.5 Правила решения (для уровня 1%)

Если вычисленный P-value < 0.01, тогда решите, что последовательность непроизвольная. В противном случае, решать, что последовательность произвольная.

2.15.6 Вывод и Интерпретация Результатов Теста

С тех пор как P-value полученное на этапе 8 Секции 2.15.4 ^0.01 (P-value 0.502529), вывод - в том, что последовательность произвольная.

Отметьте, что если значения X²{obs}, были слишком большими, тогда последовательность должна отобразить отклонение от теоретического распределения для данного состояния через все циклы.

2.15.7 Рекомендации для входных данных

Рекомендовано, что каждая последовательность, которую нужно тестировать состоит минимум из 1,000,000 битов (то есть, n 10⁶).

2.15.8 Пример

(ввод) =11001001000011111101101010100010001000010110100011

00001000110100110001001100011001100010100010111000

(ввод) n = 1000000 = 10⁶

(обработка) J = 1490

Значения	X1	P-value	Вывод
-4	3.83569	0.573306	Random
-3	7.31870	0.197996	Random
-2	7.86192	0.164011	Random
-1	15.6926	0.007779	Non-random
+1	2.48590	0.778616	Random
+2	5.42938	0.365752	Random
+3	2.40417	0.790853	Random
+4	2.39392	0.792378	Random

(Вывод)

Для семи из состояний х, P-value > 0.01, и вывод должен быть в том, что последовательность будет произвольной. Тем не менее, для одного состояния х (х=1), P-value < 0.01, так что вывод должен быть в том, что последовательность непроизвольная. Когда возникают противоречия, дальнейшие последовательности должны быть изучены, чтобы определить что такое поведение характерное.

Ссылки для теста:

[1] Frank Spitzer, Principles of Random Walk. Princeton: Van Nostrand, 1964 (especially p. 269).

[2] Pal Revesz, Random Walk in Random And Non-Random

Qirxrorx-trp- World Scientific- 1990.

3.15 Тест произвольные отклонения.

Этот тест основан на рассмотрении последующих сумм двоичных битов (плюс или минус простой те) как одномерный произвольный проход. Тест обнаруживает отклонения из распределения количества попаданий произвольного прохода в определенное "состояние", то есть, любая величина целого.

Рассматривайте произвольный проход

как последовательность

отклонений от нуля

Здесь J обозначает общее число таких отклонений в строке, ограничивающее распределение для этого числа (произвольных) J (то есть, количество нулей среди S_k сумм, k = 1, 2,..., n где

S₀ = 0) известно, что будет:

z >0

Тест отвергает гипотезу произвольности немедленно если J слишком небольшая, то есть, если следующая Р - величина небольшая:

Если J < тах(0.005 л/и , 500), гипотеза произвольности отвергается. В противном случае количество попаданий произвольного прохода S в определенное состояние будет оценен.

Обозначим (х)- это количеством попаданий для х,х 0, в течение одного 0 - отклонения. Распределение приведено в Revesz (1990) и ВагопиКикЫп(1999):

Это означает, что (х) = 0 с вероятностью 1 - 1/2|х|; в противном случае (с вероятностью 1/2 |х|), (х) совпадает с геометрической произвольной переменной с параметром 1/2|х|.

Это легко можно увидеть

(15)

Вышеуказанные результаты использованы для произвольности, тестирующей следующим образом. Для сбора "представителя" х-переменной (при этом скажем, что 1 < х < 7 или -7 < х < - 1 : - 4 < х < 4 использованы в коде блока теста), оценены наблюдаемые частоты V ^ (х) числа k попаданий в состояние х в течение отклонений J, которые происходят в строке.

Итак V_k (х) = (х), где 0 (х)=1,

если количество попаданий х в течение j-ых отклонений (j = 1,...,J) точно равно k, в противном случае (х) = 0. Значение величины (х) в классе, где k = 0,1,... 4 с дополнительным классом k > 5.

Теоретическая вероятность для этих классов:

Эта вероятность имеет форму

Сравните эти частоты с теоретическими используя X² - тест.

которое, для любого х под гипотезой произвольности, должно иметь приблизительно X² - распределение с 5 градусами свободы. Это -правильный тест, когда Jminn- (х) > 5, то есть, если J > 500. (Код блока теста использует (х = 4) для (х). Если это условие не выполняется, то величина £(x), должна быть переведена в большие классы.

Соответствующая Р - величина сообщения. Эти величины может быть получена из формулы: