IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v32y2020i1p135-144.html
   My bibliography  Save this article

Spectral Analysis of the MIXMAX Random Number Generators

Author

Listed:
  • 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)

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.

Suggested Citation

  • Pierre L’Ecuyer & Paul Wambergue & Erwan Bourceret, 2020. "Spectral Analysis of the MIXMAX Random Number Generators," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 135-144, January.
  • Handle: RePEc:inm:orijoc:v:32:y:2020:i:1:p:135-144
    DOI: 10.1287/ijoc.2018.0878
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2018.0878
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2018.0878?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Savvidy, Konstantin & Savvidy, George, 2016. "Spectrum and entropy of C-systems MIXMAX random number generator," Chaos, Solitons & Fractals, Elsevier, vol. 91(C), pages 33-38.
    2. L’Ecuyer, Pierre & Munger, David & Oreshkin, Boris & Simard, Richard, 2017. "Random numbers for parallel computers: Requirements and methods, with emphasis on GPUs," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 135(C), pages 3-17.
    3. Pierre L'Ecuyer & Raymond Couture, 1997. "An Implementation of the Lattice and Spectral Tests for Multiple Recursive Linear Random Number Generators," INFORMS Journal on Computing, INFORMS, vol. 9(2), pages 206-217, May.
    4. Pierre L'Ecuyer & Richard Simard, 2014. "On the Lattice Structure of a Special Class of Multiple Recursive Random Number Generators," INFORMS Journal on Computing, INFORMS, vol. 26(3), pages 449-460, August.
    5. L’Ecuyer, Pierre & Simard, Richard, 2001. "On the performance of birthday spacings tests with certain families of random number generators," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 55(1), pages 131-137.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Pierre L'Ecuyer & Richard Simard, 2014. "On the Lattice Structure of a Special Class of Multiple Recursive Random Number Generators," INFORMS Journal on Computing, INFORMS, vol. 26(3), pages 449-460, August.
    2. L’Ecuyer, Pierre & Granger-Piché, Jacinthe, 2003. "Combined generators with components from different families," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 62(3), pages 395-404.
    3. L'Ecuyer, Pierre, 2004. "Random number generation," Papers 2004,21, Humboldt University of Berlin, Center for Applied Statistics and Economics (CASE).
    4. Savvidy, George & Savvidy, Konstantin, 2018. "Exponential decay of correlations functions in MIXMAX generator of pseudorandom numbers," Chaos, Solitons & Fractals, Elsevier, vol. 107(C), pages 244-250.
    5. Harase, Shin, 2019. "Conversion of Mersenne Twister to double-precision floating-point numbers," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 161(C), pages 76-83.
    6. Pierre L'Ecuyer & Christiane Lemieux, 2000. "Variance Reduction via Lattice Rules," Management Science, INFORMS, vol. 46(9), pages 1214-1235, September.
    7. L'Ecuyer, Pierre & Andres, Terry H., 1997. "A random number generator based on the combination of four LCGs," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 44(1), pages 99-107.
    8. Pierre L'Ecuyer & Richard Simard & E. Jack Chen & W. David Kelton, 2002. "An Object-Oriented Random-Number Package with Many Long Streams and Substreams," Operations Research, INFORMS, vol. 50(6), pages 1073-1075, December.
    9. Hui-Chin Tang & Chiang Kao, 2004. "Searching for Good Multiple Recursive Random Number Generators via a Genetic Algorithm," INFORMS Journal on Computing, INFORMS, vol. 16(3), pages 284-290, August.
    10. Aljahdali Asia & Mascagni Michael, 2017. "Feistel-inspired scrambling improves the quality of linear congruential generators," Monte Carlo Methods and Applications, De Gruyter, vol. 23(2), pages 89-99, June.
    11. Tang, Hui-Chin, 2005. "Reverse multiple recursive random number generators," European Journal of Operational Research, Elsevier, vol. 164(2), pages 402-405, July.
    12. Martirosyan, Narek & Savvidy, Konstantin & Savvidy, George, 2019. "Spectral test of the MIXMAX random number generators," Chaos, Solitons & Fractals, Elsevier, vol. 118(C), pages 242-248.
    13. L’Ecuyer, Pierre & Simard, Richard, 2001. "On the performance of birthday spacings tests with certain families of random number generators," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 55(1), pages 131-137.
    14. Kolonko, Michael & Gu, Feng & Wu, Zijun, 2019. "Improving the statistical quality of random number generators by applying a simple ratio transformation," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 157(C), pages 130-142.
    15. Pierre L'Ecuyer, 1999. "Good Parameters and Implementations for Combined Multiple Recursive Random Number Generators," Operations Research, INFORMS, vol. 47(1), pages 159-164, February.
    16. Michael S. Delgado & Christopher F. Parmeter, 2013. "Embarrassingly Easy Embarrassingly Parallel Processing in R: Implementation and Reproducibility," Working Papers 2013-06, University of Miami, Department of Economics.
    17. Tang, Hui-Chin, 2006. "Theoretical analyses of forward and backward heuristics of multiple recursive random number generators," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1760-1768, November.
    18. L’Ecuyer, Pierre & Munger, David & Oreshkin, Boris & Simard, Richard, 2017. "Random numbers for parallel computers: Requirements and methods, with emphasis on GPUs," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 135(C), pages 3-17.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:32:y:2020:i:1:p:135-144. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.