随机算法 (Spring 2013)/Mixing Time and Coupling

Mixing Time

The mixing time of a Markov chain gives the rate at which a Markov chain converges to the stationary distribution. To rigorously define this notion, we need a way of measuring the closeness between two distributions.

Total Variation Distance

In probability theory, the total variation distance measures the difference between two probability distributions.

Definition (total variation distance)

Let $p$ and $q$ be two probability distributions over the same finite state space $\mathrm{\Omega }$, the total variation distance between $p$ and $q$ is defined as $\parallel p-q{\parallel }_{TV}=\frac{1}{2}\sum _{x\in \mathrm{\Omega }}|p(x)-q(x)|=\frac{1}{2}\parallel p-q{\parallel }_1$, where $\parallel \cdot {\parallel }_1$ is the ${\ell }_1$-norm of vectors.

It can be verified (left as an exercise) that

$\underset{A\subset \mathrm{\Omega }}{max}|p(A)-q(A)|=\frac{1}{2}\sum _{x\in \mathrm{\Omega }}|p(x)-q(x)|$,

thus the total variation distance can be equivalently defined as

$\parallel p-q{\parallel }_{TV}=\underset{A\subset \mathrm{\Omega }}{max}|p(A)-q(A)|$.

So the total variation distance between two distributions gives an upper bound on the difference between the probabilities of the same event according to the two distributions.

Mixing Time

Definition (mixing time)

Let $\pi$ be the stationary of the chain, and $p_x^{(t)}$ be the distribution after $t$ steps when the initial state is $x$. ${\mathrm{\Delta }}_x(t)=\parallel p_x^{(t)}-\pi {\parallel }_{TV}$ is the distance to stationary distribution $\pi$ after $t$ steps, started at state $x$. $\mathrm{\Delta }(t)=\underset{x\in \mathrm{\Omega }}{max}{\mathrm{\Delta }}_x(t)$ is the maximum distance to stationary distribution $\pi$ after $t$ steps. ${\tau }_x(ϵ)=min\{t\mid {\mathrm{\Delta }}_x(t)\le ϵ\}$ is the time until the total variation distance to the stationary distribution, started at the initial state $x$, reaches $ϵ$. $\tau (ϵ)=\underset{x\in \mathrm{\Omega }}{max}{\tau }_x(ϵ)$ is the time until the total variation distance to the stationary distribution, started at the worst possible initial state, reaches $ϵ$.

We note that ${\mathrm{\Delta }}_x(t)$ is monotonically non-increasing in $t$. So the definition of ${\tau }_x(ϵ)$ makes sense, and is actually the inverse of ${\mathrm{\Delta }}_x(t)$.

Definition (mixing time)

The mixing time ${\tau }_{\mathrm{m}\mathrm{i}\mathrm{x}}$ of a Markov chain is $\tau (1/2\mathrm{e})$.

The mixing time is the time until the total variation distance to the stationary distribution, starting from the worst possible initial state $x\in \mathrm{\Omega }$, reaches $\frac{1}{2\mathrm{e}}$. The value $\frac{1}{2\mathrm{e}}$ is chosen just for the convenience of calculation. The next proposition says that $\tau (ϵ)$ with general $ϵ$ can be estimated from ${\tau }_{\mathrm{m}\mathrm{i}\mathrm{x}}$.

Proposition

$\mathrm{\Delta }(k\cdot {\tau }_{\mathrm{m}\mathrm{i}\mathrm{x}})\le {\mathrm{e}}^{-k}$ for any integer $k\ge 1$. $\tau (ϵ)\le {\tau }_{\mathrm{m}\mathrm{i}\mathrm{x}}\cdot \lceil \ln \frac{1}{ϵ}\rceil$.

So the distance to stationary distribution $\mathrm{\Delta }(t)$ decays exponentially in multiplications of ${\tau }_{\mathrm{m}\mathrm{i}\mathrm{x}}$.

Both the formal proofs of the monotonicity of ${\mathrm{\Delta }}_x(t)$ and the above proposition uses the coupling technique and is postponed to next section.

Coupling

We will discuss how to bound the mixing time by coupling two Markov chains. Before that, we will first formally introduce the coupling of two probability distributions.

