Reverse multiple recursive random number generators

Every multiple recursive generator (MRG) has an associated reverse MRG that generates the same sequence but in reverse order. An explicit formula for the recurrence of this reverse MRG is derived based on finite field arithmetic. These two MRGs are equal in both periodicity and spectral value. This property could be exploited to reduce the number of candidates when searching for good MRG parameters.     

On goodness-of-fit tests for multiple recursive random number generators

This paper considers the problem of reducing the computational time in testing uniformity for a full period multiple recursive generator (MRG). If a sequence of random numbers generated by a MRG is divided into even number of segments, say 2s, then the multinomial goodness-of-fit tests and the empirical distribution function goodness-of-fit tests calculated from the ith segment are the same as those of the (s + i)th segment. The equivalence properties of the goodness-of-fit test statistics for a MRG and its associated reverse and additive inverse MRGs are also discussed.     

Efficient computer search of large-order multiple recursive pseudo-random number generators

Utilizing some results in number theory, we propose an efficient method to speed up the computer search of large-order maximum-period Multiple Recursive Generators (MRGs). We conduct the computer search and identify many efficient and portable MRGs of order up to 25,013, which have the equi-distribution property in up to 25,013 dimensions and the period lengths up to 10^233,361 approximately. In addition, a theoretical test is adopted to further evaluate and compare these generators. An extensive empirical study shows that these generators behave well when tested with the stringent Crush battery of the test package TestU01.     

A multiple recursive non-linear congruential pseudo random number generator

On-linear multiple recursive congruential pseudo random number generator with prime modulus p is introduced. Let x, n0, be the sequence generated by a usual linear (r+1)-step recursive congruential generator with prime modulus p and denote by N(n), n0, the sequence of non-negative integers with x_N(n)0 (mod p). The non-linear generator is defined by z_nx_N(n)+1·x _N(n) ^–1 (mod p), n0, where x _N(n) ^–1 denotes the inverse element of x_N(n) in the Galois field GF(p). A condition is given which ensures that the generated sequence is purely periodic with period length p^r and all (p–1)^r r-tupels (y₁,...,y_r) with 1y₁,...,y_rp are generated once per period when r-tupels of consecutive numbers of the generated sequence are formed. For r=1 this generator coincides with the generator introduced by Eichenauer and Lehn [2].     

Theoretical and empirical convergence results for additive congruential random number generators

Additive Congruential Random Number (ACORN) generators represent an approach to generating uniformly distributed pseudo-random numbers that is straightforward to implement efficiently for arbitrarily large order and modulus; if it is implemented using integer arithmetic, it becomes possible to generate identical sequences on any machine.This paper briefly reviews existing results concerning ACORN generators and relevant theory concerning sequences that are well distributed mod 1 in k dimensions. It then demonstrates some new theoretical results for ACORN generators implemented in integer arithmetic with modulus M=2^μ showing that they are a family of generators that converge (in a sense that is defined in the paper) to being well distributed mod 1 in k dimensions, as μ=log₂M tends to infinity. By increasing k, it is possible to increase without limit the number of dimensions in which the resulting sequences approximate to well distributed.The paper concludes by applying the standard TestU01 test suite to ACORN generators for selected values of the modulus (between 2⁶⁰ and 2¹⁵⁰), the order (between 4 and 30) and various odd seed values. On the basis of these and earlier results, it is recommended that an order of at least 9 be used together with an odd seed and modulus equal to 2^30p, for a small integer value of p. While a choice of p=2 should be adequate for most typical applications, increasing p to 3 or 4 gives a sequence that will consistently pass all the tests in the TestU01 test suite, giving additional confidence in more demanding applications.The results demonstrate that the ACORN generators are a reliable source of uniformly distributed pseudo-random numbers, and that in practice (as suggested by the theoretical convergence results) the quality of the ACORN sequences increases with increasing modulus and order.     

Anosov C-systems and random number generators

