Coupling with the stationary distribution and improved sampling for colorings and independent sets

Mathematics – Probability

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Published at http://dx.doi.org/10.1214/105051606000000330 in the Annals of Applied Probability (http://www.imstat.org/aap/) by

Scientific paper

10.1214/105051606000000330

We present an improved coupling technique for analyzing the mixing time of Markov chains. Using our technique, we simplify and extend previous results for sampling colorings and independent sets. Our approach uses properties of the stationary distribution to avoid worst-case configurations which arise in the traditional approach. As an application, we show that for $k/\Delta >1.764$, the Glauber dynamics on $k$-colorings of a graph on $n$ vertices with maximum degree $\Delta$ converges in $O(n\log n)$ steps, assuming $\Delta =\Omega(\log n)$ and that the graph is triangle-free. Previously, girth $\ge 5$ was needed. As a second application, we give a polynomial-time algorithm for sampling weighted independent sets from the Gibbs distribution of the hard-core lattice gas model at fugacity $\lambda <(1-\epsilon)e/\Delta$, on a regular graph $G$ on $n$ vertices of degree $\Delta =\Omega(\log n)$ and girth $\ge 6$. The best known algorithm for general graphs currently assumes $\lambda <2/(\Delta -2)$.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Coupling with the stationary distribution and improved sampling for colorings and independent sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Coupling with the stationary distribution and improved sampling for colorings and independent sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Coupling with the stationary distribution and improved sampling for colorings and independent sets will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-656549

All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.