Coupling of Two Distributions

Coupling is a powerful proof technique in probability theory. It allows us to compare two unrelated variables (or processes) by forcing them to share some randomness.

Definition (coupling)

Let $p$ and $q$ be two probability distributions over $\mathrm{\Omega }$. A probability distribution $\mu$ over $\mathrm{\Omega }\times \mathrm{\Omega }$ is said to be a coupling if its marginal distributions are $p$ and $q$; that is $\begin{array}{rl}p(x)& =\sum _{y\in \mathrm{\Omega }}\mu (x,y);\\ q(x)& =\sum _{y\in \mathrm{\Omega }}\mu (y,x).\end{array}$

The interesting case is when $X$ and $Y$ are not independent. In particular, we want the probability that $X=Y$ to be as large as possible, yet still maintaining the respective marginal distributions $p$ and $q$. When $p$ and $q$ are different it is inevitable that $X\ne Y$ with some probability, but how small this probability can be, that is, how well two distributions can be coupled? The following coupling lemma states that this is determined by the total variation distance between the two distributions.

Lemma (coupling lemma)

Let $p$ and $q$ be two probability distributions over $\mathrm{\Omega }$. For any coupling $(X,Y)$ of $p$ and $q$, it holds that $Pr[X\ne Y]\ge \parallel p-q{\parallel }_{TV}$. There exists a coupling $(X,Y)$ of $p$ and $q$ such that $Pr[X\ne Y]=\parallel p-q{\parallel }_{TV}$.

Proof. 1. Suppose $(X,Y)$ follows the distribution $\mu$ over $\mathrm{\Omega }\times \mathrm{\Omega }$. Due to the definition of coupling, $\begin{array}{rlr}p(x)=\sum _{y\in \mathrm{\Omega }}\mu (x,y)& \text{and }& q(x)=\sum _{y\in \mathrm{\Omega }}\mu (y,x).\end{array}$ Then for any $z\in \mathrm{\Omega }$, $\mu (z,z)\le min\{p(z),q(z)\}$, thus $\begin{array}{rl}Pr[X=Y]& =\sum _{z\in \mathrm{\Omega }}\mu (z,z)\le \sum _{z\in \mathrm{\Omega }}min\{p(z),q(z)\}.\end{array}$ Therefore, $\begin{array}{rl}Pr[X\ne Y]& \ge 1-\sum _{z\in \mathrm{\Omega }}min\{p(z),q(z)\}\\ & =\sum _{z\in \mathrm{\Omega }}(p(z)-min\{p(z),q(z)\})\\ & =\sum _{\genfrac{}{}{0ex}{}{z\in \mathrm{\Omega }}{p(z)>q(z)}}(p(z)-q(z))\\ & =\frac{1}{2}\sum _{z\in \mathrm{\Omega }}|p(z)-q(z)|\\ & =\parallel p-q{\parallel }_{TV}.\end{array}$ 2. We can couple $X$ and $Y$ so that for each $z\in \mathrm{\Omega }$, $X=Y=z$ with probability $min\{p(z),q(z)\}$. The remaining follows as above. $◻$

The proof is depicted by the following figure, where the curves are the probability density functions for the two distributions $p$ and $q$, the colored area is the diference between the two distribution, and the "lower envelope" (the red line) is the $min\{p(x),q(x)\}$.

Monotonicity of ${\mathrm{\Delta }}_x(t)$

Consider a Markov chain on state space $\mathrm{\Omega }$. Let $\pi$ be the stationary distribution, and $p_x^{(t)}$ be the distribution after $t$ steps when the initial state is $x$. Recall that ${\mathrm{\Delta }}_x(t)=\parallel p_x^{(t)}-\pi {\parallel }_{TV}$ is the distance to stationary distribution $\pi$ after $t$ steps, started at state $x$.

We will show that ${\mathrm{\Delta }}_x(t)$ is non-decreasing in $t$. That is, for a Markov chain, the variation distance to the stationary distribution monotonically decreases as time passes. Although this is rather intuitive at the first glance, the proof is nontrivial. A brute force (algebraic) proof can be obtained by analyze the change to the 1-norm of $p_x^{(t)}-\pi$ by multiplying the transition matrix $P$. The analysis uses eigen decomposition. We introduce a cleverer proof using coupling.

