About testing the dense embedding hypothesis for discrete random sequences

The dense embedding hypothesis says that one discrete sequence can be embedded in the other in such a way that the characters of the inserted sequence are separated in the resulting sequence by at most one character. We propose a sequential test for the dense imbedding hypothesis for discrete equiprobable random sequences over a finite alphabet and study its properties. The probability of type I error (the probability of rejection of the dense embedding hypothesis when it’s true) of the constructed test equals zero. We derive an expression for the probability of type II error under the alternative hypothesis that the discrete sequences under consideration are independent. A class of similar test is also considered. It turns out that a small change in the testing procedure greatly changes the error probabilities. A numerical illustration and discussion of the results are given.