Distributed Symmetry Breaking in Sampling
(Optimal Distributed Randomly Coloring with Fewer Colors)

arXiv:1802.06953v1 [] 20 Feb 2018

Weiming Feng

∗§

Thomas P. Hayes

†

Yitong Yin

‡§

Abstract
We examine the problem of almost-uniform sampling proper q-colorings of a graph whose
maximum degree is ∆. A famous result, discovered independently by Jerrum [30] and Salas and
Sokal [38], is that, assuming q > (2+δ)∆, the Glauber dynamics (a.k.a. single-site dynamics) for
this problem has mixing time O(n log n), where n is the number of vertices, and thus provides
a nearly linear time sampling algorithm for this problem. A natural question is the extent to
which this algorithm can be parallelized. Previous work [15] has shown that a O(∆ log n) time
parallelized algorithm is possible, and that Ω(log n) time is necessary.
We give a distributed sampling algorithm, which we call the Lazy Local Metropolis Algorithm, that achieves an optimal parallelization of this classic algorithm. It improves its predecessor, the Local Metropolis algorithm of Feng, Sun and Yin [PODC’17], by introducing a step
of distributed symmetry breaking that helps the mixing of the distributed sampling algorithm.
For sampling almost-uniform proper q-colorings of graphs G on n vertices, we show that
the Lazy Local Metropolis algorithm achieves an optimal O(log n) mixing time if either of the
following conditions is true for an arbitrary constant δ > 0:
• q ≥ (2 + δ)∆, on general graphs with maximum degree ∆;
∗

• q ≥ (α∗ + δ)∆, where α∗ ≈ 1.763 satisfies α∗ = e1/α , on graphs with sufficiently large
maximum degree ∆ ≥ ∆0 (δ) and girth at least 9.

∗

Department of Computer Science and Technology, Nanjing University. Email: fengwm@smail.nju.edu.cn.
Department of Computer Science, University of New Mexico. Email:hayes@cs.unm.edu. Partially supported by
NSF CAREER award CCF-1150281.
‡
State Key Laboratory for Novel Software Technology, Nanjing University. Email: yinyt@nju.edu.cn.
§
Supported by the National Science Foundation of China under Grant No. 61672275 and No. 61722207.
†

1

Introduction

Sampling almost-uniform graph colorings is one of the most extensively studied problems in
Markov chain Monte Carlo (MCMC) sampling. Let G = (V, E) be a graph and q a positive
integer. A proper q-coloring σ ∈ [q]V of G assigns each vertex a color from [q] = {1, 2, . . . , q}
such that no adjacent vertices receive the same color. A classic sequential algorithm for sampling
almost-uniform proper q-colorings is the Markov chain known as the heat bath Glauber dynamics
(a.k.a. single-site dynamics) on proper q-colorings. For this Markov chain (Xt )t≥0 , each Xt ∈
[q]V is a q-coloring, and in a transition Xt → Xt+1 , a vertex v ∈ V is chosen uniformly at
random and its color Xt (v) is updated to a color chosen uniformly at random from the available
colors in [q] that are not currently assigned by Xt to v’s neighbors.
A famous result, discovered independently by Jerrum [30] and Salas and Sokal [38], is that,
assuming q > (2 + δ)∆, where ∆ is the maximum degree and δ > 0 is an arbitrary constant,
the Glauber dynamics defined above has mixing time O(n log n), where n is the number of
vertices, and thus provides a nearly linear time sequential algorithm for sampling almost-uniform
proper q-colorings. For graphs with large maximum degree and large girth, Dyer and Frieze [11]
developed an approach, known as the burn-in mehtod, to obtain O(n log n) mixing time of the
Glauber dynamics with an improved condition q ≥ (α∗ + δ)∆, where α∗ ≈ 1.763 satisfies
∗
α∗ = e1/α . Subsequently, the condition for the rapid mixing was improved in a series of
works [41, 11, 28, 25, 36, 29, 18, 8]. See a survey of Frieze and Vigoda [19] for more detail.
In distributed computing, the problem of constructing a proper q-coloring by local distributed
graph algorithms has been extensively studied [34, 22, 1, 35, 40, 37, 31, 32, 39, 3, 6, 2, 4, 17], and is
a main application for distributed symmetry breaking [4]. These distributed algorithms assume
the synchronous message-passing model of communications. The graph G = (V, E) represents
a communication network. Communications are synchronized and take place in rounds. In each
round, each vertex receives messages from all neighbors, then performs the local computation,
and finally sends messages to all neighbors. The time complexity is given by the number
of rounds. Ideally, the sizes of messages are bounded in polylogarimic of |V | and the local
computations are tractable.
On the other hand, the problem of sampling an almost-uniform proper q-coloring by local
distributed algorithms received much less studies. A natural question is the extent to which the
sequential sampling algorithms can be parallelized.
Continuous-time Glauber dynamics: Perhaps the most natural process to talk about as a starting
point is the continuous-time Glauber dynamics. Each vertex gets an i.i.d. Poisson clock with
expected delay 1; the vertex updates its color every time the clock rings. The relationship
between continuous-time and discrete-time Markov chains is well understood, and there are
very close connections between their mixing times; see, for instance, [33][Theorem 20.3], and
[27] [Corollary 2.2]. In our setting, we get that the mixing time for the continuous-time dynamics
is very close to being a factor n speedup of the discrete Glauber dynamics.
How fast can we simulate this chain in a distributed setting? Offhand, it looks potentially
very tricky, since every now and then, there will be long chains of consecutive updates done in
very short time intervals, each of which affects the next one. However, a simple disagreement
percolation argument shows that, with high probability, the continuous-time Glauber dynamics
can be simulated for time t in a distributed setting, with one processor for each vertex, in the
time needed for O(t∆/n + log(n)) single-vertex updates, essentially an n/∆ factor of parallel
speedup. Assuming we are in a setting, such as q > (2 + δ)∆, in which the discrete-time Glauber
dynamics has mixing time O(n log n), this implies a local distributed algorithm with running
time O(∆ log n).
Chromatic scheduler and systematic scans: A natural way to parallelize single-site dynamics is
to use a chromatic scheduler to parallelize the updates, so that updates in the same round will

1

not affect each other. The idea was implemented in [24] and also by the LubyGlauber algorithm
in a previous work [15]. The latter achieves a O(∆ log n) mixing time under the condition
q ≥ (2 + δ)∆, which is essentially due to the rapidly mixing of systematic scans [10, 9], in which
vertices are updated sequentially according to an arbitrarily fixed order.
A fundamental issue of this type of approaches is: as a price for not allowing adjacent updates
in the same round, a factor of chromatic number (or the maximum degree ∆ for local distributed
algorithms) is inevitably introduced to the time complexity.
Local Metropolis filters: In a previous work [15], a new parallel Markov chain, called the Local Metropolis algorithm is introduced. It falls into the propose-and-filter paradigm of the
Metropolis-Hastings algorithm. In each step, every vertex independently proposes a random
color and applies a local filtration rule to √
accept or reject the proposals. Assuming a stronger
condition on the number of colors q ≥ (2 + 2 + δ)∆, this new Markov chain achieves a O(log n)
mixing time, beating the barrier of factor-Θ(∆) slowdown in previous approaches and achieving an ideal factor-Θ(n) speedup of the O(n log n) mixing time of Glauber dynamics. It was
also proved in [15] that this O(log n) time complexity is optimal for sampling almost-uniform
q-colorings by message-passing distributed algorithms as long as q = O(∆). It seems that the
drawback of this approach is its requirement of bigger number of colors.

1.1

Main results

We give a distributed MCMC sampling algorithm, called the Lazy Local Metropolis algorithm,
for sampling almost-uniform proper q-colorings. The algorithm improves the Local Metropolis
algorithm in [15] by introducing a step of symmetry breaking, and achieves the optimal O(log n)
mixing time while assuming smaller lower bounds on the number of colors q.
For sampling almost-uniform proper q-colorings of graphs with maximum degree ∆, assuming
q ≥ (2 + δ)∆, the Lazy Local Metropolis chain is rapidly mixing with rate τ (ǫ) = O(log( nǫ )).
Theorem 1. For any constant δ > 0, for every graph G on n vertices with maximum degree
∆ = ∆G , if q ≥ (2 + δ)∆, then given any ǫ > 0, the Lazy Local Metropolis algorithm returns
an almost uniform proper q-coloring of G within total variation distance ǫ in O(log n + log 1ǫ )
rounds, where the constant factor in O(·) depends only on δ.
For graphs with large girth and sufficiently large maximum degree, by an advanced coupling
similar to the one developed by Dyer et al. for sequential dynamics [8], the condition on q can
be further relaxed.
Theorem 2. For any constant δ > 0, there exists a constant ∆0 = ∆0 (δ), such that for every
graph G on n vertices with maximum degree ∆ = ∆G and girth g = g(G), if
• ∆ ≥ ∆0 and g ≥ 9,

∗

• and q ≥ (α∗ + δ)∆, where α∗ ≈ 1.763 satisfies α∗ = e1/α ,

then given any ǫ > 0, the Lazy Local Metropolis algorithm returns an almost uniform proper
q-coloring of G within total variation distance ǫ in O(log n + log 1ǫ ) rounds, where the constant
factor in O(·) depends only on δ.
The condition q ≥ (α∗ +δ)∆ matches the one achieved by Dyer et al. in [8] for the O(n log n)rapidly mixing of the Glauber dynamics on proper q-colorings of graphs with girth at least
5 and sufficiently large maximum degree. The threshold q ≥ (α∗ + δ)∆ has also appeared
elsewhere variously, including: the strong spatial mixing of proper q-colorings of triangle-free
graphs [23, 20], and rapid mixing of sequential Markov chains on proper q-colorings of graphs
with large girth and sufficiently large maximum degree [12, 25, 29], neighborhood-amenable
graphs [23], or Erdős-Rényi random graphs G(n, ∆/n) [13].

2

The Lazy Local Metropolis algorithm in above two theorems is communication- and computationefficient: each message consists of at most O(log n) bits and all local computations are fairly
cheap. In a concurrent work [16], through network decomposition [21, 37], a O(log3 n)-round
algorithm is given for sampling proper q-colorings of triangle-free graphs with maximum degree
∆ assuming q ≥ (α∗ + δ)∆, however, with messages of unbounded sizes and unbounded local
computations.
Theorem 2 is proved by establishing a so-called local uniformity property for the Markov chain
of the Lazy Local Metropolis algorithm. Similar properties have been analyzed by Hayes [26] for
Glauber dynamics. This is perhaps the first time this property is proved on a chain other than
Glauber dynamics, not to mention a chain as a distributed algorithm.
Due to a lower bound proved in [15], approximately sampling within total variation distance
ǫ > 0 from a joint distribution with exponential decay of correlations (which is the case for uniform proper q-colorings as long as q = O(∆)) requires Ω(log n+log 1ǫ ) rounds of communications.
Therefore, the time complexity O(log n + log 1ǫ ) in Theorem 1 and 2 is optimal.

Organization of the paper. Preliminaries are given in Section 2. The Lazy Local Metropolis algorithm is given in Section 3. Theorem 1 is proved in Section 4. The local uniformity
property is proved in Section 5, with which Theorem 2 is proved in Section 6.

2
2.1

Preliminaries
Graph colorings

Let G = (V, E) be an undirected graph. For any vertex v ∈ V , we use Γ(v) = {u | {u, v} ∈ E}
to denote the set of neighbors of v, and Γ+ (v) = Γ(v) ∪ {v} the inclusive neighborhood of
v. Let deg(v) = |Γ(v)| denote the degree of v, and ∆ = ∆G = maxv∈V deg(v) the maximum
degree of G. For vertices u, v ∈ V , let dist(u, v) = distG (u, v) denote the distance between u
and v in G, which equals the length of the shortest path between u and v in graph G. For
any integer r ≥ 0 and vertex v ∈ V , the r-ball and r-sphere centered at v are defined as
Br (v) , {u ∈ V | dist(u, v) ≤ r} and Sr (v) , {u ∈ V | dist(u, v) = r}, respectively.
Let q be a positive integer. A q-coloring, or just coloring, is a vector X ∈ [q]V . A coloring
X ∈ [q]V is proper if for all edges {u, w} ∈ E, X(u) 6= X(v). For any coloring X ∈ [q]V and
subset S ⊆ V , we denote by X(S) the set of colors used by X on subset S, i.e. X(S) , {X(v) |
v ∈ S}. For any two colorings X, Y ∈ [q]V , we denote by X ⊕ Y the set of vertices on which
X, Y disagree:
X ⊕ Y , {v ∈ V | X(v) 6= Y (v)}.
The Hamming distance between two colorings X, Y is |X ⊕ Y |.
Let Ω = [q]V be the set of all colorings of graph G. A uniform distribution over proper
colorings of G is a distribution µ over Ω such that for any coloring X ∈ [q]V , µ(X) > 0 if and
only if X is proper; and µ(X) = µ(Y ) for any two proper colorings X, Y .

