О проверке гипотезы о плотном вложении для дискретных случайных последовательностей
Автор: Меженная Наталья Михайловна
Журнал: Вестник Бурятского государственного университета. Математика, информатика @vestnik-bsu-maths
Рубрика: Теория вероятностей и математическая статистика
Статья в выпуске: 4, 2017 года.
Бесплатный доступ
Гипотеза о плотном вложении состоит в том, что одна дискретная последовательность может быть вложена в другую таким образом, что знаки вкладываемой последовательности разделены в результирующей последовательности не более, чем одним знаком. В работе предложен последовательный критерий проверки гипотезы о плотном вложении для дискретных равновероятных случайных последовательностей над конечным алфавитом и изучены его свойства. Вероятность ошибки первого рода (вероятность отклонения верной гипотезы о плотном вложении) построенного критерия равна нулю. Получено выражение для вероятности ошибки второго рода при альтернативной гипотезе, которая состоит в том, что рассматриваемые дискретные последовательности независимы. Рассмотрен также класс подобных критериев. Оказывается, что небольшое изменение процедуры проверки сильно меняет вероятности ошибок. Приведена численная иллюстрация и обсуждение полученных результатов.
Плотное вложение, последовательный критерий, гипотеза о независимости, вероятности ошибок первого и второго рода, дискретная случайная последовательность
Короткий адрес: https://sciup.org/14835243
IDR: 14835243 | DOI: 10.18101/2304-5728-2017-4-9-20
Список литературы О проверке гипотезы о плотном вложении для дискретных случайных последовательностей
- 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 с.