Proposition

${\mathrm{\Delta }}_x(t)$ is non-decreasing in $t$.

Proof. Let $X_0=x$ and $Y_0$ follow the stationary distribution $\pi$. Two chains $X_0,X_1,X_2,\dots$ and $Y_0,Y_1,Y_2,\dots$ can be defined by the initial distributions $X_0$ and $Y_0$. The distributions of $X_t$ and $Y_t$ are $p_x^{(t)}$ and $\pi$, respectively. For any fixed $t$, we can couple $X_t$ and $Y_t$ such that $Pr[X_t\ne Y_t]=\parallel p_x^{(t)}-\pi {\parallel }_{TV}={\mathrm{\Delta }}_x(t)$. Due to the Coupling Lemma, such coupling exists. We then define a coupling between $X_{t+1}$ and $Y_{t+1}$ as follows. If $X_t=Y_t$, then $X_{t+1}=Y_{t+1}$ following the transition matrix of the Markov chain. Otherwise, do the transitions $X_t\to X_{t+1}$ and $Y_t\to Y_{t+1}$ independently, following the transitin matrix. It is easy to see that the marginal distributions of $X_{t+1}$ and $Y_{t+1}$ both follow the original Markov chain, and $Pr[X_{t+1}\ne Y_{t+1}]\le Pr[X_t\ne Y_t].$ In conclusion, it holds that ${\mathrm{\Delta }}_x(t+1)=\parallel p_x^{(t+1)}-\pi {\parallel }_{TV}\le Pr[X_{t+1}\ne Y_{t+1}]\le Pr[X_t\ne Y_t]={\mathrm{\Delta }}_x(t),$ where the first inequality is due to the easy direction of the Coupling Lemma. $◻$

Rapid Mixing by Coupling

Consider an ergodic (irreducible and aperiodic) Markov chain on finite state space $\mathrm{\Omega }$. We want to upper bound its mixing time. The coupling technique for bounding the mixing time can be sumerized as follows:

Consider two random walks starting at state $x$ and $y$ in $\mathrm{\Omega }$. Each individual walk follows the transition rule of the original Markov chain. But the two random walks may be "coupled" in some way, that is, may be correlated with each other. A key observation is that for any such coupling, it always holds that

$\mathrm{\Delta }(t)\le \underset{x,y\in \mathrm{\Omega }}{max}Pr[\text{ the two }\mathit{c}\mathit{o}\mathit{u}\mathit{p}\mathit{l}\mathit{e}\mathit{d}\text{ random walks started at }x,y\text{ have not met by time }t]$

where we recall that $\mathrm{\Delta }(t)=\underset{x\in \mathrm{\Omega }}{max}\parallel p_x^{(t)}-\pi {\parallel }_{TV}$.

Definition (coupling of Markov chain)

A coupling of a Markov chain with state space $\mathrm{\Omega }$ and transition matrix $P$, is a Markov chain $(X_t,Y_t)$ with state space $\mathrm{\Omega }\times \mathrm{\Omega }$, satisfying each of $X_t$ and $Y_t$ viewed in isolation is a faithful copy of the original Markov chain, i.e. $Pr[X_{t+1}=v\mid X_t=u]=Pr[Y_{t+1}=v\mid Y_t=u]=P(u,v)$; once $X_t$ and $Y_t$ reaches the same state, they make identical moves ever since, i.e. $X_{t+1}=Y_{t+1}$ if $X_t=Y_t$.

Lemma (coupling lemma for Markov chains)

Let $(X_t,Y_t)$ be a coupling of a Markov chain $M$ with state space $\mathrm{\Omega }$. Then $\mathrm{\Delta }(t)$ for $M$ is bounded by $\mathrm{\Delta }(t)\le \underset{x,y\in \mathrm{\Omega }}{max}Pr[X_t\ne Y_t\mid X_0=x,Y_0=y]$.

