Spectral Analysis of the MIXMAX Random Number Generators

Pierre L’Ecuyer (), Paul Wambergue () and Erwan Bourceret ()
Additional contact information
Pierre L’Ecuyer: Département d’Informatique et de Recherche Opérationnelle, Université de Montréal, Montréal, Québec H3C 3J7, Canada
Paul Wambergue: École Centrale, 92290 Châtenay-Malabry, France
Erwan Bourceret: École Polytechnique, 91128 Palaiseau, France

INFORMS Journal on Computing, 2020, vol. 32, issue 1, 135-144

Abstract: We study the lattice structure of random number generators of the MIXMAX family, a class of matrix linear congruential generators that produces a vector of random numbers at each step. The design of these generators was inspired by Kolmogorov K-systems over the unit torus in the real space, for which the transition function is measure preserving and produces a chaotic behavior. In actual implementations, however, the state space is a finite set of rational vectors, and the MIXMAX has a lattice structure just like linear congruential and multiple recursive generators. Its matrix entries were also selected in a special way to allow a fast implementation, and this has an impact on the lattice structure. We study this lattice structure for vectors of successive and nonsuccessive output values in various dimensions. We show in particular that for coordinates at specific lags not too far apart, in three dimensions, or if we construct points of k +2 or more successive values from the beginning of an output vector of size k , all the nonzero points lie in only two hyperplanes. This is reminiscent of the behavior of lagged-Fibonacci and add-with-carry/subtract-with-borrow generators. And even if we skip the output coordinates involved in this bad structure, other highly structured projections often remain, depending on the choice of parameters. We show that empirical statistical tests can easily detect this structure.

Keywords: random number generators; matrix linear congruential generators; lattice structure; spectral test; simulation (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0878 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:32:y:2020:i:1:p:135-144

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().