Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
все тесты.docx
Скачиваний:
2
Добавлен:
01.05.2025
Размер:
242 Кб
Скачать
☆

13. Энтропийные тесты.

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

Рассмотрим цепочки и вычислим их относительные частоты

Пусть

есть их выборочная энтропия и

есть статистика приращения энтропии.

Заметим, что малым значениям соответствует последовательность с «сильной регулярностью» и, напротив, большие значения соответствуют чисто случайным последовательностям.

Если то при фиксированном

если же и при так, что то

случайные величины независимы и распределены по закону Пуассона с параметром , а функция имеет вид

Соотношения (13.4) и (13.5) позволяют построить соответствующие критерии согласия для гипотезы : в условиях (13.4)

в условиях (13.5)

где и -заданный уровень значимости.

14. Тест, основанный на линейной сложности.

Линейной сложностью двоичной последовательности называется минимальный порядок линейной рекурренты на полем

где - коэффициенты линейной реккурренты, порождающей последовательность . Для вычисления линейной сложности может быть использован алгоритм Берлекэмпа-Месси [10].

Известно [4], что при гипотезе

при этом для статистика

Имеет следующее предельное распределение:

Для практического использования этого результата удобно разбить область значений на 7 ячеек:

Теоретически вероятности попадания в эти ячейки равны:

На основании этих результатов предлагается следующий алгоритм тестирования наблюдаемой последовательности .

  1. Последовательность разбивается на блоков по битов

  2. Для каждого блока вычисляется линейная сложность и по формуле (14.1) находится теоретическое среднее

  3. Для каждого вычисляется статистика

  4. Находятся частоты попадания в ячейки

15. Тест на основе экстремальной статистики скалярного произведения.

Этот тест предложен в работе [11] и служит для проверки гипотезы о том, что наблюдаемая двоичная последовательность - равновероятная бернуллиевская.

Пусть и последовательность разбита на m непересекающихся фрагментов длиной

Определим статистики

Тогда при гипотезе

А совместное распределение имеет вид

Далее вводится статистика максимального скалярного произведения

При гипотезе

а при

На основании этих результатов строится соответствующий -тест. Для этого сначала нужно получить выборку , т.е. независимых наблюдений над статистикой (15.2), что организуется следующим образом: наблюдаемая последовательность длиной разбивается на длиной и для каждой подпоследовательности по описанному выше алгоритму вычисляется статистика максимального скалярного произведения. Далее по полученной выборке строится

и выносятся решение с помощью статистического правила:

Замечание. В описанном алгоритме параметр выбирается так, чтобы обеспечить условие применяемости

Можно также построить и критерий Колмогорова на основе статистики максимального скалярного произведения. Для этого надо использовать последовательность длиной разбить ее на подпоследовательностей длиной каждая, для подпоследовательности по описанному выше алгоритму вычисляется статистика (15.3), обозначим ее , Таким образом, получим выборку которая при гипотезе имеет асимптотически распределение хи-квадрат с степенями свободы. С помощью преобразования Смирнова: перейдем к выборке из равномерного (при гипотезе ) распределения на отрезке [0,1]. Если -вариационный ряд этой выборки, то статистика

имеет при гипотезе распределение Колмогорова.

На основании статистики получаем в итоге следующий тест:

Где - квантиль уровня распределения Колмогорова.