PATH COUPLING AND AGGREGATE PATH COUPLING YEVGENIY KOVCHEGOV AND PETER T. OTTO 5 Abstract. Inthissurveypaper,wedescribeandcharacterizeanextensiontotheclassicalpath 1 coupling method applied statistical mechanical models, referred to as aggregate path coupling. 0 In conjunction with large deviations estimates, we use this aggregate path coupling method 2 to prove rapid mixing of Glauber dynamics for a large class of statistical mechanical models, n including models that exhibit discontinuous phase transitions which have traditionally been a more difficult to analyze rigorously. The parameter region for rapid mixing for the generalized J Curie-Weiss-Pottsmodelisderivedasanewapplicationoftheaggregatepathcouplingmethod. 3 1 ] R Contents P . h 1. Introduction 2 t a 2. Mixing Times and Path Coupling 2 m 2.1. Coupling Method 3 [ 2.2. Path Coupling 4 2.3. Random-to-Random Shuffling 6 1 v 3. Gibbs Ensembles and Glauber Dynamics 9 7 4. Large Deviations and Equilibrium Macrostate Phase Transitions 10 0 5. Mean-field Blume-Capel model 12 1 3 5.1. Equilibrium Phase Structure 12 0 5.2. Glauber Dynamics 16 . 1 5.3. Path Coupling 17 0 5.4. Standard Path Coupling in the Continuous Phase Transition Region 21 5 5.5. Aggregate Path Coupling in the Discontinuous Phase Transition Region 22 1 5.6. Slow Mixing 24 : v 6. Aggregate Path Coupling for General Class of Gibbs Ensembles 25 i X 6.1. Class of Gibbs Ensembles 26 r 6.2. Large Deviations 27 a 6.3. Glauber Dynamics 29 6.4. Coupling of Glauber Dynamics 31 6.5. Mean Coupling Distance 32 6.6. Aggregate Path Coupling 33 6.7. Main Result 36 7. Aggregate Path Coupling applied to the Generalized Potts Model 40 References 47 Date: January 14, 2015. 2000 Mathematics Subject Classification. Primary 60J10; Secondary 60K35. ThisworkwaspartiallysupportedbyagrantfromtheSimonsFoundation(#284262toYevgeniyKovchegov). 1 2 YEVGENIYKOVCHEGOVANDPETERT.OTTO 1. Introduction Thetheoryofmixingtimesaddressesafundamentalquestionthatliesattheheartofstatistical mechanics. Howquicklydoesaphysicalsystemrelaxtoequilibrium? Arelatedproblemarisesin computationalstatisticalphysicsconcerningtheaccuracyofcomputersimulationsofequilibrium data. One typically carries out such simulations by running Glauber dynamics or the closely related Metropolis algorithm, in which case the theory of mixing times allows one to quantify the running time required by the simulation. An important question driving the work in the field is the relationship between the mixing times of the dynamics and the equilibrium phase transition structure of the corresponding sta- tistical mechanical models. Many results for models that exhibit a continuous phase transition wereobtainedbyadirectapplicationofthestandardpathcouplingmethod. Standardpathcou- pling [5] is a powerful tool in the theory of mixing times of Markov chains in which rapid mixing can be proved by showing that the mean coupling distance contracts between all neighboring configurations of a minimal path connecting two arbitrary configurations. For models that exhibit a discontinuous phase transition, the standard path coupling method fails. In this survey paper, we show how to combine aggregate path coupling and large deviation theory to determine the mixing times of a large class of statistical mechanical models, including thosethatexhibitadiscontinuousphasetransition. Theaggregatepathcouplingmethodextends theuseofthepathcouplingtechniqueintheabsenceofcontractionofthemeancouplingdistance between all neighboring configurations of a statistical mechanical model. The primary objective of this survey is to characterize the assumptions required to apply this new method of aggregate path coupling. The manuscript is organized as follows: in Section 2, we give a brief overview of mixing times, coupling and path coupling methods, illustrated with a new example of path coupling. Then, beginning in Section 3, we introduce the class of statistical mechanical models considered in the survey. In Sections 5 and 6, we develop and characterize the theory of aggregate path coupling and apply it in Section 7, where we derive the parameter region for rapid mixing for the generalized Curie-Weiss-Potts model that was introduced recently in [25]. 2. Mixing Times and Path Coupling The mixing time is a measure of the convergence rate of a Markov chain to its stationary distribution and is defined in terms of the total variation distance between two distributions µ and ν defined by 1 (cid:88) (cid:107)µ−ν(cid:107) = sup |µ(A)−ν(A)| = |µ(x)−ν(x)| TV 2 A⊂Ω x∈Ω Given the convergence of the Markov chain, we define the maximal distance to stationary to be d(t) = max(cid:107)Pt(x,·)−π(cid:107) TV x∈Ω where Pt(x,·) is the transition probability of the Markov chain starting in configuration x and π is its stationary distribution. Rather than obtaining bounds on d(t), it is sometimes easier to PATH COUPLING AND AGGREGATE PATH COUPLING 3 bound the standardized maximal distance defined by (1) d¯(t) := max (cid:107)Pt(x,·)−Pt(y,·)(cid:107) TV x,y∈Ω which satisfies the following result. Lemma 2.1. ([29] Lemma 4.11) With d(t) and d¯(t) defined above, we have d(t) ≤ d¯(t) ≤ 2d(t). Given ε > 0, the mixing time of the Markov chain is defined by t (ε) = min{t : d(t) ≤ ε} mix In the modern theory of Markov chains, the interest is in the mixing time as a function of the (n) system size n and thus, for emphasis, we will often use the notation t (ε). With only a handful mix of general techniques, rigorous analysis of mixing times is difficult and the proof of exact mixing time asymptotics (with respect to n) of even some basic chains remain elusive. See [29] for a survey on the theory of mixing times. Rates of mixing times are generally categorized into two groups: rapid mixing which implies thatthemixingtimeexhibitspolynomialgrowthwithrespecttothesystemsize,andslowmixing whichimpliesthatthemixingtimegrowsexponentiallywiththesystemsize. Determiningwhere amodelundergoesrapidmixingisofmajorimportance,asitisinthisregionthattheapplication of the dynamics is physically feasible. 2.1. Coupling Method. The application of coupling (and path coupling) to mixing times of Markov chains begins with the following lemma: Lemma 2.2. Let µ and ν be two probability distributions on Ω. Then (cid:107)µ−ν(cid:107) = inf{P{X (cid:54)= Y} : (X,Y) is a coupling of µ and ν} TV Thislemmaimpliesthatthetotalvariationdistancetostationarity, andthusthemixingtime, of a Markov chain can be bounded above by the probability P(X (cid:54)= Y ) for a coupling of the t t Markov chain (X ,Y ) starting in different configurations; i.e. (X ,Y ) = (σ,τ), or if one of the t t 0 0 coupled chains is distributed by the stationary distribution π for all t. We run the coupling of the Markov chain, not necessarily independently, until they meet at time τ . This is called the coupling time. After τ , we run the chains together. We see that X c c t must have the stationary distribution for t ≥ τ , since X = Y after coupling. c t t Theorem 2.3 (The Coupling Inequality). Let (X ,Y ) be a coupling of a Markov chain where t t Y is distributed by the stationary distribution π. The coupling time of the Markov chain is t defined by τ := min{t : X = Y }. c t t Then, for all initial states x, (cid:107)Pt(x,·)−π(cid:107) ≤ P(X (cid:54)= Y ) = P [τ > t] TV t t c and thus τ (ε) ≤ E[τ /ε]. mix c 4 YEVGENIYKOVCHEGOVANDPETERT.OTTO From the Coupling Inequality, it is clear that in order to use the coupling method to bound the mixing time of a Markov chain, one needs to bound the coupling time for a coupling of the Markov chain starting in all pairs of initial states. The advantage of the path coupling method described in the next section is that it only requires a bound on couplings starting in certain pairs of initial states. 2.2. Path Coupling. The idea of the path coupling method is to view a coupling that starts in configurations σ and τ as a sequence of couplings that start in neighboring configurations (x ,x ) such that (σ = x ,x ,x ,...,x = τ). Then the contraction of the original coupling i i+1 0 1 2 r distance can be obtained by proving contraction between neighboring configurations which is often easier to show. Let Ω be a finite sample space, and suppose (X ,Y ) is a coupling of a Markov chain on Ω. t t SupposealsothereisaneighborhoodstructureonΩ, andsupposeitistransitiveinthefollowing sense: for any x and y, there is a neighbor-to-neighbor path x ∼ x ∼ x ∼ ... ∼ x ∼ y, 1 2 r−1 where u ∼ v denotes that sites u and v are neighbors. Let d(x,y) be a metric over Ω such that d(x,y) ≥ 1 for any x (cid:54)= y, and r (cid:88) d(x,y) = min d(x ,x ), i−1 i ρ:x→y i=1 where the minimum is taken over all neighbor-to-neighbor paths ρ : x = x ∼ x ∼ x ∼ ... ∼ x ∼ x = y 0 1 2 r−1 r of any number of steps r. Such metric is called path metric. Next, we define the diameter of the sample space: diam(Ω) = max d(x,y). x,y∈Ω Finally, the coupling construction allows us to define the transportation metric of Kantorovich (1942) as follows: d (x,y) := E[d(X ,Y ) |X = x,Y = y]. K t+1 t+1 t t One can check d (x,y) is a metric over Ω. K Path coupling, invented by Bubley and Dyer in 1997, is a method that employs an existing couplingconstructioninordertoboundthemixingtimefromabove. Thismethodinitsstandard form usually requires certain metric contraction between neighbor sites. Specifically, we require that for any x ∼ y, (cid:0) (cid:1) (2) d (x,y) = E[d(X ,Y ) |X = x,Y = y] ≤ 1−δ(Ω) d(x,y), K t+1 t+1 t t where 0 < δ(Ω) < 1 does not depend on x and y. The above contraction inequality (2) has the following implication. PATH COUPLING AND AGGREGATE PATH COUPLING 5 Proposition 2.4. Suppose inequality (2) is satisfied. Then (cid:24) (cid:25) logdiam(Ω)−log(cid:15) t ((cid:15)) ≤ . mix δ(Ω) Proof. For any x and y in Ω, consider the path metric minimizing path ρ : x = x ∼ x ∼ x ∼ ... ∼ x ∼ x = y 0 1 2 r−1 r such that r (cid:88) d(x,y) = d(x ,x ). i−1 i i=1 Then E[d(X ,Y ) |X = x,Y = y] = d (x,y) t+1 t+1 t t K r (cid:88) ≤ d (x ,x ) K i−1 i i=1 r (cid:1)(cid:88) ≤ (1−δ(Ω) d(x ,x ) i−1 i i=1 (cid:1) = (1−δ(Ω) d(x,y). Hence, after t iterations, (cid:1)t (cid:0) (cid:1)t E[d(X ,Y )] ≤ (1−δ(Ω) d(X ,Y ) ≤ 1−δ(Ω) diam(Ω) t t 0 0 for any initial (X ,Y ), and 0 0 (cid:0) (cid:1) (cid:0) (cid:1)t P(X (cid:54)= Y ) = P d(X ,Y ) ≥ 1 ≤ E[d(X ,Y )] ≤ 1−δ(Ω) diam(Ω) ≤ (cid:15) t t t t t t whenever logdiam(Ω)−log(cid:15) t ≥ . (cid:0) (cid:1) −log 1−δ(Ω) Thus, by the Coupling Inequality, (cid:38) (cid:39) (cid:24) (cid:25) logdiam(Ω)−log(cid:15) logdiam(Ω)−log(cid:15) t ((cid:15)) ≤ ≤ . mix −log(cid:0)1−δ(Ω)(cid:1) δ(Ω) (cid:3) Example. ConsidertheIsingmodeloverad-dimensionaltorusZd/nZd. ThereΩ = {−1,+1}nd isthespaceofallspinconfigurations,andforanypairofconfigurationsσ,τ ∈ Ω,thepathmetric d(σ,τ) is the number of discrepancies between them (cid:88) d(σ,τ) = 1{σ (cid:54)= τ }. x x x∈Zd/nZd The diameter diam(Ω) = nd. It can be checked that if the inverse temperature parameter β satisfies tanh(β) < 1 , the contraction inequality (2) is satisfied with 2d 1−2dtanh(β) δ(n) = . n 6 YEVGENIYKOVCHEGOVANDPETERT.OTTO Hence (cid:24) (cid:25) (cid:24) (cid:25) logdiam(Ω)−log(cid:15) dlogn−log(cid:15) (cid:16) (cid:17) t ((cid:15)) ≤ = n = O Cnlogn , mix δ(Ω) 1−2dtanh(β) where C = d . 1−2dtanh(β) The emergence of the path coupling technique [5] has allowed for a greater simplification in the use of the coupling argument, as rigorous analysis of coupling can be significantly easier when one considers only neighboring configurations. However, the simplification of the path coupling technique comes at the cost of the strong assumption that the coupling distance for all pairs of neighboring configurations must be contracting. Observe that although the contraction between all neighbors is a sufficient condition for the above mixing time bound, it is far from being a necessary condition. In fact, this condition is an artifact of the method. There had been some successful generalizations of the path coupling method. Specifically in [15], [24] and [4]. In [15], the path coupling method is generalized to account for contraction after a specific number of time-steps, defined as a random variable. In [24] a multi-step non- Markovian coupling construction is considered that evolves via partial couplings of variable lengths determined by stopping times. In order to bound the coupling time, the authors of [24] introduce a technique they call variable length path coupling that further generalizes the approach in [15]. 2.3. Random-to-Random Shuffling. An example illustrating the idea of path coupling can be found in the REU project [32] of Jennifer Thompson that was supervised by Yevgeniy Kovchegov in the summer of 2010 at Oregon State University. There, we consider the shuf- fling algorithm whereby on each iteration we select a card uniformly from the deck, remove it from the deck, and place it in one of the n positions in the deck, selected uniformly and independently. Each iteration being done independently of the others. This is referred to as the random-to-random card shuffling algorithm. We need to shuffle the deck so that when we are done with shuffling the deck each of n! possible permutations is obtained with probability close to 1. Its mixing time can be easily shown to be of order O(nlogn) using the notion of n! strong stationary time. For this one would consider the time it takes for each card in the deck to be selected at least once. Then use the coupon collector problem to prove the O(nlogn) upper bound on the mixing time. The same coupon collector problem is applied to show that we need at least O(nlogn) iterations of the shuffling algorithm to mix the deck. The goal of the REU project in [32] was to arrive with the O(nlogn) upper bound using the coupling method. 2.3.1. The Coupling. Take two decks of n cards, A and B. • Randomly choose i ∈ [1,n]. • Remove card with label i from each deck. • Randomly reinsert card i in deck A. • (1) If the new location of i in A is the top of A, then insert i on the top of B. (2) If the new location of i in A is below card j, insert i below j in B. Let A ∈ S and B ∈ S denote the card orderings (permutations) in decks A and B after t t n t n iterations. PATH COUPLING AND AGGREGATE PATH COUPLING 7 A B 2 4 4 3 1 1 3 2 Figure 1. One configuration of matchings between two decks of n = 4 cards. 2.3.2. Computing the coupling time with a laces approach. We introduce the following path metric d(·,·) : S ×S → Z by letting d(σ,σ(cid:48)) be the minimal number of nearest neighbour n n + transpositions to traverse between the two permutations, σ and σ(cid:48). For example, for the two decks A and B in Figure 1, a distance minimizing path connecting the two permutations is given in Figure 2. A B 2 4 4 4 4 4 2 2 3 3 1 1 3 2 1 3 3 1 1 2 Figure 2. Minimal number of crossings between the two permutations is four. Note that d(σ,σ(cid:48)) ≤ (cid:0)n(cid:1). We consider the quantity d = d(A ,B ), the distance between our two 2 t t t decks at time t. We want to find the relationship between E[d ] and E[d ]. t+1 t We consider a d(·,·)-metric minimizing path. We call the path taken by a card label a lace. Thus each lace representing a card label is involved in a certain number of crossings. Let r be t the number crossings per lace, averaged over all n card labels. Then we have d = nrt. t 2 The evolution of the path connecting A to B can be described as following. At each timestep t t we pick a lace (corresponding to a card label, say i) at random and remove it. For example, take a minimal path connecting decks A and B in Figure 2, and remove a lace corresponding to label 3, obtaining Figure 3. Then we reinsert the removed lace back. There will be two cases: (1) Withprobability 1 we placethe lacecorrespondingto cardlabelitothe topof thedeck. n See Figure 4. Then there will be no new crossings. 8 YEVGENIYKOVCHEGOVANDPETERT.OTTO 2 4 4 4 2 1 1 1 2 Figure 3. Removing lace 3 decreases the number of crossings to two. 3 3 3 2 4 4 4 2 1 1 1 2 Figure 4. Placing lace 3 on top does not add new crossings. (2) We choose a lace j randomly and uniformly chosen among the remaining n−1 laces, and place lace i directly below lace j. This has probability n−1. Then the number of n additional new crossings is the same as the number of crossings of lace j, as in Figure 5. Here (cid:16)nr (cid:17) 1 E[new crossings] = E[average number of crossings for the remaining laces] = t −r . t 2 n−1 2 2 4 4 4 2 4 4 3 3 4 2 2 1 4 2 1 = 3 4 3 3 1 2 1 1 2 3 1 1 1 3 3 Figure5. Insertinglace3directlybelowlace2addsthesamenumberofcrossing as there were of lace 2. Then (cid:18) (cid:19) (cid:18) (cid:19) nr n−1 (cid:16)nr (cid:17) 1 1 2 E[d |A ,B ] = t −r + t −r = 1− − d . t+1 t t 2 t n 2 t n−1 n n2 t Hence (cid:18) (cid:19) 1 2 E[d ] = 1− − E[d ], t+1 n n2 t PATH COUPLING AND AGGREGATE PATH COUPLING 9 and therefore (cid:18) 1 2 (cid:19)t (cid:18) 1 2 (cid:19)t(cid:18)n(cid:19) P(A (cid:54)= B ) = P(d ≥ 1) ≤ E[d ] = 1− − E[d ] ≤ 1− − ≤ (cid:15) t t t t n n2 0 n n2 2 whenever −2logn+log2+log(cid:15) t ≥ = 2nlogn+O(n). log(cid:0)1− 1 − 2 (cid:1) n n2 Thus providing an upper bound on mixing time. 3. Gibbs Ensembles and Glauber Dynamics In recent years, mixing times of dynamics of statistical mechanical models have been the focus of much probability research, drawing interest from researchers in mathematics, physics and computer science. The topic is both physically relevant and mathematically rich. But up to now, most of the attention has focused on particular models including rigorous results for several mean-field models. A few examples are (a) the Curie-Weiss (mean-field Ising) model [13,14,20,28], (b)themean-fieldBlume-Capelmodel[19,26], (c)theCurie-Weiss-Potts(mean- field Potts) model [1, 11]. A good survey of the topic of mixing times of statistical mechanical models can be found in the recent paper by Cuff et. al. [11]. The aggregate path coupling method was developed in [26] and [27] to obtain rapid mixing results for statistical mechanical models, in particular, those models that undergo a first-order, discontinuous phase transition. For this class of models, the standard path coupling method fails to be applicable. The remainder of this survey is devoted to the exposition of the aggregate path coupling method applied to statistical mechanical models. As stated in [17], “In statistical mechanics, one derives macroscopic properties of a substance from a probability distribution that describes the complicated interactions among the individual constituent particles.” The distribution referred to in this quote is called the Gibbs ensemble or Gibbs measure which are defined next. A configuration of the model has the form ω = (ω ,ω ,...,ω ) ∈ Λn, where Λ is some finite, 1 2 n discrete set. We will consider a configuration on a graph with n vertices and let X (ω) = ω i i denote the spin at vertex i. The random variables X ’s for i = 1,2,...,n are independent and i identicallydistributedwithcommondistributionρ. Theinteractionsamongthespinsaredefined throughtheHamiltonianfunctionH andwedenotebyM (ω)therelevantmacroscopicquantity n n correspondingtotheconfigurationω. Theliftfromthemicroscopicleveloftheconfigurationsto the macroscopic level of M is through the interaction representation function H that satisfies n (3) H (ω) = nH(M (ω)). n n Definition 3.1. The Gibbs measure or Gibbs ensemble in statistical mechanics is defined as (cid:90) (cid:90) 1 1 (4) P (B) = exp{−βH (ω)}dP = exp{−βnH(M (ω))}dP n,β n n n n Z (β) Z (β) n B n B 10 YEVGENIYKOVCHEGOVANDPETERT.OTTO (cid:82) where P is the product measure with identical marginals ρ and Z (β) = exp{−βH (ω)}dP n n Λn n n is the partition function. The positive parameter β represents the inverse temperature of the external heat bath. Definition 3.2. On the configuration space Λn, we define the Glauber dynamics for the class of spin models considered in this paper. These dynamics yield a reversible Markov chain Xt with stationary distribution being the Gibbs ensemble P . n,β (i) Select a vertex i from the underlying graph uniformly, (ii) Update the spin at vertex i according to the distribution P , conditioned on the event n,β that the spins at all vertices not equal to i remain unchanged. For more on Glauber dynamics, see [6]. An important question of mixing times of dynamics of statistical mechanical models is its relationshipwiththethermodynamicphasetransitionstructureofthesystem. Morespecifically, as a system undergoes an equilibrium phase transition with respect to some parameter; e.g. temperature, how do the corresponding mixing times behave? The answer to this question depends on the type of thermodynamic phase transition exhibited by the model. In the next section we define the two types of thermodynamic phase transition via the large deviation principle of the macroscopic quantity. 4. Large Deviations and Equilibrium Macrostate Phase Transitions Theapplicationoftheaggregatepathcouplingmethodtoproverapidmixingtakesadvantage of large deviations estimates that these models satisfy. In this section, we give a brief summary of large deviations theory used in this paper, written in the context of Gibbs ensembles defined in the previous section. For a more complete theory of large deviations see for example [12] and [17]. A function I on Rq is called a rate function if I maps Rq to [0,∞] and has compact level sets. Definition 4.1. Let I be a rate function on Rq. The sequence {M } with respect to the Gibbs β n ensemble P is said to satisfy the large deviation principle (LDP) on Rq with rate function n,β I if the following two conditions hold. β For any closed subset F, 1 (5) limsup logP {M ∈ F} ≤ −I (F) n,β n β n n→∞ and for any open subset G, 1 (6) liminf logP {M ∈ G} ≥ −I (G) n,β n β n→∞ n where I (A) = inf I (z). β z∈A β The LDP upper bound in the above definition implies that values z satisfying I (z) > 0 have β an exponentially small probability of being observed as n → ∞. Hence we define the set of equilibrium macrostates of the system by E = {z : I (z) = 0}. β β