close

Вход

Забыли?

вход по аккаунту

?

Об одном критерии проверки гипотезы о наличии вкраплений в двоичной цепи Маркова.

код для вставкиСкачать
Теоретические основы прикладной дискретной математики
УДК 519.651
9
DOI 10.17223/2226308X/9/2
ОБ ОДНОМ КРИТЕРИИ ПРОВЕРКИ ГИПОТЕЗЫ О НАЛИЧИИ
ВКРАПЛЕНИЙ В ДВОИЧНОЙ ЦЕПИ МАРКОВА
А. В. Волгин
Рассматривается модель побитового вкрапления в простые цепи Маркова с неизвестной матрицей переходных вероятностей, основанная на LSB-методе. Получено
условие на взаимное асимптотическое соотношение длины отрезка исходной последовательности и объёма вкраплений, позволяющее гарантировать состоятельность статистического критерия выявления факта наличия вкраплений.
Ключевые слова: цепи Маркова, вкрапления в псевдослучайные последовательности, статистические критерии различия гипотез.
В [1] рассматриваются условия, при которых возможно гарантированно обнаружить факт наличия независимых вкраплений в простой конечной неразложимой и
ацикличной цепи Маркова с неизвестной матрицей переходных вероятностей в рамках следующей модели: к каждому элементу исходной последовательности применяется случайное преобразование. При этом преобразования получены по схеме серий
и являются независимыми. В данной работе получено дополнительное (по сравнению
с [1]) условие на взаимное асимптотическое соотношение длины отрезка исходной последовательности и объёма вкраплений, позволяющее гарантировать состоятельность
статистического критерия выявления факта наличия вкраплений.
Пусть X = {X0 , X1 , . . .} — простая конечная неразложимая и ацикличная цепь
Маркова с двумя состояниями 0, 1 и фиксированной положительной матрицей переходных вероятностей Π = (πa,b )2×2 , a, b ∈ {0, 1}. Стационарное распределение цепи обозначим через π = (π0 , π1 ), π0 , π1 ∈ (0, 1). В процедуре внесения вкраплений используются
две последовательности — Z = {Z0 , Z1 , . . .} и δ = {δ0 , δ1 , . . .}, Zi , δi ∈ {0, 1}, i > 0, которые являются реализациями испытаний в схеме Бернулли. При этом P{Zi = a} = pa ,
pa 6= πa , a ∈ {0, 1}, и P{δi = 0} = τ, i > 0, pa , τ ∈ [0, 1]. В результате внесения
вкраплений образуется последовательность Y = {Y0 , Y1 , . . .}:
Yi = Xi I{δi = 1} + Zi I{δi = 0}, i > 0,
где через I{A} обозначается индикатор события A. При этом предполагается, что последовательности X, Z и δ являются независимыми.
Постановка задачи заключается в следующем. Наблюдается отрезок двоичной последовательности (Y0 , . . . , Yn−1 ) длины n. Относительно способа образования данного
отрезка выдвигаются две сложные гипотезы H0 : τ = 0 и H1 : τ > 0 об отсутствии
и наличии вкраплений в цепь Маркова X соответственно. При обеих гипотезах будем
предполагать, что матрица Π, стационарное распределение π цепи Маркова X, а также
величины pa , a ∈ {0, 1}, и τ неизвестны. Рассмотрим схему серий, в которой
τ = τ (n) → 0 при n → ∞.
Задача заключается в построении состоятельного критерия различия гипотез H0 и H1 .
В [1] для выявления факта наличия вкраплений в цепь Маркова рассматривается
статистика
P (νabc − νab νbc /νb )2
,
(1)
S=
νab νbc /νb
a,b,c∈{0,1}
10
Прикладная дискретная математика. Приложение
где a, b, c ∈ {0, 1},
νabc = (n − 2)−1
n−3
P
I{Yi = a, Yi+1 = b, Yi+2 = c},
i=0
νab = (n − 1)−1
n−2
P
I{Yi = a, Yi+1 = b},
νa = n−1
i=0
n−1
P
I{Yi = a},
i=0
при этом в [1] рассматривается не двоичный, а произвольный конечный алфавит состояний цепи Маркова.
Рассмотрим критерий проверки гипотезы H0 против H1 , основанный на статистике (1):
H0 , если S < tχ22 ,1−α ,
(2)
принимается гипотеза
H1 , если S > tχ22 ,1−α ,
n
o
где α = P S > tχ22 ,1−α H0 − вероятность ошибки первого рода; tχ22 ,α − квантиль
уровня α распределения χ-квадрат с двумя степенями свободы.
Теорема 1. Пусть в модели вкраплений pa 6= πa , a ∈ {0, 1}, и среди элементов
матрицы переходных вероятностей Π есть хотя бы один, отличный от 1/2. Тогда при
выполнении условий
τ → 0, n → ∞,
√
nτ → ∞, n → ∞,
(3)
(4)
критерий (2) проверки гипотезы H0 против альтернативы H1 является состоятельным.
Замечание 1. При отсутствии вкраплений (τ ≡ 0) и при наличии вкраплений
во всех позициях последовательности X (τ ≡ 1) гипотезы H0 и H1 неразличимы, поскольку в обоих случаях Y является простой однородной цепью Маркова (с глубиной
зависимости 1 и 0 соответственно). Критерий будет состоятельным, когда вкраплений
«не слишком много», что гарантируется условием (3), но в то же время когда число вкраплений превосходит по порядку квадратный корень из длины наблюдаемого
отрезка последовательности X (условие (4)).
ЛИТЕРАТУРА
1. Шойтов А. М. О выявлении факта зашумления конечной цепи Маркова с неизвестной
матрицей переходных вероятностей // Прикладная дискретная математика. Приложение.
2010. № 3. C. 44–45.
УДК 519.7
DOI 10.17223/2226308X/9/3
АЛГОРИТМ РАСПОЗНАВАНИЯ ПОЛНОТЫ МНОЖЕСТВА СЛОВ
И ДИНАМИКА ЗАПРЕТОВ1
А. А. Евдокимов
Вводятся инвариантные операции и даётся описание алгоритма распознавания
полноты множества слов. Приводится теорема о результатах работы алгоритма
и их отношении к свойству полноты исходного множества слов. Формулируется
1
Работа поддержана Новосибирским государственным университетом и грантом РФФИ, проект
№ 14-01-00507.
Документ
Категория
Без категории
Просмотров
4
Размер файла
491 Кб
Теги
гипотезы, проверка, двоичной, одной, маркова, вкраплений, критерии, наличие, цепи
1/--страниц
Пожаловаться на содержимое документа