Testing Randomness: A Suite of Statistical Procedures (2001)

Previous article Next article Testing Randomness: A Suite of Statistical ProceduresA. L. RuhkinA. L. Ruhkinhttps://doi.org/10.1137/S0040585X97978087PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstractA suite of procedures designed to test randomness of binary sequences is discussed.[1] D. Aldous and and P. Shields, A diffusion limit for a class of randomly‐growing binary trees, Probab. Theory Related Fields, 79 (1988), pp. 509–542. aj9 PTRFEU 0178-8051 Probab. Theory Relat. Fields CrossrefGoogle Scholar[2] Google Scholar[3] M. Baron and and A. L. Rukhin, Distribution of the number of visits of a random walk, Comm. Statist. Stochastic Models, 15 (1999), pp. 593–597. CrossrefGoogle Scholar[4] P. Billingsley, Asymptotic distributions of two goodness of fit criteria, Ann. Math. Statist., 27 (1956), pp. 1123–1129. aax AASTAD 0003-4851 Ann. Math. Stat. CrossrefGoogle Scholar[5] Google Scholar[6] Google Scholar[7] Google Scholar[8] J. Gibbons and and J. Pratt, P‐values: Interpretations and methodology, Amer. Statist., 29 (1975), pp. 20–25. aak ASTAAJ 0003-1305 Am. Stat. Google Scholar[9] I. J. Good, The serial test for sampling numbers and other tests for randomness, Proc. Cambridge Philos. Soc., 47 (1953), pp. 276–284. pcx PCPSA4 0068-6735 Proc. Cambridge Philos. Soc. CrossrefGoogle Scholar[10] L. J. Guibas and and A. M. Odlyzko, String overlaps, pattern matching and nontransitive games, J. Combin. Theory Ser. A, 30 (1981), pp. 183–208. cta JCBTA7 0097-3165 J. Comb. Theory, Ser. A CrossrefGoogle Scholar[11] H. Gustafson, , E. Dawson, , L. Nielsen and , and W. Caelli, A computer package for measuring the strength of encryption algorithms, Computers and Security, 13 (1994), pp. 687–697. CrossrefGoogle Scholar[12] Google Scholar[13] P. Kirschenhofer, , H. Prodinger and , and W. Szpankowski, Digital search trees again revisited: The internal path length perspective, SIAM J. Comput., 23 (1994), pp. 598–616. sim SMJCAT 0097-5397 SIAM J. Comput. LinkGoogle Scholar[14] I. N. Kovalenko, Distribution of the linear rank of a random matrix, Theory Probab. Appl., 17 (1972), pp. 342–346. tba TPRBAU 0040-585X Theor. Probab. Appl. LinkGoogle Scholar[15] Google Scholar[16] Google Scholar[17] Google Scholar[18] G. Marsaglia and and A. Zaman, Monkey tests for random number generators, Comput. Math. Appl., 9 (1993), pp. 1–10. cap CMAPDK 0898-1221 Comput. Math. Appl. CrossrefGoogle Scholar[19] U. M. Maurer, A universal statistical test for random bit generators, J. Cryptology, 5 (1992), pp. 89–105. jzq JOCREQ 0933-2790 J. Cryptology Google Scholar[20] Google Scholar[21] V. G. Mikhailov, Asymptotic normality of decomposable statistics from the frequencies of m‐chains, Discrete Math. Appl., 1 (1991), pp. 335–347. CrossrefGoogle Scholar[22] S. Pincus and and R. E. Kalman, Not all (possibly) “random” sequences are created equal, Proc. Nat. Acad. Sci. USA, 94 (1997), pp. 3513–3518. pna PNASA6 0027-8424 Proc. Natl. Acad. Sci. U.S.A. CrossrefGoogle Scholar[23] S. Pincus and and B. H. Singer, Randomness and degrees of irregularity, Proc. Nat. Acad. Sci. USA, 93 (1996), pp. 2083–2088. pna PNASA6 0027-8424 Proc. Natl. Acad. Sci. U.S.A. CrossrefGoogle Scholar[24] Google Scholar[25] Google Scholar[26] Google Scholar[27] A. L. Rukhin, Approximate entropy for testing randomness, J. Appl. Probab., 37 (2000), pp. 88–100. jza JPRBAM 0021-9002 J. Appl. Probab. CrossrefGoogle Scholar[28] Google Scholar[29] A. V. Skorokhod and and N. P. Slobodenyuk, Limit theorems for random walks, I, II, Theory Probab. Appl., 10 (1965), pp. 596–606; tba TPRBAU 0040-585X Theor. Probab. Appl. LinkGoogle Scholar[30] M. I. Tikhomirova and and V. P. Chistyakov, On the asymptotics of moments of nonappearing s‐chains, Discrete Math. Appl., 7 (1997), pp. 13–32. CrossrefGoogle Scholar[31] Google Scholar[32] V. A. Vatutin and and V. G. Mikhailov, Statistical estimation of entropy of discrete random variables with a large number of possible values, Russian Math. Surveys, 50 (1995), pp. 121–132. a2g RMSUAF 0036-0279 Russ. Math. Surveys CrossrefGoogle Scholar[33] Google Scholar[34] J. Ziv and and A. Lempel, A universal algorithm for sequential data compression, IEEE Trans. Information Theory, IT‐23 (1977), pp. 337–343. CrossrefGoogle ScholarKeywordscorrelation polynomialentropydistribution of m-patternsP-values$\chi^2$-distribution Previous article Next article FiguresRelatedReferencesCited byDetails A Class of Quadratic Polynomial Chaotic Maps and Its Application in CryptographyIEEE Access Cross Ref A simulation study on the accuracy of cryptographic randomness tests29 August 2017 | SIMULATION, Vol. 93, No. 12 Cross Ref Proposing a new approach and a rigorous cut-off value for identifying precognitionMeasurement, Vol. 93 Cross Ref Ensuring Quality of Random Numbers from TRNG: Design and Evaluation of Post-Processing Using Genetic AlgorithmJournal of Computer and Communications, Vol. 04, No. 04 Cross Ref Random number generation based on sensor with decimation method Cross Ref Detection of periodicity based on serial dependence of phase-folded data2 April 2015 | Monthly Notices of the Royal Astronomical Society, Vol. 449, No. 3 Cross Ref New Statistical Randomness Tests Based on Length of RunsMathematical Problems in Engineering, Vol. 2015 Cross Ref Non-Deductive Logic in Mathematics Cross Ref Conceptual Analysis27 September 2012 Cross Ref Non-deductive Logic in Mathematics: The Probability of Conjectures25 May 2013 Cross Ref Joint Distribution of Pattern Frequencies and Multivariate Pòlya–Aeppli LawA. L. Rukhin21 May 2010 | Theory of Probability & Its Applications, Vol. 54, No. 2AbstractPDF (221 KB)On occurrence of subpattern and method of gambling teams21 September 2006 | Annals of the Institute of Statistical Mathematics, Vol. 60, No. 1 Cross Ref TestU01ACM Transactions on Mathematical Software, Vol. 33, No. 4 Cross Ref On the Estimation of Differential Entropy From Data Located on Embedded ManifoldsIEEE Transactions on Information Theory, Vol. 53, No. 7 Cross Ref Pattern Correlation Matrices for Markov Sequences and Tests of RandomnessA. L. Rukhin19 November 2007 | Theory of Probability & Its Applications, Vol. 51, No. 4AbstractPDF (218 KB)Testing multivariate uniformity: The distance-to-boundary methodCanadian Journal of Statistics, Vol. 34, No. 4 Cross Ref Eukaryotic cells are dynamically ordered or critical but not chaotic9 September 2005 | Proceedings of the National Academy of Sciences, Vol. 102, No. 38 Cross Ref The SAC Test: A New Randomness Test, with Some Applications to PRNG Analysis Cross Ref Volume 45, Issue 1| 2001Theory of Probability & Its Applications History Published online:25 July 2006 InformationCopyright © 2001 Society for Industrial and Applied MathematicsKeywordscorrelation polynomialentropydistribution of m-patternsP-values$\chi^2$-distributionPDF Download Article & Publication DataArticle DOI:10.1137/S0040585X97978087Article page range:pp. 111-132ISSN (print):0040-585XISSN (online):1095-7219Publisher:Society for Industrial and Applied Mathematics