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 and Oliver Matheau-Raven, I have recently proved the existence of a cutoff for a type of biased transposition shuffle. In this shuffle the Right hand chooses a card uniformly at random, and then the Left hand chooses a card at random below the card selected by the Right hand; the two chosen cards are then transposed. Our upper bound on the mixing time was obtained by spectral analysis, using lifting ideas to obtain an explicit formula for all the eigenvalues of the transition matrix.
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 a natural class of hypergraphs, 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".
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.
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.
More recently, in work with Roberta Merli I considered Brownian motion on the circumference of the unit circle, which jumps to the opposite point of the circumference at incident times of an independent Poisson process. We showed that optimality properties of two intuitive coupling strategies for this process depend in a non-trivial way upon the jump rate, using ideas from excursion theory and stochastic control.