Proof. Due to the coupling lemma (for probability distributions), $Pr[X_t\ne Y_t\mid X_0=x,Y_0=y]\ge \parallel p_x^{(t)}-p_y^{(t)}{\parallel }_{TV},$ where $p_x^{(t)},p_y^{(t)}$ are distributions of the Markov chain $M$ at time $t$, started at states $x,y$. Therefore, $\begin{array}{rl}\mathrm{\Delta }(t)& =\underset{x\in \mathrm{\Omega }}{max}\parallel p_x^{(t)}-\pi {\parallel }_{TV}\\ & \le \underset{x,y\in \mathrm{\Omega }}{max}\parallel p_x^{(t)}-p_y^{(t)}{\parallel }_{TV}\\ & \le \underset{x,y\in \mathrm{\Omega }}{max}Pr[X_t\ne Y_t\mid X_0=x,Y_0=y].\end{array}$ $◻$

Corollary

Let $(X_t,Y_t)$ be a coupling of a Markov chain $M$ with state space $\mathrm{\Omega }$. Then $\tau (ϵ)$ for $M$ is bounded as follows: $\underset{x,y\in \mathrm{\Omega }}{max}Pr[X_t\ne Y_t\mid X_0=x,Y_0=y]\le ϵ⟹\tau (ϵ)\le t$.

Geometric convergence

Consider a Markov chain on state space $\mathrm{\Omega }$. Let $\pi$ be the stationary distribution, and $p_x^{(t)}$ be the distribution after $t$ steps when the initial state is $x$. Recall that

• ${\mathrm{\Delta }}_x(t)=\parallel p_x^{(t)}-\pi {\parallel }_{TV}$;
• $\mathrm{\Delta }(t)=\underset{x\in \mathrm{\Omega }}{max}{\mathrm{\Delta }}_x(t)$;
• ${\tau }_x(ϵ)=min\{t\mid {\mathrm{\Delta }}_x(t)\le ϵ\}$;
• $\tau (ϵ)=\underset{x\in \mathrm{\Omega }}{max}{\tau }_x(ϵ)$;
• ${\tau }_{\mathrm{m}\mathrm{i}\mathrm{x}}=\tau (1/2\mathrm{e})$.

We prove that

Proposition

$\mathrm{\Delta }(k\cdot {\tau }_{\mathrm{m}\mathrm{i}\mathrm{x}})\le {\mathrm{e}}^{-k}$ for any integer $k\ge 1$. $\tau (ϵ)\le {\tau }_{\mathrm{m}\mathrm{i}\mathrm{x}}\cdot \lceil \ln \frac{1}{ϵ}\rceil$.

Proof. 1. We denote that $\tau ={\tau }_{\mathrm{m}\mathrm{i}\mathrm{x}}$. We construct a coupling of the Markov chain as follows. Suppose $t=k\tau$ for some integer $k$. If $X_t=Y_t$ then $X_{t+i}=Y_{t+i}$ for $i=1,2,\dots ,\tau$. For the case that $X_t=u,Y_t=v$ for some $u\ne v$, we couple the $X_{t+\tau }$ and $Y_{t+\tau }$ so that $Pr[X_{t+\tau }\ne Y_{t+\tau }\mid X_t=u,Y_t=v]=\parallel p_u^{(t)}-p_v^{(t)}{\parallel }_{TV}$. Due to the Coupling Lemma, such coupling does exist. For any $u,v\in \mathrm{\Omega }$ that $u\ne v$, $\begin{array}{rl}Pr[X_{t+\tau }\ne Y_{t+\tau }\mid X_t=u,Y_t=v]& =\parallel p_u^{(\tau )}-p_v^{(\tau )}{\parallel }_{TV}\\ & \le \parallel p_u^{(\tau )}-\pi {\parallel }_{TV}+\parallel p_v^{(\tau )}-\pi {\parallel }_{TV}\\ & ={\mathrm{\Delta }}_u(\tau )+{\mathrm{\Delta }}_v(\tau )\\ & \le \frac{1}{\mathrm{e}}.\end{array}$ Thus $Pr[X_{t+\tau }\ne Y_{t+\tau }\mid X_t\ne Y_t]\le \frac{1}{\mathrm{e}}$ by the law of total probability. Therefore, for any $x,y\in \mathrm{\Omega }$, $\begin{array}{rl}& Pr[X_{t+\tau }\ne Y_{t+\tau }\mid X_0=x,Y_0=y]\\ & =Pr[X_{t+\tau }\ne Y_{t+\tau }\mid X_t\ne Y_t]\cdot Pr[X_t\ne Y_t\mid X_0=x,Y_0=y]\\ & \le \frac{1}{\mathrm{e}}Pr[X_t\ne Y_t\mid X_0=x,Y_0=y].\end{array}$ Then by induction, $Pr[X_{k\tau }\ne Y_{k\tau }\mid X_0=x,Y_0=y]\le {\mathrm{e}}^{-k},$ and this holds for any $x,y\in \mathrm{\Omega }$. By the Coupling Lemma for Markov chains, this means $\mathrm{\Delta }(k{\tau }_{\mathrm{m}\mathrm{i}\mathrm{x}})=\mathrm{\Delta }(k\tau )\le {\mathrm{e}}^{-k}$. 2. By the definition of $\tau (ϵ)$, the inequality is straightforwardly implied by (1). $◻$

