О проверке гипотезы о плотном вложении для дискретных случайных последовательностей
Автор: Меженная Наталья Михайловна
Журнал: Вестник Бурятского государственного университета. Математика, информатика @vestnik-bsu-maths
Рубрика: Теория вероятностей и математическая статистика
Статья в выпуске: 4, 2017 года.
Бесплатный доступ
Гипотеза о плотном вложении состоит в том, что одна дискретная последовательность может быть вложена в другую таким образом, что знаки вкладываемой последовательности разделены в результирующей последовательности не более, чем одним знаком. В работе предложен последовательный критерий проверки гипотезы о плотном вложении для дискретных равновероятных случайных последовательностей над конечным алфавитом и изучены его свойства. Вероятность ошибки первого рода (вероятность отклонения верной гипотезы о плотном вложении) построенного критерия равна нулю. Получено выражение для вероятности ошибки второго рода при альтернативной гипотезе, которая состоит в том, что рассматриваемые дискретные последовательности независимы. Рассмотрен также класс подобных критериев. Оказывается, что небольшое изменение процедуры проверки сильно меняет вероятности ошибок. Приведена численная иллюстрация и обсуждение полученных результатов.
Плотное вложение, последовательный критерий, гипотеза о независимости, вероятности ошибок первого и второго рода, дискретная случайная последовательность
Короткий адрес: https://sciup.org/14835243
IDR: 14835243 | УДК: 519.226, | DOI: 10.18101/2304-5728-2017-4-9-20
About testing the dense embedding hypothesis for discrete random sequences
The dense embedding hypothesis says that one discrete sequence can be embedded in the other in such a way that the characters of the inserted sequence are separated in the resulting sequence by at most one character. We propose a sequential test for the dense imbedding hypothesis for discrete equiprobable random sequences over a finite alphabet and study its properties. The probability of type I error (the probability of rejection of the dense embedding hypothesis when it’s true) of the constructed test equals zero. We derive an expression for the probability of type II error under the alternative hypothesis that the discrete sequences under consideration are independent. A class of similar test is also considered. It turns out that a small change in the testing procedure greatly changes the error probabilities. A numerical illustration and discussion of the results are given.
Список литературы О проверке гипотезы о плотном вложении для дискретных случайных последовательностей
- Golic J. Dj. Constrained embedding probability for two binary strings//SIAM J. Discrete Math. 1996. Vol. 9, No. 3. P. 360-364.
- Михайлов В. Г., Меженная Н. М. Оценки для вероятности плотного вложения одной дискретной последовательности в другую//Дискретная математика. 2005. Т. 17, № 3. С. 19-27.
- Меженная Н. М., Михайлов В. Г. Нижние оценки для вероятности вложения с произвольным допуском//Вестник Московского государственного технического университета им. Н. Э. Баумана. Серия: Естественные науки. 2012.№ 2. С. 3-11.
- Donovan D. М., Lefevre J., Simpson L. A Discussion of Constrained Binary Embeddings with Applications to Cryptanalysis of Irregularly Clocked Stream Ciphers//Balakrishnan R. Veni Madhavan C. (Eds.) Discrete mathematics. Proceedings of the international conference on discrete mathematics, Indian Institute of Science, Bangalore, December 2006. P. 73-86.
- Kholosha A. Clock-Controlled Shift Registers for Key-Stream Generation. IACR Cryptology ePrint Archive 2001: 61 (2001). URL: eprint.iacr.org/2001/061.pdf.
- Кошевой H. Д., Костенко E. М., Доценко H. В., Павлик А. В. Метод перечисления символьных последовательностей//Радiоелектроннi i комп’ютернi системи. 2012. № 3 (55). С. 45-49.
- Меженная H. М. Предельные теоремы в задачах о плотном вложении и плотных сериях в дискретных случайных последовательностях, дис.. канд. физ.-мат. наук/Московский государственный институт электроники и математики. М., 2009.
- Феллер В. Введение в теорию вероятностей и ее приложения: в 2 т. М.: Мир, 1984. Т. 1.528 с
- Феллер В. Введение в теорию вероятностей и ее приложения: в 2 т. М.: Мир, 1984. Т. 2. 751 с.
