  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)$.
