Markov Chain Monte Carlo:
The technique of Markov chain Monte Carlo (MCMC) first arose in statistical physics, marked by the celebrated 1953 paper of Metropolis, Rosenbluth, Rosenbluth, Teller and Teller. The underlying principle is simple: if one wishes to sample randomly from a specific probability distribution then design a Markov chain whose long-time equilibrium is that distribution, write a computer program to simulate the Markov chain, run it for a time long enough to be confident that approximate equilibrium has been attained, then record the state of the Markov chain as an approximate draw from equilibrium. The Metropolis et al paper used a symmetric Markov chain; later developments included an adaptation to the case of non-symmetric Markov chains described by Hastings in 1970.
The technique has developed strongly in the statistical physics community but also in separate ways and with rather different emphases in the computer science community concerned with the study of random algorithms (where the emphasis is on whether the resulting algorithm scales well with increasing size of the problem), in the spatial statistics community (where one is interested in understanding what kinds of patterns arise from complex stochastic models), and also in the applied statistics community (where it is applied largely in Bayesian contexts, enabling researchers to formulate statistical models which would otherwise be resistant to effective statistical analyses). Within the statistics community, landmark papers include the famous Geman-Geman 1984 paper on image restoration, work by Gelfand and Smith in 1990 showing that MCMC can be applied effectively to Bayesian problems, and Green's (1995) work on dimension-varying problems.
The simplicity of the underlying principle of MCMC is a major reason for its success. However a substantial complication arises as the underlying target problem becomes more complex; namely, how long should one run the Markov chain so as to ensure that it is close to equilibrium? This has stimulated much research, into mathematical upper bounds on rates of convergence, into varieties of different Markov chains for which convergence may be hoped to be rapid or susceptible to analysis, into diagnostics for convergence, and even into modifications of the basic algorithm which replace approximate by exact draws from the equilibrium distribution for (essentially rather finite) Markov chains on ordered state-spaces (the so-called perfect simulation idea). This last rather startling development was given practical effect in two different ways in the seminal papers of Propp and Wilson (1996) and of Fill (1998). As often is the case in mathematical science, a simple idea has led to much interesting mathematics; other more recent developments include the use of weighted MCMC (in some cases substantially though not entirely avoiding simulation, as in the case of the Binary Tree Summation Algorithm) and innovations and applications in statistics, physics, and bioinformatics.of modifications based on genetic algorithms. Subsequent work has filled out the mathematical picture by clarifying how recent developments relate to previous work (both the Propp-Wilson and the Fill algorithms relate in interesting ways to each other and to prior theoretical concepts, while adding their own attractively empirical flavour). Ongoing work is developing and extending these ideas; for example we now know how to generalize Propp-Wilson algorithms to deal with Markov chains whose state-spaces are not essentially finite, and which permit some deviation from order. Finally there have been significant applications of some of these algorithmic developments back to mathematical theory; in particular the Propp-Wilson idea has been significant in suggesting further developments in the combinatorial theory of random forests, and has also motivated new work on the Markov chain phenomenon of small sets.
The development of the theoretical work also benefits the development of statistical applications. The MCMC/perfect simulation techniques have been applied to develop practical statistical inferences for almost all problems in (bio)statistics, for example, the problems in longitudinal data analysis, image analysis, genetics, contagious disease epidemics, random spatial pattern, and financial statistical models such as GARCH and stochastic volatility. The techniques also constitute a major part of today's bioinformatics toolbox.
Another line of development for the past 10 years in the statistical physics community is that of extended ensemble methods, beginning with Berg's work in multicanonical method, followed by simulated tempering, parallel tempering, broad histogram Monte Carlo, transition matrix Monte Carlo, etc. These methods substantially extend the ability to simulate complicated systems that are very difficult to sample, such as spin-glasses, or protein models.
The purpose of this programme is to bring together people who work on innovative developments and applications in statistics, physics, and bioinformatics. Our intention is first to encourage cross-fertilization between workers in rather different developments, second to challenge the theoretical capacity of these methods by exposing them to statistical and bioinformatical applications.
There will be a tutorial on background material and a workshop at research level, in addition to seminars and informal discussions.
Contributed poster presentations and limited number of short contributed talks in week 4 are welcome. Please submit your title/name/affiliation/abstract to us latest by 1 Mar 2004.
IMS membership is not required for participation in workshops or tutorials. For attendance at these activities, please complete the registration form (MSWord|PDF|PS) and fax it to us at (65) 6873 8292 or email it to us at email@example.com.
If you are an IMS member or are applying for IMS membership, you do not need to register for these activities.
The Institute for Mathematical Sciences invites applications for membership for participation in the above program. Limited funds to cover travel and living expenses are available to young scientists. Applications should be received at least six (6) months before the commencement of membership. Application form is available in MSWord | PDF | PS format for download.