tailieunhanh - Báo cáo toán học: " A Note on the Glauber Dynamics for Sampling Independent Sets"

Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: A Note on the Glauber Dynamics for Sampling Independent Sets. | A Note on the Glauber Dynamics for Sampling Independent Sets Eric Vigoda Division of Informatics King s Buildings University of Edinburgh Edinburgh EH9 3JZ vigoda@ Submitted September 25 2000 Accepted January 17 2001. MR Subject Classifications 68W20 60J10 Abstract This note considers the problem of sampling from the set of weighted independent sets of a graph with maximum degree A. For a positive fugacity A the weight of an independent set Ơ is Alơl. Luby and Vigoda proved that the Glauber dynamics which only changes the configuration at a randomly chosen vertex in each step has mixing time O n log n when A 2 for triangle-free graphs. We extend their approach to general graphs. 1 Introduction Given a graph G V E with maximum degree A we are interested in sampling from the set Q of independent sets weighted by a positive fugacity A. The weight of an independent set Ơ is w ơ A l. Our focus is the associated probability measure tỵ - w ơ IĂơ V Ha eo w a This corresponds to the hard-core lattice gas model from statistical physics . see 4 . We study the Glauber dynamics a very simple Markov Chain whose stationary distribution is the desired distribution. The transitions of the chain consist of selecting a vertex uniformly at random and modifying the configuration only at the chosen vertex. The goal is to analyze the time required for the dynamics to get close to its stationary distribution known as its mixing time formally defined in Section 2 . Luby and Vigoda 5 proved the Glauber dynamics has mixing time O n log n when A on any triangle-free graph. This result was extended to general graphs in a THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R8 1 preliminary version of this note 7 the proof presented here is simpler than the original version . An alternative approach was pursued by Dyer and Greenhill who analyzed a slightly different though also quite simple chain roughly speaking they consider the Glauber dynamics with an extra slide-type move . They .