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.