Тест на следующий бит

Двоичный генератор проходит S сравнительный тест на следующий бит относительно модели M, если: для любого i и любого вероятностного полиномиального по времени алгоритма ${\displaystyle A\colon \{0,1\}^{i}\rightarrow \{0,1\}}$ (то есть алгоритм, имеющий в качестве начальных данных последовательность битов длиной i и выдающий на своём выходе бит), выполняется следующее неравенство:

${\displaystyle |P_{S}(A(s_{1}^{i-1})=s_{i})-P_{M}(A(s_{1}^{i-1})=s_{i})|<O(v(n)),}$

где ${\displaystyle P_{M}(A(s_{1}^{i-1})=s_{i})}$ — вероятность предсказания алгоритмом следующего бита для модельного генератора.

Очевидно, что задавшись моделью M, представляющей истинно случайную последовательность, мы получим ${\displaystyle P_{M}(A(s_{1}^{i-1})=s_{i})=1/2)}$, то есть классический тест на следующий бит. Задавшись же моделью с ${\displaystyle P_{M}(A(s_{1}^{i-1})=1)=b}$ и ${\displaystyle P_{M}(A(s_{1}^{i-1})=0)=1-b}$, получим искомый случай теста для несбалансированной последовательности с заданным смещением ${\displaystyle b}$.

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

Алгоритм вычисления m-битных последовательностей может быть представлен в виде двоичного дерева с взвешенными ребрами. В данном дереве каждый лист на глубине l хранит информацию о том, сколько раз встретилась данная l-битная последовательность. Так как дерево является взвешенным, то его каждому его ребру приписывается отношение количества, записанного в дочернем листе, к количеству, записанному в родительском. Для достаточно большой случайной последовательности предполагается, что числа, соответствующие рёбрам, будут примерно равны 1/2.

1. Задаём уровень ошибки ${\displaystyle \alpha =\left(1+{\sqrt {(\chi ^{2})/n}}\right)/2}$, соответствующий χ²-распределению с одной степенью свободы и допущением ошибки 5 %.
2. Вычисляем l = round(${\displaystyle log_{2}}$(n) — 1), n — длина исследуемой последовательности.
3. Приписываем к концу последовательности первые ${\displaystyle (l-1)}$ бит и разделяем последовательность на перекрывающиеся блоки длины ${\displaystyle l}$.
4. Вычисляем частоту встреч для всех листьев длины ${\displaystyle l}$.
5. Формируем ${\displaystyle l}$ и ${\displaystyle (l-1)}$ уровни дерева. Вычисляем соответствующие вероятности для всех рёбер.
6. Для каждого листа на уровне (l-1), если следующий бит(0 или 1) появляется с вероятностью меньшей, чем α, следующий бит предсказывается соответственно частоте этого появления. В противном случае предсказание невозможно.
7. Отбрасываем самый левый бит l-битной последовательности. Используя оставшиеся (l-1) бит снова переходим на шаг 6 и определяем следующий бит. Повторяем данную операцию до тех пор, пока это возможно. После того, как получаем невозможность предсказания следующего бита, подсчитываем количество предсказанных бит. Таким образом мы получим для каждой последовательности длины (l-1) количество следующих бит, предсказываемых при помощи предыдущего шага.
8. Вычисляем P-value равное отношению предсказанных бит ко всем попыткам предсказания.

Зададим величину r как вероятность того, что идеальный генератор сгенерировал последовательность менее случайную, чем исследуемый. Обычно r выбирают в пределах [0.001; 0.01]. Тогда если P-value больше r, то исследуемая последовательность считается случайной и наоборот в противном случае.

Тест Садегяна-Мохаери не дает ясного и точного критерия для определения случайности последовательности. Вместо этого создатели алгоритма предполагают возможность сделать некоторые выводы о общем поведении последовательности. Когда алгоритм успешно предсказывает (l+1) бит, то считается, что наступила локальная детерминированность.

Цель данного теста — определение отклонений в статистике появления следующего бита для подпоследовательности. Если же такое отклонение имеется — тест пытается использовать его для предсказания следующего бита. Последовательность считается неслучайной, если она содержит слишком много подпоследовательностей, чей последний бит предсказуем.

Практический тест показывает более разумные результаты в сравнении с оригинальным тестом Садегяна-Мохаери.

1. Задаём уровень ошибки ${\displaystyle a={\frac {1+{\sqrt {X^{2}/n}}}{2}}}$, соответствующий ${\displaystyle X^{2}}$-распределению с одной степенью свободы и допущением ошибки 5 %, аналогично алгоритму Садегяна-Мохаери.
2. Вычисляем l = round(${\displaystyle log_{2}}$(n) — 2), n — длина исследуемой последовательности.
3. Перемещаем первые l бит в конец последовательности.
4. Составляем дерево, аналогичное дереву в алгоритме Садегяна-Мохаери, в конечных узлах устанавливаем счетчики, соответствующие количеству нулей и единиц в следующем бите.
5. «Сканируем» последовательность окном размером l бит. Начальное положение окна — первые l бит. С каждым тактом двигаем окно на 1 бит вперед и в зависимости от значения в следующем за окном бите, увеличиваем счетчик узла, соответствующего значениям битов в окне.
6. Для каждого из узлов вычисляем отношения ${\displaystyle n_{0}/(n_{0}+n_{1})}$ и ${\displaystyle n_{1}/(n_{0}+n_{1})}$, где ${\displaystyle n_{0}}$ и ${\displaystyle n_{1}}$ — значения счетчиков для данного узла. Если одно из этих отношений превышает α, то увеличиваем счетчик ${\displaystyle Y_{o}bs}$.
7. Вычисляем P-value = (1/2)*erfc((${\displaystyle Y_{o}bs}$ — μ)/sqrt(2σ²)

Стоит отметить, что нет[4] известной теории, позволяющей вычислить точные значения μ и σ, используемые в последнем шаге алгоритма. Поэтому эти значения вычисляются приближенно.