Archive for pseudo-random generator

about randomness (im Hamburg)

Posted in Statistics, Travel, University life with tags , , , , , , , , , , , , on February 20, 2013 by xi'an

exhibit in DESY campus, Hamburg, Germany, Feb. 19, 2013True randomness was the topic of the `Random numbers; fifty years later’ talk in DESY by Frederick James from CERN. I had discussed a while ago a puzzling book related to this topic. This talk went along a rather different route, focussing on random generators. James put this claim that there are computer based physical generators that are truly random. (He had this assertion that statisticians do not understand randomness because they do not know quantum mechanics.) He distinguished those from pseudo-random generators: “nobody understood why they were (almost) random”, “IBM did not know how to generate random numbers”… But then spent the whole talk discussing those pseudo-random generators. Among other pieces of trivia, James mentioned that George Marsaglia was the one exhibiting the hyperplane features of congruential generators. That Knuth achieved no successful definition of what randomness is in his otherwise wonderful books! James thus introduced Kolmogorov’s mixing (not Kolmogorov’s complexity, mind you!) as advocated by Soviet physicists to underlie randomness. Not producing anything useful for RNGs in the 60′s. He then moved to the famous paper by Ferrenberg, Landau and Wong (1992) that I remember reading more or less at the time. In connection with the phase transition critical slowing down phenomena in Ising model simulations. And connecting with the Wang-Landau algorithm of flipping many sites at once (which exhibited long-term dependences in the generators). Most interestingly, a central character in this story is Martin Lüscher, based in DESY, who expressed the standard generator of the time RCARRY into one studied by those Soviet mathematicians,

X’=AX

showing that it enjoyed Kolmogorov mixing, but with a very poor Lyapunov coefficient. I partly lost track there as RCARRY was not perfect. And on how this Kolmogorov mixing would relate to long-term dependencies. One explanation by James was that this property is only asymptotic. (I would even say statistical!) Also interestingly, the 1994 paper by Lüscher produces the number of steps necessary to attain complete mixing, namely 15 steps, which thus works as a cutoff point. (I wonder why a 15-step RCARRY is slower, since A15 can be computed at once… It may be due to the fact that A is sparse while A15 is not.) James mentioned that Marsaglia’s Die Hard battery of tests is now obsolete and superseded by Pierre Lecuyer’s TestU01.

In conclusion, I did very much like this presentation from an insider, but still do not feel it makes a contribution to the debate on randomness, as it stayed put on pseudorandom generators. To keep the connection with von Neumann, they all produce wrong answers from a randomness point of view, if not from a statistical one. (A final quote from the talk: “Among statisticians and number theorists who are supposed to be specialists, they do not know about Kolmogorov mixing.”) [Discussing with Fred James at the reception after the talk was obviously extremely pleasant, as he happened to know a lot of my Bayesian acquaintances!]

dirty MCMC streams

Posted in Statistics, Travel, University life with tags , , , , on May 7, 2012 by xi'an

 

Iain Murray and Lloyd T. Elliott had posted this paper on arXiv just before I left for my U,K, 2012 tour and I did not have time to read it in detail, nor obviously to report on it. Fortunately, during the ICMS meeting, Iain presented an handmade poster on this paper that allowed me a quick tour, enough to report on the contents! The main point of the paper is that it is possible to modify many standard MCMC codes so that they can be driven by a dependent random sequence. The authors show that various if specific dependent sequences of uniform variates do not modify the right target and the ergodicity of the MCMC scheme. As mentioned in the conclusion of the paper, this may have interesting consequences in parallel implementations where randomness becomes questionable, or in physical random generators, whose independence may also be questionable…

WSC 2[0]11

Posted in pictures, Statistics, Travel, University life with tags , , , , , , , , , on December 12, 2011 by xi'an

I have now registered for the WSC 2011 conference and I am looking forward the first day of talks tomorrow. Especially since, reading from the abstracts to the talks, it sounds as if many participants have a different understanding of the word simulation than I have. (I had the same impression this summer when taking part in a half-day of talks in Lancaster.) I am however slightly worried at having prepared my (advanced) tutorial for the right crowd, being unable to judge the background of the audience. Some of the talks are highly technical, others seem much more elementary… (I spent the whole night and morning, except for a fairly long and great run in the hills at sunrise, collating and adapting my slides from my graduate course and from different talks. The outcome is on slideshare.)

Randomness through computation

Posted in Books, Statistics, University life with tags , , , , , , , , , , , , , , on June 22, 2011 by xi'an

A few months ago, I received a puzzling advertising for this book, Randomness through Computation, and I eventually ordered it, despite getting a rather negative impression from reading the chapter written by Tomasso Toffoli… The book as a whole is definitely perplexing (even when correcting for this initial bias) and I would not recommend it to readers interested in simulation, in computational statistics or even in the philosophy of randomness. My overall feeling is indeed that, while there are genuinely informative and innovative chapters in this book, some chapters read more like newspeak than scientific material (mixing the Second Law of Thermodynamics, Gödel’s incompleteness theorem, quantum physics, and NP completeness within the same sentence) and do not provide a useful entry on the issue of randomness. Hence, the book is not contributing in a significant manner to my understanding of the notion. (This post also appeared on the Statistics Forum.) Continue reading

A survey of the [60′s] Monte Carlo methods [2]

Posted in Books, R, Statistics, University life with tags , , , , , on May 18, 2011 by xi'an

The 24 questions asked by John Halton in the conclusion of his 1970 survey are

  1. Can we obtain a theory of convergence for random variables taking values in Fréchet spaces?
  2. Can the study of Monte Carlo estimates in separable Fréchet spaces give a theory of global approximation?
  3. When sampling functions, what constitutes a representative sample of function values?
  4. Can one apply Monte Carlo to pattern recognition?
  5. Relate Monte Carlo theory to the theory of random equations.
  6. What can be said about quasi-Monte Carlo estimates for finite-dimensional and infinite-dimensional integrals?
  7. Obtain expression, asymptotic forms or upper bounds for L² and L discrepancies of quasirandom sequences.
  8. How should one improve quasirandom sequences?
  9. How to interpret the results of statistical tests applied to pseudo- or quasirandom sequences?
  10. Can we develop a meaningful statistical theory of quasi-Monte Carlo estimates?
  11. Can existing Monte Carlo techniques be improved and applied to new classes of problems?
  12. Can the design of Monte Carlo estimators be made more systematic?
  13. How can the idea of sequential Monte Carlo be extended?
  14. Can sampling with signed probabilities be made practical?
  15. What is the best allocation effort in obtaining zeroth- and first-level estimators in algebraic problems?
  16. Examine the Monte Carlo analogues of the various matrix iterative schemes.
  17. Develop the schemes of grid refinement in continuous problems.
  18. Develop new Monte Carlo eigenvectors and eigenvalue techniques.
  19. Develop fast, reliable true canonical random generators.
  20. How is the output of a true random generator to be tested?
  21. Develop fast, efficient methods for generating arbitrary random generators.
  22. Can we really have useful general purpose pseudorandom sequences.
  23. What is the effect of the discreteness of digital computers on Monte Carlo calculations?
  24. Is there a way to estimate the accuracy of Monte Carlo estimates?
Follow

Get every new post delivered to your Inbox.

Join 558 other followers