Проверка гипотезы о вложении с допуском для дискретных случайных последовательностей | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/3

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

Последовательность X является подпоследовательностью с допуском d последовательности Y, если X получается из Y удалением несмежных отрезков не более чем из d знаков. В этом случае говорят, что X может быть вложена в Y с допуском d. Предложен последовательный критерий проверки гипотезы о вложении с допуском d для дискретных случайных последовательностей над конечным алфавитом и изучены его свойства. Вероятность ошибки первого рода (вероятность отклонения верной гипотезы о вложении с допуском) построенного критерия равна нулю. Трудоёмкость предложенной процедуры пропорциональна длине вкладываемой последовательности, что по порядку намного меньше трудоёмкости тотального опробования. Получено выражение для вероятности ошибки второго рода при альтернативной гипотезе о том, что рассматриваемые дискретные последовательности образованы независимыми в совокупности случайными величинами с равномерными распределениями на конечном алфавите.

Testing of embedding with margin for discrete random sequences.pdf Введение Пусть Xn = (x1,... , xn) и Ym = (y1,..., ym) -последовательности элементов множества An = {0,... , N - 1}, N ^ 2, длин n и m ^ 1 + (d + 1)(n - 1) соответственно. Последовательность Xn может быть вложена c допуском d ^ 1 в начало последовательности Ym, если существуют такие натуральные числа 1= j1 jk-1 : xk = yt}, k = 2,...,n; V = 1; Vk = Vk(Xn) = = jk - jk-1, k = 2,...,n; Tk = V2 + ... + Vk. Построим критерий T по следующему правилу. Последовательно по k = 2,... ,n вычисляем значение Tk. Если x1 = y1 и на k-м шаге неравенство Tk ^ (d +1)(k - 1) не выполнено, то гипотеза H0n отклоняется. В противном случае продолжаем проверку. Если x1 = y1 и при всех k = 2,... ,n выполнено (2), то гипотеза H0n принимается. Замечание 1. Если H0n верна, то существует набор чисел j1,...,jn, удовлетворяющих (1), и xk = yjk ,k = 1,..., n. Значит, Vk = jk - jk-1 ^ d + 1, k = 2,... , n, и Tk = V2 + ... + Vk ^ (d + 1)(k - 1). Таким образом, вероятность ошибки первого рода критерия T равна нулю. Нас интересует вероятность ошибки второго рода при альтернативной гипотезе H1n о том, что последовательность Xn не зависит от последовательности Ym и тоже состоит из независимых равномерно распределённых на множестве An случайных величин, а также среднее число знаков, используемых критерием до принятия решения. Теорема 1. Вероятность ошибки второго рода критерия T при n ^ 2 равна (3) 1 N 1 Среднее число шагов до принятия решения при гипотезе H1n равно Замечание 2. Можно показать, что P{Vk = l|H1n} = N-1(1 - N-1)1-1, I ^ 1, k = 2,...,n. Согласно [8, теорема 2 §2 гл. XII, с. 448-449], случайная величина с законом распределения, соответствующим производящей функции (3), является собственной, если EV2 ^ d + 1, и имеет конечное математическое ожидание, если EV2 > d + 1. Очевидно, EV2 = N. Значит, а(1) = 1 при N ^ d +1 и а'(1) = 1 при N ^ d + 2.

Ключевые слова

discrete random sequence, probabilities of type I and type II errors, hypothesis of independence, sequential test, embedding with margin, dense embedding, дискретная случайная последовательность, вероятности ошибок первого и второго рода, гипотеза о независимости, последовательный критерий, вложение с допуском, плотное вложение

Авторы

ФИООрганизацияДополнительноE-mail
Меженная Наталья МихайловнаМосковский государственный технический университет им. Н. Э. Бауманадоцент, кандидат физико-математических наук, доцент кафедры прикладной математикиnatalia.mezhennaya@gmail.com
Всего: 1

Ссылки

Феллер В. Введение в теорию вероятностей и ее приложения: в 2 т. М.: Мир, 1984. Т. 2. 751 с.
Меженная Н. М. Предельные теоремы в задачах о плотном вложении и плотных сериях в дискретных случайных последовательностях: диа.. канд. физ.-мат. наук. Московский государственный институт электроники и математики. М., 2009.
Kholosha A. Clock-controlled shift registers for key-stream generation // IACR Cryptology ePrint Archive 2001: 61 (2001). http://eprint.iacr.org/2001/061.pdf
Меженная Н. М. О проверке гипотезы о плотном вложении для дискретных случайных последовательностей // Вестник БГУ. Математика, Информатика. 2017. №4. С. 9-20.
Donovan D. M., Lefevre J., and Simpson L. A discussion of constrained binary embeddings with applications to cryptanalysis of irregularly clocked stream ciphers // R. Balakrishnan and C.V. Madhavan (eds.) Discrete Mathematics. Proc. Intern. Conf. on Discr. Math., Indian Institute of Science, Bangalore, December 2006. P. 73-86.
Михайлов В. Г., Меженная Н. М. Нижние оценки для вероятности вложения с произвольным допуском // Вестник Московского государственного технического университета им. Н.Э. Баумана. Сер. Естественные науки. 2012. №2. С. 3-11.
Golic J. Dj. Constrained embedding probability for two binary strings // SIAM J. Discrete Math. 1996. V. 9. No. 3. P. 360-364.
Михайлов В. Г., Меженная Н. М. Оценки для вероятности плотного вложения одной дискретной последовательности в другую // Дискретная математика. 2005. Т. 17. №3. С. 19-27.
 Проверка гипотезы о вложении с допуском для дискретных случайных последовательностей | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/3

Проверка гипотезы о вложении с допуском для дискретных случайных последовательностей | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/3