Geodesic
Testing of embedding with margin for discrete random sequences
Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 12-14.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: dense embedding, embedding with margin, sequential test, hypothesis of independence, probabilities of type I and type II errors, discrete random sequence. 
@article{PDMA_2018_11_a2,
     author = {N. M. Mezhennaya},
     title = {Testing of embedding with margin for discrete random sequences},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {12--14},
     publisher = {mathdoc},
     number = {11},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2018_11_a2/}
}
TY  - JOUR
AU  - N. M. Mezhennaya
TI  - Testing of embedding with margin for discrete random sequences
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2018
SP  - 12
EP  - 14
IS  - 11
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2018_11_a2/
LA  - ru
ID  - PDMA_2018_11_a2
ER  - 
%0 Journal Article
%A N. M. Mezhennaya
%T Testing of embedding with margin for discrete random sequences
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2018
%P 12-14
%N 11
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2018_11_a2/
%G ru
%F PDMA_2018_11_a2
N. M. Mezhennaya. Testing of embedding with margin for discrete random sequences. Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 12-14. http://geodesic.mathdoc.fr/item/PDMA_2018_11_a2/

[1] Golic J. Dj., “Constrained embedding probability for two binary strings”, SIAM J. Discrete Math., 9:3 (1996), 360–364 | DOI | MR | Zbl

[2] Mikhailov V. G., Mezhennaya N. M., “Otsenki dlya veroyatnosti plotnogo vlozheniya odnoi diskretnoi posledovatelnosti v druguyu”, Diskretnaya matematika, 17:3 (2005), 19–27 | DOI | MR | Zbl

[3] Mikhailov V. G., Mezhennaya N. M., “Nizhnie otsenki dlya veroyatnosti vlozheniya s proizvolnym dopuskom”, Vestnik Moskovskogo gosudarstvennogo tekhnicheskogo universiteta im. N. E. Baumana. Ser. Estestvennye nauki, 2012, no. 2, 3–11

[4] Donovan D. M., Lefevre J., Simpson L., “A discussion of constrained binary embeddings with applications to cryptanalysis of irregularly clocked stream ciphers”, Discrete Mathematics, Proc. Intern. Conf. on Discr. Math., eds. R. Balakrishnan, C. V. Madhavan, Indian Institute of Science, Bangalore, December 2006, 73–85 | MR

[5] Kholosha A., Clock-controlled shift registers for key-stream generation IACR Cryptology, ePrint Archive, , 2001 http://eprint.iacr.org/2001/061.pdf

[6] Mezhennaya N. M., “O proverke gipotezy o plotnom vlozhenii dlya diskretnykh sluchainykh posledovatelnostei”, Vestnik BGU. Matematika, Informatika, 2017, no. 4, 9–20

[7] Mezhennaya N. M., Predelnye teoremy v zadachakh o plotnom vlozhenii i plotnykh seriyakh v diskretnykh sluchainykh posledovatelnostyakh, Dic. $\dots$ kand. fiz.-mat. nauk, Moskovskii gosudarstvennyi institut elektroniki i matematiki, M., 2009

[8] Feller V., v 2 t., v. 2, Mir, M., 1984, 751 pp. | Zbl