Application: Random Walk on the Hypercube

A $n$-dimensional hypercube is a graph on vertex set $\{0,1{\}}^n$. For any $x,y\in \{0,1{\}}^n$, there is an edge between $x$ and $y$ if $x$ and $y$ differ at exact one coordinate (the hamming distance between $x$ and $y$ is 1).

We use coupling to bound the mixing time of the following simple random walk on a hypercube.

Random Walk on Hypercube

At each step, for the current state $x\in \{0,1{\}}^n$: with probability $1/2$, do nothing; else, pick a coordinate $i\in \{1,2,\dots ,n\}$ uniformly at random and flip the bit $x_i$ (change $x_i$ to $1-x_i$).

This is a lazy uniform random walk in an $n$-dimensional hypercube. It is equivalent to the following random walk.

Random Walk on Hypercube

At each step, for the current state $x\in \{0,1{\}}^n$: pick a coordinate $i\in \{1,2,\dots ,n\}$ uniformly at random and a bit $b\in \{0,1\}$ uniformly at random; let $x_i=b$.

It is easy to see the two random walks are the same. The second form hint us to couple the random choice of $i$ and $b$ in each step. Consider two copies of the random walk $X_t$ and $Y_t$, started from arbitrary two states $X_0$ and $Y_0$, the coupling rule is:

• At each step, $X_t$ and $Y_t$ choose the same (uniformly random) coordinate $i$ and the same (uniformly random) bit $b$.

Obviously the two individual random walks are both faithful copies of the original walk.

For arbitrary $x,y\in \{0,1{\}}^n$, started at $X_0=x,Y_0=y$, the event $X_t=Y_t$ occurs if everyone of the coordinates on which $x$ and $y$ disagree has been picked at least once. In the worst case, $x$ and $y$ disagree on all $n$ coordinates. The time $T$ that all $n$ coordinates have been picked follows the coupon collector problem collecting $n$ coupons, and we know from the coupon collector problem that for $c>0$,

$Pr[T\ge n\ln n+cn]\le {\mathrm{e}}^{-c}.$

Thus for any $x,y\in \{0,1{\}}^n$, if $t\ge n\ln n+cn$, then $Pr[X_t\ne Y_t\mid X_0=x,Y_0=y]\le {\mathrm{e}}^{-c}$. Due to the coupling lemma for Markov chains,

$\mathrm{\Delta }(n\ln n+cn)\le {\mathrm{e}}^{-c},$

which implies that

$\tau (ϵ)=n\ln n+n\ln \frac{1}{ϵ}$.

So the random walk achieves a polynomially small variation distance $ϵ=\frac{1}{\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(n)}$ to the stationary distribution in time $O(n\ln n)$.

Note that the number of states (vertices in the $n$-dimensional hypercube) is $2^n$. Therefore, the mixing time is exponentially small compared to the size of the state space.

Card Shuffling

We consider the Markov chain of shuffling a deck of cards, and prove the rapid mixing of the chain by coupling.

Riffle Shuffle

The following is the Gilbert-Shannon-Reeds model of riffle shuffle introduced by Gilbert and Shannon in 1955 and independently by Reeds in 1985.