We further develop our previous proposal to use hyperbolic Anosov C-systems to generate pseudorandom numbers and to use them for efficient Monte Carlo calculations in high energy particle physics. All trajectories of hyperbolic dynamical systems are exponentially unstable, and C-systems therefore have mixing of all orders, a countable Lebesgue spectrum, and a positive Kolmogorov entropy. These exceptional ergodic properties follow from the C-condition introduced by Anosov. This condition defines a rich class of dynamical systems forming an open set in the space of all dynamical systems. An important property of C-systems is that they have a countable set of everywhere dense periodic trajectories and their density increases exponentially with entropy. Of special interest are the C-systems defined on higher-dimensional tori. Such C-systems are excellent candidates for generating pseudorandom numbers that can be used in Monte Carlo calculations. An efficient algorithm was recently constructed that allows generating long C-system trajectories very rapidly. These trajectories have good statistical properties and can be used for calculations in quantum chromodynamics and in high energy particle physics.     

Some properties of random number generators

Translated from Problemy Ustoichivosti Stokhasticheskikh Modelei, Trudy Seminara, pp. 36–40, 1987.     

Regularities in congruential random number generators

Summary This paper suggests, as did an earlier one, [1] that points inn-space produced by congruential random number generators are too regular for general Monte Carlo use. Regularity was established in [1] for multiplicative congruential generators by showing that all the points fall in sets of relatively few parallel hyperplanes. The existence of many containing sets of parallel hyperplanes was easily established, but proof that the number of hyperplanes was small required a result of Minkowski from the geometry of numbers—a symmetric, convex set of volume 2 ⁿ must contain at least two points with integral coordinates. The present paper takes a different approach to establishing the coarse lattice structure of congruential generators. It gives a simple, self-contained proof that points inn-space produced by the general congruential generatorr _i+1 ar _i +b modm must fall on a lattice with unit-cell volume at leastm ^n–1 There is no restriction ona orb; this means thatall congruential random number generators must be considered unsatisfactory in terms of lattices containing the points they produce, for a good generator of random integers should have ann-lattice with unit-cell volume 1.     

Parallelization of random number generators and long-range correlations

Summary Partitions of pseudo-random sequences generated by congruential schemes are investigated for use on computer systems where multiple processing units run in parallel for the solution of a Monte Carlo problem. A special partition is suggested which ensures independence between the units working simultaneously, and yields reproducible sequences. The analysis performed has brought out the existence of strong autocorrelations between terms located far apart in the sequences, dependent only on the congruential nature of the generators. The study of these correlations — carried out in a number theoretic framework — points out that only small fractions of the sequences can be safely used.     

Re-seeding invalidates tests of random number generators

Kim et al. [C. Kim, G.H. Choe, D.H. Kim, Test of randomness by the gambler’s ruin algorithm, Applied Mathematics and Computation 199 (2008) 195-210] recently presented a test of random number generators based on the gambler’s ruin problem and concluded that several generators, including the widely used Mersenne Twister, have hidden defects. We show here that the test by Kim et al. suffers from a subtle, but consequential error: re-seeding the pseudorandom number generator with a fixed seed for each starting point of the gambler’s ruin process induces a random walk of the test statistic as a function of the starting point. The data presented by Kim et al. are thus individual realizations of a random walk and not suited to judge the quality of pseudorandom number generators. When generating or analyzing the gambler’s ruin data properly, we do not find any evidence for weaknesses of the Mersenne Twister and other widely used random number generators.     

The additive congruential random number generator—A special case of a multiple recursive generator

This paper considers an approach to generating uniformly distributed pseudo-random numbers which works well in serial applications but which also appears particularly well-suited for application on parallel processing systems. Additive Congruential Random Number (ACORN) generators are straightforward to implement for arbitrarily large order and modulus; if implemented using integer arithmetic, it becomes possible to generate identical sequences on any machine.     

Efficiency test of pseudorandom number generators using random walks

Markov chain Monte Carlo methods and computer simulations usually use long sequences of random numbers generated by deterministic rules, so-called pseudorandom number generators. Their efficiency depends on the convergence rate to the stationary distribution and the quality of random numbers used for simulations. Various methods have been employed to measure the convergence rate to the stationary distribution, but the effect of random numbers has not been much discussed. We present how to test the efficiency of pseudorandom number generators using random walks.     

The sub-lattice structure of linear congruential random number generators

