Efficient Markovian couplings: Examples and counterexamples

In this paper we study the notion of an efficient coupling of Markov proces ses. Informally, an efficient coupling is one which couples at the maximum possible exponential rate, as given by the spectral gap. This notion is of interest not only for its own sake, but also of growing importance arising from the recent advent of methods of "perfect simulation": it helps to esta blish the "price of perfection" for such methods. In general, one can alway s achieve efficient coupling if the coupling is allowed to "cheat" (if each component's behavior is affected by the future behavior of the other compo nent), but the situation is more interesting if the coupling is required to be co-adapted. We present an informal heuristic for the existence of an ef ficient coupling, and justify the heuristic by proving rigorous results and examples in the contexts of finite reversible Markov chains and of reflect ing Brownian motion in planar domains.