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.     

Maximal covers of finite groups

Abstract

Let λ(G) be the maximum number of subgroups in an irredundant covering of the finite group G. We prove that if G is a group with λ(G) ≤ 6, then G is supersolvable. We also describe the structure of groups G with λ(G) = 6. Moreover, we show that if G is a group with λ(G)?<?31, then G is solvable.     

On the number of generators needed for free profinite products of finite groups

We provide lower estimates on the minimal number of generators of the profinite completion of free products of finite groups. In particular, we show that if C ₁, ..., C _n are finite cyclic groups then there exists a finite group G which is generated by isomorphic copies of C ₁, ..., C _n and the minimal number of generators of G is n. The first author’s research is partially supported by NSF grant DMS-0701105. The second author’s research is partially supported by OTKA grant T38059 and the Magyary Zoltán Postdoctoral Fellowship.     

Pseudorandom generators for space-bounded computation

Pseudorandom generators are constructed which convertO(SlogR) truly random bits toR bits that appear random to any algorithm that runs inSPACE(S). In particular, any randomized polynomial time algorithm that runs in spaceS can be simulated using onlyO(Slogn) random bits. An application of these generators is an explicit construction of universal traversal sequences (for arbitrary graphs) of lengthn ^O(logn).The generators constructed are technically stronger than just appearing random to spacebounded machines, and have several other applications. In particular, applications are given for deterministic amplification (i.e. reducing the probability of error of randomized algorithms), as well as generalizations of it.This work was done in the Laboratory for Computer Science, MIT, supported by NSF 865727-CCR and ARO DALL03-86-K-017     

On finite groups whose Sylow subgroups have a bounded number of generators

Let G be a finite non-nilpotent group such that every Sylow subgroup of G is generated by at most δ elements, and such that p is the largest prime dividing |G|. We show that G has a non-nilpotent image G/N, such that N is characteristic and of index bounded by a function of δ and p. This result will be used to prove that G has a nilpotent normal subgroup of index bounded in terms of δ and p.     

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.     

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.     

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.     

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.     

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.     

Two generators for the general linear groups over finite fields

For every finite field F and every n≥2, the group GL(n,F) can be generated by two elements (which are explicitly described). The multiplicative semigroup of all n by n matrices over F can then be generated by three elements.     

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.     

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.     

On random permutations of finite groups

Given a finite abelian group G,  consider a uniformly random permutation of the set of all elements of G. Compute the difference of each pair of consecutive elements along the permutation. What is the number of occurrences of \(h\in G\setminus \{0\}\) in this sequence of differences? How do these numbers of occurrences behave for several group elements simultaneously? Can we get similar results for non-abelian G? How do the answers change if differences are replaced by sums? In this paper, we answer these questions. Moreover, we formulate analogous results in a general combinatorial setting.