Coupling: Cutoffs, CFTP and Tameness

The principal theme underlying this work is that of coupling. Coupling is a general technique with applications in many areas of probability, as well as being an active area of research in its own right. In this thesis a number of problems involving coupling are investigated: some new results, as well as an indication of exciting possibilities for future research, are given in each case. Our journey into the world of coupling begins with the topic of the cutoff phenomenon for random walks on groups. Chapter 2 investigates the behaviour of a coupling for a general random walk on the hypercube, proving the existence under a simple condition of a new type of threshold behaviour called a coupling-cutoff. Chapter 3 is concerned with the theory of maximal couplings of Markov chains. This concept is generalised to maximal coalescent couplings, and an explicit description of an optimal co-adapted coupling for the symmetric random walk on Z~ is presented. The difference between optimal co-adapted and maximal couplings is also investigated for Brownian motion and the Ornstein-Uhlenbeck process. Coupling is at the heart of the simulation technique known as perfect simulation, and this subject forms the focus of the second half of the thesis. Some consideration is given to the efficiency of Coupling from the Past (CFTP) algorithms, but the principal novel contribution to this area is an investigation into the existence of a dominated CFTP algorithm for subgeometrically ergodic Markov chains. This question turns out to be significantly harder than that for geometrically ergodic chains: we introduce a class of positive recurrent chains, named tame chains, for which a perfect simulation algorithm is shown to exist.EThOS - Electronic Theses Online ServiceGBUnited Kingdo