Вестник БГУ. Математика, информатика
Библиографическое описание:
О ПРОВЕРКЕ ГИПОТЕЗЫ О ПЛОТНОМ ВЛОЖЕНИИ ДЛЯ ДИСКРЕТНЫХ СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ // Вестник БГУ. Математика, информатика. - 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. M., 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 mathe- matics. 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 Genera- tion. IACR Cryptology ePrint Archive 2001: 61 (2001). URL: eprint.iacr.org/2001/061.pdf.
Кошевой Н. Д., Костенко Е. М., Доценко Н. В., Павлик А. В. Метод перечисления символьных последовательностей // Радіоелектронні і комп’ютерні системи. 2012. № 3 (55). С. 45–49.
Меженная Н. М. Предельные теоремы в задачах о плотном вло- жении и плотных сериях в дискретных случайных последовательностях. дис… канд. физ.-мат. наук / Московский государственный институт элек- троники и математики. М., 2009.
Феллер В. Введение в теорию вероятностей и ее приложения: в 2 т. М.: Мир, 1984. Т. 1. 528 с
Феллер В. Введение в теорию вероятностей и ее приложения: в 2 т. М.: Мир, 1984. Т. 2. 751 с.
Михайлов В. Г., Меженная Н. М. Оценки для вероятности плотного вложения одной дискретной последовательности в другую // Дискретная математика. 2005. Т. 17, № 3. С. 19–27.
Меженная Н. М., Михайлов В. Г. Нижние оценки для вероятности вложения с произвольным допуском // Вестник Московского государст- венного технического университета им. Н. Э. Баумана. Серия: Естествен- ные науки. 2012. № 2. С. 3–11.
Donovan D. M., 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 mathe- matics. 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 Genera- tion. IACR Cryptology ePrint Archive 2001: 61 (2001). URL: eprint.iacr.org/2001/061.pdf.
Кошевой Н. Д., Костенко Е. М., Доценко Н. В., Павлик А. В. Метод перечисления символьных последовательностей // Радіоелектронні і комп’ютерні системи. 2012. № 3 (55). С. 45–49.
Меженная Н. М. Предельные теоремы в задачах о плотном вло- жении и плотных сериях в дискретных случайных последовательностях. дис… канд. физ.-мат. наук / Московский государственный институт элек- троники и математики. М., 2009.
Феллер В. Введение в теорию вероятностей и ее приложения: в 2 т. М.: Мир, 1984. Т. 1. 528 с
Феллер В. Введение в теорию вероятностей и ее приложения: в 2 т. М.: Мир, 1984. Т. 2. 751 с.
Статья.pdf