О критерии проверки вложения с допуском для дискретных последовательностей
Автор: Меженная Наталья Михайловна
Журнал: Вестник Бурятского государственного университета. Математика, информатика @vestnik-bsu-maths
Рубрика: Теория вероятностей и математическая статистика
Статья в выпуске: 4, 2018 года.
Бесплатный доступ
Последовательность X является подпоследовательностью с допуском d последовательности Y, если X получается из Y удалением несмежных отрезков не более чем из d знаков. В этом случае говорят, что X может быть вложена в Y с допуском d. В работе предложен последовательный критерий проверки гипотезы о вложении с допуском d для дискретных случайных последовательностей над конечным алфавитом и изучены его свойства. Вероятность ошибки первого рода (вероятность отклонения верной гипотезы о вложении с допуском) построенного критерия равна нулю. Получено выражение для вероятности ошибки второго рода при альтернативной гипотезе о том, что рассматриваемые дискретные последовательности образованы независимыми в совокупности случайными величинами с равномерными распределениями на конечном алфавите. Найдено значение среднего числа знаков вкладываемой последовательности, используемых критерием до принятия решения при альтернативной гипотезе. Трудоемкость предложенной процедуры при верной гипотезе о плотном вложении пропорциональна длине вкладываемой последовательности или меньше при альтернативной гипотезе, что по порядку намного меньше трудоемкости тотального опробования. Приведены численные значения вероятности ошибки второго рода и среднего количества используемых знаков при различных значениях d и размерах алфавита.
Плотное вложение, вложение с допуском, последовательный критерий, гипотеза о независимости, вероятности ошибок первого и второго рода, дискретная случайная последовательность
Короткий адрес: https://sciup.org/148308918
IDR: 148308918 | УДК: 519.244.2, | DOI: 10.18101/2304-5728-2018-4-3-15
About a test of embedding with margin for discrete sequences
Sequence X is a subsequence with margin d of sequence Y if X is constructed from Y by deleting non-adjacent segments consisted of at most d letters. In this case we say that X can be embedded into Y with margin d. The article presents a sequential test for the hypothesis of embedding with margin d for discrete random sequences over a finite alphabet and study its properties. The probability of type I error (the probability of rejection of true hypothesis of embedding with margin) of the constructed test is equal to zero. We derive an expression for the probability of type II error under the alternative hypothesis that the discrete sequences under consideration consist of mutually independent random variables with uniform distributions on finite alphabet. We find out the average number of letters of the embedded sequence used by test before the decision is made under the alternative hypothesis. The complexity of the proposed procedure is proportional to the length of the embedded sequence under true hypothesis of embedding with margin and is smaller under the alternative hypothesis which is less than complexity of total testing by order of magnitude. We have presented numerical values of the probability of type II error and the average number of used letters for different values of d and the alphabet size.
Список литературы О критерии проверки вложения с допуском для дискретных последовательностей
- Golic J. Dj. Constrained embedding probability for two binary strings//SIAM J. Discrete Math. 1996. V. 9, № 3. P. 360-364. DOI: 10.1137/S0895479894246917
- Михайлов В. Г., Меженная Н. М. Оценки для вероятности плотного вложения одной дискретной последовательности в другую//Дискретная математика. 2005. Т. 17, № 3. С. 19-27. DOI: 10.4213/dm113
- Меженная Н. М., Михайлов В. Г. Нижние оценки для вероятности вложения с произвольным допуском//Вестник Московского государственного технического университета им. Н. Э. Баумана. Сер. Естественные науки. 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 mathematics. Proceedings of the international conference on discrete mathematics. Bangalore: Indian Institute of Science, 2006. P. 73-86.
- Golic J. Dj. Embedding probabilities for the alternating step generator//IEEE Trans. Inform. Theory. 2005. V. 51(7). P. 2543-2553. DOI: 10.1109/TIT.2005.850114
