Probabilistic coupling: co-adaptedness, maximality and efficiency

My proposed research programme concerns the idea of coupling of Markov chains. Markov chains are random processes which satisfy the appealing quality that predictions about the future behaviour of the chain only depend upon its present state - knowing extra information about where the chain has been in the past does not help us to better predict the future. Markov chains have been intensely studied during the past hundred years, and are now used in a multitude of applications including weather forecasting, the analysis of card-shuffling techniques, and the PageRank method used by Google.

This investigation concerns the problem of constructing two copies of the same chain, started from different locations, so that once the two processes meet one another they stay together from that time onwards: this is known as a 'coupling' of the two chains. There is a range of possible coupling constructions available to us, and so a natural question to ask is how quickly it is possible to make the two chains meet. As well as being an interesting mathematical question, answers to this problem have significant implications for problems in theoretical computer science and statistical physics. The fastest couplings are known as 'maximal' couplings: we know that these couplings exist for a wide range of processes, but they are almost always difficult (if not impossible) to compute explicitly. This problem usually arises because the maximal coupling is often not co-adapted - loosely speaking, one chain has to use information about the future behaviour of the other in order to determine the next step of its trajectory. This makes co-adapted couplings (ones where no such 'cheating by looking into the future' is allowed) much more widely used in applications, but little is known about how good such couplings can be.

My proposed plan of research will investigate this problem, looking first of all at a particular class of Markov chains called random walks on groups. These random walks have a lot of nice structure, which can often be exploited to enable explicit computations to be performed. I will look at how good co-adapted couplings can be for these types of Markov chain, and how this is related to the underlying structure of the state-space. Another major objective of the project to is to look at maximal couplings in a more general setting, and try to understand when such couplings can be constructed in a co-adapted manner. The final aim of the proposal is to investigate the implications of the above results for 'perfect simulation' algorithms, many of which make use of co-adapted couplings to produce random samples from the exact stationary distribution of a Markov chain.

The research to be undertaken in this project will be innovative and timely, and will benefit other mathematicians and the wider scientific community; there is also a high probability that some of the results will be of interest to the general public.

The proposed research deals with a theoretical area of probability, and so the people who will benefit the most from this work are fellow mathematicians, especially those working in the fields of coupling theory, Markov processes and perfect simulation algorithms. However, I also anticipate a great deal of interest in the work from scientists in other related fields.

Objective 1 of the proposal deals with the problem of constructing optimal co-adapted couplings for random walks on groups, and how the existence of such couplings is related to the structure of the underlying state space. There are already a lot of deep results concerning random walks on groups, which provide interesting links between probability, algebra and analysis: accordingly, it is to be expected that there will be a large audience for my work from pure mathematicians as well as fellow probabilists. In addition, Goal 1.1 of the proposal focuses on random walks on the symmetric group; these walks can be thought of as methods for shuffling a pack of playing cards, and results in this area are hence likely to be of interest to the general public.

Objectives 2 and 3 concern an investigation into the relationships between optimal co-adapted, efficient and maximal couplings. Co-adapted couplings are often used by those working in probability and theoretical computer science to establish convergence rates of Markov processes; for example, the concept of path-coupling has played an important role in analysing algorithms for approximating #P-hard problems such as counting graph colourings. A better understanding of how fast co-adapted couplings can be for any given process will thus be of great benefit to researchers tackling such problems.

Finally, Objective 4 seeks to understand the implications of the results from the first three objectives for perfect simulation algorithms. These algorithms are similar to the much-used method of Markov chain Monte Carlo (MCMC), in that they return a sample from the stationary distribution of an ergodic Markov chain. Unlike with MCMC however, the output from a perfect simulation algorithm is from the exact stationary distribution (rather than an approximation, hence the name), at the cost of a random run-time. These algorithms have been successfully used in a wide number of applications by probabilists, applied statisticians, computer scientists and statistical physicists during the past 15 years. It is therefore to be anticipated that any new results concerning the speed of such algorithms will be of benefit to a wide variety of scientists.