Glauber Dynamics is rapid mixing for k > 2Δ

Glauber Dynamics is a well studied Markov Chain to sample k-colorings of a graph. However, a basic coupling/path coupling analysis of Glauber Dynamics requires $k>3\Delta$ for the chain to be rapid mixing. However, it is hypothesized (and intuitive) that the chain should be rapid mixing for any $k>\Delta +2$. Bringing this gap down is a popular open problem. Jerrum used an extremely clever coupling to bring it down to $k>2\Delta$. Here I’ll give a simple path coupling proof that uses the same idea.

Glauber Dynamics

The Glauber Dynamics chain ${\sigma }_t$ works as follows:

1. Choose $v{\in }_{R}V$ and $c{\in }_{R}C$, where $V$ is the vertex set and $C$ is the set of colors.
2. If $c\notin \{{\sigma }_t(w):w\in N(v)\}$, set ${\sigma }_{t+1}(v)=c$ and ${\sigma }_{t+1}(w)={\sigma }_t(w)$ for all $w\ne v$. Here $N(v)$ is the set of neighbors of $v$.
3. Else set ${\sigma }_{t+1}(w)={\sigma }_t(w)$ for all $w\in V$.

Path Coupling

For a metric $d$ defined on the state space, such that for any pair of states $x_t,y_t\in \Omega$, there exists a path $x_t=z_0,z_1,\cdots ,z_r=y_t$ where ${\sum }_{i=0}^{r-1}d(z_i,z_{i+1})=d(x_t,y_t)$. The path coupling theorem implies that if for each pair of states $x_0,y_0$ such that $d(x_0,y_0)=1$, if $E[d(x_1,y_1)]\le \beta d(x_0,y_0)$ for some $0<\beta <1$, the the mixing time satisfies

${\tau }_{mix}(ϵ)\le \frac{log(D)-log(ϵ)}{log({\beta }^{-1})}$.

where $D$ is maximum value taken by the metric.

Jerrum’s Coupling

Choose $d(\sigma ,\tau )$ to be the number of vertices where the colorings differ. Consider $({\sigma }_0,{\tau }_0)$ that differ exactly at a single vertex $u$. The maximum value $d$ can take is $n$ since the two colorings can differ at all vertices. Jerrum’s coupling does the following:

1. Choose $v{\in }_{R}V$ and $c{\in }_{R}C$.
2. If $c\notin \{{\sigma }_t(w):w\in N(v)\}$, set ${\sigma }_{t+1}(v)=c$ and ${\sigma }_{t+1}(w)={\sigma }_t(w)$ for all $w\ne v$.
3. Else set ${\sigma }_{t+1}(w)={\sigma }_t(w)$ for all $w\in V$.
4. If $f(c)\notin \{{\sigma }_t(w):w\in N(v)\}$, set ${\sigma }_{t+1}(v)=f(c)$ and ${\sigma }_{t+1}(w)={\sigma }_t(w)$ for all $w\ne v$. Here $N(v)$ is the set of neighbors of $v$.
5. Else set ${\sigma }_{t+1}(w)={\sigma }_t(w)$ for all $w\in V$.

Where

$$f(c)=\{\begin{array}{ll}{\sigma }_t(u)& \text{if }c={\tau }_t(u)\\ {\tau }_t(u)& \text{if }c={\sigma }_t(u)\\ c& \text{otherwise}\end{array}$$

It is simple to see that this is indeed a coupling. Each chain when viewed in isolation evolves exactly like Glauber Dynamics. In order to bound $E[d({\sigma }_1,{\tau }_1)]$ lets look at the possible cases.

• $v\ne u$ and $v\notin N(u)$: Here the update either goes through in both chains or neither chain. In both these cases the distance does not change.
• $v=u$: Here if the update goes through, it does so in both chains and the distance decreases by 1. However if it doesn’t go through in one chain, it doesn’t in the other as well and so the distance does not change. The update goes through with probability at least $\frac{(k-\Delta )}{nk}$ since in the worst case, $u$ has $\Delta$ neighbours each with their unique color.
• $v\in N(u)$: Here, if $c={\sigma }_t(u)$ the update doesn’t go through in either chain since $f(c)={\tau }_t(u)$. However, if $c={\tau }_t(u)$ a different update goes through in both the chains: ${\sigma }_{t+1}(v)={\tau }_t(u)$ and ${\tau }_{t+1}(v)={\sigma }_t(u)$. This causes the distance to increase by 1. This occurs with probabilty $\frac{\Delta }{nk}$.

Thus, $E[d(x_1,y_1)]\le 1-1\frac{k-\Delta }{nk}+1\frac{\Delta }{nk}$. Simplifying this gives us $1-\frac{2\Delta -k}{nk}$. Since $1+x\le e^x$, $E[d(x_1,y_1)]\le e^{\frac{2\Delta -k}{nk}}$. For this quantity to be between 0 and 1, $2\Delta -k<0$. Hence if $k>2\Delta$, by the Path Coupling Theorem, ${\tau }_{mix}(ϵ)\le \frac{log(n)-log(ϵ)}{\frac{1}{nk}}$. Therefore Glauber Dynamics mixes in time $O(nklog(n{ϵ}^{-1}))$.