Perfect simulation algorithms can be used to return a sample from the exact stationary distribution of a Markov chain, at the expense of a random run time. With Wilfrid Kendall I showed how to produce perfect simulation algorithms, based on the idea of Dominated Coupling from the Past, for M/G/c queues (Markovian arrivals, general service durations, and c servers). More recently I have demonstrated how it is possible to use these algorithms to perform omnithermal perfect simulation; this allows for simultaneous sampling from the equilibrium distribution of the workload vector for varying numbers of servers.
In general it is not clear whether a perfect simulation algorithm exists for any given Markov chain. Also in work with Kendall, I introduced a new class of chains (named tame chains) for which perfect simulation is theoretically possible. The rate at which a chain converges to equilibrium is extremely important to our results, which are proved using stochastic stability arguments.
In addition to providing insight into possibilities for perfect simulation, some of the ideas developed during my research into tame chains turned out to have important consequences for the more general theory of stochastic stability of Markov chains; with Gersende Fort I investigated the interplay between Foster-Lyapunov drift conditions and adaptive subsampling schemes.
Mixing time and the cutoff phenomenon
The mixing time of an ergodic Markov chain is a measure of the "time taken for it to approach equilibrium". Obtaining good bounds on this time is a topic of great interest in a variety of fields. For some natural sequences of random walks, especially random walks on groups, the cutoff phenomenon is a frequently observed occurrence. Loosely speaking, this phenomenon occurs when the distance of the random walk from equilibrium stays close to its maximum for a time, before dropping rapidly towards zero. Showing the existence of a cutoff is often a complicated affair.
With Michael Bate I have given bounds on the mixing time of a random walk on the ring of integers mod n. At each time point this chain either makes an additive "step" or else a multiplicative "jump"; when the probability of making a jump decreases as a suitable function of n we show that the sequence exhibits a so-called "pre-cutoff". Along with our PhD student, Oliver Matheau-Raven, we have recently proved the existence of a cutoff for a type of biased transposition shuffle.
It is of interest to be able to bound the mixing time of multi-particle systems in terms of how long it takes for only one or two particles to approach equlibrium. In work with Richard Pymar I have shown how to bound the mixing time of the exclusion process on hypergraphs belonging to a natural class, in terms of the mixing time of just two particles. The proofs rely on careful coupling arguments and a generalisation of something called the "chameleon process".
Optimal co-adapted coupling
Coupling can be used to bound the distance between the distributions of two copies of a Markov chain, via the coupling inequality. It is known that, for any given Markov chain, there exists a coupling that attains equality in this inequality. Such a coupling is known as a maximal coupling. However, maximal couplings are in general not co-adapted (the evolution of one chain is allowed to depend on the future behaviour of the other), and are therefore often hard to describe. Since co-adapted couplings are easier to work with, it is of interest to study the best possible such coupling for a given Markov chain.
With Saul Jacka I used arguments from the theory of stochastic control to prove stochastic minimality of a certain co-adapted coupling for a simple random walk on the hypercube. This result was subsequently generalised to produce an optimal co-adapted coupling for a random walk on a hyper-complete graph.