Geodesic
Formulas for the numbers of sequences containing a given pattern given number of times
Diskretnaya Matematika, Tome 32 (2020) no. 4, pp. 120-136.

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

Explicit recurrent formulas for the numbers of sequences containing a given pattern given number of times are constructed. These formulas depend on the length of the sequence, the length of the pattern and its period only. By means of these results one may find the distribution of statistics of the NIST overlapping matching test for binary sequences and arbitrary pattern parameters.
Keywords: statistical tests, binary sequence, pattern (sequence segment), recurrence relations. 
@article{DM_2020_32_4_a6,
     author = {A. A. Serov},
     title = {Formulas for the numbers of sequences containing a given pattern given number of times},
     journal = {Diskretnaya Matematika},
     pages = {120--136},
     publisher = {mathdoc},
     volume = {32},
     number = {4},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2020_32_4_a6/}
}
TY  - JOUR
AU  - A. A. Serov
TI  - Formulas for the numbers of sequences containing a given pattern given number of times
JO  - Diskretnaya Matematika
PY  - 2020
SP  - 120
EP  - 136
VL  - 32
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2020_32_4_a6/
LA  - ru
ID  - DM_2020_32_4_a6
ER  - 
%0 Journal Article
%A A. A. Serov
%T Formulas for the numbers of sequences containing a given pattern given number of times
%J Diskretnaya Matematika
%D 2020
%P 120-136
%V 32
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2020_32_4_a6/
%G ru
%F DM_2020_32_4_a6
A. A. Serov. Formulas for the numbers of sequences containing a given pattern given number of times. Diskretnaya Matematika, Tome 32 (2020) no. 4, pp. 120-136. http://geodesic.mathdoc.fr/item/DM_2020_32_4_a6/

[1] Harborth H., “Endliche $0-1$-Folgen mit gleichen Teilblöcken”, J. Reine Angew. Math., 271 (1974), 139–154 | MR | Zbl

[2] Odlyzko A.M., Guibas L.J., “Maximal prefix-synchronized codes”, SIAM J. Appl. Math., 35:2 (1978), 401–418 | DOI | MR | Zbl

[3] Odlyzko A.M., Guibas L.J., “String overlaps, pattern matching, and nontransitive games”, J. Combinatorial Theory, Series A 30 (1981), 183-208 | MR | Zbl

[4] Chrysaphinou O., Papastavridis S., “A limit theorem on the number of overlapping appearances of a pattern in a sequence of independent trials”, Probability Theory and Related Fields, 79 (1988), 129–143 | DOI | MR | Zbl

[5] Johnson N., Kotz S., Kemp A.W., Univariate discrete distributions, 2ed, John Wiley Sons, 1992, 569 pp. | MR | Zbl

[6] Rukhin A., Soto J., Nechvatal J., Smid M., Barker E., Leigh S., Levenson M., Vangel M., Banks D., Heckert A., Dray J., Vo S., A statistical test suite for the validation of random number generators and pseudo random number generators for cryptographic applications, NIST Special Publication 800-22 Revision 1a, ed. L. E. Bassham III, NIST, 27 April 2010

[7] Hamano K., Kaneko T., “Correction of overlapping template matching test included in NIST randomness test suite”, IEICE Trans. Fundam. Electron., 90:9 (2007), 1788–1792 | DOI

[8] Sulak F., Doganaksoy A., Uguz M., Kocak O., “Periodic template tests – A family of statistical randomness tests for a collection of binary sequences”, Discrete Applied Mathematics, 271 (2019), 191–204 | DOI | MR | Zbl

[9] Fu J. C., Wendy Lou W. Y., “On the normal approximation for the distribution of the number of simple or compound patterns in a random sequence of multi-state trials”, Methodol. Comput. Appl. Probab., 9 (2007), 195–205 | DOI | MR | Zbl