Slow mixing of Glauber dynamics for the hard-core model on the hypercube
David Galvin
Abstract
For  > 0, let  be the probability measure on the independent sets of the hypercube {0, 1}d in which I is chosen with probability proportional to |I | . We study the Glauber dynamics, or single-site-update Markov chain, whose stationary distribution is  , and show that for values of  tending to 0 as d grows, the convergence to stationarity is exponentially slow in the volume of the cube. The proof combines a conductance argument with combinatorial enumeration methods.


Prasad Tetali



exponentially slowly in the volume of the cube for  =  (log d/d1/4 ). 2 Statement of the result For a graph  = (V , E ), write I () for the collection of independent sets (sets of vertices spanning no edges) in V . For  > 0 define the hard-core measure with activity  on I () by

 ({I }) =  ()({I }) = |I | /Z () for I  I , I |I | where Z () = I ()  . This is the stationary distribution of the Markov chain M = M () with 1 Intro duction We consider the well known hard-core model on a finite transition probabilities P (I , J ) (I , J  I ()) given by  graph, with activity . Our particular focus is the if |I J| > 1 0 1  mixing time of the Glauber dynamics, or single-site if I  J · |V | 1+ P (I , J ) = 1 1 update Markov chain, for this model. if J  I ·  |V | 1+  J  In [1] it was shown that for  growing exponentially ) 1- if I = J . P (I , J =J with d, the Glauber dynamics for the hard-core model d (Here I  J means |I J| = 1, I  J .) This chain is · on the discrete torus [-L, L] (with the obvious adjacency) mixes exponentially slowly in the surface area of often referred to as the Glauber dynamics on I (). Write P t (I , ·) for the distribution of the chain the torus. at time t, giveJ that it started in state I , and set n In light of a recent result of Galvin and Kahn t V ARI (t) = [3], it is tempting to believe that slow mixing on the I () |P (I , J ) -  (J )|. The mixing torus should hold for much smaller values of . The time M = M () of M , which measures the speed main result of [3] is that the hard-core model on Zd at which the chain converges to stationarity, is, as usual, t . exhibits multiple Gibbs phases for  =  (log3/4 d/d1/4 ). 1 M = max min : V ARI (t )  t > t This suggests that for  in this range, the typical e I I () independent set chosen from the torus according to the hard-core distribution is either predominantly odd Our main result concerns M (Qd ), where Qd is the d (defined in the obvious way: x = (x1 , . . . , xd ) is odd usual discrete hypercube (the graph on vertex set {0, 1} i if xi is odd) or predominantly even. Thus there is in which pairs of strings are adjacent iff they differ on d-1 an unlikely "bottleneck" set of balanced independent exactly one coordinate). Writing M for 2 , we have sets separating the predominantly odd sets from the Theorem 2.1. There are constants c1 , c2 , c3 > 0 such predominantly even ones. This bottleneck should cause that for al l d and for  > c1 log d/d1/4 , the conductance of the Glauber dynamics chain to be min{2 ,1} log2 (1+) c2 M  d(log(1+)+c3 log d) small, and so cause its mixing time to be large. M (Qd ) > 2 . In this paper, by studying a simpler but related Remark 1: Our bound on  is no doubt not optimal. graph, we provide some evidence for slow mixing on In the other direction, a result of Luby and Vigoda the discrete torus at small values of . We outline [5] implies that M (Qd ) is a polynomial in M for a proof that the Glauber dynamics for the hard-core   2/(d - 2). model on the d-dimensional hypercube {0, 1}d mixes Remark 2: We can prove an analog of Theorem 2.1 for any family of regular graphs with bounded co-degree  Microsoft Research, 1 Microsoft Way, Redmond WA 98052.  Georgia Tech, Atlanta GA 30332-0160; research supp orted in (every pair of vertices having a bounded number of part by NSF grant DMS-0100289. common neighbours) and reasonable expansion.
Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688

466


3 Outline of the pro of We assume throughout that d is large enough to support our assertions. For simplicity we assume   1; we may deal with  > 1 similarly. The proof combines a conductance argument (introduced to the study of Markov chains in [4], and used in [1]) with a combinatorial enumeration argument based on ideas of Sapozhenko [6]. This argument was used in [7] to show that |I (Qd )|   2 e2M . (See also [2, 3] for recent applications.) Write E and O for the bipartition classes of Qd and set S = {I  I (Qd ) : |I  E | = |I  O|}. The removal of S splits I (Qd ) into two sets of equal measure with the property that the Glauber dynamics cannot pass between the two without visiting S . By a well known conductance argument (see [1, 4]), it follows that M (Qd )  (1 -  (S )2 )/4 (S ). Thus to prove Theorem 2.1 it suffices to show that (3.1)  ( S ) < 2
-c2 M 
2 log2 (1+) d(log(1+)+c3 log d)

We now come to the main lemma, whose (omitted) proof draws on ideas of Sapozhenko [6, 7]. It may be considered a weighted version of a lemma from [6]. Lemma 3.1. There are constants c1 , c3 , c5 > 0 such that for any a, g and  > c1 log d/d1/4 we have  (A(a, g ))  2
c5 M log d - 2 log(1+)+c 2
d (g -a) log2 (1+) 3 log d

(1 + )g .

/8.

Set S triv = {I  S : |I  E |  M } and S nt = S \ S triv , where  = 2 /100. Using the trivial lower bound Z (Qd )  2(1 + )M we have  (S triv ) (3.2) 
M i

The idea of the proof is as follows. For every 1   = o(d), we construct, using a combination of probabilistic and algorithmic arguments, a set B(a, g ) log d log d of size at most 2O(M d2 +(g-a)  ) with two properties. The first is that each A  A(a, g ) is "approximated" in an appropriate sense by some B  B (a, g ). The second is that for each B  B (a, g ), the measure of the set of A's in A(a, g ) that B can approximate is log(1+)-c3 l at most (1 + )g- (g-a) , where  = d (log(1+)+c3loog d . d g d) Optimizing over the choice of  , we obtain Lemma 3.1. Since g - a  0 always, we maximize the exponent of the bound in Lemma 3.1 by taking g - a as small as possible. For the r ge of values under consideration we an  have g - a > c4 a/ d > c4 2 M /100 d, and so
n  (SE t ) 

M 22 2

c5 M log d - 2004log(1+)+c 2
d 2 log2 (1+) d(log(1+)+c3 log d)

c M 2 log2 (1+) 3 log d

M2 2 i . i /2(1 + )M



-c2 M 

/32,

<2
nt

=0 - M /2

This gives  (S nt )  2 /16 which, combined with (3.2) gives (3.1) and Theorem 2.1. References
[1] C. Borgs, J. Chayes, A. Frieze, J.H. Kim, P. Tetali, E. Vigoda, V. Vu, Torpid Mixing of some Monte Carlo Markov Chain algorithms in Statistical Physics, FOCS '99, 218­229. [2] D. Galvin, On homomorphisms from the Hamming cube to Z, to appear. [3] D. Galvin and J. Kahn, On phase transition in the hard-core model on Zd , to appear. [4] M. Jerrum and A. Sinclair, The Monte Carlo Markov Chain method: an approach to approximate counting and integration, in Approximation Alorithms for NPhard problems, PWS, 1996. [5] M. Luby and E. Vigoda, Fast convergence of the Glauber dynamics for sampling independent sets, Random Structures and Algorithms 15 (1999), 229­241. [6] A. Sapozhenko, On the number of connected subsets with given cardinality of the boundary in bipartite graphs, Metody Diskret. Analiz. 45 (1987), 42­70. (Russian) [7] A. Sapozhenko, The number of antichains in ranked partially ordered sets, Diskret. Mat. 1 (1989), 74­93. (Russian; translation in Discrete Math. Appl. 1 no. 1 (1991), 35­58.)

-c2 M

2 log2 (1+)  d(log(1+)+c3 log d)

We now turn to S . For A  Qd , define the closure of A to be [A] = {v  Qd :  {v }   A}, where  A denotes the set of vertices adjacent to A. Say that I  I (Qd ) is smal l on E if |[I  E ]|  M /2, and set
n SE t = {I  S nt : I is small on E }. n Define smal l on O and SOt similarly. That it is easier to work with [A] than with A is a crucial idea introduced in [6]. A simple argument, based on the fact that Qd has a perfect matching, shows that any I  I (Qd ) must be small on at least one of E , O, and so n n n  (S nt )  2 max{ (SE t ),  (SOt )} = 2 (SE t ).

For each M /2  a  M and g  a set A(a, g ) = {A  E : |[A]| = a, |N (A)| = g }. Note that by an isoperimetric inequality in the cube (see e.g. [7]), there is a constant c4 such that A(a, g ) =   unless g > (1 + c4 / d)a. We have a n  (A(a, g ))(1 + )M -g /(1 + )M  (SE t ) 
,g

 M 2 max  (A(a, g ))(1 + )-g .
a,g

467