Disclaimer: This unpublished survey was written in 2000, and is being posted unedited in its original form, in response to requests for a permanent URL that can be cited. It is thus outdated and does not reflect the state of the art in 2016. Abstract For many fundamental sampling problems, the best, and often the only known, approach to solving them is to take a long enough random walk on a certain Markov chain and then return the current state of the chain. Techniques to prove how long "long enough" is, i.e., the number of steps in the chain one needs to take in order to be sufficiently close to the stationary distribution of the chain, are of great importance in obtaining estimates of running times of such sampling algorithms. In this report, we survey existing techniques to bound the mixing time of Markov chains. The mixing time of a Markov chain is exactly captured by the "spectral gap" of its underlying transition matrix. The spectral gap is closely related to a geometric parameter called "conductance" which is a measure of the "edge-expansion" of the Markov chain. Conductance also captures the mixing time up to square factors. Lower bounds on conductance, which give upper bounds on the mixing time, are typically obtained by a technique called "canonical paths" where the idea is to find a set of paths, one between every unequal source-destination pair, such that no edge is very heavily congested. Unlike conductance, the canonical paths approach cannot always show rapid mixing of a rapidly mixing chain. It is known that this "drawback" disappears if we allow the flow between a pair of states to be spread along multiple paths. We prove that for a large class of Markov chains, including all the ones that we use in the sampling applications we will be interested in, canonical paths does capture rapid mixing, i.e., we show that small mixing time implies the existence of some collection of paths with low edge congestion. Allowing multiple paths to route the flow still does help a great deal in the design of such flows, and this is best illustrated by a recent result of Morris and Sinclair [34] on the rapid mixing of a natural Markov chain for sampling 0-1 knapsack solutions; this result seems to rely critically on fractional flows. An entirely different approach to prove rapid mixing, which in fact historically preceded the conductance/canonical paths based approach, is "Coupling". Coupling is a very elegant technique and has been used to prove rapid mixing of several chains where designing good canonical paths seems to be a hideous task. "Path Coupling" is a related technique discovered by Bubley and Dyer [5] that often tremendously reduces the complexity of designing good Couplings. We present several applications of Path Coupling in proofs of rapid mixing, and these invariably lead to much better bounds on mixing time than known using conductance, and moreover Coupling based proofs usually turn out to be much simpler. These applications motivate the question of whether Coupling indeed can be made to work whenever the chain is rapidly mixing. This question was answered in the negative in very recent work by Kumar and Ramesh [27], who showed that no Coupling strategy can prove the rapid mixing of the famous Jerrum-Sinclair chain for sampling perfect and near-perfect matchings (the chain is known to be rapidly mixing via a canonical paths argument). * Computer Science Department, Carnegie Mellon University, Pittsburgh, PA. guruswami@cmu.edu. Survey written in 2000 when the author was a student at MIT. Suppose Ω is a large finite set of combinatorial structures (for example the set of feasible solutions to a combinatorial optimization problem), and let π be a probability distribution on Ω. The general "sampling" problem is then to pick an element of Ω at random according to the distribution π. The Markov chain Monte Carlo method, which is the subject of our study here, provides an elegant technique to efficiently solve this general computational task in a wide variety of contexts. Sampling problems are inherently interesting, and in addition turn out to have many computational applications, the most notable ones being: • Approximate counting: Here we want to estimate the size of Ω to a very good accuracy. It is well known [23] that, provided a certain technical condition known as self-reducibility is met, almost uniform sampling (that is sampling from a distribution that is statistically close to the uniform distribution) is possible in polynomial time if and only if approximate counting is. This has been one of the main motivations, at least from the computer science point of view, behind the rapid progress that has been made in this area. In particular, for a host of counting problems including several very hard #P-complete problems, the Markov chain Monte Carlo method is the only known approach to approximate the number of feasible solutions. • Statistical physics: Here the space Ω represents possible configurations of statistical mechanical system, and π is a "natural" probability distribution on Ω, in which the probability of a configuration is related to its energy. The task is to sample configurations according to π, in order to examine properties of a "typical" physical configuration. In this report, we focus only on the sampling problem and omit the connections to counting since these involve by now standard reductions. The Markov chain Monte Carlo method has been a great success story in solving sampling problems. It solves the sampling problem by the following approach. An underlying "Markov chain" M on the state space Ω is specified through a stochastic transition probability matrix of dimension |Ω| × |Ω| whose (x, y) th entry specifies the probability P(x, y) that the chain moves from state x to state y in a single step (we assume states of M are labeled by elements of Ω). Starting at any state x 0 , there is a natural random walk X 0 = x 0 , X 1 , X 2 , . . . defined on M such that Pr[X t+1 |X 0 , . . . , X t ] = Pr[X t+1 |X t ] where the latter conditional probability is specified by the matrix P, i.e., Pr[X t+1 = y|X t = x] = P(x, y). In other words we start at state X 0 and at each time step t, we make a move to a next state X t+1 by moving to a random state from the current state X t according to the transition probabilities of the chain. Note the crucial "forgetting property" of Markov chains: the state at time t + 1 depends probabilistically on the state at time t, but not on the state at any other time. To sample according to a distribution π, the Markov chain M is defined in such a way that it is ergodic, i.e., has a (unique) stationary distribution η on Ω such that Pr[X t = y|X 0 = x] → η(y) as t → ∞, for all pairs of states x, y ∈ Ω, and moreover the transition probabilities are set up so that η = π. Now we may sample from Ω according to π as follows: starting from an arbitrary state in Ω, take a random walk on the Markov chain (which we will loosely refer to as "simulating the Markov chain" in the sequel) for some number, T , of steps, and then output the final state. The ergodicity of M implies that, by taking T large enough, we can ensure that the output state is arbitrarily close to the desired distribution π. One of the most appealing things about this method is its simplicity -in fact in most applications it is not hard to construct a Markov chain having the above properties. The crux of the method, which is also its sticking point, is to obtain good upper bounds on the mixing time of the chain, i.e., the number of simulation steps T necessary before the Markov chain is close to its stationary distribution. This 2 is critical as this forms the crucial factor in the running time of any sampling algorithm that uses the chain. Since our aim is to sample from a set Ω which is very large, we would like T to be much smaller than the size of Ω, say at most a polynomial in the logarithm of |Ω|. We shall refer to such chains as rapidly mixing. Over the years several deep and novel analytic tools have been developed and refined to bound mixing times of Markov chains. It is the goal of this report to survey the known techniques for proving rapid mixing, to present representative examples of their use, and to compare and contrast their scope, their relative strengths and limitations, and their applicability to various contexts. Organization. We begin in the next section by reviewing the relevant definitions and properties of Markov chains, and by giving a precise characterization of when a Markov chain mixes rapidly in terms of its spectral properties. In Section 3 we discuss the notion of conductance and its relation to the spectral gap of the chain. Section 4 discusses the canonical paths approach and some of its generalizations that yield bounds on the conductance and the spectral gap, and also proves that for a large class of chains a small mixing time implies the existence of some collection of good canonical paths. We then present an illustrative application of this technique to the problem of sampling 0-1 knapsack solutions in Section 5. Section 6 discusses Coupling which is an entirely different approach to bounding the mixing time, gives an illustrative example of Coupling in action, and also discusses Path Coupling, which is a useful design tool in constructing Couplings. Several elegant applications of Path Coupling are presented in Section 7. In Section 8 we discuss the recent result of [27] which proves that Coupling is in fact weaker than conductance, in that there are chains with large conductance which cannot be shown to be rapidly mixing by any Coupling strategy. Finally, we conclude with a few remarks and open questions in Section 9. Acknowledgments. This survey was written as part of the author's Area Examination at MIT, the goal of which was to survey the papers by Bubley and Dyer [5] , Anil Kumar and Ramesh [27] , and Morris and Sinclair [34] . This survey (specifically Sections 5, 6.4, 7.1 and 8) uses liberal portions of the contents of these papers. This work was also influenced greatly by the reading of the survey by Jerrum [19] , and the paper by Sinclair [37] , among several other papers. I would like to thank Kumar and Ramesh for sending me a copy of the most recent version of their paper [27] . A Markov chain on state space Ω is completely specified by the transition matrix P whose entry P(x, y) represents the probability that the chain moves from state x to state y is a single transition; i.e., P(x, y) = Pr[X t+1 = y|X t = x] for all t ≥ 0. Thus in order to study and analyze the properties of the Markov chain, it suffices to investigate the properties of this matrix P. Starting from an initial distribution µ (0) , the distribution of the chain after t steps µ (t) is clearly given by µ (t) = µ (0) P n (here we view the distributions as row vectors in R Ω ). Thus, when using a Markov chain to randomly sample from its state space, we must study the evolution of µ (t) as t increases, and we would like µ (t) to (quickly) approach a limiting stationary distribution, say π; it is not surprising that π must be fixed under steps of the chain. Definition 2.1 A row vector π ∈ R Ω is a stationary distribution for a Markov chain M with transition matrix P if (a) π(x) ≥ 0 for all x ∈ Ω, (b) ∑ x∈Ω π(x) = 1, and (c) π = πP.
A comprehensive survey on techniques to bound the mixing time of a Markov Chain is REF .
Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey)
ArXiv
ArXiv
Mathematics Computer Science