2.2

Mixing rate and coupling

Let µ and ν be two distributions over Ω, the total variation distance between µ and ν is defined
as
1X
|µ(σ) − ν(σ)| = max |µ(A) − ν(A)|.
dTV (µ, ν) =
A⊆Ω
2
σ∈Ω

Let (Xt )t≥0 denote a Markov chain on a finite state space Ω. Assume that the chain is irreducible
and aperiodic, and is reversible with respect to the stationary distribution π. Then by the Markov

3

chain Convergence Theorem [33], the chain (Xt )t≥0 converges to the stationary distribution π.
For the formal definitions of these concepts, we refer to the textbook [33].
Let πσt denote the distribution of Xt when X0 = σ. The mixing rate τ (·) is defined as


∀ǫ > 0 : τ (ǫ) , max min t | dTV πσt , π ≤ ǫ .
σ∈Ω

Let (Xt )t≥0 , (Yt )t≥0 be two Markov chains with the same transition rule. A coupling of the
Markov chains is a joint process (Xt , Yt )t≥0 satisfying that (Xt ) and (Yt ) individually follow
the same transition rule as the original chain and Xt+1 = Yt+1 if Xt = Yt . For any coupling
(Xt , Yt )t≥0 of the Markov chains, the total variation distance between πσt and π is bounded as

max dTV πσt , π ≤ max Pr[Xt 6= Yt ].
σ∈Ω

X0 ,Y0 ∈Ω

The path coupling is a powerful engineering tool for constructing couplings.

Lemma 3 (Bubley and Dyer [5]). Given a pre-metric, which is a weighted connected undirected
graph on state space Ω with positive edge weights such that every edge is an shortest path. Let
Φ(X, Y ) be the length of shortest path between states X and Y in pre-metric. Suppose that there
is a coupling (X, Y ) → (X ′ , Y ′ ) of the Markov chain defined only for adjacent states X, Y in
pre-metric, which satisfies that
E [Φ(X ′ , Y ′ ) | X, Y ] ≤ (1 − δ)Φ(X, Y ),
for some 0 < δ < 1. Then the mixing rate of the Markov chain is bounded by


1
diam(Ω)
,
τ (ǫ) ≤ log
δ
ǫ
where diam(Ω) = maxX,Y ∈Ω Φ(X, Y ) stands for the diameter of Ω in the pre-metric.

3

The Lazy Local Metropolis Algorithm

In this section, we give the lazy local metropolis algorithm ll-Metropolis for uniform sampling
random proper graph coloring.
The algorithm is a Markov chain. Let G = (V, E) be a graph, q a positive integer and
0 < p < 1. The ll-Metropolis chain with activeness p on q-colorings of graph G, denoted as
(Xt )≥0 , is defined as follows. Initially X0 ∈ [q]V is arbitrary (not necessarily a proper coloring).
At time t, given the current coloring Xt ∈ [q]V , the Xt+1 is constructed as follows:
• Each vertex v ∈ V becomes active independently with probability p, otherwise it becomes
lazy. Let A ⊆ V denote the set of active vertices.
• Each active vertex v ∈ A independently proposes a color c(v) ∈ [q] uniformly at random.

• For each active edge {u, v} ∈ E(A), where E(A) , {{u, v} ∈ E | u ∈ A ∧ v ∈ A} , we say
that the edge {u, v} passes its check if and only if c(u) 6= c(v)∧c(u) 6= Xt (v)∧Xt (u) 6= c(v).
For each boundary edge {u, v} ∈ δA, where δA , {{u, v} ∈ E | u ∈
/ A ∧ v ∈ A} and v ∈ A
is active, we say that the edge {u, v} passes its check if and only if c(v) 6= Xt (u).

• For each vertex v ∈ V , if v is active and all edges incident to v passed their checks,
then v accepts its proposed color and updates its color as Xt+1 (v) ← c(v); otherwise
Xt+1 (v) ← Xt (v).

The algorithm terminates after T iterations and outputs X = (XT (v))v∈V . The parameters
p and T will be specified later. The pseudocode for the ll-Metropolis algorithm is given in
Algorithm 1.

4

Algorithm 1: Pseudocode for the ll-Metropolis algorithm
Input: Each vertex v ∈ V receives the set of colors [q] and 0 < p < 1 as input.
1 each v ∈ V initializes X(v) to an arbitrary color in [q];
2 for t = 1 through T do
3
foreach v ∈ V do
4
become active independently with probability p, otherwise become lazy;
5
6
7
8
9
10
11
12
13

14

foreach active v ∈ V do
propose a color c(v) ∈ [q] uniformly at random;

foreach {u, v} ∈ E where both u and v are active do
pass the check if c(u) 6= c(v) ∧ c(u) 6= X(v) ∧ X(u) 6= c(v);
foreach {u, v} ∈ E where u is lazy and v is active do
pass the check if c(v) 6= X(u);

foreach v ∈ V and v is active do
if all edges incident to v passed their checks then
X(v) ← c(v);
each v ∈ V returns X(v);
Compared to the Local Metropolis chain proposed in [15], the ll-Metropolis chain allows each
vertex to be lazy independently. It turns out this step is an operation of symmetry breaking and
is essential to the mixing of the parallel chain. We will see this in details in later sections.
Let µ denote the uniform distribution over proper colorings of graph G = (V, E), and ∆ the
maximum degree of G. The following theorem guarantees that the ll-Metropolis chain converges
to the correct stationary distribution µ.
Theorem 4. For any 0 < p < 1, the ll-Metropolis chain with activeness p is reversible with
stationary distribution µ, and converges to the stationary distribution µ as long as q ≥ ∆ + 2.
Proof. First, when q ≥ ∆ + 2, in each iteration, each vertex v with positive probability becomes
the only active vertex in its neighborhood and successfully updates its color. Once a vertex v
being successfully updated, its color will not conflict with its neighbors and will keep in that
way. Therefore, when q ≥ ∆ + 2, the ll-Metropolis chain is absorbing to proper colorings.
|Ω|×|Ω|
Let Ω = [q]V denote the state space and P ∈ R≥0
the transition matrix for the llMetropolis chain. We will then verify the chain’s irreducibility among proper colorings and
aperiodicity. For any two proper colorings X, Y , since q ≥ ∆ + 2, we can construct a finite
sequence of proper colorings X = Z0 → Z1 → . . . → Zℓ = Y , such that Zi and Zi+1 differ at a
single vertex vi . When the current coloring is Zi , with positive probability, all vertices except
vi are lazy, and vi proposes the color of vi in Zi+1 (vi ), in which case the chain will move from
coloring Zi to coloring Zi+1 . The chain is irreducible among proper colorings. On the other
hand, due to the laziness, P (X, X) > 0 for all X ∈ Ω, so the chain is aperiodic.
In the rest of the proof, we show that the following detailed balance equation is satisfied:
∀X, Y ∈ Ω :

µ(X)P (X, Y ) = µ(Y )P (Y, X).

(1)

This will prove the reversibility of the chain with respect to the stationary distribution µ. Together with the absorption to the proper colorings, the irreducibility among proper colorings, and
the aperiodicity proved above, the theorem follows according to the Markov chain convergence
theorem.

5

If both X, Y are improper colorings, then µ(X) = µ(Y ) = 0, the equation holds trivially. If
precisely one of X, Y is proper, say X is a proper coloring and Y is an improper coloring, then
X cannot move to Y since at least one edge cannot pass its check, which implies P (X, Y ) = 0.
In both cases, the detailed balance equation holds.
Assume that X, Y are both proper colorings. Consider a single move in the ll-Metropolis
chain. Let A be the set of active vertices and c ∈ [q]A be the colors proposed by active vertices.
Given the current coloring, the next coloring of ll-Metropolis chain is fully determined by the
pair (A, c).
Let ΩX→Y be the set of pairs (A, c) with which X moves to Y . Given the current coloring
X, the set of active vertices A and the colors c proposed by active vertices , we say a vertex v is
non-restricted under the tuple (X, A, c) if and only if v is active and all edges incident to v can
pass their checks. Let S(X, A, c) denote the the set of non-restricted vertices. Note that vertex
v accepts its proposed color if and only if v ∈ S(X, A, c). Let ∆X,Y = {v ∈ V | X(v) 6= Y (v)}
denote the set of vertices on which X, Y disagree. Hence, each (A, c) ∈ ΩX→Y satisfies:
• ∆X,Y ⊆ S(X, A, c).

• ∀v ∈ S(X, A, c) : c(v) = Y (v).

Similar holds for ΩY →X , the set of pairs (A, c) with which Y moves to X. Then we have
P
P (X, Y )
(A,c)∈ΩX→Y Pr[A] Pr[c | A]
=P
′
′
′
P (Y, X)
(A′ ,c′ )∈ΩY →X Pr[A ] Pr[c | A ]

(2)

In order to verify the detailed balance equation, we construct a bijection φX,Y : ΩX→Y →
ΩY →X , and for each pair (A, c) ∈ ΩX→Y , denote (A′ , c′ ) = φX,Y (A, c). Then, we show that
Pr[A] Pr[c | A] = Pr[A′ ] Pr[c′ | A′ ].

(3)

Since µ(X) = µ(Y ), then combining (2) and (3) proves the detailed balance equation (1).
The bijection φX,Y : ΩX→Y → ΩY →X is constructed as follows:
• A′ = A.

• ∀v ∈ A∩S(X, A, c): since (A, c) ∈ ΩX→Y it must hold c(v) = Y (u), then set c′ (v) = X(v).
• ∀v ∈ A\ S(X, A, c): since (A, c) ∈ ΩX→Y it must hold X(v) = Y (v), then set c′ (v) = c(v).

Note that the laziness and random proposed colors are fully independent. Since A = A′ , then
n−|A|

Pr[A] Pr[c | A] = (1 − p)

 |A|
 |A′ |
p
p
n−|A′ |
= (1 − p)
= Pr[A′ ] Pr[c | A′ ],
q
q

