Limit joint distribution of the statistics of >, within a Block>> and the Longest Run of Ones in a Block>>

M. P. Savelov

Diskretnaya Matematika, Tome 34 (2022) no. 3, pp. 70-84.

Résumé

For a sequence consisting of independent random variables having a Bernoulli distribution with the parameter $p = \frac12$ the limit joint distribution of the statistics $T_1, T_2, T_3$ of the following three tests of the NIST package is obtained: «Monobit Test», «Frequency Test within a Block» and «Test for the Longest Run of Ones in a Block». It is proved that the covariance matrix $C$ of the limit distribution of the vector $(T_1, T_2, T_3)$ satisfies the relations $C_{12}=C_{21}=C_{13}=C_{31}=0$, $C_{23}=C_{32} \ge 0$. For arbitrary $p$ necessary and sufficient conditions for asymptotic uncorrelatedness and\slash or asymptotic independence of these statistics are obtained. The limit behavior of the vector $(T_1, T_2, T_3)$ is described for a wide class of values $p \neq \frac12$.

Détail

Keywords: joint distributions of statistics, NIST package, goodness-of-fit tests, «Monobit Test», «Frequency Test within a Block», «Test for the Longest Run of Ones in a Block», asymptotically uncorrelated statistics, asymptotically independent statistics.

Bibliographie

[1] 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, 2010

[2] Serov A. A., “Formuly dlya chisel posledovatelnostei, soderzhaschikh zadannyi shablon zadannoe chislo raz”, Diskretnaya matematika, 32:4 (2020), 120–136 | MR

[3] Zubkov A. M., Serov A. A., “A natural approach to the experimental study of dependence between statistical tests”, Matem. vopr. kriptogr., 12:1 (2021), 131–142 | MR | Zbl

[4] Zubkov A. M., Serov A. A., “Testing the NIST Statistical Test Suite on artificial pseudorandom sequences”, Matem. vopr. kriptogr., 10:2 (2019), 89–96 | MR | Zbl

[5] Zaman J. K. M. , Ghosh R., “Review on fifteen statistical tests proposed by NIST”, J. Theor. Phys. Cryptography, 1 (2012), 18–31

[6] Sulak F., Doǧanaksoy A., Uǧuz M., Koçak 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

[7] Soto J., Bassham L., “Randomness Testing of the Advanced Encryption Standard Finalist Candidates”, NIST IR 6483, Nat. Inst. Stand. and Technol., 1999

[8] Sulak F., Uǧuz M., Koçak O., Doǧanaksoy A., “On the independence of statistical randomness tests included in the NIST test suite”, Turkish J. Electr. Eng. $\$ Comput. Sci., T., 25 (2017), 3673–3683 | DOI | MR

[9] Georgescu C., Simion E., “New results concerning the power of NIST randomness tests”, Proc. Romanian acad., ser. A., 18 (2017), 381–388 | MR

[10] Iwasaki A., Umeno K., “A new randomness test solving problems of Discrete Fourier Transform Test”, IEICE Trans. Fundam. Electronics, Commun. and Comput. Sci., E101.A:8 (2018), 1204–1214 | DOI

[11] Ryabko B. Ya., Pestunov A. I., “«Stopka knig» kak novyi staticheskii test dlya sluchainykh chisel”, Probl. peredachi inform., 40:1 (2004), 73–78 | MR | Zbl

[12] Maltsev M. V., Kharin Yu. S., “O testirovanii vykhodnykh posledovatelnostei kriptograficheskikh generatorov na osnove tsepei Markova uslovnogo poryadka”, Informatika, 4 (2013), 104–111

[13] Burciu P., Simion E., “A systematic approach of NIST statistical tests dependencies”, J. Electr. Eng., Electronics, Control and Comput. Sci., 5:15 (2019), 1–6

[14] Savelov M. P., “Predelnye sovmestnye raspredeleniya statistik chetyrekh kriteriev paketa NIST”, Diskretnaya matematika, 33:2 (2021), 141–154

[15] Savelov M. P., “Predelnye sovmestnye raspredeleniya statistik trekh kriteriev paketa NIST”, Diskretnaya matematika, 33:3 (2021), 92–106

[16] Savelov M. P., “Predelnaya teorema dlya sglazhennogo varianta spektralnogo kriteriya ravnoveroyatnosti dvoichnoi posledovatelnosti”, Diskretnaya matematika, 33:4 (2021), 132–140

[17] Balakrishnan N., Koutras M. V., Runs and Scans with Applications, Wiley, New York, 2002, 488 pp. | MR | Zbl

[18] Serfling R., Approximation Theorems of Mathematical Statistics, John Wiley Sons, New York, 1980, 398 pp. | MR | Zbl

[19] Tumanyan S. Kh., “Asimptoticheskoe raspredelenie kriteriya $\chi^2$ pri odnovremennom vozrastanii ob'ema nablyudenii i chisla grupp”, Teoriya veroyatn. i ee primen., 1:1 (1956), 131—145 | MR | Zbl