Random Sampling via Geometric Coupling

Sam Greenberg (Dana Randall) - In the analysis of Markov chains, coupling is one of the most popular methods, both because of its elegance and its simplicity. The key is to define a valid coupling and then demonstrate that the coupling time TX0,Y0 is polynomial for all initial starting states X0 and Y0. The method that has been the most successful defines a distance function f on pairs of states, such that f takes integer values in the range [0, B], and f(X,Y) = 0 if and only if X = Y. Luby, Randall, and Sinclair [5] studied the stochastic process f(t) = f(Xt,Yt), and showed that if the expected change in distance Df(t) is always non-positive, then the coupling time is polynomial with respect B.

The difficulty with analyzing many coupled chains is that there exist worst-case pairs of configurations that are more likely to drift apart than come together. However, the naive definition of distance ignores the enormous flexibility we typically have in defining the metric; we may create a new distance function so as to assign the bad moves smaller weight than the good moves. We are particularly interested in a geometrically decreasing distance function, as this seems necessary for the applications detailed below. Here configurations differing by a single move are allowed to be exponentially far apart. With this metric, the state space is contracting under moves of the coupled chain.

Unfortunately, for traditional methods, it is important that B is bounded by a polynomial. However, we show the following theorem, which allows us to conclude that the chain will couple quickly in such circumstances, even with B exponential in n.