Riffle Shuffle (Gilbert-Shannon 1955; Reeds 1985)

Given a deck of $n$ cards, at each round, do as follows. Split the original deck into two decks according to the binomial distribution $\mathrm{B}\mathrm{i}\mathrm{n}(n,1/2)$. Cut off the first $k$ cards with probability $\frac{(\genfrac{}{}{0ex}{}{n}{k})}{2^n}$, put into the left deck, and put the rest $n-k$ cards into the right deck. Drop cards in sequence, where the next card comes from one of the two decks with probability proportional to the size of the deck at that time. Suppose at a step there are $L$ cards in the left deck and $R$ cards in the right deck. A card is dropped from left with probability $\frac{L}{L+R}$, and from right otherwise.

The second step actually samples a uniform interleaving of left and right deck. The magician and mathematician Diaconis in 1988 found evidence showing that this mathematical model reasonably approximate the riffle shuffling acted by human.

The above model is equivalent to the following model of inverse riffle shuffle.

Inverse Riffle Shuffle

Label each card with a bit from $\{0,1\}$ uniformly and independently at random. Place all cards labeled with 0 above all cards labeled with 1, keeping the cards with the same label in the same the relative order as before.

The process of inverse riffle shuffle is depicted as follows.

For each card, the random bits used for labeling the card compose a binary code $x$, with the $t$-th bit (from lower to higher radix) $x_t$ being the random bit chosen in round $t$ to label the card.

Lemma

After every round of the inverse riffle shuffle, the cards are sorted in non-decreasing order of their corresponding binary codes.

Proof. By induction. After the first round, all $0$ are above all $1$s. Assume that the hypothesis is true for the first $t-1$ rounds. After the $t$-th round, all cards with the highest coordinate $x_t=0$ are above all cards with $x_t=1$, and by the definition of inverse riffle shuffle, cards with the same highest bit $x_t$ are kept in the same relative order as they are after the $(t-1)$-th round of the shuffling, which due to the hypothesis, means that the cards with the same highest bit $x_t$ are sorted in the non-decreasing order of $x_{t-1}{x}_{t-2}\cdots x_1$. By the definition of binary representation, all cards are sorted. $◻$

Rapid Mixing of Riffle Shuffle by Coupling

Theorem

The mixing time of inverse riffle shuffle of a deck of $n$ cards is ${\tau }_{\mathrm{m}\mathrm{i}\mathrm{x}}=O(\log n)$.

Consider two instance of shuffling, started with two decks, each in an arbitrary order. We couple the two shuffling processes by coupling their random choices of labelings:

• In each round, we label the same cards (same content, not the same order) in the two decks with the same random bit.

Formally, for each $i\in [n]$, we uniformly and independently choose a random $b_i\in \{0,1\}$ as the label of the card $i$ in each of the two decks in that round. It is easy to see that, each of the two shuffling processes viewed individually follows exactly the rules of inverse riffle shuffle.

Lemma

With the above coupling rule, started with arbitrary two decks of cards, the two decks are the same once all cards in the first (or the second) deck have distinct labels.

Proof. By the definition of the coupling rule, any two identical cards in the two decks always have the same label, since in every round they choose the same random bit. And we have shown that after each round, the labels are sorted in non-decreasing order. Thus, we can conclude: after each round, the sequences of the labels of the two decks are identical (and sorted in non-decreasing order). Therefore, when all cards in the first deck have distinct labels, the second deck have the same set of distinct labels, and the cards are sorted increasingly in their labels in the respective decks. Since any two identical cards have the same labels, the cards in the two decks must be in the same order. $◻$

We denote by $T$ the random variable representing the time that in an inverse riffle shuffle, all cards in the deck have distinct labels. Due to the coupling lemma for Markov chains,

$\mathrm{\Delta }(t)\le Pr[T\ge t]$.

This bound can be deduced from the birthday problem. After $t$ round, each of the $n$ cards is randomly assigned one of the $2^t$ possible labels. We know that for some $2^t=O(n^2)$, i.e. $t=2\log n+O(1)$, the probability that no two cards have the same label is $>1-1/2\mathrm{e}$, i.e. $\mathrm{\Delta }(t)<1/2\mathrm{e}$, thus

