An excursion into the mythical forest of random bits.
It was a special opportunity to host a visit of Prof. Werner Krauth from the Ecole Normale Supérieure (ENS), one of the world’s leading experts in Monte-Carlo techniques, to discuss opportunities for collaboration and learn about new strategies for improving the Monte-Carlo techniques that we develop in my group. Having been inspired by Werner’s course when I was a student at ENS a good while back, it was a particular pleasure that Werner offered to give a few lectures during his visit and bring that experience to our own graduate students here at the University of Kent. We also heard a research seminar about his latest results on the hard sphere problem.
Werner’s lectures took us well beyond the basics of Monte-Carlo sampling into the more novel topic of irreversible Markov chains, which Werner has pioneered in recent years, leading to a spectacular speed-up compared to the conventional approach. It turns out that when one gives up the requirement of detailed balance (i.e. matching the flows between each pair of Monte-Carlo configurations), it is still possible to satisfy global balance conditions. This is achieved by considering a lifted Markov chain, which remembers not only a microscopic state of the physical/statistical system being considered, but also to remember the previous move of the random walk. It is then possible to force a walk to be only in the forwards direction, which ends up being radically faster, but still gives the right distribution.
Sounds like magic – well, it does indeed, but there’s still time to convince yourself of the science behind the miracle if you head over to the course page and check out Werner’s resources and the recordings.
Not to forget, this is quite an amusing activity thanks to Werner’s excellent sense of humour. Check out the figure above on convergence of a Markov Chain for the hard-sphere problem, above, as an example!