Premium
Fast convergence of the Glauber dynamics for sampling independent sets
Author(s) -
Luby Michael,
Vigoda Eric
Publication year - 1999
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199910/12)15:3/4<229::aid-rsa3>3.0.co;2-x
Subject(s) - glauber , mathematics , markov chain , simple random sample , markov chain monte carlo , combinatorics , discrete mathematics , convergence (economics) , sampling (signal processing) , independent set , monte carlo method , graph , computer science , statistics , physics , population , demography , filter (signal processing) , sociology , scattering , optics , economics , computer vision , economic growth
We consider the problem of sampling independent sets of a graph with maximum degree δ. The weight of each independent set is expressed in terms of a fixed positive parameter λ≤2/(δ−2), where the weight of an independent set σ is λ |σ| . The Glauber dynamics is a simple Markov chain Monte Carlo method for sampling from this distribution. We show fast convergence (in O ( n log n ) time) of this dynamics. This paper gives the more interesting proof for triangle‐free graphs. The proof for arbitrary graphs is given in a companion paper (E. Vigoda, Technical Report TR‐99‐003, International Computer Institute, Berkeley, CA, 1998). We also prove complementary hardness of approximation results, which show that it is hard to sample from this distribution when λ> c /δ for a constant c ≤0. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15, 229–241, 1999