${\tau }_{\mathrm{m}\mathrm{i}\mathrm{x}}\le 2\log n+O(1)$.

Note that the state space is the set of all permutations, which is of size $n!$, whose logarithm is still as large as $\log (n!)=O(n\ln n)$ due to Stirling's approximation. Thus the riffle shuffle is mixing extremely fast.

This estimation of mixing time is fairly tight. For the case that $n=52$, the real mixing rate is as follows.

$t$	1	2	3	4	5	6	7	8	9
$\mathrm{\Delta }(t)$	1.000	1.000	1.000	1.000	0.924	0.614	0.334	0.167	0.003

Graph Colorings

A proper coloring of a graph $G(V,E)$ is a mapping $f:V\to [q]$ for some integer $q$, satisfying that $f(u)\ne f(v)$ for all $uv\in E$.

We consider the problem of sampling a uniformly random proper coloring of a given graph. We will later see that this is useful for counting the number of proper colorings of a given graph, which is a fundamental combinatorial problem, having important applications in statistic physics.

Let's first consider the decision version of the problem. That is, given as input a graph $G(V,E)$, decide whether there exists a proper $q$-coloring of $G$. Denote by $\mathrm{\Delta }$ the maximum degree of $G$.

• If $q\ge \mathrm{\Delta }+1$, there always exists a proper coloring. Moreover, the proper coloring can be found by a simple greedy algorithm.
• If $q=\mathrm{\Delta }$, $G$ has a proper coloring unless it contains a $(\mathrm{\Delta }+1)$-clique or it is an odd cycle. (Brooks Theorem)
• If $q<\mathrm{\Delta }$, the problem is NP-hard.

Sampling a random coloring is at least as hard as deciding its existence, so we don't expect to solve the sampling problem when $q<\mathrm{\Delta }$. The decision problem for the case $q=\mathrm{\Delta }$ is also nontrivial. Thus people are interested only in the case when $q\ge \mathrm{\Delta }+1$.

The following is a natural Markov chain for sampling proper colorings.

Markov Chain for Graph Coloring ${\mathcal{M}}_c$

Start with a proper coloring of $G(V,E)$. At each step: Pick a vertex $v\in V$ and a color $c\in [q]$ uniformly at random. Change the color of $v$ to $c$ if the resulting coloring is proper; do nothing if otherwise.

For a fixed graph $G(V,E)$, the state space of the above Markov chain is the set of all proper colorings of $G$ with $q$ colors.

Lemma

The followings hold for ${\mathcal{M}}_c$. Aperiodic. The transition matrix is symmetric. Irreducible if $q\ge \mathrm{\Delta }+2$.

The followings are the two most important conjectures regarding the problem.

Conjecture

${\mathcal{M}}_c$ has mixing time $O(n\ln n)$ whenever $q\ge \mathrm{\Delta }+2$. Random sampling of proper graph colorings can be done in polynomial time whenever $q\ge \mathrm{\Delta }+1$.

These two conjectures are still open. People approach them by relax the requirement for the number of colors $q$. Intuitively, the larger the $q$ is, the more freedom we have, the less dependency are there between non-adjacent vertices.

Rapid mixing of the case $q>4\mathrm{\Delta }$

We couple the two copies of ${\mathcal{M}}_c$, $X_t$ and $Y_t$, by the following coupling rule:

• At each step, let $X_t$ and $Y_t$ choose the same vertex $v$ and same color $c$.

Note that by this coupling, it is possible that $v$ is recolored to $c$ in both chains, in one of the two chains, or in no chain. We may separate these cases by looking at the Hamming distance between two colorings.

Let $d(X_t,Y_t)$ be the number of vertices whose colors in $X_t$ and $Y_t$ disagree. For each step, for any choice of vertex $v$ and color $c$, there are three possible cases:

• "Good move" ($d(X_t,Y_t)$ decreases by 1): $X_t$ disagree with $Y_t$ at $v$, and $c$ is not used in the colors of $v$ in both $X_t$ and $Y_t$.
• "Bad move" ($d(X_t,Y_t)$ increases by 1):
• "Neutral move" ($d(X_t,Y_t)$ is unchanged):