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

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