which proves equation (3). We finish the proof of reversibility by showing that φX,Y is indeed
a bijection from ΩX→Y to ΩY →X .
Consider the move from X to Y with pair (A, c). For each edge {u, v} ∈ E(A) ∪ δA, define
the indictor variable pass(u, v, X, A, c) indicating whether edge {u, v} passes its check under the
tuple (X, A, c). Note that X(u) 6= X(v) because X is a proper coloring, we have
(
1 (c(u) 6= c(v)) 1 (c(u) 6= X(v)) 1 (X(u) 6= c(v)) if uv ∈ E(A)
pass(uv, X, A, c) =
1 (c(v) 6= X(u))
if uv ∈ δA and v ∈ A
(Q
if uv ∈ E(A)
x∈{c(u),X(u)} 1 (x 6= y)
.
= Q y∈{c(v),X(v)}
x∈{c(v),X(v)} 1 (x 6= X(u)) if uv ∈ δA and v ∈ A

6

Similarly, for each edge {u, v} ∈ E(A′ ) ∪ δA′ , note that A′ = A, we have
Q
 x∈{c′ (u),Y (u)} 1 (x 6= y)
if uv ∈ E(A)
.
pass(uv, Y, A′ , c′ ) = Q y∈{c′ (v),Y (v)}

x∈{c′ (v),Y (v)} 1 (x 6= Y (u)) if uv ∈ δA and v ∈ A

According to the definition of φX,Y , it must hold that {c(v), X(v)} = {c′ (v), Y (v)}; {c(u), X(u)} =
{c′ (u), Y (u)} (if u is active); X(u) = Y (u) (if u is lazy), which implies pass(uv, X, A, c) =
pass(uv, Y, A′ , c′ ). Hence, it holds that S(X, A, c) = S(Y, A′ , c′ ), with which we can easily ver−1
ify that (A′ , c′ ) ∈ ΩY →X and φX,Y = φY,X
. This proves that φX,Y is a bijection from ΩX→Y
to ΩY →X .

4

Mixing When q ≥ (2 + δ)∆ on General Graphs

In this section, we analyze the mixing time for the ll-Metropolis chain for proper q-colorings on
general graphs. We show that the chain mixes within O (log n) rounds under the Dobrushin’s
condition q ≥ (2 + δ)∆, even when the maximum degree ∆ is unbounded.
Theorem 5. For all δ > 0, there exists C = C(δ), such that for every graph G on n vertices
with maximum degree
 ∆, if q ≥ (2 + δ)∆, then the mixing rate of the ll-Metropolis chain with
activeness p = min 3δ , 21 on q-colorings of graph G satisfies
τ (ǫ) ≤ C log

n
.
ǫ

The mixing rate is proved by a path coupling with respect to the Hamming distance. Compared to the coupling based on disagreement percolation for a non-lazy version of the chain
in [15], where the disagreement may percolate to distant vertices within one step, our new coupling is local, as within one step the disagreement can at most contaminate the adjacent vertices.
Thanks to the symmetry breaking due to the independent laziness, this local coupling achieves
a much better mixing condition than the one achieved in [15] with a much shorter analysis.

The local coupling: Assume X, Y ∈ [q]V to be two colorings (not necessarily proper) that

differ only at one vertex v0 . Without loss of generality, we assume X(v0 ) = Red, Y (v0 ) = Blue.
We then construct a coupling (X, Y ) → (X ′ , Y ′ ). Given the current coloring X, the random
coloring of the next step X ′ is determined by the random choice of (AX , cX ) where AX is the
set of active vertices and cX ∈ [q]AX is the vector of colors proposed by active vertices. The
coupling of the chain (X, Y ) → (X ′ , Y ′ ) is then specified by a coupling of the random choices
(AX , cX ) and (AY , cY ) of the two chains, which is described as follows:
1. First, the laziness is coupled identically. Each vertex v ∈ V becomes active in both chains,
independently with probability p. Let A = AX = AY denote the set of active vertices.

2. Then, the random proposals (cX , cY ) for the active vertices in A are coupled step by step
as follows. Recall that Γ(v0 ) denotes the set of neighbors of v0 .
(a) For every active vertex v 6∈ Γ(v0 ), the random proposals (cX (v), cY (v)) are coupled
identically such that cX (v) = cY (v) = c(v) ∈ [q] is sampled uniformly and independently.
(b) For every active vertex v ∈ Γ(v0 ), if at least one of the following conditions is satisfied,
the random proposals (cX (v), cY (v)) are coupled identically:
• for at least one of v’s neighbor u 6= v0 , the current color satisfies that X(u) =
Y (u) ∈ {Red, Blue};

7

• for at least one of v’s active neighbor u 6∈ Γ(v0 ), the random proposal already
sampled as in Step 2a has cX (u) = cY (u) ∈ {Red, Blue}.
For all other active vertices v ∈ Γ(v0 ), the random proposals (cX (v), cY (v)) are coupled identically except with the roles of Red and Blue switched in the two chains.
With the random choices (AX , cX ) and (AY , cY ) coupled as above, the colorings (X ′ , Y ′ ) of the
next step are constructed following the rules of the ll-Metropolis chain described in Algorithm 1.
It is easy to verify this is a valid coupling of the ll-Metropolis chain, as in each individual
chain X or Y , each vertex v becomes active independently with probability p and proposes a
random color c(v) ∈ [q] uniformly and independently.
The following observations for the coupling can be verified by case analysis.
Observation 6. The followings hold for the coupling constructed above:
• For each vertex u 6= v0 that Xu = Yu ∈ {Red, Blue}, all its active neighbors w ∈ Γ(u) ∩ A
Y
sample (cX
w , cw ) consistently.
Y
• For each vertex u ∈ Γ(v0 ), cX
u = cu if and only if there exists a vertex w ∈ Γ(u), such that
X
Xw = Yw ∈ {Red, Blue} or cw = cYw ∈ {Red, Blue}.

Y
• For each vertex u 6= v0 , the event Xu′ 6= Yu′ occurs only if u ∈ A and {cX
u , cu } ⊆
{Red, Blue}.

The following lemma bounds the discrepancy at each vertex in (X ′ , Y ′ ).

Lemma 7. For vertex v0 at which the two colorings X, Y ∈ [q]V differ, it holds that

∆
3p
1−
.
q

(4)

p
.
q

(5)

Pr[X ′ (w) 6= Y ′ (w) | X, Y ] = 0.

(6)

p(q − ∆)
Pr[X (v0 ) = Y (v0 ) | X, Y ] ≥
q
′

′

For any vertex u ∈ Γ(v0 ), it holds that
Pr[X ′ (u) 6= Y ′ (u) | X, Y ] ≤
For any vertex w ∈ V \ Γ+ (v0 ), it holds that

Proof. The event X ′ (v0 ) = Y ′ (v0 ) occurs if following events occur simultaneously:
• Vertex v0 is active, which happens with probability p.

• cX (v0 ) 6∈ {X(u) | u ∈ Γ(v0 )} (hence cY (v0 ) 6∈ {Y (u) | u ∈ Γ(v0 )} due to cX (v0 ) = cY (v0 )
and X(u) = Y (u) for all u ∈ Γ(v0 )). Since v0 has at most ∆ neighbors, this event occurs
conditioning on the occurrence of the previous event.
with probability at least q−∆
q
• For every vertex u ∈ Γ(v0 ), either u is lazy in both chains or cX (u) 6∈ {Red, Blue, cX (v0 )}
(hence regardless of whether (cX (u), cY (u)) is coupled identically or with Red/Blue switched,
it must hold that cY (u) 6∈ {Red, Blue, cY (v0 )} by the coupling). Since each vertex becomes
lazy and proposes color independently and v0 has at most ∆ neighbors, this event occurs
∆
∆


= 1 − 3p
conditioning on the occurrences
with probability at least 1 − p + p q−3
q
q
of previous events.
Inequality (4) then follows by the chain rule.
For each u ∈ Γ(v0 ), by Observation 6, the event X ′ (u) 6= Y ′ (u) occurs only if u is active and
{cX (u), cY (u)} ⊆ {Red, Blue}. Vertex u becomes active with probability p. Assuming that u is
active, we prove inequality (5) by exhausting the two cases:

8

• Case 1: (cX (u), cY (u)) are coupled identically. Note that the event X ′ (u) 6= Y ′ (u)
occurs only if {cX (u), cY (u)} ⊆ {Red, Blue}. However, by the part two of Observation 6,
there must exist w ∈ Γ(u) such that X(w) = Y (w) ∈ {Red, Blue} or cX (w) = cY (w) ∈
{Red, Blue}. Without loss of generality, assume that X(w) = Y (w) = Red (other cases
follow by symmetry). If cX (u) = cY (u) = Red, then the edge {u, w} cannot pass its
check in either chain, which implies X ′ (u) = X(u) = Y (u) = Y ′ (u). Thus, the event
X ′ (u) 6= Y ′ (u) occurs with probability at most 1q conditioning on u being active.

• Case 2: (cX (u), cY (u)) are coupled with the roles of Red/Blue switched. Note that the
event X ′ (u) 6= Y ′ (u) occurs only if {cX (u), cY (u)} ⊆ {Red, Blue}. However, if cX (u) =
Red = X(v0 ) and cY (u) = Blue = Y (v0 ), then the edge {u, v0 } cannot pass its check
neither in chain X nor in chain Y , which implies X ′ (u) = X(u) = Y (u) = Y ′ (u). Thus,
the event X ′ (u) 6= Y ′ (u) occurs with probability at most q1 conditioning on u being active.
Combining the two cases we have the inequality (5).
Now we prove (6). If w is at distance 3 or more from v0 , then for all vertices u ∈ Γ+ (w), it
holds that X(u) = Y (u); and furthermore, for all vertices u ∈ Γ+ (w) ∩ A, it holds that cX (u) =
cY (u), which implies X ′ (w) = Y ′ (w). If w is at distance 2 from v0 , then by Observation 6, the
event X ′ (w) 6= Y ′ (w) occurs only if w is active and {cX (w), cY (w)} ⊆ {Red, Blue}. Note that
w must propose color identically in the two chains. If cX (w) = cY (w) ∈ {Red, Blue}, then by
the coupling all vertices u ∈ Γ+ (w) ∩ A must propose color identically in the two chains. Note
that for all vertices u ∈ Γ+ (w), it holds that X(u) = Y (u). Combining them together we have
X ′ (w) = Y ′ (w).
Proof of Theorem 5. Combining (4), (5) and (6) in Lemma 7 together and due to linearity of
expectation, we have
X
E [|X ′ ⊕ Y ′ | | X, Y ] =
Pr[X ′ (v) 6= Y ′ (v) | X, Y ]
v∈V

= Pr[X ′ (v0 ) 6= Y ′ (v0 ) | X, Y ] +

(q ≥ (2 + δ)∆)
(Assume p ≤ 1/2)

X

u∈Γ(v0 )

Pr[X ′ (u) 6= Y ′ (u) | X, Y ]


∆
3p
p∆
p(q − ∆)
1−
+
≤1−
q
q
q
!

∆
1+δ
3p
1
≤1−p
1−
−
2+δ
(2 + δ)∆
2+δ




1+δ
3p
1
≤1−p
1−
−
.
2+δ
2+δ
2+δ

The last inequality is due to Bernoulli’s inequality (1 + x)r ≥ 1 + rx for r ≥ 1 and x ≥ −1. For
p = min{ 3δ , 21 }, it holds that
(
δ2
if δ ≤ 32 ,
1 − 3(2+δ)
2
′
′
E [|X ⊕ Y | | X, Y ] ≤
2
2δ −δ
1 − 4(2+δ)
if δ > 32 .
2
The Hamming distance between two colorings
is at most n. By the path coupling lemma 3, the

mixing rate is τ (ǫ) = O log n + log 1ǫ , where the constant in O(·) depends only on δ.

5

Local Uniformity for Parallel Chain

In this section, we establish the so-called local uniformity property for the ll-Metropolis chain,
with which we can prove Theorem 2 i.e. the mixing condition with few colors in graphs with
large girth and large maximum degree.

9

To properly state this property for colorings, we need to define the notion of available colors.
Definition 8. Let G = (V, E) be a graph, and X ∈ [q]V an arbitrary coloring, not necessarily
proper. For any vertex v ∈ V , the set of available colors at v under coloring X is defined as
A(X, v) = [q] \ X(Γ(v)),

(7)

where X(Γ(v)) = {Xu | u ∈ Γ(v)} is the set of colors used by v’s neighbors in the coloring X.
Inequality (4) of the worst-case path coupling in last section can be generalized to:

∆
3p
p · |A(X, v0 )|
1−
,
Pr[X ′ (v0 ) = Y ′ (v0 ) | X, Y ] ≥
q
q
where the inequality (4) is actually obtained by applying this general inequality with the naive
bound |A(X, v0 )| ≥ q − ∆ for the worst case colorings X, Y .
When the current coloring X is produced by a Markov chain, especially after running for
a while, it is conceivable that the number of available colors |A(X, v)| at each vertex v with
high probability is much bigger than this worst case lower bound, and is closer to that in a
uniform random coloring, which is ≈ qe− deg(v)/q . This is guaranteed by the local uniformity
properties established for the respective chains. More precisely, the local uniformity properties
are a number of “local” properties of graph coloring which holds with high probability for a
uniformly random coloring [26]. Here in particular, what we need is the lower bound on the
number of available colors. The following theorem states a local uniformity for the ll-Metropolis
chain on graphs with girth at least 9 and sufficiently large maximum degree.
1
Theorem 9 (ll-Metropolis local uniformity). For all δ > 0, 0 < ζ < 10
, 0 < p < 21 , there exists
∆0 = ∆0 (p, δ, ζ), C = C(δ, ζ), such that for all graphs G = (V, E) with maximum degree ∆ ≥ ∆0
and girth at least 9, all q ≥ (1 + δ)∆, the following holds. Let (Xt )t≥0 be the ll-Metropolis chain
with activeness p for q-colorings on graph G. For any v ∈ V ,


|A(Xt , v)|
≥ (1 − 10ζ)e− deg(v)/q ≥ 1 − exp(−∆/C),
Pr ∀t ∈ [t0 , t∞ ] :
q

2
where t0 = p1 1+δ
ln ζ1 and t∞ = exp(∆/C).
δ

This is the first local uniformity result proved for a parallel chain. In fact, to the best
of our knowledge, all previous local uniformity results were established for Glauber dynamics.
Compared to typical local uniformity results [26, 14], the parallel chain acquires the local uniformity much faster: after O(1) steps instead of O(n) steps, and a t∞ = exp(∆/C) (instead of
n exp(∆/C)) is sufficient for applying the local uniformity in proving the mixing rate. Meanwhile, we need a bigger girth (≥ 9) to deal with the local dependencies between adjacent vertices
in the parallel chain.
The rest of this section is dedicated to the proof of this theorem.

5.1

The ll-Metropolis chain on a modified graph G∗

In order to prove the local uniformity property in Theorem 9, we construct a modified graph
G∗ and define a ll-Metropolis chain on the modified graph G∗ . We will show a local uniformity
property for this process on G∗ . Then Theorem 9 can be proved by comparing the original
ll-Metropolis chain on G with this modified process on G∗ .
Consider an undirected graph G = (V, E) with girth at least 9. Fix any vertex v ∈ V . The
graph G∗ is a mixed graph, meaning that it has both directed and undirected edges. The mixed
graph G∗ is obtained by replacing all the undirected edges within the ball of radius 4 centered
at v with directed edges towards v. Since the girth of G is at least 9, each directed edge has a
unique direction. The remaining edges in graph G are preserved and kept undirected in G∗ .

10

Definition 10. Let r ≥ 1 and G = (V, E) an undirected graph with girth at least 2r + 1. Fix
any vertex v ∈ V . Let Gin (v, r) denote the mixed graph G∗ = (V, E ∗ , F ∗ ) with vertex set V ,
undirected edge set E ∗ , and directed edge set F ∗ , where
• E ∗ = {{u, w} ∈ E | distG (v, u) > r ∨ distG (v, w) > r ∨ distG (v, u) = distG (v, w) = r},

• F ∗ = {(u, w) | {u, w} ∈ E ∧ distG (v, w) < distG (v, u) ≤ r}.

In particular, let G = (V, E) be an undirected graph with girth at least 9. Fix an arbitrary
v ∈ V . We define G∗ = Gin (v, 4).
For any vertex u in graph G∗ , we define

Γun (u) , {w | {u, w} ∈ E ∗ },
Γin (u) , {w | (w, u) ∈ F ∗ },

Γout (u) , {w | (u, w) ∈ F ∗ }.
We have Γ(u) = Γun (u) ∪ Γin (u) ∪ Γout (u) for the set of neighbors Γ(u) of u in G∗ (and also in
G).
The ll-Metropolis chain (Xt∗ )t≥0 on q-colorings of graph G∗ = Gin (v, 4) is defined as follows.
∗
Initially, X0∗ ∈ [q]V is arbitrary. Given the current coloring Xt∗ ∈ [q]V , the Xt+1
is obtained as:
• Each vertex u ∈ V becomes active independently with probability p, otherwise it becomes
lazy. Let A∗ ⊆ V denote the set of active vertices.

• Each active vertex u ∈ A∗ independently proposes a color c∗ (u) ∈ [q] uniformly at random.
• For each vertex u ∈ A∗ , for each w ∈ Γ(u), we say
initiated at u if and only if
 ∗
c (u) 6= c∗ (w) ∧ c∗ (u) 6= Xt∗ (w) ∧ Xt∗ (u) 6= c∗ (w)



c∗ (u) 6= X ∗ (w)
t
∗
∗

c
(u)
=
6
c
(w) ∧ Xt∗ (u) 6= c∗ (w)



always pass check

that the pair (u, w) passes the check

if
if
if
if

w
w
w
w

∈ A∗
6∈ A∗
∈ A∗
6∈ A∗

and
and
and
and

w ∈ Γun (u) ∪ Γin (u),
w ∈ Γun (u) ∪ Γin (u),
w ∈ Γout (u),
w ∈ Γout (u).

• Let R∗ ⊆ A∗ denote the subset of active vertices u such that ∀w ∈ Γ(u), the pair (u, w)
passed the check initiated at u. The coloring Xt+1 ∈ [q]V at time t + 1 is constructed as
(
c∗ (u)
if u ∈ R∗ ,
∗
Xt+1
(u) =
Xt∗ (u) if u 6∈ R∗ .

Note that the original ll-Metropolis chain in Algorithm 1 can be seen as a special case of the
above process when Γ(u) = Γun (u) and Γin (u) = Γout (u) = ∅ for every vertex u ∈ V .
The only differences between this new Markov chain (Xt∗ )t≥0 on G∗ and the original llMetropolis chain (Xt )t≥0 on graph G are the trimmed local Metropolis filters on outgoing
directed edges. Consider a directed edge (u, w) in graph G∗ . Vertex u updates its color oblivious
to the current color of vertex w. This makes the ll-Metropolis chain on graph G∗ not reversible,
and may move from proper colorings to improper ones. Nevertheless, this ll-Metropolis chain on
graph G∗ has two nice features. First, the random colors assigned to u ∈ Γ(v) are conditional
independent, which helps establishing the local uniformity property (proved in Section 5.2).
Second, there is a coupling between this new process and the original ll-Metropolis chain on G
that preserves the local uniformity (proved in Section 5.3).

11

5.2

Local uniformity for the ll-Metropolis chain on G∗

We prove a local uniformity property for the ll-Metropolis chain on the modified graph G∗ ,
in terms of the lower bound on the number of available colors. For the mixed graph G∗ ,
we override the definition of the set of available colors A(X, u) in (7) by assuming Γ(u) =
Γun (u) ∪ Γin (u) ∪ Γout (u).
Lemma 11. For all δ, ℓ, ζ > 0, 0 < p < 1/2, there exists ∆1 = ∆1 (ℓ, p, δ, ζ), such that for all
graphs G = (V, E) with maximum degree ∆ ≥ ∆1 and girth at least 9, all q ≥ (1 + δ)∆, the
following holds. Fix any vertex v ∈ V and let G∗ = Gin (v, 4).
Let (Xt∗ )t≥0 be the ll-Metropolis chain with activeness p for q-colorings on graph G∗ .
#
"
deg(v)/(q−ℓ)

1−γ
∗
− ζq ≥ 1 − exp(−ζ 2 q/2),
Pr |A(Xℓ , v)| ≥ (q − ℓ)
e
where
γ = exp −p



δ
1+δ

2 !

2
1 1+δ
ℓ +
.
q
δ

To prove the lemma, we need Chernoff bounds of various forms.
Theorem 12 (Chernoff bound). Let X1 , X2 ,P
. . . , Xn ∈ {0, 1} be mutually independent or negn
atively associated random variables, let X = i=1 Xi and µ = E [X]. For any δ > 0, it holds
that
(1+δ)µ
µ 

e
eδ
.
(8)
≤
Pr[X ≥ (1 + δ)µ] ≤
1+δ
(1 + δ)(1+δ)
In particular, if k ≥ e2 µ, then
Pr[X ≥ k] ≤ exp(−k).

(9)



2t2
.
Pr[X ≤ µ − t] ≤ exp −
n

(10)

Let t > 0, it holds that

We also need the following technical lemma due to Dyer and Frieze [11], and refined by
Hayes [26] for proving the local uniformity property for Glauber Dynamics. We use a slightly
modified version here, which says that for a sequence of independent random colors, if there
exists a subset of colors, in which no color is very likely to be sampled in any step, then with
high probability, there are many missed colors. The proof is very similar to the ones in [11]
and [26], which we include here for completeness.
Lemma 13 (Dyer and Frieze). Let q, s be positive integers, and let c1 , . . . , cs be independent
(but not necessarily identically distributed) random variables taking values in [q]. Let S ⊆ [q]
with size |S| = m. Suppose that there is a γ < 1 such that Pr[ci = j] ≤ γ for every 1 ≤ i ≤ s
and j ∈ S. Let A = [q] \ {c1 . . . , cs } be the set of missed colors. Then
s/mγ

E [|A|] ≥ m(1 − γ)

and for every a > 0, Pr [|A| ≤ E [|A|] − a] ≤ e−a

2

12

≥m

/2q

.



1−γ
e

s/m

,

Proof. For each 1 ≤ i ≤ s and 1 ≤ j ≤ q, let random variable ηij indicate the event ci = j, thus
|A| =

q Y
s
X

j=1 i=1

(1 − ηij ).

By the linearity of expectation and the independence of the colors ci , we have
E [|A|] =
(0 ≤ ηij ≤ 1)

≥

q Y
s
X

j=1 i=1
s
XY

(1 − E [ηij ])

j∈S i=1
s Y
Y

≥m

(AM-GM inequality)

(1 − E [ηij ])

i=1 j∈S

1

(1 − E [ηij ]) m .

Pq
P
[ηij ] ≤ j=1 E [ηij ] = 1 and for all j ∈ S,
Note that for each 1 ≤ i ≤ s, it holds that j∈S EP
0 ≤ E [ηij ] ≤ γ. For each 1 ≤ i ≤ s, suppose that j∈S E [ηij ] = βi ≤ 1, the minimum of the
Q
j∈S (1 − E [ηij ]) is achieved when as many as possible of E [ηij ] equal γ, hence
Y

j∈S

(1 − E [ηij ]) ≥ (1 − γ)⌊βi /γ⌋ (1 − (βi − γ⌊βi /γ⌋))

(r = βi /γ − ⌊βi /γ⌋ < 1)
(∗)
(βi ≤ 1)

=

(1 − γ)βi /γ
(1 − γr)
(1 − γ)r

≥ (1 − γ)βi /γ

≥ (1 − γ)1/γ ,

where (∗) is due to Bernoulli’s inequality (1 + x)t ≤ 1 + xt when 0 ≤ t ≤ 1 and x ≥ −1. Thus
E [|A|] ≥ m(1 − γ)s/mγ ≥ m



1−γ
e

s/m

.

Pq
For each 1 ≤ i ≤ s, since j=1 ηij = 1, the random 0-1 variables ηi1 , ηi2 , . . . , ηiq are negatively associated. Since the color choices are mutually independent, then all ηij are negatively
associated. Because decreasing functions of disjoint subsets of a family
Q of negatively associated
variables are also negatively associated [7], the q random variables { si=1 (1 − ηij )}(1≤j≤q) are
negatively associated. Then by the Chernoff bound for negatively associated variables (10), for
2
every a > 0 it holds that Pr[|A| ≤ E [|A|] − a] ≤ e−a /2q .
Proof of Lemma 11. Recall that Br (v) ⊆ V and Sr (v) ⊆ V denote the r-ball and r-sphere
centered at vertex v in graph G, which contains the same set of vertices as the r-ball in G∗ .
And we use notation Γ+ (v) denote Γ(v) ∪ {v}.
Let F denote the random choices for the laziness and proposed colors of all vertices in
(V \ B2 (v)) ∪ {v} during the time interval [1, ℓ] in the chain (Xt∗ )t≥0 . Note that given any F ,
the followings hold.
• For all vertices in V \ B3 (v), the whole procedure of ll-Metropolis on graph G∗ during
the time interval [0, ℓ] is fully determined. Because the procedure outside the ball B3 (v)
requires no information in B3 (v) except the laziness and the random proposed colors of
vertices in S3 (v), which are given by condition F .

• The laziness and random proposed colors of vertex v are given by condition F .

13

• The subgraph reduced by B3 (v) is a tree because the girth of graph is at least 9.

Hence, given the condition F , for each vertex u ∈ Γ(v), the random color Xℓ∗ (u) only depends on
the random choices of laziness and proposed colors of vertices w ∈ Γ+ (u)\{v} during [1, ℓ]. Since
the laziness and proposed colors are fully independent, then given condition F , the neighbor
colors Xℓ∗ (u) for u ∈ Γ(v) are conditionally fully independent.
Next, we describe the conditional distribution of Xℓ∗ (u) given F , where u is a neighbor of
v. Let SF be the set of colors proposed by vertex v during the time interval [1, ℓ], which is
uniquely determined by the condition F . For each color c ∈ [q] \ SF , we bound the probability
of the event Xℓ∗ (u) = c. We say vertex u successfully updates its color at step t if and only if u
accepts its proposed color at step t. The event Xℓ∗ (u) = c occurs only if one of following two
events occurs.
• Vertex u never successfully updates its color in time interval [1, ℓ] and X0∗ (u) = c. Then,
in each step t, Xt∗ (u) = c. Note that c 6∈ SF , which implies the color proposed by v cannot
coincide with color c. Thus, the event that u successfully updates its color at step t occurs
if following three events occur simultaneously :
1. vertex u is not lazy at step t, which occurs with probability p;
∗
2. vertex u proposes a color σ such that σ 6∈ Xt−1
(Γ(w) \ {v}) and σ does not coincide
with the color proposed by v if v is not lazy at step t, which occurs with probability
at least (q − ∆)/q condition on previous event;
∗
3. each vertex w ∈ Γ(u) \ {v} either becomes lazy or does not propose Xt−1
(u) = c or
∆
σ, which occurs with probability at least (1 − 2p/q) condition on previous events;

Thus, the probability that u successfully updates its color at each step t is at least

∆

∆
2p
2p
pδ
1−
1−
≥
q
1+δ
(1 + δ)∆


pδ
2p
(∗)
≥
1−
1+δ
(1 + δ)
2

δ
,
(p < 1/2)
≥p
1+δ

p(q − ∆)
q

where (∗) is because Bernoulli’s inequality (1 + x)r ≥ 1 + rx for r ≥ 1 and x ≥ −1. Hence,
the probability of the event that X0∗ (u) = c and u never successfully updates its color in

 

2 ℓ
2 
δ
δ
the time interval [1, ℓ] is at most 1 − p 1+δ
≤ exp −p 1+δ
ℓ .

• Vertex u successfully updates its color in the time interval [1, ℓ], and at the last time when
u successfully updates its color, u updates it into color c. For each 1 ≤ i ≤ ℓ, let Ui be the
event that vertex u successfully updates its color intoSc at time i and u never makes any
successful update during [i + 1, ℓ]. Then this event is 1≤i≤ℓ Ui . The event Ui occurs only
if vertex u is not lazy and proposes color c at step t and u never successfully updates its
color during [i + 1, ℓ]. The event Ui implies Xt (u) = c for all i + 1 ≤ t ≤ ℓ, thus we have
p
Pr [Ui | F ] ≤
q

1−p



δ
1+δ

2 !ℓ−i

.

Take a union bound over all 1 ≤ i ≤ ℓ, we have



2 !ℓ−i

2
ℓ
X
[
δ
1 1+δ
p


1−p
≤
.
Pr
Ui | F ≤
q i=1
1+δ
q
δ
1≤i≤1

14

Combine two cases together and use the union bound, we have
2 !

2

1 1+δ
δ
∗
ℓ +
.
Pr[Xℓ (u) = c | F ] ≤ exp −p
1+δ
q
δ
Recall that the above probability bound holds for all color c ∈ [q]\SF 
. Note that |[q]\ SF | ≥ q−ℓ

2
2
δ
because the size of SF is at most ℓ. Apply Lemma 13 with γ = exp −p 1+δ
ℓ + q1 1+δ
,
δ
a = ζq, m = q − ℓ and s = deg(v). Note that if we take ∆ >

1+δ
δ 2 (1−exp(−pδ 2 ℓ/(1+δ)2 )) ,

then γ < 1;

ℓ
1+δ ,

then m > 0. Thus, for ∆ sufficiently large, we have
#
"
deg(v)/(q−ℓ)

1−γ
∗
Pr |A(Xℓ , v)| ≤ (q − ℓ)
− ζq | F ≤ exp(−ζ 2 q/2).
e

if we take ∆ >

Finally, by the law of total probability, summing over all conditions F yields
"
#

deg(v)/(q−ℓ)
1−γ
∗
Pr |A(Xℓ , v)| ≤ (q − ℓ)
− ζq ≤ exp(−ζ 2 q/2).
e

5.3

Comparison of the ll-Metropolis chains

Next, we show that there is a coupling between the ll-Metropolis chains respectively on G and
G∗ that preserves the local uniformity.
Lemma 14. For all C, δ, ζ > 0, 0 < p < 1, there exists ∆2 = ∆2 (C, p, δ, ζ), such that for
all graphs G = (V, E) with maximum degree ∆ ≥ ∆2 and girth at least 9, all q ≥ (1 + δ)∆,
the following holds. Fix any vertex v ∈ V and let G∗ = Gin (v, 4). Let (Xt )t≥0 and (Xt∗ )t≥0
be the ll-Metropolis chains with activeness p for q-colorings on G and G∗ respectively, where
X0 = X0∗ ∈ [q]V . There exists a coupling (Xt , Xt∗ )t≥0 of the processes (Xt )t≥0 and (Xt∗ )t≥0 such
that
Pr [∀t ≤ C, ∀u ∈ V : |(Xt ⊕ Xt∗ ) ∩ Γ(u)| ≤ ζ∆] ≥ 1 − exp(−∆).
Proof. Define the identical coupling (Xt , Xt∗ ) as follows: In each step, two chains sample the
same active vertex set A = A∗ andSall active vertices propose the same random colors c = c∗ .
Let random variable D≤t = t′ ≤t (Xt′ ⊕ Xt∗′ ) denote the set of all disagreeing vertices
appeared before time t. We prove the Lemma by showing that with probability at least
1 − exp(−∆), for all u ∈ V , it holds that |D≤C ∩ Γ(u)| ≤ ζ∆.
Let R = C + 6. The bad events B1 and B2 defined as follows:
B1 : D≤C 6⊆ BR−3 (v);

B2 : |D≤C | ≥ ∆13/4 .

we then show that B1 can never occur and B2 occurs with very small probability.
We begin by showing that disagreements cannot percolate outside the ball BR−3 (v), i.e.:
Pr[B1 ] = 0.

(11)

Consider any vertex u ∈
/ B4 (v). Since no directed edge is incident to u in graph G∗ , then
the updating rule for vertex u is identical in two chains. Vertex u becomes a new disagreeing
∗
(w). Since
vertex at step t only if there exists a vertex w ∈ Γ(u), such that Xt−1 (w) 6= Xt−1

15

X0 = X0∗ , then it must hold that D≤1 ⊆ B4 (v). Furthermore, for all t ≥ 1, it must hold that
D≤t ⊆ Bt+3 (v). In particular, D≤C ⊆ BC+3 (v), which implies (11).
To bound the probability of bad event B2 , consider the random variable
∗
N (Dt ) = |(Xt ⊕ Xt∗ ) \ (Xt−1 ⊕ Xt−1
)|,

which gives the number of new disagreements contributed at time t. Any u with Xt−1 (u) =
∗
Xt−1
(u) but becomes a disagreement at time t only if it is incident to following two types of bad
edges:
• Type-1 bad edge: An undirected edge {u, w} ∈ E ∗ or a directed edge (w, u) ∈ F ∗ such
∗
that Xt−1 (w) 6= Xt−1
(w). For such bad edges, u becomes a new disagreement only if u is
∗
active at time t and proposes Xt−1 (w) or Xt−1
(w).
• Type-2 bad edge: A directed edge (u, w) ∈ F ∗ . For such bad edges, u becomes a new
disagreement only if u is active at time t and proposes Xt−1 (w). In this case, the pair
(u, w) may pass the check initiated at vertex u in chain X ∗ but the undirected edge {u, w}
can not pass the check in chain X.
Suppose vertex u is incident to k bad edges, then the probability that u becomes a new disagreement is at most 2kp/q. Since the maximum degree is at most ∆ and |F ∗ | ≤ ∆4 , then the
total number of bad edges is at most ∆|D≤t−1 | + ∆4 . Hence, we have
E [N (Dt ) | D≤t−1 ] ≤

2p(|D≤t−1 | + ∆3 )
2p(∆|D≤t−1 | + ∆4 )
≤
.
q
1+δ

Furthermore, the laziness and proposed colors are mutually independent, which implies N (Dt )
is stochastically dominated by the sum of independent random 0-1 variables. Then by the
Chernoff bound (9), together with |D≤t | ≤ |D≤t−1 | + N (Dt ) we have




20p(|D≤t−1 | + ∆3 )
20p(|D≤t−1 | + ∆3 )
| D≤t−1 ≤ Pr N (Dt ) ≥
| D≤t−1
Pr |D≤t | ≥ |D≤t−1 | +
1+δ
1+δ


20p(|D≤t−1| + ∆3 )
(Chernoff bound)
≤ exp −
1+δ
(∗)

≤ exp(−∆2 ),

20p(|D

|+∆3 )

≤t−1
where (∗) is because if we take ∆ ≥ 1+δ
20p , then
1+δ
probability at least 1 − C exp(−∆2 ), it holds that
(
|D≤t | ≤ |D≤t−1 | + 20p(|D≤t−1 | + ∆3 )/(1 + δ)
|D0 | = 0

Solving above recurrence, we have
"

3

Pr ∀1 ≤ t ≤ C : |D≤t | ≤ ∆

If we take ∆ >



20p
1+δ

+1

C

−1

4



20p
+1
1+δ

t

3

−∆

#

≥

20p∆3
1+δ

≥ ∆2 . Hence, with

∀1 ≤ t ≤ C

.

≥ 1 − C exp(−∆2 ).

, then it holds that ∆13/4 > ∆3



20p
1+δ

+1

C

− ∆3 . Thus

#
"

C
i
h
20p
+1
Pr[B2 ] = Pr |D≤C | ≥ ∆13/4 ≤ Pr |D≤C | ≥ ∆3
− ∆3 ≤ C exp(−∆2 ).
1+δ
Finally, we define four more bad events C1 , C2 , C3 , C4 as follows

16

(12)

• C4 : ∃u ∈ V : |D≤C ∩ B4 (u)| ≥ ∆13/4 = ∆3+1/4 .

T
C
∩ {∃u ∈ V : |D≤C ∩ Bk (u)| ≥ ∆k−1+1/k }.
• For k ∈ {2, 3}, define Ck =
j
k<j≤4

T
• C1 :
1<j≤4 Cj ∩ {∃u ∈ V : |D≤C ∩ Γ(u)| ≥ ζ∆}.

If none of bad events C1 , C2 , C3 , C4 occurs, then for all u ∈ V : |D≤C ∩ Γ(u)| < ζ∆. Thus we
prove the Lemma by bounding the probability of bad events C1 , C2 , C3 , C4 .
Note that the bad event C4 implies the bad event B2 , thus by (12) we have
Pr[C4 ] ≤ Pr[B2 ] ≤ C exp(−∆2 ).

(13)

For k = 1, 2, 3 we show that the bad event Ck occurs with low probability. Assuming that none
of events Cj with j > k occurs, otherwise the bad event Ck can not occur. Fix a vertex u ∈ V ,
let random variable Z = |D≤C ∩ Bk (u)| count the number of disagreements formed in Bk (u)
∗
during time interval [0, C]. Let random variable Zt = | (Xt ⊕ Xt∗ ) \ (Xt−1 ⊕ Xt−1
) ∩ Bk (u)|
count the number of new disagreements in Bk (u) generated at step t. Since X0 = X0∗ , then
PC
Z ≤ t=1 Zt . By (11), any disagreements can not percolate outside the ball BR−3 (v) which
implies Z = 0 if u 6∈ BR (v). Assuming u ∈ BR (v), let us bound the expected value of each Zt .
∗
As is stated in previous proof, a vertex w ∈ Bk (u) satisfies Xt−1 (w) = Xt−1
(w) but becomes
a disagreement at step t only if vertex w is incident to bad edges, vertex w is active at step t
and vertex w proposes specific colors (which are determined by bad edges). We bound the total
number of two types of bad edges incident to vertices in Bk (u) at step t as follows:
• Type-1 bad edges within Bk (u): There are at most ∆k edges with both endpoints in Bk (u).
Each of these edges should be counted as a bad edge at most once, because we only consider
the type of bad edges that join an existing disagreement to a vertex w ∈ Bk (u) such that
∗
Xt−1
(w) = Xt−1 (w).
• Type-1 bad edges at the boundary of Bk (u): Since none of bad events Cj with j > k
occurs, then there are at most ∆k+1/(k+1) disagreements in Bk+1 (u) \ Bk (u). Each of
disagreements has at most one neighbor in Bk (u) because the girth is at least 9. There
are at most ∆k+1+1/k such bad edges in total.
∗
• Type-2 bad edges: For each vertex w ∈ Bk (u) such that Xt−1
(w) = Xt−1 (w) , the event
that w becomes a new disagreement at step t may be caused by a directed edge (w, w′ ) in
graph G∗ . By the definition of graph G∗ , there is at most one such edge incident to each
vertex w. Hence, the total number of such edges is at most ∆k .

Thus, the expected value of random variable Zt is upper bounded by
E [Zt ] ≤


2p 2∆k−1 + ∆k−1+1/(k+1)
2p(2∆k + ∆k+1/(k+1) )
≤
.
q
1+δ

Further, the laziness and proposed colors are fully independent, which implies Zt is stochastically
dominated by the sum of independent random 0-1 variables. For k ∈ {2, 3}, if we take large ∆
1/(k+1)

)
such that ∆1/k ≥ 20Cp(2+∆
, then ∆k−1+1/k /C ≥ 10E [Zt ]. Thus by Chernoff bound (9),
1+δ
we have




i
h
∆k−1+1/k
∆k−1+1/k
≤ C exp −
≤ exp(−∆ log ∆).
Pr Z ≥ ∆k−1+1/k ≤ Pr ∃t : Zt ≥
C
C

The last equality holds when ∆ is sufficiently large such that ∆3/2 ≥ C ln C + C∆ log ∆. For
k = 1, we use Chernoff bound (8), then


ζ∆/C
2Cep(2 + ∆1/2 )
ζ∆
≤C
= exp (−Ω(∆ log ∆)) ,
Pr [Z ≥ ζ∆] ≤ Pr ∃t : Zt ≥
C
ζ(1 + δ)∆


17

where the constant factor in Ω(·) depends only on C, p, δ, ζ. For k = 1, 2, 3, take a union bound
over the ∆R = ∆C+6 vertices u ∈ BR (v), then
Pr[Ck ] = ∆C+6 exp(−Ω (∆ log ∆)) = exp(−Ω (∆ log ∆)),

k = 1, 2, 3 :

(14)

where the constant factor in nation Ω(·) depends only on C, p, δ, ζ. Summing the bounds in
inequalities (13) and (14) completes the proof.

5.4

Proof of local uniformity (Theorem 9)

Finally, the local uniformity property for the ll-Metropolis chain on graph G can be proved by
combining Lemma 11 and Lemma 14.
2 1
ln ζ . Remark that ℓ is determined by p, δ, ζ. Consider any time T ∈ [t0 , t∞ ],
Let ℓ = p1 1+δ
δ
where t0 = ℓ and t∞ = exp(∆/C). Fix any coloring XT −ℓ at time (T − ℓ), we apply the identical
coupling (Xt , Xt∗ ) for T − ℓ ≤ t ≤ T from the same initial coloring XT −ℓ = XT∗ −ℓ , where X ∗ is
given by the ll-Metropolis chain on graph G∗ = Gin (v, 4). Note that, during the coupling, the
ll-Metropolis on graph G∗ starts from the coloring XT −ℓ and runs for ℓ steps. By Lemma
11, if

∆ ≥ ∆1 (ℓ, p, δ, ζ) = ∆1 (p, ζ, δ), then with probability at least 1 − exp −ζ 2 (1 + δ)∆/2 , we have


|A(XT∗ , v)| > (q − ℓ)
 
2 
δ
where γ = exp −p 1+δ
ℓ +

1
q


1+δ 2
.
δ

1−γ
e

deg(v)/(q−ℓ)

− ζq,

(15)

By the definition of ℓ, if we take ∆ ≥

1+δ
ζδ 2 ,

then

ζ ≤ γ ≤ 2ζ. Note that γ < 1 because ζ < 1/10. Furthermore, it holds that
∆>

q−ℓ
2ℓ
=⇒
≥ 1 − ζ/2.
(δ + 1)ζ
q

(16)

It can be verified that there exists ∆′ = ∆′ (δ, ζ, p) such that if ∆ ≥ ∆′ , it holds that
deg(v)
 deg(v)
q−ℓ −
q

ℓ

1 − 2ζ (1+δ)(q−ℓ)
≥ 1 − ζ/2.
e
n
o
′
Combining (16), (17) together, if ∆ ≥ max 1+δ
ζδ 2 , ∆ , then it holds that



1−γ
e

(q − ℓ)



1−γ
e

≥



deg(v)/(q−ℓ)

≥ (1 − ζ/2)2 q



1−γ
e

deg(v)/q

(17)

.

(18)

Combining (15) and (18) implies
|A(XT∗ , v)|
> (1 − ζ/2)2
q
(deg(v) < q)
(γ < 2ζ)



1−γ
e

deg(v)/q

−ζ

≥ (1 − ζ)(1 − γ)e− deg(v)/q − ζ

≥ (1 − 3ζ)e− deg(v)/q − ζ.

(19)

Two chains are coupled for ℓ steps. Note that ℓ is determined by p, δ, ζ. By Lemma 14, if
∆ ≥ ∆2 (ℓ, p, δ, ζ) = ∆2 (p, δ, ζ), then with probability at least 1 − exp(−∆), it holds that
|A(XT , v)| ≥ |A(XT∗ , v)| − ζ∆.

18


Thus, condition on any coloring XT −ℓ , with probability at least 1 − exp −ζ 2 (1 + δ)∆/2 −
exp(−∆), it holds that
|A(XT∗ , v)| ζ∆
|A(XT , v)|
≥
−
q
q
q
(By (19) and q > ∆)
(q > deg(v))

≥ (1 − 3ζ)e− deg(v)/q − 2ζ
≥ (1 − 10ζ)e− deg(v)/q .

By the law of total probability, summing over all possible coloring XT −ℓ implies



|A(XT , v)|
Pr
≤ (1 − 10ζ)e− deg(v)/q ≤ exp −ζ 2 (1 + δ)∆/2 + exp(−∆)
q

′
C = 2/ min{ζ 2 (1 + δ)/2, 1}
≤ 2 exp(−2∆/C ′ )
(∆ ≥ C ′ ln 2)

≤ exp(−∆/C ′ ).

Finally, let C = 2C ′ . The theorem is proved by taking a union bound over all the steps
2 1
ln ζ and t∞ = exp(∆/C).
T ∈ [t0 , t∞ ], where t0 = ℓ = p1 1+δ
δ

6

Coupling with Local Uniformity

In this section, we use local uniformity property to avoid the worst case analysis in (4) and
obtain a better mixing condition for graphs with girth at least 9 and maximum degree is greater
than a sufficiently large constant.
We define the constant α∗ ≈ 1.763 to be the positive solution of
∗

α∗ = e1/α .
We consider q-colorings of graphs G with maximum degree ∆, where q ≥ (α∗ + δ)∆ for an
arbitrary constant δ > 0. Without loss of generality we assume δ < 0.3 because bigger δ is
already covered by Theorem 5 on general graphs.
Theorem 15. For all 0 < δ < 0.3, there exists ∆3 = ∆3 (δ), C ′ = C ′ (δ), such that for every
graph G on n vertices with maximum degree ∆ ≥ ∆3 and girth ≥ 9, if q ≥ (α∗ + δ)∆, then the
δ
mixing rate of the ll-Metropolis chain with activeness p = 30
on q-colorings of graph G satisfies
τ (ǫ) ≤ C ′ log

n
.
ǫ

Given the local uniformity property guaranteed by Theorem 9, the mixing rate in above
theorem is proved by following a similar framework as in [8]. We modify the framework to make
it adaptive to the parallel chain, where the experiments carried on in a time scale of O(n) steps
in a sequential chain, are now in O(1) steps, and a disagreement may percolate to many vertices
in one step.
We begin with constructing a grand coupling of the ll-Metropolis as below.

6.1

Coupling of arbitrary pair of colorings

In Section 4, we give a local coupling (X, Y ) → (X ′ , Y ′ ) for X, Y that differ only at a single
vertex. Here, we use the path coupling to extend this coupling to a coupling of arbitrary pair
of colorings.

19

Let X, Y ∈ [q]V be an arbitrary pair of colorings, not necessarily proper. Suppose that X
and Y differ on precisely ℓ vertices v1 , v2 , . . . , vℓ . A sequence of colorings X = Z0 → Z1 →
. . . → Zℓ = Y is constructed as follows: for every 0 ≤ i ≤ ℓ,


X(v) = Y (v) if v 6∈ (X ⊕ Y ),
Zi (v) = X(v)
if v ∈ (X ⊕ Y ) ∧ v ∈ {vj | i < j ≤ ℓ},


Y (v)
if v ∈ (X ⊕ Y ) ∧ v ∈ {vj | 1 ≤ j ≤ i}.
Each coloring Zi is not necessarily proper, and Zi−1 ⊕ Zi = {vi }. A coupling (X, Y ) → (X ′ , Y ′ )
is then constructed by the path coupling:

• Sample a pair (X ′ , Z1′ ) of colorings according to the local coupling (X, Z1 ) → (X ′ , Z1′ )
defined in Section 4.
′
• For i = 2, 3, . . . , ℓ, conditioning on the sampled coloring Zi−1
, sample coloring Zi′ according
′
′
to the local coupling (Zi−1 , Zi ) → (Zi−1 , Zi ) defined in Section 4. Finally, let Y ′ = Zℓ′ .

Note that the local coupling in Section 4 is constructed by coupling active vertex set and random
proposed colors. Hence, a sequence of active vertex sets and random proposed colors (AZi , cZi )
for 0 ≤ i ≤ ℓ is constructed by the above process.
Observation 16. Let X, Y ∈ [q]V be two colorings, and X ⊕ Y the set of vertices on which X
and Y disagree. The followings hold for the coupling (X, Y ) → (X ′ , Y ′ ) defined above:
1. If distG (v, X ⊕ Y ) ≥ 2, then X ′ (v) = Y ′ (v).

2. If distG (v, X ⊕ Y ) = 1, then X ′ (v) 6= Y ′ (v) occurs only if vertex v is active and proposes
color cX (v) ∈ {X(u), Y (u) | u ∈ Γ(v) ∩ (X ⊕ Y )} in chain X.
Proof. By the local coupling defined in Section 4, two chains X and Y must select the same set
of active vertices. If vertex v ∈
/ X ⊕ Y is lazy in chain X, then it must be lazy in chain Y , which
implies that X ′ (v) = X(v) = Y (v) = Y ′ (v).
Assume that vertex v is active in chain X. We prove a stronger Claim which implies both
claims in the observation:
Claim. If v 6∈ (X ⊕ Y ) and cX (v) 6∈ {X(u), Y (u) | u ∈ Γ(v) ∩ (X ⊕ Y )}, then it must hold that
X(v) = Y (v) and cX (v) = cY (v).
Note that if distG (v, X ⊕ Y ) ≥ 2, then cX (v) 6∈ ∅ holds trivially. Thus it covers the first part
of the Observation. Suppose that |X ⊕ Y | = k, we prove it by induction on k.

• Base case k = 1. Suppose X ⊕ Y = {v1 }. If distG (v, X ⊕ Y ) ≥ 2, then by (6) in
Lemma 7, we have X ′ (v) = Y (v), and by construction of the coupling, it holds that
cX (v) = cY (v). If distG (v, X ⊕ Y ) = 1, then by Observation 6 , X ′ (v) 6= Y ′ (v) occurs only
if {cX (v), cY (v)} ⊆ {X(v1 ), Y (v1 )}. If cX (v) 6∈ {X(v1 ), Y (v1 )}, then X ′ (v) = Y ′ (v) and
cX (v) = cY (v) regardless of which distribution (cX (v), cY (v)) is sampled from.
• Suppose the Claim holds for all pairs of colorings that differ on no more than k vertices. For
any X, Y differ at k + 1 vertices, consider the coloring sequence X = Z0 ∼ . . . ∼ Zk+1 = Y .
Then (X ′ , Zk′ ) is sampled from the coupling (X, Zk ) → (X ′ , Zk′ ) and Y ′ is sampled from the
coupling (Zk , Y ) → (Zk′ , Y ′ ) condition on Zk′ . Note that v ∈
/ (X ⊕ Y ) implies v ∈
/ (X ⊕ Zk )
and v ∈
/ (Zk ⊕Y ). Since v 6∈ (X⊕Zk ) and cX (v) 6∈ {X(u), Zk (u) | u ∈ Γ(v)∩(X⊕Zk )}, then
by I.H., it must hold that X ′ (v) = Zk′ (v) and cX (v) = cZk (v). Further, since v 6∈ (Zk ⊕ Y )
and cZk (v) = cX (v) 6∈ {Zk (u), Y (u) | u ∈ Γ(v) ∩ (Zk ⊕ Y )}, then by I.H., it must hold that
Zk′ (v) = Y ′ (v) and cZk (v) = cY (v). Combine them together, we have X ′ (v) = Y ′ (v) and
cX (v) = cY (v).

20

We then consider the coupling (Xt , Yt ) = (Xt , Yt )t≥0 of two ll-Metropolis chains starting
from initial colorings (X0 , Y0 ), constructed by applying the coupled transition (X, Y ) → (X ′ , Y ′ )
defined above at each step.
The following corollary of Observation 16 says that if the initial colorings X0 , Y0 differ at
single vertex v, then disagreements can not percolate too fast in the coupled chains.
Corollary 17. Let v ∈ V and X0 , Y0 ∈ [q]V be two colorings that differ only at vertex v. For
the coupling (Xt , Yt ) of two ll-Metropolis chains, it holds that Xt ⊕ Yt ⊆ Bt (v) for all t ≥ 0.
The next corollary bounds the expectation and the deviation from expectation, for the
number of new disagreements generated at each step of the couple chains.
Corollary 18. Let (Xt , Yt ) be the coupling of two ll-Metropolis chains with activeness p on
q-colorings of graph G with maximum degree ∆. Let N (Dt ) = |(Xt ⊕ Yt ) \ (Xt−1 ⊕ Yt−1 )| be the
number of new disagreements generated at step t. Then it holds that
E [N (Dt ) | Xt−1 , Yt−1 ] ≤
Furthermore, for any ℓ ≥

20p∆|Xt−1 ⊕Yt−1 |
,
q

2p∆|Xt−1 ⊕ Yt−1 |
.
q

we have

Pr [N (Dt ) ≥ ℓ | Xt−1 , Yt−1 ] ≤ exp (−ℓ) .
Proof. Let ∂(Xt−1 ⊕ Yt−1 ) = {v ∈ V | v 6∈ (Xt−1 ⊕ Yt−1 ) ∧ Γ(v) ∩ (Xt−1 ⊕ Yt−1 ) 6= ∅}. From
Observation 16, vertex v becomes a new disagreement at step t only if v ∈ ∂(Xt−1 ⊕ Yt−1 ), v
is active and proposes the color cX (v) ∈ {Xt−1 (u), Yt−1 (u) | u ∈ Γ(v) ∩ (Xt−1 ⊕ Yt−1 )}. Hence,
the expected number of new disagreements is at most 2p∆|Xt−1 ⊕ Yt−1 |/q.
Furthermore, the laziness and proposed colors are fully independently. Thus, the number of
new disagreements is stochastically dominated by the sum of independent 0-1 random variables.
The second inequality holds by the Chernoff bound (9).

6.2

Analysis of the coupling

Next, we show that starting from any two colorings that differ at a single vertex v, after constant
many steps of coupling, the Hamming distance contracts with a constant factor in expectation.
Lemma 19. For all 0 < δ < 0.3, there exists ∆4 = ∆4 (δ), such that for every graph G = (V, E)
with maximum degree ∆ ≥ ∆4 and girth at least 9, if q ≥ (α∗ + δ)∆, then for any vertex v ∈ V ,
any initial colorings X0 , Y0 ∈ [q]V that differ only at v, the coupling (Xt , Yt ) of two ll-Metropolis
δ
on q-colorings of graph G satisfies
chains with activeness p = 30
E [XTm ⊕ YTm ] ≤ 1/3,
where Tm =

1200
δ2

ln 600
δ = Θ(1).

The main theorem regarding the mixing rate (Theorem 15) is then an easy consequence
of this lemma. Let ∆3 (δ) = ∆4 (δ), where ∆4 is the threshold in Lemma 19. For arbitrary
two colorings differ at a single vertex, there exists a coupling such that the expected Hamming
600
distance between them is at most 1/3 after C ′′ = 1200
δ 2 ln δ = Θ(1) steps. Since the Hamming
distance between any two colorings is at most n, by the path coupling lemma, we have
τ (ǫ) ≤

n
3C ′′
log .
2
ǫ

The rest of the section is dedicated to the proof of Lemma 19.

21

We use the technique developed in [8] to prove Lemma 19, which partitions the time interval
[0, Tm ] into to two disjoint phases [0, Tb ] and [Tb + 1, Tm ], the first phase is called the burnin phase. After the burn-in phase, typically, the Hamming distance between two chains are
bounded, all disagreements are near vertex v, and the local uniformity properties is guaranteed.
Then we can prove that the expected Hamming distance will decrease in each step during
[Tb + 1, Tm ]. A crude upper bound is applied on the Hamming distance if non-typical events
occur.
Proof of Lemma 19. For two colorings Xt , Yt , define their difference as
Dt = {u | Xt (u) 6= Yt (u)}.
Let Ht = |Dt | denote their Hamming distance. Also, denote their cumulative difference by
[
D≤t =
Dt ,
t′ ≤t

and denote their cumulative Hamming distance as H≤t = |D≤t |.
Let δ ′ , p′ , ζ ′ and C ′ = C ′ (δ ′ , ζ ′ ) denote the parameters δ, p, ζ and C = C(δ, ζ) in Theorem 9,
δ
respectively. We apply Theorem 9 with p′ = p = 30
, δ ′ = 1.7 and ζ ′ = p/20. Define
Tb =

1
p



2.7
1.7

2

ln

20
.
p

600
Note that C ′ = C ′ (δ ′ , ζ ′ ) now depends only on δ. Recall that Tm = 1200
δ 2 ln δ . If we take
′
′
∆ ≥ C ln Tm , then Tm < exp(∆/C ). Thus we can assume that the local uniformity property
in Theorem 9 holds for all time t ∈ [Tb , Tm ]. If ∆ ≥ ∆0 (p, δ ′ , ζ ′ ) = ∆0 (δ), then it holds that


|A(Xt , v)|
− deg(v)/q
≥ 1 − exp(−∆/C ′ ).
(20)
≥ (1 − p/2)e
Pr ∀t ∈ [tb , tm ] :
q

For each t ≥ Tb , we define following bad events:

• E(t): there exists some time s < t, such that |Xs ⊕ Ys | > ∆2/3 .

• B1 (t): D≤t 6⊆ BTm (v).

• B2 (t): there exists some time Tb ≤ τ ≤ t and a vertex z ∈ BTm (v) such that
|A(Xτ , z)| ≤ (1 − p/2)qe−d(z)/q .

Define bad event B(t) as
B(t) = B1 (t) ∪ B2 (t).
Define good event G(t) as
G(t) = E(t) ∩ B(t).
For all events when the time t is dropped, we are referring to the event at time t = Tm . Then
the Hamming distance between XTm and YTm can be bounded as follows



E [HTm ] = E [HTm 1 (E)] + E HTm 1 E 1 (B) + E [HTm 1 (G)]
≤ E [HTm 1 (E)] + ∆2/3 Pr[B] + E [HTm 1 (G)] .

(21)

Since the bad events (non-typical events) occur with small probability, then we have following
Claims.

22

√
√
Claim 20. Pr[B] ≤ exp(− ∆) and E [HTm 1 (E)] ≤ exp(− ∆).
If the good event (typical event) G occurs, then we can use local uniformity property to
prove that the Hamming distance decreases by a constant factor during [Tb + 1, Tm ]. Thus we
have following Claim.
Claim 21. E [HTm 1 (G)] ≤ 1/9.
Lemma 19 follows by combining (21), Claim 20 and Claim 21.
Proof of Claim 20. At first, we prove that
√
Pr[B] ≤ exp(− ∆).
By Corollary 17, we know that disagreements can not percolate outside the ball BTm (v), which
implies Pr[B1 ] = 0. The probability of bad event B2 can be bounded by (20). Thus, we have
Pr[B] = Pr[B1 ] + Pr[B2 ]
= Pr[B2 ]
≤ ∆Tm exp(−∆/C ′ )
√
≤ exp(− ∆),

(∗)

where inequality (∗) is a union bound over all vertices
z ∈ BTm (v). The last inequality holds for
√
sufficiently large ∆ such that ∆ ≥ C ′ (Tm ln ∆ + ∆). Note the C ′ and Tm depends only on δ.
Next, we prove that
√
E [HTm 1 (E)] ≤ exp(− ∆).
We will prove that for every ℓ ≥ ∆2/3 , there exists C ′′ = C ′′ (δ) > 0 such that
Pr[H≤Tm ≥ ℓ] ≤ exp(−C ′′ ℓ).

(22)

Then, we bound the expected Hamming distance between XTm and YTm as follows
E [HTm 1 (E)] ≤ E [H≤Tm 1 (E)]
X
(By definition of E)
≤
ℓ Pr[H≤Tm = ℓ]
ℓ≥∆2/3

= ∆2/3 Pr[H≤Tm ≥ ℓ] +
≤ ∆2/3
(By (22) )

≤ ∆2/3
2/3

X

ℓ≥∆2/3

X

ℓ≥∆2/3 +1

Pr[H≤Tm ≥ ℓ]

Pr[H≤Tm ≥ ℓ]
exp(−ℓC ′′ )

ℓ≥∆2/3

exp(−∆2/3 C ′ )
1 − exp(−C ′′ )
√
≤ exp(− ∆).

=

X

∆

√
The last inequality holds for large ∆ such that C ′′ ∆2/3 ≥ 32 ln ∆ + ∆ − ln(1 − exp(−C ′′ )).
Now we prove inequality (22). Define a sequence c0 , c1 , . . . , cTm as follows
• cTm = 1;

• For each 1 ≤ t ≤ Tm , ct = (1 + 12p) ct−1 = 1 +

23

2δ
5



ct−1 .

For every ℓ ≥ ∆2/3 , we bound the probability of the event H≤t ≥ ct ℓ for 0 ≤ t ≤ Tm , where

2δ 3Tm /2
600
, then
Tm = 1200
δ 2 ln δ . Note that H≤0 = 1, if we take ∆ > 1 + 5
Pr [H≤0 ≥ c0 ℓ] = 0.

(23)

Then for each 1 ≤ t ≤ Tm , by the law of total probability, we have
Pr [H≤t ≥ ct ℓ] = Pr[H≤t ≥ ct ℓ | H≤t−1 ≥ ct−1 ℓ] Pr[H≤t−1 ≥ ct−1 ℓ]

+ Pr[H≤t ≥ ct ℓ | H≤t−1 < ct−1 ℓ] Pr[H≤t−1 < ct−1 ℓ]
≤ Pr[H≤t−1 ≥ ct−1 ℓ] + Pr[H≤t ≥ ct ℓ | H≤t−1 < ct−1 ℓ]

Let N (Dt ) = |(Xt ⊕ Yt ) \ (Xt−1 ⊕ Yt−1 )| be the number of new disagreements generated at step
t, then it holds that
Pr[H≤t ≥ ct ℓ | H≤t−1 < ct−1 ℓ] ≤ Pr[N (Dt ) ≥ (ct − ct−1 )ℓ | H≤t−1 < ct−1 ℓ]
(ct = (1 + 12p) ct−1 )

= Pr[N (Dt ) ≥ 12pct−1ℓ | H≤t−1 < ct−1 ℓ]
≤ exp(−12pct−1 ℓ).

The last inequality is due to Corollary 18 (Note that q ≥ 1.7∆ and |Xt−1 ⊕ Yt−1 | ≤ H≤t−1 ).
Thus
Pr [H≤t ≥ ct ℓ] ≤ Pr[H≤t−1 ≥ ct−1 ℓ] + exp(−12pct−1 ℓ).

(24)

Combining (23), (24) and the definition of sequence c (note that cTm = 1) implies
Pr [H≤Tm ≥ ℓ] ≤

Tm
X
i=1

exp(−12pct−1 ℓ) ≤ Tm exp(−12pc0 ℓ) = exp (−12pc0ℓ + ln Tm ) .

Note that ℓ ≥ ∆2/3 and c0 = (1 + 12p)−Tm . If ∆ ≥



ln Tm
11pc0

3/2

(note that Tm , c0 , p depend only

on δ), then we have −12pc0 ℓ + ln Tm ≤ −pc0 ℓ, which implies


pℓ
= exp(−ℓC ′′ ).
Pr [H≤Tm ≥ ℓ] ≤ exp(−pc0 ℓ) = exp −
(1 + 12p)Tm
Recall that p =

δ
30

and Tm =

1200
δ2

′′
′′
ln 600
δ , thus C = C (δ). This proves inequality (22).

Proof of Claim 21. Condition on Xt , Yt , we will bound the expected value of Ht+1 by path
coupling. Suppose Xt , Yt differ at h vertices v1 , v2 , . . . , vh . Then, according to the coupling, we
construct a sequence of colorings X = Z0 ∼ Z1 ∼ . . . ∼ Zh = Y , such that each Zi and Zi−1
′
differ only at vertex vi . Consider the coupling (Zi−1 , Zi ) → (Zi−1
, Zi′ ), by Lemma 7, we have

 ′
p(q − ∆)
E |Zi−1
⊕ Zi′ | | Zi−1 , Zi ≤ 1 −
q
p
∗
(q > α ∆)
≤1+ ∗
α


∆
3p
p∆
1−
+
q
q

Therefore, give Xt , Yt , the expected value of Ht+1 can be bounded by triangle inequality as
follows

p 
E [Ht+1 | Ht ] ≤ 1 + ∗ Ht .
(25)
α
The inequality shows that the number of disagreements increases in each step. However, this
bound will only be used during the burn-in phase [0, Tb ].

24

For each time t ∈ [Tb , Tm ], given Xt , Yt , assuming the good event G(t) occurs, we bound the
the expected value of Ht+1 by path coupling. Suppose Xt , Yt differ at h vertices v1 , v2 , . . . , vh .
According to the coupling, we construct the path X = Z0 ∼ Z1 ∼ . . . ∼ Zh = Y . Since we
assume that the good event G(t) occurs, then for each 0 ≤ i ≤ h, it holds that |X ⊕ Zi | ≤ ∆2/3 ,
vi ∈ BTm (v) and |A(X, vi )| ≥ (1 − p/2)qe− deg(vi )/q . Thus we have
|A(Zi , vi )| ≥ |A(X, vi )| − ∆2/3 ≥ (1 − p/2)qe− deg(vi )/q − ∆2/3 ≥ (1 − p/2)qe−∆/q − ∆2/3 .

Together with inequalities (5) and (6), we have

∆

 ′
p|A(Zi , vi )|
3p
p∆
E |Zi−1
⊕ Zi′ | | Zi−1 , Zi ≤ 1 −
1−
+
q
q
q



1
p∆
3p
≤ 1 − p (1 − p/2)e−∆/q − ∗ 1/3
,
1− ∗ +
α
q
α ∆
∆

≥ 1 − α3p∗ due to Bernoulli’s
where the last inequality is because q > α∗ ∆ and 1 − 3p
q
 ∆/q 3
 1/α∗ 3
≥ 2epα∗
, then α∗ ∆1 1/3 ≤ p2 e−∆/q . It holds
inequality. Note that, if we take ∆ ≥ 2epα∗
that


 ′

3p
p∆
E |Zi−1
⊕ Zi′ | | Zi−1 , Zi ≤ 1 − p(1 − p)e−∆/q 1 − ∗ +
α
q


∗
1
≤ 1 − p (1 − 3p)e−1/(α +δ) − ∗
α +δ



1
∗
1
− 3pe− α∗ +δ
=1−p
e−1/(α +δ) − ∗
α +δ


δ
− 3p ,
≤1−p
5
∗

where the last inequality is because for 0 < δ < 0.3, e−1/(α
δ
For p = 30
, it holds that

+δ)

−

1
α∗ +δ

≥

δ
5

1

and e− α∗ +δ ≤ 1.


 ′
δ2
.
E |Zi−1
⊕ Zi′ | | Zi−1 , Zi ≤ 1 −
300

Hence, for each t ∈ [Tb , Tm − 1], given Xt , Yt , assuming the good event G(t) holds, we have


δ2
E [Ht+1 | Xt , Yt ] ≤ 1 −
Ht .
(26)
300
For each t ∈ [Tb , Tm − 1], it holds that
E [Ht+1 1 (G(t))] = E [E [Ht+1 1 (G(t)) | X0 , Y0 , . . . , Xt , Yt ]]
(∗)

(By (26))
(∗∗)

≤ E [E [Ht+1 | X0 , Y0 , . . . , Xt , Yt ] 1 (G(t))]


δ2
≤ 1−
E [Ht 1 (G(t))]
300


δ2
E [Ht 1 (G(t − 1))] .
≤ 1−
300

Inequality (∗) is because the event G(t) is determined by X0 , Y0 , . . . , Xt , Yt . Inequality (∗∗) is
because the event G(t) implies the event G(t − 1). By induction, it holds that

Tm −Tb
δ2
E [HTm 1 (G)] ≤ E [HTm 1 (G(Tm − 1))] ≤ 1 −
E [HTb 1 (G(Tb − 1))] .
300

25

Note that E [HTb 1 (G(Tb − 1))] ≤ E [HTb ], and apply (25) for t ∈ [0, Tb − 1], we have
Tm −Tb 

p Tb
δ2
1+ ∗
H0 .
E [HTm 1 (G)] ≤ 1 −
300
α

(27)

2 20
600
δ
. It holds that Tb = 1p 2.7
ln p ≤ 120
Note that 1 < δ < 0.3, p = 30
1.7
δ ln δ . Since Tm =
1200
900
600
600
δ 2 ln δ , then we have Tm − Tb ≥ δ 2 ln δ . Note that H0 = 1. We have
 900 ln 600

δ 
δ 2 δ2
p  p4 ln 600
δ
1−
1+ ∗
300
α

3−4/α∗
δ
≤
600
1
≤ .
9

E [HTm 1 (G)] ≤

References
[1] B. Awerbuch, M. Luby, A. V. Goldberg, and S. A. Plotkin. Network decomposition and
locality in distributed computation. In Proceedings of the 30th IEEE Annual Symposium
on Foundations of Computer Science (FOCS), pages 364–369, 1989.
[2] L. Barenboim. Deterministic (∆+ 1)-coloring in sublinear (in ∆) time in static, dynamic,
and faulty networks. Journal of the ACM (JACM), 63(5):47, 2016.
[3] L. Barenboim and M. Elkin. Deterministic distributed vertex coloring in polylogarithmic
time. Journal of the ACM (JACM), 58(5):23, 2011.
[4] L. Barenboim, M. Elkin, S. Pettie, and J. Schneider. The locality of distributed symmetry
breaking. Journal of the ACM (JACM), 63(3):20, 2016.
[5] R. Bubley and M. Dyer. Path coupling: A technique for proving rapid mixing in markov
chains. In Proceedings of the 38th IEEE Annual Symposium on Foundations of Computer
Science (FOCS), pages 223–231, 1997.
[6] K.-M. Chung, S. Pettie, and H.-H. Su. Distributed algorithms for the Lovász local lemma
and graph coloring. In Proceedings of the 33rd ACM Symposium on Principles of Distributed
Computing (PODC), pages 134–143, 2014.
[7] D. Dubhashi and D. Ranjan. Balls and bins: A study in negative dependence. Random
Structures and Algorithms, 13(2):99–124, 1998.
[8] M. Dyer, A. Frieze, T. P. Hayes, and E. Vigoda. Randomly coloring constant degree graphs.
Random Structures & Algorithms, 43(2):181–200, 2013.
[9] M. Dyer, L. A. Goldberg, and M. Jerrum. Dobrushin conditions and systematic scan.
In Proceedings of the 10th International Workshop on Randomization and Computation
(RANDOM), pages 327–338. Springer, 2006.
[10] M. Dyer, L. A. Goldberg, and M. Jerrum. Systematic scan for sampling colorings. The
Annals of Applied Probability, 16(1):185–230, 2006.

26

[11] M. E. Dyer and A. M. Frieze. Randomly colouring graphs with lower bounds on girth and
maximum degree. In Proceedings of the 42nd Annual IEEE Symposium on Foundations of
Computer Science (FOCS), pages 579–587, 2001.
[12] M. E. Dyer and A. M. Frieze. Randomly coloring graphs with lower bounds on girth and
maximum degree. Random Struct. Algorithms, 23(2):167–179, 2003.
[13] C. Efthymiou, T. P. Hayes, D. Stefankovic, and E. Vigoda. Sampling random colorings of
sparse random graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA), pages 1759–1771, 2018.
[14] C. Efthymiou, T. P. Hayes, D. Štefankovic, E. Vigoda, and Y. Yin. Convergence of MCMC
and loopy BP in the tree uniqueness region for the hard-core model. In Proceedings of
the 57th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages
704–713, 2016.
[15] W. Feng, Y. Sun, and Y. Yin. What can be sampled locally? In Proceedings of the ACM
Symposium on Principles of Distributed Computing (PODC), pages 121–130, 2017.
[16] W. Feng and Y. Yin. On local distributed sampling and counting.
arXiv:1802.06686, 2018.

arXiv preprint

[17] P. Fraigniaud, M. Heinrich, and A. Kosowski. Local conflict coloring. In Proceedings of
the 57th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages
625–634, 2016.
[18] A. Frieze and J. Vera. On randomly colouring locally sparse graphs. Discrete Mathematics
and Theoretical Computer Science, 8, 2006.
[19] A. Frieze and E. Vigoda. A survey on the use of markov chains to randomly sample
colourings. Oxford Lecture Series in Mathematics and its Applications, 34:53, 2007.
[20] D. Gamarnik, D. Katz, and S. Misra. Strong spatial mixing of list coloring of graphs.
Random Structures & Algorithms, 2013.
[21] M. Ghaffari, F. Kuhn, and Y. Maus. On the complexity of local distributed graph problems.
In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
(STOC), pages 784–797. ACM, 2017.
[22] A. V. Goldberg, S. A. Plotkin, and G. E. Shannon. Parallel symmetry-breaking in sparse
graphs. SIAM Journal on Discrete Mathematics, 1(4):434–446, 1988.
[23] L. Goldberg, R. Martin, and M. Paterson. Strong spatial mixing with fewer colors for
lattice graphs. SIAM Journal on Computing, 35(2):486, 2005.
[24] J. E. Gonzalez, Y. Low, A. Gretton, and C. Guestrin. Parallel Gibbs sampling: From
colored fields to thin junction trees. In Proceedings of the 14th International Conference
on Artificial Intelligence and Statistics (AISTATS), volume 15, pages 324–332, 2011.
[25] T. P. Hayes. Randomly coloring graphs of girth at least five. In Proceedings of the 35th
Annual ACM Symposium on Theory of Computing (STOC), pages 269–278. ACM, 2003.
[26] T. P. Hayes. Local uniformity properties for glauber dynamics on graph colorings. Random
Struct. Algorithms, 43(2):139–180, 2013.

27

[27] T. P. Hayes and A. Sinclair. A general lower bound for mixing of single-site dynamics on
graphs. The Annals of Applied Probability, pages 931–952, 2007.
[28] T. P. Hayes and E. Vigoda. A non-markovian coupling for randomly sampling colorings.
In Proceedings of the 44th IEEE Annual Symposium on Foundations of Computer Science
(FOCS), pages 618–627. IEEE, 2003.
[29] T. P. Hayes, E. Vigoda, et al. Coupling with the stationary distribution and improved
sampling for colorings and independent sets. The Annals of Applied Probability, 16(3):1297–
1318, 2006.
[30] M. Jerrum. A very simple algorithm for estimating the number of k-colorings of a low-degree
graph. Random Structures & Algorithms, 7(2):157–165, 1995.
[31] Ö. Johansson. Simple distributed δ+ 1-coloring of graphs. Information Processing Letters,
70(5):229–232, 1999.
[32] F. Kuhn and R. Wattenhofer. On the complexity of distributed graph coloring. In Proceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing (PODC),
pages 7–15, 2006.
[33] D. A. Levin, Y. Peres, and E. L. Wilmer. Markov chains and mixing times. American
Mathematical Soc., 2009.
[34] N. Linial. Distributive graph algorithms global solutions from local data. In Proceedings
of the 28th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages
331–335. IEEE, 1987.
[35] N. Linial. Locality in distributed graph algorithms.
(SICOMP), 21(1):193–201, 1992.

SIAM Journal on Computing

[36] M. Molloy. The glauber dynamics on colorings of a graph with high girth and maximum
degree. SIAM Journal on Computing, 33(3):721–737, 2004.
[37] A. Panconesi and A. Srinivasan. On the complexity of distributed network decomposition.
Journal of Algorithms, 20(2):356–374, 1996.
[38] J. Salas and A. D. Sokal. Absence of phase transition for antiferromagnetic Potts models
via the Dobrushin uniqueness theorem. Journal of Statistical Physics, 86(3):551–579, 1997.
[39] J. Schneider and R. Wattenhofer. A new technique for distributed symmetry breaking. In
Proceedings of the 29th ACM Symposium on Principles of Distributed Computing (PODC),
pages 257–266. ACM, 2010.
[40] M. Szegedy and S. Vishwanathan. Locality based graph coloring. In Proceedings of the 25th
Annual ACM Symposium on Theory of Computing (STOC), pages 201–207. ACM, 1993.
[41] E. Vigoda. Improved bounds for sampling colorings. Journal of Mathematical Physics,
41(3):1555–1569, 2000.

28