Sequences of pseudo-random numbers are discussed which are generated by the linear congruential method where the period is equal to the modulus m. Such sequences are divided into non-overlapping vectors with n components. In this way for each initial number exactly m/gcd(n, m) different vectors are obtained. It is shown that the periodic continuation (with period m) of these vectors forms a grid which is a sub-grid of the familiar grid generated by all m overlapping vectors. A sub-lattice structure also exists for certain multiplicative congruential generators which are often used in practice.     

Kalman-Bucy filtering equations of forward and backward stochastic systems and applications to recursive optimal control problems

This paper is concerned with Kalman-Bucy filtering problems of a forward and backward stochastic system which is a Hamiltonian system arising from a stochastic optimal control problem. There are two main contributions worthy pointing out. One is that we obtain the Kalman-Bucy filtering equation of a forward and backward stochastic system and study a kind of stability of the aforementioned filtering equation. The other is that we develop a backward separation technique, which is different to Wonham's separation theorem, to study a partially observed recursive optimal control problem. This new technique can also cover some more general situation such as a partially observed linear quadratic non-zero sum differential game problem is solved by it. We also give a simple formula to estimate the information value which is the difference of the optimal cost functionals between the partial and the full observable information cases.     

A CLASS OF RANDOM NUMBER GENERATORS BASED ON WEYL SEQUENCE

The generation of good pseudo-random numbers is the base of many important fields in scientific computing, such as randomized algorithms and numerical solution of stochastic differential equations. In this paper, a class of random number generators （RNGs） based on Weyl sequence is proposed. The uniformity of those RNGs is proved theoretically. Statistical and numerical computations show the efficiency of the methods.     

Patterns in stock market movements tested as random number generators

This paper shows that tests of Random Number Generators (RNGs) may be used to test the Efficient Market Hypothesis (EMH). It uses the Overlapping Serial Test (OST), a standard test in RNG research, to detect anomalous patterns in the distribution of sequences of stock market movements up and down. Our results show that most stock markets exhibit idiosyncratic recurrent patterns, contrary to the efficient market hypothesis; also that OST detects a different kind of non-randomness to standard econometric long- and short-memory tests. Exposure of these anomalies should contribute to making markets more efficient.     

Pseudorandom number generators based on random covers for finite groups

Random covers for finite groups have been introduced in Magliveras et?al. (J Cryptol 15:285–297, 2002), Lempken et?al. (J Cryptol 22:62–74, 2009), and Svaba and van Trung (J Math Cryptol 4:271–315, 2010) for constructing public key cryptosystems. In this article we describe a new approach for constructing pseudorandom number generators using random covers for large finite groups. We focus, in particular, on the class of elementary abelian 2-groups and study the randomness of binary sequences generated from these generators. We successfully carry out an extensive test of the generators by using the NIST Statistical Test Suite and the Diehard battery of tests. Moreover, the article presents argumentation showing that the generators are suitable for cryptographic applications. Finally, we include performance data of the generators and propose a method of using them in practice.     

Testing random number generators by numerical modeling of an exactly solvable problem

Monte Carlo numerical modeling of a problem with a known exact solution is used to test linear multiplicative generators with modulus M = 2³¹ ? 1 for their applicability in parallel computing. The deviations of the calculated values of the rotational temperature from the known theoretical values are compared with the possible errors of the Monte Carlo method due to the finiteness of statistical samples. In addition, sample correlation coefficients are used to estimate true correlation coefficients between the values of the rotational temperature obtained on different processors with different multipliers, as well as in the case where additional samples were drawn at the terminal state on each processor in order to increase the size of the total sample. For this purpose, by means of special partial averaging, the random values of the rotational temperature were transformed into approximately normally distributed variables; then, for the variables obtained, true correlation coefficients were estimated by sample correlation coefficients. It was discovered that 204 different multipliers suggested by G.S. Fishman, L.R. Moore exhibit the best performance when used in a parallel implementation of the Monte Carlo method: all deviations are less than the theoretical Monte Carlo errors. Moreover, no correlations between the random variables produced by generators with different multipliers were detected. This suggests that generators with different multipliers produce independent sequences of pseudorandom numbers. However, drawing additional samples on each processor, which is frequently done to increase the size of the total sample, gives rise to correlations. Moreover, in many such cases, the theoretical errors of the Monte Carlo method for multipliers in the bottom part of the list proposed by Fishman and Moore are less than the values of temperature deviations and, therefore, should not be used in this way.