Probabilistic coupling: mixing times and optimality

The main focus of this thesis is probabilistic coupling. This technique and its connection with the total variation distance will be a common thread through the exploration of the random processes investigated in this thesis. In Chapter 2, we generalise a recent result on the mixing time of the random walk on Z_2^n that at each step flips k randomly chosen coordinates. In our work, we let the number of coordinates flipped at each step be a random variable K, and, using a path coupling argument, we establish bounds for the mixing time of this random walk. Furthermore, we show that, under some stricter assumptions on the distribution of K, the random walk has a pre-cutoff. In Chapter 3, we focus on properties of particular couplings, such as co-adaptedness, maximality, and other types of optimality. We consider the Brownian motion on the circumference of the unit circle that, at times of an independent Poisson process of rate λ, jumps to the opposite point on the circle. We construct a co-adapted coupling for this process and, using excursion theory and Bellman's principle of optimality, we prove that it is mean-optimal in the class of co-adapted couplings, i.e. it minimises the expected coupling time. We describe how this coupling depends upon λ, and show that it is maximal only when λ = 0. We also give an explicit construction of a maximal coupling for this "jumpy Brownian motion" (for any value of λ) in the case where the two copies of the process begin at opposite sides of the circle.