Testing of embedding with margin for discrete random sequences

Sequence $X$ is a subsequence with margin $d$ of sequence $Y$ if $X$ is constructed from $Y$ by deleting non-adjacent segments consisting of at most $d$ characters. In this case, we say that $X$ can be embedded into $Y$ with margin $d$. In the paper, we propose 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. The complexity of the proposed procedure is proportional to the length of the embedded sequence which is less than complexity of total testing by order of magnitude. 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.