Gambling tests for pseudorandom number generators

DOI10.1016/S0378-4754(00)00271-8MaRDI QIDQ5938387zbMATH OpenWikidataFDO

Authors Stefan Wegenkittl

Publication date 26 November 2002

Published in Mathematics and Computers in Simulation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0378-4754(00)00271-8

zbMATH Keywords

gambling testgeneralized phi-divergencerandom number generatortwisted GFSR generator

Mathematics Subject Classification ID

Pseudo-random numbers; Monte Carlo methods (11K45) Random number generation in numerical analysis (65C10)

Review text

An important test for randomness of a sequence of pseudo-random numbers is the serial test what, applied to \(s\)-tuples, consists in a partition of the unit cube \([0,1)^s\) in \(m\) nonempty subsets. Although for the cyclic variant, the so-called overlapping serial test, the covariance matrix of the frequency counting vector is easier to compute than for the non-overlapping test, for greater \(s\) and \(m=\tilde m^s\), \(\tilde m\) fixed, the implementation is very time-consuming and almost impossible.NEWLINENEWLINENEWLINEThe author proposes now the following gambling test: Some feature of a random number will be compared with tossing an ideal coin. Now a gambler can bet whether among \(\lambda\) random numbers at least \(\kappa\) times ``head will occur, he can bet on ``tails or skip betting. The counting vector is 3-dimensional and its covariance matrix can be computed. This leads to a considerable dimension reduction. \(\lambda=52\) and \(\kappa=26\) are chosen.NEWLINENEWLINENEWLINEThe usual formed quadratic form is a special case of the \(\phi\)-divergence investigated by \textit{F. Liese} and \textit{I. Vajda} [Convex statistical distances. Teubner (1987; Zbl 0656.62004)], whose parameter as a design parameter of the test can be varied. It is mentioned that the new kind of test at the twisted GFSR generators of \textit{M. Matsumoto} and \textit{Y. Kurita} [ACM Trans. Model. Comput. Simul. 2, No.~3, 179-194 (1992; Zbl 0849.94014); ibid. 4, No.~3, 254-266 (1994; Zbl 0849.94015)] could detect deviations from equidistribution in higher dimensions.

Recommendations

• Sparse Serial Tests of Uniformity for Random Number Generators
• Statistical testing of PRNG: generalized gambler's ruin problem
• Tests of randomness by the gambler's ruin algorithm
• Testing the tests: using random number generators to improve empirical tests
• scientific article; zbMATH DE number 1736451

Cites work

• A comparative study of some pseudorandom number generators
• Good random number generators are (not so) easy to find
• Goodness-of-fit statistics for discrete multivariate data
• scientific article; zbMATH DE number 3911472 (Why is no real title available?)
• scientific article; zbMATH DE number 1103061 (Why is no real title available?)
• scientific article; zbMATH DE number 3082097 (Why is no real title available?)
• Inversive and linear congruential pseudorandom number generators in empirical tests
• Sparse Serial Tests of Uniformity for Random Number Generators
• Twisted GFSR generators
• Twisted GFSR generators II

Cited in

(10)

• Sum-discrepancy test on pseudorandom number generators
• scientific article; zbMATH DE number 2175081 (Why is no real title available?)
• On the Testing of Random Number Generators
• LAST VISIT TIME TESTS FOR PSEUDORANDOM NUMBERS
• scientific article; zbMATH DE number 6538334 (Why is no real title available?)
• Statistical testing of PRNG: generalized gambler's ruin problem
• Computing conditional probabilities for F₂-linear pseudorandom bit generators by splitting MacWilliams identity
• scientific article; zbMATH DE number 2219664 (Why is no real title available?)
• Re-seeding invalidates tests of random number generators
• Tests of randomness by the gambler's ruin algorithm

This page was built for publication: Gambling tests for pseudorandom number generators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5938387)