Limit joint distribution of $\phi$-entropy test>> statistics

M. P. Savelov

Diskretnaya Matematika, Tome 35 (2023) no. 3, pp. 60-70.

Résumé

Consider a sequence of independent polynomial trials with $s$ outcomes. «Approximate Entropy Test» is one of the tools used to test the hypothesis of the equiprobability of outcomes. In 2000 A.L. Rukhin proposed a more general «Approximate $\phi$-Entropy Test» and found the limiting distribution of its statistic $T^{\phi}$. In the present paper a generalization of this result is obtained in a simpler way. In addition, the limiting joint distribution $(T^{\phi_1}, \ldots, T^{\phi_r}$) is obtained in the situation with equiprobable outcomes. As a corollary, in the case $s=2$ the limiting joint distribution of the statistics of two NIST package tests «Approximate Entropy Test» and «Serial Test» is found for a sequence of independent Bernoulli trials with parameter $\frac12$.

Détail

Keywords: goodness of fit test, «Approximate Entropy Test», «Approximate $\phi$-Entropy Test», «Serial Test», NIST package.

Bibliographie

[1] Ryabko B. Ya., Fionov A. N., Kriptograficheskie metody zaschity informatsii, 2-e izd., Goryachaya liniya-Telekom, M., 2012, 229 pp.

[2] 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 random and pseudorandom number generators for cryptographic applications, NIST Special Publication 800-22, Revision 1a, April 2010

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

[4] 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 | DOI | MR | Zbl

[5] Pareschi F., Rovatti R., Setti G., “On statistical tests for randomness included in the NIST SP800-22 Test Suite and based on the binomial distribution”, IEEE Trans. Inf. Forensics Secur., 7:2 (2012), 491–505 | DOI

[6] Sulak F., Uğuz M., Koçak O. O., Doğanaksoy A., “On the independence of statistical randomness tests included in the NIST test suite”, Turk. J. Electr. Eng. $\$ Comp. Sci., 25:5 (2017), 3673–3683 | DOI

[7] Kievets N. G. Korzun A. I., “Sravnenie statistik testov serii i approksimirovannoi entropii”, Doklady BGUIR, 3 (2014), 12–17

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

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

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

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

[12] Savelov M. P., “Predelnoe sovmestnoe raspredelenie statistik kriteriev «Monobit test», «Frequency Test within a Block» i «Test for the Longest Run of Ones in a Block»”, Diskretnaya matematika, 34:3 (2022), 70–84 | DOI

[13] Savelov M. P., “Predelnoe sovmestnoe raspredelenie statistik kriteriev «Monobit test», «Frequency Test within a Block» i «Binary Matrix Rank Test»”, Diskretnaya matematika, 34:4 (2022), 84–98 | DOI | MR

[14] Savelov M. P., “Predelnoe sovmestnoe raspredelenie statistik kriteriev «Monobit test», «Frequency Test within a Block» i obobscheniya kriteriya «Serial Test»”, Diskretnaya matematika, 35:1 (2023), 88–106 | DOI | MR

[15] Savelov M. P., “Predelnoe sovmestnoe raspredelenie statistik kriteriev paketa NIST «Monobit Test», «Frequency Test within a Block» i obobscheniya kriteriya «Approximate Entropy Test»”, Diskretnaya matematika, 35:2 (2023), 93–108 | DOI

[16] Karell-Albo J. A., Legón-Pérez C. M., Madarro-Capó E. J., Rojas O., Sosa-Gómez G., “Measuring independence between statistical randomness tests by mutual information”, Entropy, 22:7(741) (2020), 1–18 | DOI | MR

[17] Pincus S. M., Huang W.-M., “Approximate entropy: statistical properties and applications”, Commun. Stat. – Theory Methods, 21:11 (1992), 3061–3077 | DOI | Zbl

[18] Pincus S., Singer B. H., “Randomness and degrees of irregularity”, Proc. Natl. Acad. Sci. USA, 93:5 (1996), 2083–2088 | DOI | MR | Zbl

[19] Pincus S., Kalman R. E., “Not all (possibly) “random” sequences are created equal”, Proc. Natl. Acad. Sci. USA, 94:8 (1997), 3513–3518 | DOI | MR | Zbl

[20] Rukhin A. L., “Approximate entropy for testing randomness”, J. Appl. Prob., 37:1 (2000), 88–100 | DOI | MR | Zbl

[21] Good I. J., “The serial test for sampling numbers and other tests for randomness”, Math. Proc. Cambridge Philos. Soc., 49:2 (1953), 276–284 | DOI | MR | Zbl

[22] Good I. J., Gover T. N., “The generalized serial test and the binary expansion of $\sqrt{2}$”, J. R. Stat. Soc. A, 130:1 (1967), 102–107 | DOI

[23] Zubkov A. M., “Predelnye raspredeleniya statisticheskoi otsenki entropii”, Teoriya veroyatn. i ee primen., 18:3 (1973), 643–650 | Zbl

[24] Stepanov V. E., “Nekotorye statisticheskie kriterii dlya tsepei Markova”, Teoriya veroyatn. i ee primen., 2:1 (1957), 143–144 | Zbl

[25] Vaart A. W. van der, Asymptotic Statistics, Cambridge Univ. Press, 2000, 443 pp. | MR