Evaluation of the discrepancy of the linear congruential pseudo-random number sequences

DOI10.1007/BF02017347MaRDI QIDQ1813701zbMATH OpenOpenAlexFDO

Authors Virendra C. Bhavsar, Uday G. Gujar, J. D. Horton, Lambros A. Lambrou

Publication date 25 June 1992

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02017347

zbMATH Keywords

discrepancylinear congruential generatorpseudo-random uniform sequencerandom number generation

Mathematics Subject Classification ID

Irregularities of distribution, discrepancy (11K38) Pseudo-random numbers; Monte Carlo methods (11K45) Random number generation in numerical analysis (65C10)

Review text

The authors use the following measure \(D_ n(x_ 1,x_ 2,\dots,x_ n) = \hbox{supremum}\{| N(a,b;x,n)-(b-a)| : 0\leq a<b\leq 1\}\) to appreciate the discrepancy of a given pseudo-random uniform sequence \(x_ 1,x_ 2,\dots,x_ n\) from its real rectangular distribution, where \(N(a,b;x,n)\) is the number of terms \(x_ j\), \(1\leq j\leq n\), which belongs to the interval \([a,b)\). Essentially they compute the maximum of the differences between the empirical frequencies of the sequence \(x_ 1,x_ 2,\dots,x_ n\) into the domains \(D\) and their theoretical probabilities, this for all possible domains \(D\subset [0,1)\). Practically is impossible to consider all domains \(D\). For solving the problem the authors propose three variants which differ by the selection of the domains \(D\). In the first procedure the domains \(D\) are intervals \([a,b]\) where \(a\) and \(b-a\) vary with imposed quantities. The second procedure uses the domains \([0,x_ j]\), \(1\leq j \leq n\). The third procedure considers the domains \([0,k/m]\), \(1\leq k \leq m\), where \(1/m\) is the computation error of the discrepancy. Graphic results are included, too.

Recommendations

• The Exact Determination of Rectangle Discrepancy for Linear Congruential Pseudorandom Numbers
• The Performance of k-Step Pseudorandom Number Generators under the Uniformity Test
• Publication:4724719
• The serial test for pseudo-random numbers generated by the linear congruential method
• On pseudorandom \([0,1)\) and binary sequences

Cites work

• A Retrospective and Prospective Survey of the Monte Carlo Method
• Design and Analysis of Parallel Monte Carlo Algorithms
• scientific article; zbMATH DE number 3440485 (Why is no real title available?)
• scientific article; zbMATH DE number 3190084 (Why is no real title available?)
• On the Distribution of Pseudo-Random Numbers Generated by the Linear Congruential Method
• On the Distribution of Pseudo-Random Numbers Generated by the Linear Congruential Method. II
• On the Distribution of Pseudo-Random Numbers Generated by the Linear Congruential Method. III
• Quasi-Monte Carlo methods and pseudo-random numbers

Cited in

(5)

• The Exact Determination of Rectangle Discrepancy for Linear Congruential Pseudorandom Numbers
• Sequences with low discrepancy and pseudo-random numbers:theoretical results and numerical tests
• scientific article; zbMATH DE number 3997925 (Why is no real title available?)
• Geometric discrepancy. An illustrated guide
• Applications of uniformly distributed functions and sequences in statistic ergodic measuring techniques

This page was built for publication: Evaluation of the discrepancy of the linear congruential pseudo-random number sequences

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