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…

WSC 2[0]11

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

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.)

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

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?

On randomness

A while ago, I posted how strangely people seem to be attracted by re- and re-explaining Bayes’ theorem when I see it as a tautological consequence of the definition of conditional probability (and hence of limited interest per se, although with immense consequences for conducting inference). Through the “spam” book mentioned earlier this week, I noticed that the same (or even worse) fatal attraction holds for randomness! (Although I had already posted on the “truly random” generators…) Having access only to one chapter, I read with a sense of growing puzzlement through Tommaso Toffoli’s chapter and came with the following comments, which are nothing but a Saturday afternoon idle thoughts!

Measure theory, and much of the axiomatic apparatus that goes into what is often called the “foundations” of probability, is just about developing more refined accounting techniques for when the outcome space becomes so large (viz., uncountably infinite) that simple minded techniques lead to paradoxes: “If a line consists of points, and a point has no length, how come a line has length?”