dirty MCMC streams

 

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…

atmospheric random generator?!

As I was glancing through The Cleanest Line, (the outdoor clothing company) Patagonia‘s enjoyable—as long as one keeps in mind Patagonia is a company, although with commendable ethical and ecological goals—blog, I came upon this entry “And the Winner of “Chasing Waves” is …” where the name of the winner of the book Chasing Wave was revealed. (Not that I am particularly into surfing…!) The interesting point to which I am coming so circumlocutory (!) is that they use a random generator based on atmospheric noise to select the winner! I particularly like the sentence that the generator “for many purposes is better than the pseudo-random number algorithms typically used in computer programs”. For which purpose exactly?!

Now, to be (at least a wee) fair, the site of random.org contains an explanation about the quality of their generator. I am however surprised by the comparison they run with the rand() function from PHP on Microsoft Windows, since it produces a visible divergence from uniformity on a bitmap graph… Further investigation led to this explanation of the phenomenon, namely the inadequacy of the PHP language rather than of the underlying (pseudo-)random generator. (It had been a while since I had a go at this randomness controvery!)

How quickly does randomness appear?

This was the [slightly off-key]  title of the math column in the November issue of La Recherche, in any case intriguing enough for me to buy this general public science magazine on the metro platform and to read it immediately while waiting for an uncertain train, thanks to the nth strike of the year on my train line… But this was the occasion for an exposition of the Metropolis algorithm in a general public journal! The column actually originated from a recently published paper by Persi Diaconis, Gilles Lebeaux, and Laurent Michel,  Geometric analysis for the Metropolis algorithm on Lipschitz domain, in Inventiones Mathematicae [one of the top pure math journals]. The column in La Recherche described the Metropolis algorithm (labelled there a random walk on Markov chains!), alluded to the use of MCMC methods in statistics, told the genesis of the paper [namely the  long-term invitation of Persi Diaconis in Nice a few years ago] and briefly explained the convergence result, namely the convergence of the Metropolis algorithm to the stationary measure at a geometric rate, with an application to the non-overlapping balls problem.

If you take a look at the paper, you will see it is a beautiful piece of mathematics, establishing a spectral gap on the Markov operator associated with the Metropolis algorithm and deducing a uniformly geometric convergence [in total variation] for most regular-and-bounded-support distributions. A far from trivial and fairly general result. La Recherche however fails to mention the whole corpus of MCMC convergence results obtained in the 1990′s and 2000′s, by many authors, incl. Richard Tweedie, Gareth Roberts, Jeff Rosenthal, Eric Moulines, Gersende Fort, Randal Douc, Kerrie Mengersen, and others…

Decision systems and nonstochastic randomness

“Thus the informativity of stochastic experiment turned out to depend on the Bayesian system and to coincide to within the scale factor with the previous “value of information”.” V. Ivanenko, Decision systems and nonstochastic randomness, p.208

This book, Decision systems and nonstochastic randomness, written by the Ukrainian researcher Victor Ivanenko, is related to decision theory and information theory, albeit with a statistical component as well. It however works at a fairly formal level and the reading is certainly not light. The randomness it address is the type formalised by Andreï Kolmogorov (also covered in the book Randomness through Computation I [rather negatively] reviewed a few months ago, inducing angry comments and scathing criticisms in the process). The terminology is slightly different from the usual one, but the basics are those of decision theory as in De Groot (1970). However, the tone quickly gets much more mathematical and the book lost me early in Chapter 3 (Indifferent uncertainty) on a casual reading. The following chapter on non-stochastic randomness reminded me of von Mises for its use of infinite sequences, and of the above book for its purpose, but otherwise offered an uninterrupted array of definitions and theorems that sounded utterly remote from statistical problems. After failing to make sense of the chapter on the informativity of experiment in Bayesian decision problems, I simply gave up… I thus cannot judge from this cursory reading whether or not the book is “useful in describing real situations of decision-making” (p.208). It just sounds very remote from my centres of interest. (Anyone interested by writing a review?)

Randomness [French version]

As a (weak) coincidence (with my review of Randomness through Computation), the French Mathematical Society chose the theme of its yearly meeting (on June 17-18 at CIRM) as “Qu’est ce qu’un nombre au hasard ?” with talks by

• Laurent Bienvenu (LIAFA, Université Paris Diderot) : «Qu’est-ce qu’un nombre aléatoire ? Hasard et calculabilité»
• Benoît Rittaud (Laboratoire LAGA, Université Paris XIII) : «De la “Grande Année” aux suites de Kronecker»
• David Xiao (LIAFA, Université Paris Diderot) : «Le pseudo-aléa : objets et génération»

The talk by David Xiao is accompanied by a fairly interesting survey that goes much farther than what is found in Randomness through Computation. The same applies to the talk by Laurent Bienvenu, with a survey that is closer in spirit to the themes of Randomness through Computation (Kolmogorov and Chaitin complexities, Martin-Löf randomness).

Another (weak) coincidence is that I received yesterday in the mail Richard von Mises’ Probability, Statistics and Truth, which I hope to read carefully in the coming weeks, in connection with the above, but also Bayesian statistics (“a misundertsanding of one of the classical formulas of probability calculus”).