Sparse serial tests of uniformity for random number generators
Abstract
Different versions of the serial test for testing the uniformity and independence of vectors of successive values produced by a (pseudo)random number generator are studied. These tests partition the t-dimensional unit hypercube into k cubic cells of equal volume, generate n points (vectors) in this hypercube, count how many points fall in each cell, and compute a test statistic defined as the sum of values of some univariate function f applied to these k individual counters. Both overlapping and nonoverlapping vectors are considered. For different families of generators, such as linear congruential, Tausworthe, nonlinear inversive, etc., different ways of choosing these functions and of choosing k are compared, and formulas are obtained for the (estimated) sample size required to reject the null hypothesis of independent uniform random variables, as a function of the period length of the generator. For the classes of alternatives that correspond to linear generators, the most efficient tests turn out to have $k \gg n$ (in contrast to what is usually done or recommended in simulation books) and to use overlapping vectors.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In two-level tests, computational errors accumulate at each level and two-level tests detect the lack-of-fit of the approximation, leading to rejection even if the generator is good.
“In this case, computational errors accumulate at each level and two-level tests detect the Lack-Of-Fit of that approximation, leading to rejection even if the generator is good [7, 10, 13, 17].”
From Checking the quality of approximation of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="mml84" display="inline" overflow="scroll" altimg="si2.gif"><mml:mi>p</mml:mi></mml:math>-values in statistical tests for random number generators by using a three-level test (2019) · cites this paper as [13]
Cites
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 16,097 · see citing works
Simulation Modeling and Analysis.
Schervish, M. J., Law, A. M., & Kelton, W. D. (1983) · Journal of the American Statistical Association · doi:10.2307/2288169 · Cited by 8,884 · see citing works
Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator
Matsumoto, M., & Nishimura, T. (1998) · ACM Transactions on Modeling and Computer Simulation · doi:10.1145/272991.272995 · Cited by 5,780 · see citing works
Random Number Generation and Quasi-Monte Carlo Methods.
Collings, B. J., & Niederreiter, H. (1993) · Journal of the American Statistical Association · doi:10.2307/2290359 · Cited by 2,944 · see citing works
Random Number Generation and Quasi-Monte Carlo Methods
Niederreiter, H. (1992) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970081 · Cited by 2,786 · see citing works
Bratley, P., Fox, B. L., & Schrage, L. E. (1983) · Springer eBooks · doi:10.1007/978-1-4419-8724-2 · Cited by 1,479 · see citing works
Information-type measures of difference of probability distributions and indirect observation
Csiszár, I. (1967) · Studia Scientiarum Mathematicarum Hungarica · Cited by 1,349 · see citing works
Random number generators: good ones are hard to find
Park, S. K., & Miller, K. (1988) · Communications of the ACM · doi:10.1145/63039.63042 · Cited by 1,268 · see citing works
Barbour, A. D., Holst, L. K., & Janson, S. (1992) · doi:10.1093/oso/9780198522355.001.0001 · Cited by 1,254 · see citing works
The Art of Computer Programming, Vol. 2
Knuth, D. E. (1981) · Medical Entomology and Zoology · Cited by 861 · see citing works
Goodness-of-Fit Statistics for Discrete Multivariate Data
Read, T. R. C., & Cressie, N. (1988) · Springer series in statistics · doi:10.1007/978-1-4612-4578-0 · Cited by 778 · see citing works
Goodness-of-fit statistics for discrete multivariate data
Read, T. R. C., & Cressie, N. (1989) · Choice Reviews Online · doi:10.5860/choice.26-2740 · Cited by 745 · see citing works
A Guide to Chi-Squared Testing
Koehler, K. J., Greenwood, P. E., & Nikulin, M. S. (1997) · Journal of the American Statistical Association · doi:10.2307/2965733 · Cited by 628 · see citing works
Efficient and portable combined random number generators
L’Ecuyer, P. (1988) · Communications of the ACM · doi:10.1145/62959.62969 · Cited by 494 · see citing works
Self-citationGood Parameters and Implementations for Combined Multiple Recursive Random Number Generators
L’Ecuyer, P. (1999) · Operations Research · doi:10.1287/opre.47.1.159 · Cited by 463 · see citing works
Self-citationSchruben, L. W., Bratley, P., Fox, B. L., et al. (1985) · Journal of the American Statistical Association · doi:10.2307/2287950 · Cited by 430 · see citing works
A New Class of Random Number Generators
Marsaglia, G., & Zaman, A. (1991) · The Annals of Applied Probability · doi:10.1214/aoap/1177005878 · Cited by 373 · see citing works
An Object-Oriented Random-Number Package with Many Long Streams and Substreams
L’Ecuyer, P., Simard, R., Chen, E. J., et al. (2002) · Operations Research · doi:10.1287/opre.50.6.1073.358 · Cited by 349 · see citing works
Self-citationMaximally equidistributed combined Tausworthe generators
L'Ecuyer, P. (1996) · Mathematics of Computation · doi:10.1090/s0025-5718-96-00696-5 · Cited by 276 · see citing works
Self-citationUniform random number generation
L’Ecuyer, P. (1994) · Annals of Operations Research · doi:10.1007/bf02136827 · Cited by 268 · see citing works
Self-citationA Guide to Chi-Squared Testing
Antoch, J. (1997) · Computational Statistics & Data Analysis · doi:10.1016/s0167-9473(97)84761-5 · Cited by 256 · see citing works
Tables of linear congruential generators of different sizes and good lattice structure
L’Ecuyer, P. (1999) · Mathematics of Computation · doi:10.1090/s0025-5718-99-00996-5 · Cited by 234 · see citing works
Self-citationFishman, G. S., & Moore, L. R. (1986) · SIAM Journal on Scientific and Statistical Computing · doi:10.1137/0907002 · Cited by 205 · see citing works
RANLUX: A Fortran implementation of the high-quality pseudorandom number generator of Lüscher
James, F. (1994) · Computer Physics Communications · doi:10.1016/0010-4655(94)90233-x · Cited by 192 · see citing works
Combined Multiple Recursive Random Number Generators
L'Ecuyer, P. (1995) · Operational Research · doi:10.1287/opre.44.5.816 · Cited by 150 · see citing works
Self-citationThe serial test for sampling numbers and other tests for randomness
Good, I. J. (1953) · Mathematical Proceedings of the Cambridge Philosophical Society · doi:10.1017/s030500410002836x · Cited by 115 · see citing works
Testing random number generators
L'Ecuyer, P. (1992) · Proceedings of the 24th conference on Winter simulation - WSC '92 · doi:10.1145/167293.167354 · Cited by 115 · see citing works
Self-citationAsymptotic normality and efficiency for certain goodness-of-fit tests
Holst, L. K. (1972) · Biometrika · doi:10.1093/biomet/59.1.137 · Cited by 110 · see citing works
Asymptotic divergence of estimates of discrete distributions
Morales, D., Pardo, L., & Vajda, I. (1995) · Journal of Statistical Planning and Inference · doi:10.1016/0378-3758(95)00013-y · Cited by 106 · see citing works
Monkey tests for random number generators
Marsaglia, G., & Zaman, A. (1993) · Computers & Mathematics with Applications · doi:10.1016/0898-1221(93)90001-c · Cited by 103 · see citing works
Inversive Congruential Pseudorandom Numbers: A Tutorial
Eichenauer‐Herrmann, J., & Eichenauer‐Herrmann, J. (1992) · International Statistical Review · doi:10.2307/1403647 · Cited by 92 · see citing works
A random number generator based on the combination of four LCGs
L’Ecuyer, P., & Andres, T. (1997) · Mathematics and Computers in Simulation · doi:10.1016/s0378-4754(97)00052-9 · Cited by 89 · see citing works
Self-citationThoughts on pseudorandom number generators
Ripley, B. D. (1990) · Journal of Computational and Applied Mathematics · doi:10.1016/0377-0427(90)90346-2 · Cited by 82 · see citing works
Portable Random Number Generators
Press, W. H., & Teukolsky, S. A. (1992) · Computers in Physics · doi:10.1063/1.4823101 · Cited by 76 · see citing works
Bad Lattice Structures for Vectors of Nonsuccessive Values Produced by Some Linear Recurrences
L'Ecuyer, P. (1997) · INFORMS journal on computing · doi:10.1287/ijoc.9.1.57 · Cited by 73 · see citing works
Self-citationRandom Number Generators: Selection Criteria and Testing
L'Ecuyer, P., & Hellekalek, P. (1998) · Lecture notes in statistics · doi:10.1007/978-1-4612-1702-2_5 · Cited by 71 · see citing works
Self-citationInversive and linear congruential pseudorandom number generators in empirical tests
Leeb, H., & Wegenkittl, S. (1997) · ACM Transactions on Modeling and Computer Simulation · doi:10.1145/249204.249208 · Cited by 59 · see citing works
Self-citationOn the lattice structure of the add-with-carry and subtract-with-borrow random number generators
Tezuka, S., L'Ecuyer, P., & Couture, R. (1993) · ACM Transactions on Modeling and Computer Simulation · doi:10.1145/159737.159749 · Cited by 58 · see citing works
Self-citationStructural properties for two classes of combined random number generators
L’Ecuyer, P., & Tezuka, S. (1991) · Mathematics of Computation · doi:10.1090/s0025-5718-1991-1094954-3 · Cited by 52 · see citing works
Self-citationPlauger, P. J. (1991) · International Linear Collider · Cited by 49 · see citing works
Pseudorandom number generator for massively parallel molecular-dynamics simulations
Holian, B. L., Percus, O. E., Warnock, T. T., et al. (1994) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.50.1607 · Cited by 32 · see citing works
Uniform random number generators
L’Ecuyer, P. (1998) · Winter Simulation Conference · doi:10.5555/293172.293213 · Cited by 27 · see citing works
Self-citationStructural Properties for Two Classes of Combined Random Number Generators
L’Ecuyer, P., & Tezuka, S. (1991) · Mathematics of Computation · doi:10.2307/2938714 · Cited by 23 · see citing works
Self-citationBit-Wise Behavior of Random Number Generators
Altman, N. S. (1988) · SIAM Journal on Scientific and Statistical Computing · doi:10.1137/0909065 · Cited by 22 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Pareschi, F., Rovatti, R., & Setti, G. (2012) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2012.2185227 · Cited by 189 · see citing works
Haramoto, H., & Matsumoto, M. (2019) · Mathematics and Computers in Simulation · doi:10.1016/j.matcom.2018.08.005 · Cited by 8 · see citing works
“In this case, computational errors accumulate at each level and two-level tests detect the Lack-Of-Fit of that approximation, leading to rejection even if the generator is good [7, 10, 13, 17].”
Background
- Authors
- L'Ecuyer, P., Simard, R., & Wegenkittl, S.
- Affiliations
- University of Salzburg (AT)
- ORCID
- Wegenkittl, Stefan
- Venue
- SIAM Journal on Scientific Computing
- Published
- 2002-01
- Volume
- 24
- Issue
- 2
- Pages
- 652-668
- ISSN
- 1064-8275 (ISSN-L)
- 1095-7197
- OpenAlex
- W2002696859
- Cited by
- 50
- References
- 44
- Citations by year
- 2026: 1 · 2025: 1 · 2023: 1 · 2022: 1 · 2021: 3 · 2020: 4 · 2019: 1 · 2018: 3 · 2017: 2 · 2016: 1 · 2015: 2 · 2014: 1 · 2013: 1 · 2012: 2
- FWCI
- 2.01
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Journal on Scientific Computing (publishedVersion)
- Funders
- North Carolina State University
- Austrian Science Fund
- Topics
- Physical Sciences › Mathematics › Numerical Analysis › Mathematical Approximation and Integration
- Social Sciences › Decision Sciences › Management Science and Operations Research › Simulation Techniques and Applications
- Physical Sciences › Mathematics › Statistics and Probability › Probability and Statistical Research
- Keywords
- uniformity testing, random number generators, independence testing, linear congruential generator, sample size determination, pseudorandom numbers
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
