1 Probability and Computing 1.11 The Monte Carlo Method 1.13 Martingales

1.12 Coupling of Markov Chains

The motivation of coupling is to decide the rate of convergence to an ergodic Markov chain’s stationary distribution.

1.12.1 Variation Distance and Mixing Time

Definition 1.12.1 (Variation Distance).

The variation distance between two distributions $\mathcal{D}_{1}$ and $\mathcal{D}_{2}$ on a countable state space $S$ is given by

d_{\mathsf{TV}}\left(\mathcal{D}_{1},\mathcal{D}_{2}\right)=\frac{1}{2}\sum_{x% \in S}\left|\mathcal{D}_{1}(x)-\mathcal{D}_{2}(x)\right|.

The factor $1/2$ in definition 1.12.1 guarantees that the variation distance is in $[0,1]$ .

Lemma 1.12.2.

For any $A\subseteq S$ , let $\mathcal{D}(A)=\sum_{x\in A}\mathcal{D}(x)$ , then

d_{\mathsf{TV}}\left(\mathcal{D}_{1},\mathcal{D}_{2}\right)=\max_{A\subseteq S% }\left|\mathcal{D}_{1}(A)-\mathcal{D}_{2}(A)\right|.

Proof.

Let $S^{+}$ be all the $x\in S$ that $\mathcal{D}_{1}(x)\geq\mathcal{D}_{2}(x)$ , and $S^{-}=S\setminus S^{+}$ , such that $\forall x\in S^{-}$ , $\mathcal{D}_{1}(x)<\mathcal{D}_{2}(x)$ . Then

\left(\mathcal{D}_{1}(S^{+})-\mathcal{D}_{2}(S^{+})\right)+\left(\mathcal{D}_{% 2}(S^{-})-\mathcal{D}_{1}(S^{-})\right)=\sum_{a\in S}\left|\mathcal{D}_{1}(a)-% \mathcal{D}_{2}(a)\right|=2d_{\mathsf{TV}}\left(\mathcal{D}_{1},\mathcal{D}_{2% }\right).

Since $\mathcal{D}_{1}(S^{+})+\mathcal{D}_{1}(S^{-})=\mathcal{D}_{2}(S^{+})+\mathcal{% D}_{2}(S^{-})=1$ ,

\mathcal{D}_{1}(S^{+})-\mathcal{D}_{2}(S^{+})=\mathcal{D}_{2}(S^{-})-\mathcal{% D}_{1}(S^{-})=d_{\mathsf{TV}}\left(\mathcal{D}_{1},\mathcal{D}_{2}\right).

Moreover, by the definition of $S^{+}$ and $S^{-}$ , such that $\forall x\in S^{+}$ , $\mathcal{D}_{1}(x)\geq\mathcal{D}_{2}(x)$ , then $\forall A\subseteq S$ ,

\mathcal{D}_{1}(A)-\mathcal{D}_{2}(A)\leq\mathcal{D}_{1}(S^{+})-\mathcal{D}_{2% }(S^{+}).

Since $\mathcal{D}_{1}(S^{+})-\mathcal{D}_{2}(S^{+})$ is maximized, so is $\mathcal{D}_{2}(S^{-})-\mathcal{D}_{1}(S^{-})$ by symmetry, the proof is concluded. ∎

Remark 1.12.3.

The alternative characterization of variation distance by lemma 1.12.2 gives a strong statement, that supposing $d_{\mathsf{TV}}(\mathcal{D}_{1},\mathcal{D}_{2})<\varepsilon$ , then for any $x\in S$ , $\left|\mathcal{D}_{1}(x)-\mathcal{D}_{2}(x)\right|<\varepsilon$ .

Corollary 1.12.4.

Let $m(a)=\min\left(\mathcal{D}_{1}(a),\mathcal{D}_{2}(a)\right)$ for all $a\in S$ , then

d_{\mathsf{TV}}\left(\mathcal{D}_{1},\mathcal{D}_{2}\right)=1-m(S).

Proof.

The result is immediate by $d_{\mathsf{TV}}\left(\mathcal{D}_{1},\mathcal{D}_{2}\right)=\mathcal{D}_{1}(S^% {+})-\mathcal{D}_{2}(S^{+})$ and $m(S)=\mathcal{D}_{1}(S^{-})+\mathcal{D}_{2}(S^{+})$ . ∎

Definition 1.12.5 (Mixing Time).

Let $\boldsymbol{\pi}$ be the stationary distribution of an ergodic Markov chain with state space $S$ . Let $p_{x}^{t}$ represent the distribution of the state of the chain starting at state $x$ after $t$ steps. We define

	$\displaystyle\Delta_{x}(t)$	$\displaystyle=d_{\mathsf{TV}}\left(\mathcal{D}_{\boldsymbol{\pi}},p_{x}^{t}\right)$
	$\displaystyle\Delta(t)$	$\displaystyle=\max_{x\in S}\Delta_{x}(t)=\max_{x\in S}d_{\mathsf{TV}}\left(% \mathcal{D}_{\boldsymbol{\pi}},p_{x}^{t}\right),$

that is, $\Delta_{x}(t)$ is the variation distance between the stationary distribution and $p_{x}^{t}$ , and $\Delta(t)$ is the maximum of $\Delta_{x}(t)$ over all states $x$ . We also define

	$\displaystyle\tau_{x}(\varepsilon)$	$\displaystyle=\min\{t\mid\Delta_{x}(t)\leq\varepsilon\}$
	$\displaystyle\tau(\varepsilon)$	$\displaystyle=\max_{x\in S}\tau_{x}(\varepsilon)=\max_{x\in S}\min\{t\mid% \Delta_{x}(t)\leq\varepsilon\},$

that is, $\tau_{x}(\varepsilon)$ is the first step $t$ , at which the variation distance between $p_{x}^{t}$ and the stationary distribution is at most $\varepsilon$ , and $\tau(\varepsilon)$ is the maximum of $\tau_{x}(\varepsilon)$ over all states $x$ .

While $\tau(\varepsilon)$ is a function of $\varepsilon$ , it is generally called the mixing time of the Markov chain.

Definition 1.12.6 (Rapidly Mixing [JS89]).

A Markov chain with state space $S$ is rapidly mixing if its mixing time $\tau(\varepsilon)$ is $\mathsf{poly}(\log(1/\varepsilon),\log\left|S\right|)$ . We view $\log|S|$ as the problem size, since a state can be encoded using $O(\log|S|)$ bits.

1.12.2 Coupling

Coupling of Markov chains is a general technique for bounding the mixing time of a Markov chain.

Definition 1.12.7 (Markov Chain Coupling).

A coupling of a Markov chain $M_{t}$ with state space $S$ is a Markov chain $Z_{t}=(X_{t},Y_{t})$ on state space $S\times S$ such that

	$\displaystyle\Pr\left[X_{t+1}=x^{\prime}\mid Z_{t}=(x,y)\right]$	$\displaystyle=\Pr\left[M_{t+1}=x^{\prime}\mid M_{t}=x\right];$
	$\displaystyle\Pr\left[Y_{t+1}=y^{\prime}\mid Z_{t}=(x,y)\right]$	$\displaystyle=\Pr\left[M_{t+1}=y^{\prime}\mid M_{t}=y\right].$

Remark 1.12.8.

A coupling consists of two copies of the Markov chain $M_{t}$ running simultaneously, each copy behaves exactly like the original Markov chain in terms of its transition probabilities. The joint distribution preserves the marginal distribution of each copy, but the two copies may be correlated.

Remark 1.12.9.

To show a chain is close to stationarity, it suffices to couple it with a copy started from the stationary distribution. When the two chains reach the same state (the coupling time $T$ ), they can be made to evolve identically thereafter. In particular, if they have coupled by time $T$ , then the first chain is exactly equal to a stationary sample at time $T$ . Thus, the only obstruction to being close to stationarity is the probability that they have not yet met.

Lemma 1.12.10 (Mixing-Time Coupling Lemma).

Let $Z_{t}=(X_{t},Y_{t})$ be a coupling for a Markov chain $M_{t}$ on a state space $S$ . Suppose that there exists a $T$ such that, for every $x,y\in S$ ,

\Pr\left[X_{T}\neq Y_{T}\mid X_{0}=x,Y_{0}=y\right]\leq\varepsilon,

(1.19)

then $\tau(\varepsilon)\leq T$ , that the variation distance between the distribution over $S$ after $T$ steps and $\mathcal{D}_{\boldsymbol{\pi}}$ is at most $\varepsilon$ .

Proof.

Consider the coupling when initial state $x$ is fixed and $y\leftarrow\mathcal{D}_{\boldsymbol{\pi}}$ . We first prove the following core lemma.

Lemma 1.12.11.

In the coupling $Z_{t}=(X_{t},Y_{t})$ , where initial state $x$ is fixed and $y\leftarrow\mathcal{D}_{\boldsymbol{\pi}}$ , then

\Delta_{x}(T)\leq\Pr\left[X_{T}\neq Y_{T}\right].

Proof.

We begin by lower bounding $p_{x}^{T}(A)$ , where $A\subseteq S$ , by

	$\displaystyle p_{x}^{T}(A)$	$\displaystyle=\Pr\left[X_{T}\in A\right]$
		$\displaystyle=\Pr\left[X_{T}\in A\wedge Y_{T}=X_{T}\right]+\Pr\left[X_{T}\in A% \wedge Y_{T}\neq X_{T}\right]$
		$\displaystyle\geq\Pr\left[X_{T}\in A\wedge Y_{T}=X_{T}\right]=\Pr\left[Y_{T}% \in A\wedge Y_{T}=X_{T}\right],$

where the last equality holds by the same event. We continue the lower bounding by

	$\displaystyle p_{x}^{T}(A)$	$\displaystyle\geq\Pr\left[Y_{T}\in A\wedge Y_{T}=X_{T}\right]$
		$\displaystyle=1-\Pr\left[Y_{T}\notin A\vee Y_{T}\neq X_{T}\right]$
		$\displaystyle\geq 1-\Pr\left[Y_{T}\notin A\right]-\Pr\left[Y_{T}\neq X_{T}% \right]=\Pr\left[Y_{T}\in A\right]-\Pr\left[Y_{T}\neq X_{T}\right]$
		$\displaystyle=\mathcal{D}_{\boldsymbol{\pi}}(A)-\Pr\left[Y_{T}\neq X_{T}\right],$

where the third inequality holds by union bound. Symmetric to the prior derivation, we have

p_{x}^{T}(S\setminus A)\geq\mathcal{D}_{\boldsymbol{\pi}}(S\setminus A)-\Pr% \left[Y_{T}\neq X_{T}\right],

or equivalently,

\mathcal{D}_{\boldsymbol{\pi}}(A)\geq p_{x}^{T}(A)-\Pr\left[Y_{T}\neq X_{T}% \right].

Now that for all $A\subseteq S$ , we have

\left|p_{x}^{T}(A)-\mathcal{D}_{\boldsymbol{\pi}}(A)\right|\leq\Pr\left[X_{T}% \neq Y_{T}\right],

then by the alternative characterization of variation distance lemma 1.12.2, we complete the proof by

\Delta_{x}(T)=d_{\mathsf{TV}}\left(p_{x}^{T},\mathcal{D}_{\boldsymbol{\pi}}% \right)=\max_{A\subseteq S}\left|p_{x}^{T}(A)-\mathcal{D}_{\boldsymbol{\pi}}(A% )\right|\leq\Pr\left[X_{T}\neq Y_{T}\right].

∎

Since $\Pr\left[X_{T}\neq Y_{T}\right]\leq\varepsilon$ by eq. 1.19, then by lemma 1.12.11, $\Delta_{x}(T)\leq\varepsilon$ for all $x\in S$ . Hence, by definition 1.12.5,

T\geq\tau_{x}(\varepsilon)=\min\{t\mid\Delta_{x}(t)\leq\varepsilon\}

holds for all $x\in S$ , and therefore $\tau(\varepsilon)\leq T$ . ∎

Example 1.12.12 (Coupling for Card Shuffling).

A card-shuffling Markov chain for $n$ cards is defined over $n!$ states, where a state transitions to another by choosing a position $j\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}[1,n]$ , and moving the $j^{\mathrm{th}}$ card to the deck top. It is obvious that the stationary distribution is the uniform distribution.

To analyze the mixing time $\tau(\varepsilon)$ of the chain by lemma 1.12.10, we obtain 2 copies of the chain, and the coupling is constructed by sampling a card $C$ uniformly at random, and moving $C$ to the deck top in both copies. The coupling is valid: recall remark 1.12.8, that the marginal distribution is preserved, while the joint distribution may be correlated.

Moreover, when $C$ is moved to the deck top, then it is always in the same position in both copies, and the copies are coupled once every card has been moved to the top for at least once. Let $Z_{t}=(X_{t},Y_{t})$ be the coupling, then $\Pr\left[X_{T}\neq Y_{T}\right]$ is the probability that after $T$ steps, there exists cards still not chosen.

We continue by analyzing the coupon collector’s problem: with probability $(1-n^{-1})^{N}$ , a specific card is not chosen after $N$ trials. By theorem 1.5.23, let $N=n\ln n+cn$ , and by union bounding over all $n$ cards,

\Pr\left[X_{N}\neq Y_{N}\right]\leq n\left(1-\frac{1}{n}\right)^{N}\leq n\exp% \left(-\frac{N}{n}\right)=e^{-c},

where the second inequality holds by $1+x\leq e^{x}$ . When $N=n\ln(n/\varepsilon)$ , we have $\Pr\left[X_{N}\neq Y_{N}\right]\leq\varepsilon$ .

We conclude by lemma 1.12.10, that the variation distance between the uniform distribution and the distribution of the state of the chain after $n\ln(n/\varepsilon)$ steps is at most $\varepsilon$ , and $\tau(\varepsilon)\leq n\ln(n/\varepsilon)$ .

Exercise 1.12.13 (Exercise 12.2 [MU17]).

Considering the Markov chain for shuffling $n$ cards as in example 1.12.12. Suppose that, instead of running the chain for a fixed number of steps, we stop the chain at the first step where every card has been moved to the top at least once. Show that, at the stopping time, the state of the chain is uniformly distributed over $n!$ possible permutations of the cards.

Proof.

By the coupling in example 1.12.12, fix an initial state $x$ for $X_{0}$ and let $Y_{0}$ be sampled uniformly from $n!$ decks. Let $N$ be the first time that every card has been moved to the top at least once, then $X_{N}=Y_{N}$ . We conclude that $X_{N}$ is uniformly distributed over $n!$ possible decks. ∎

Exercise 1.12.14 (Exercise 12.3 [MU17]).

Considering the Markov chain for shuffling $n$ cards as in example 1.12.12. Show that if the chain runs for only $(1-\varepsilon)n\ln n$ steps for some constant $\varepsilon>0$ , then the variation distance is $1-o(1)$ .

Proof.

We started by lower bounding $d_{\mathsf{TV}}(p_{x}^{N},\mathcal{D}_{\boldsymbol{\pi}})$ , where $N=(1-\varepsilon)n\ln n$ , $x$ be an initial state. Since

d_{\mathsf{TV}}(p_{x}^{N},\mathcal{D}_{\boldsymbol{\pi}})=\max_{A\subseteq S}% \left|p_{x}^{N}(A)-\mathcal{D}_{\boldsymbol{\pi}}(A)\right|\geq\left|p_{x}^{N}% (B)-\mathcal{D}_{\boldsymbol{\pi}}(B)\right|

for all $B\subseteq S$ , the lower bound can be derived from lower bounding $\left|p_{x}^{N}(B)-\mathcal{D}_{\boldsymbol{\pi}}(B)\right|$ .

Let the cards be initially unshuffled and ordered, then we define a subset of states by $A_{\ell}$ such that the last $\ell$ cards preserve the relative order. We let $X_{i}$ be the 0-1 indicator random variable for the $i^{\mathrm{th}}$ card not being picked, and $X=\sum_{i}X_{i}$ be the random variable for the number of untouched cards.

Since $X\geq\ell$ leads to $A_{\ell}$ occurring, then $\{X\geq\ell\}\subseteq A_{\ell}$ , and

\Pr\left[X\geq\ell\right]\leq p_{x}^{N}(A_{\ell}).

By the linearity of expectation,

\operatorname*{\mathbb{E}}\left[X\right]=\sum_{i\in[1,n]}\operatorname*{% \mathbb{E}}\left[X_{i}\right]=n\left(1-\frac{1}{n}\right)^{N}\leq n\cdot\exp% \left(-(1-\varepsilon)\ln n\right)=n^{\varepsilon}.

We let $\ell=n^{\varepsilon/2}$ , and hence for any sufficiently large $n$ ,

\Pr\left[X<\ell\right]\leq\Pr\left[X\leq\frac{1}{2}n^{\varepsilon}\right].

Moreover, for $i\neq j\in[1,n]$ ,

\mathrm{Cov}\left[X_{i},X_{j}\right]=\operatorname*{\mathbb{E}}\left[X_{i}X_{j% }\right]-\operatorname*{\mathbb{E}}\left[X_{i}\right]\operatorname*{\mathbb{E}% }\left[X_{j}\right]=\left(1-\frac{2}{n}\right)^{N}-\left(1-\frac{1}{n}\right)^% {2N}<0,

hence

\mathrm{Var}\left[X\right]=\sum_{i\in[1,n]}\mathrm{Var}\left[X_{i}\right]+2% \sum_{j<k\in[1,n]}\mathrm{Cov}\left[X_{j},X_{k}\right]\leq\sum_{i\in[1,n]}% \mathrm{Var}\left[X_{i}\right]\leq\sum_{i\in[1,n]}\operatorname*{\mathbb{E}}% \left[X_{i}\right]=\operatorname*{\mathbb{E}}\left[X\right],

then by Chebyshev’s inequality,

\Pr\left[X<\ell\right]\leq\Pr\left[X\leq\frac{1}{2}n^{\varepsilon}\right]\leq% \frac{4\mathrm{Var}\left[X\right]}{n^{2\varepsilon}}\leq\frac{4}{n^{% \varepsilon}}.

On the other hand, $\mathcal{D}_{\boldsymbol{\pi}}(A_{\ell})=\left(\ell!\right)^{-1}=\left(n^{% \varepsilon/2}!\right)^{-1}$ . Hence,

d_{\mathsf{TV}}(p_{x}^{N},\mathcal{D}_{\boldsymbol{\pi}})=\max_{A\subseteq S}% \left|p_{x}^{N}(A)-\mathcal{D}_{\boldsymbol{\pi}}(A)\right|\geq\left|p_{x}^{N}% (A_{\ell})-\mathcal{D}_{\boldsymbol{\pi}}(A_{\ell})\right|\geq 1-\frac{4}{n^{% \varepsilon}}-\frac{1}{n^{\varepsilon/2}!},

which completes the proof for $d_{\mathsf{TV}}(p_{x}^{N},\mathcal{D}_{\boldsymbol{\pi}})=1-o(1)$ . ∎

Example 1.12.15 (Coupling for Random Walks on the Hypercube).

Consider the following Markov chain defined on a $n$ -dimensional hypercube. At each step, it picks a coordinate $i\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}[1,n]$ . The new state $\mathbf{x}^{\prime}$ is obtained from the current state $\mathbf{x}$ by keeping all coordinates the same, except possibly for $x_{i}$ . $x_{i}$ is set to 0 with probability $1/2$ , and to 1 with probability $1/2$ . The stationary distribution of the Markov chain is uniform distribution.

A coupling for the Markov chain can be obtained by enforcing the same move on the two copies: both changing $x_{i}$ to 0 or 1. The marginal probability of the coupling still follows the transition probability of the chain.

Moreover, once both copies make the same move on $x_{i}$ , they are surely agreeing on the $i^{\mathrm{th}}$ coordinate, and they will couple after all $n$ coordinates have each been chosen at least once. Immediate from the coupon collector’s problem, and by the same analysis in example 1.12.12, $\tau(\varepsilon)\leq n\ln\left(n/\varepsilon\right)$ .

Exercise 1.12.16 (Exercise 12.11 [MU17]).

Show that the Markov chain for sampling all independent sets of fixed size $k\leq n/(3\Delta+3)$ in a graph of $n$ vertices and maximum degree $\Delta$ is ergodic and has a uniform stationary distribution. A move is made from the independent set $X_{t}$ by choosing a vertex $v\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}X_{t}$ and $w\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}V$ . If $w\notin X_{t}$ and $X_{t}\setminus\{v\}\cup\{w\}$ is an independent set, then $X_{t+1}=X_{t}\setminus\{v\}\cup\{w\}$ ; otherwise, $X_{t+1}=X_{t}$ .

Proof.

Consider an independent set $A\subseteq V$ with $\left|A\right|=k$ , and let $\Gamma^{+}(A)$ be the inclusive neighborhood of $A$ , such that

\left|\Gamma^{+}(A)\right|\leq k(\Delta+1).

Suppose we want to transition from $A$ to $B$ , another independent set of fixed size with $k$ , we know that

\left|\Gamma^{+}(A\cup B)\right|\leq\left|\Gamma^{+}(A)\right|+\left|\Gamma^{+% }(B)\right|\leq 2k(\Delta+1).

Since $n\geq 3k(\Delta+1)$ , then $\left|V\setminus\Gamma^{+}(A\cup B)\right|\geq k(\Delta+1)$ .

We can greedily construct an independent set $C\subseteq V\setminus\Gamma^{+}(A\cup B)$ : at each step choose a vertex, put it into $C$ , and delete it together with all its neighbors. Since each step deletes at most $\Delta+1$ vertices, we can greedily select at least $k$ vertices from $V\setminus\Gamma^{+}(A\cup B)$ into $C$ . Hence there exists an independent set $C$ of size $k$ .

Then for any transition in between states of independent sets of fixed size, one can first transition to an independent set of fixed size $C\subseteq V\setminus\Gamma^{+}(A\cup B)$ , then transition to $B$ . Hence, the irreducibility is proved.

Positive recurrence is immediate by finiteness and irreducibility, and aperiodicity is immediate by the existence of odd length loop, namely the loop back to a state itself. Hence, the ergodicity is proved by corollary 1.7.47. ∎

Example 1.12.17 (Independent Sets of Fixed Size).

For 1.12.16, consider a coupling $Z_{t}=(X_{t},Y_{t})$ , requiring a perfect matching $M$ between vertices in $X_{t}\setminus Y_{t}$ and $Y_{t}\setminus X_{t}$ at each step. We choose a transition for $X_{t}$ by sampling $v\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}X_{t}$ and $w\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}V$ and perform the move. If $v\in Y_{t}$ , then perform the move over $v$ , $w$ , and $Y_{t}$ ; otherwise, perform the move over $M(v)$ , $w$ , and $Y_{t}$ .

An alternative way of coupling is established by sampling $v\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}X_{t}$ and $w\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}V$ and perform the move for $X_{t}$ , if $v\in Y_{t}$ , perform the move over $v$ , $w$ , and $Y_{t}$ ; otherwise, sample $v^{\prime}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}Y_{t}\setminus X_{t}$ and perform the move over $v^{\prime}$ , $w$ , and $Y_{t}$ .

The coupling still remains valid, by

	$\displaystyle\Pr\left[v^{\prime}\text{ chosen}\wedge v^{\prime}\in X_{t}\cap Y% _{t}\right]$	$\displaystyle=\Pr\left[v^{\prime}\text{ chosen}\mid v\stackrel{{\scriptstyle% \textsc{r}}}{{\leftarrow}}X_{t}\text{ and }v\in Y_{t}\right]\Pr\left[v% \stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}X_{t}\text{ and }v\in Y_{t}% \right]=\frac{1}{\left\|X_{t}\cap Y_{t}\right\|}\cdot\frac{\left\|X_{t}\cap Y_{t}% \right\|}{k},$
	$\displaystyle\Pr\left[v^{\prime}\text{ chosen}\wedge v^{\prime}\in Y_{t}% \setminus X_{t}\right]$	$\displaystyle=\Pr\left[v^{\prime}\text{ chosen}\mid v\stackrel{{\scriptstyle% \textsc{r}}}{{\leftarrow}}X_{t}\text{ and }v\notin Y_{t}\right]\Pr\left[v% \stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}X_{t}\text{ and }v\notin Y_{t% }\right]=\frac{1}{\left\|Y_{t}\setminus X_{t}\right\|}\cdot\frac{\left\|X_{t}% \setminus Y_{t}\right\|}{k},$

such that $v\in Y_{t}$ and $w\in V$ are still chosen with probability $1/kn$ . Note that, in the coupling, it is possible to transition in one chain and stay put in the other.

Let $D_{t}=\left|X_{t}\setminus Y_{t}\right|$ be the random variable for the difference size between $X_{t}$ and $Y_{t}$ , and $D_{t}$ can change by at most 1 at a step. We want to show $D_{t}$ is more likely to decrease, and we want to upper bound the probability of $D_{t}>0$ for a sufficiently large $t$ .

Suppose $D_{t}>0$ . In order to make $D_{t+1}=D_{t}+1$ , the vertex $v$ to be removed has to be sampled from $X_{t}\cap Y_{t}$ , while the vertex $w$ to be introduced can only cause one of the two states to transition, such that ¹⁰¹⁰10 $w$ can be strengthened from causing one of the two states to transition, by observing if $w\in(X_{t}\setminus Y_{t})\cup(Y_{t}\setminus X_{t})$ , the transition state’s shared component with the state staying put is still of size $k-D_{t}$ , by removing 1 shared element and reintroducing 1 shared element. If $w$ is sampled over the neighbors of $(X_{t}\setminus Y_{t})\cup(Y_{t}\setminus X_{t})$ , then the transition state is surely decreasing the size of the shared component with the state staying put.

w\in\Gamma^{+}\left((X_{t}\setminus Y_{t})\cup(Y_{t}\setminus X_{t})\right).

Then it follows that

\Pr\left[D_{t+1}=D_{t}+1\mid D_{t}>0\right]\leq\frac{k-D_{t}}{k}\cdot\frac{2D_% {t}(\Delta+1)}{n}.

In order to make $D_{t+1}=D_{t}-1$ , the vertex $v$ to be removed has to be sampled from $X_{t}\setminus Y_{t}$ , while the vertex $w$ to be introduced must cause both states to transition, such that

w\notin\Gamma^{+}\left(X_{t}\cup Y_{t}\setminus\{v,v^{\prime}\}\right),

hence

\Pr\left[D_{t+1}=D_{t}-1\mid D_{t}>0\right]\geq\frac{D_{t}}{k}\cdot\frac{n-(% \Delta+1)(k+D_{t}-2)}{n}.

We thus have, for $D_{t}>0$ ,

	$\displaystyle\operatorname*{\mathbb{E}}\left[D_{t+1}\mid D_{t}\right]$	$\displaystyle=D_{t}+\Pr\left[D_{t+1}=D_{t}+1\mid D_{t}>0\right]-\Pr\left[D_{t+% 1}=D_{t}-1\mid D_{t}>0\right]$
		$\displaystyle\leq D_{t}+\frac{k-D_{t}}{k}\cdot\frac{2D_{t}(\Delta+1)}{n}-\frac% {D_{t}}{k}\cdot\frac{n-(\Delta+1)(k+D_{t}-2)}{n}$
		$\displaystyle=D_{t}\left(1-\frac{n-(\Delta+1)(3k-D_{t}-2)}{kn}\right)$
		$\displaystyle\leq D_{t}\left(1-\frac{n-(\Delta+1)(3k-3)}{kn}\right),$

and once $D_{t}=0$ , $\operatorname*{\mathbb{E}}\left[D_{t+1}\mid D_{t}\right]=0$ . By conditional expectation,

\operatorname*{\mathbb{E}}\left[D_{t+1}\right]=\operatorname*{\mathbb{E}}\left% [\operatorname*{\mathbb{E}}\left[D_{t+1}\mid D_{t}\right]\right]\leq% \operatorname*{\mathbb{E}}\left[D_{t}\right]\left(1-\frac{n-(\Delta+1)(3k-3)}{% kn}\right).

We then conclude that

	$\displaystyle\Pr\left[D_{t}\geq 1\right]$	$\displaystyle\leq\operatorname{\mathbb{E}}\left[D_{t}\right]\leq\operatorname% {\mathbb{E}}\left[D_{0}\right]\left(1-\frac{n-(\Delta+1)(3k-3)}{kn}\right)^{t}$
		$\displaystyle\leq k\left(1-\frac{n-(\Delta+1)(3k-3)}{kn}\right)^{t}$
		$\displaystyle\leq k\cdot\exp\left(-t\cdot\frac{n-(\Delta+1)(3k-3)}{kn}\right),$

the first inequality holds from Markov inequality, the third holds by $\operatorname*{\mathbb{E}}\left[D_{0}\right]\leq k$ , and the last holds by $1+x\leq e^{x}$ . It converges to $0$ when $k\leq n/(3\Delta+3)$ , then in this case,

\tau(\varepsilon)\leq\frac{kn\ln(k/\varepsilon)}{n-(\Delta+1)(3k-3)}.

It turns out that $\tau(\varepsilon)$ is polynomial in $n$ (which is logarithmic in the number of independent sets of fixed size $k$ ) and $\ln(\varepsilon^{-1})$ , hence it is rapidly mixing.

Exercise 1.12.18 (Exercise 12.8 [MU17]).

Consider the random walk on a non-bipartite, connected graph with $\left|V\right|=n$ , where each vertex has the same degree $n>d>n/2$ . Show that

\tau(\varepsilon)\leq\frac{\ln\varepsilon}{\ln(1-(2d-n)/d)}.

Proof.

By theorem 1.7.75, the stationary distribution of such a graph is uniform.

A coupling can be established by sampling one copy’s initial state from the stationary distribution, while the other’s initial state is any fixed state. Suppose they are on states $u\neq v$ , then on transition, construct a perfect matching $M$ between $\Gamma(u)$ and $\Gamma(v)$ , such that $\Gamma(u)\cap\Gamma(v)$ are matched to themselves, while the other neighboring vertices are randomly 1-to-1 matched. We randomly choose 1 out of $d$ options in $M$ , and since $\left|\Gamma(u)\cap\Gamma(v)\right|\geq 2d-n$ , then

\Pr\left[X_{t+1}=Y_{t+1}\mid X_{t}\neq Y_{t},X_{0}=x,Y_{0}=y\right]\geq\frac{2% d-n}{d}

for all initial states $x\neq y$ , hence by induction

\Pr\left[X_{t}\neq Y_{t}\mid X_{0}=x,Y_{0}=y\right]\leq\left(1-\frac{2d-n}{d}% \right)^{t}=\varepsilon,

then

t=\frac{\ln\varepsilon}{\ln\left(1-(2d-n)/d\right)}.

By lemma 1.12.10, $\Delta_{x}(t)\leq\Pr\left[X_{t}\neq Y_{t}\right]$ , then it is immediate that $\tau(\varepsilon)\leq t$ . ∎

Exercise 1.12.19 (Exercise 12.9 [MU17]).

Consider a Markov chain on $n$ points $[0,n-1]$ lying in order on a circle. At each step, the chain stays at the current point with probability $1/2$ , or moves to the next point in the clockwise direction with probability $1/2$ . Show that for any $\varepsilon>0$ , the mixing time $\tau(\varepsilon)$ is $O(n^{2}\ln(1/\varepsilon))$ .

Proof.

It is clear by the cutset argument that the stationary distribution is the uniform distribution.

Consider a coupling where each copy operates oppositely, namely if one stays, the other moves to the next point. Let the distance be the number of steps to take clockwise from a chain state to the other, then it can be modeled by the gambler’s ruin example 1.7.51: states are $[0,n]$ , absorbing states are $0$ and $n$ , moving $\pm 1$ with probability $1/2$ .

By 1.7.68, if the current distance is $i$ , the expected number of moves is $i\cdot(n-i)\leq n^{2}/4$ . Let $T$ be the random variable for the number of steps before coupling, then by Markov’s inequality, for all initial states $x\neq y$ ,

\Pr\left[T\geq\frac{n^{2}}{2}~{}\middle|~{}X_{0}=x,Y_{0}=y\right]\leq\frac{1}{% 2}.

By Markov property,

\Pr\left[T\geq n^{2}~{}\middle|~{}T\geq\frac{n^{2}}{2},X_{0}=x,Y_{0}=y\right]% \leq\frac{1}{2},

and by induction,

\Pr\left[T\geq\frac{k}{2}n^{2}~{}\middle|~{}X_{0}=x,Y_{0}=y\right]\leq 2^{-k}.

Hence,

\Pr\left[X_{T}\neq Y_{T}\mid X_{0}=x,Y_{0}=y\right]=\Pr\left[T\geq\frac{\log% \left(\varepsilon^{-1}\right)}{2}n^{2}~{}\middle|~{}X_{0}=x,Y_{0}=y\right]\leq\varepsilon.

Immediate from lemma 1.12.10, we have $\tau(\varepsilon)\leq T=\log(\varepsilon^{-1})n^{2}/2$ , hence $\tau(\varepsilon)=O(\ln(\varepsilon^{-1})n^{2})$ . ∎

Exercise 1.12.20 (Exercise 12.12 [MU17]).

We improve the coupling in example 1.12.17: if an attempt is made to move $v\in X_{t}\setminus Y_{t}$ to a vertex $w$ , then the same attempt is made with the matched vertex in the other chain; if, however, if an attempt is made to move $v\in X_{t}\cap Y_{t}$ , we no longer attempt to make the same move.

•

Assume there are sets $S_{1}=\Gamma^{+}(X_{t}\setminus Y_{t})$ , and $S_{2}=\Gamma^{+}(Y_{t}\setminus X_{t})$ , each of exactly $D_{t}(\Delta+1)$ distinct vertices. Assume further that $S_{1}\cap S_{2}=\varnothing$ . Suppose that we match up elements in $S_{1}$ and $S_{2}$ in a 1-to-1 fashion.

Argue that the moves can be coupled that, when one chain attempts and fails to move $v$ to a vertex in $S_{1}$ , it also attempts and fails to move $v$ to the matching vertex in $S_{2}$ on the other chain.

Similarly, argue that the moves can be coupled that, when one chain attempts and succeeds in moving $v$ to a vertex in $S_{1}$ , it also attempts and succeeds in moving $v$ to the matching vertex in $S_{2}$ on the other chain.

Show that the coupling gives

$\Pr\left[D_{t+1}=D_{t}+1\right]\leq\frac{k-D_{t}}{k}\cdot\frac{D_{t}(\Delta+1)% }{n}.$ (1.20)
•

In the general case, $S_{1}$ and $S_{2}$ are not necessarily disjoint or of same size. Show that in the general case, by pairing up failing moves as much as possible, the number of choices for $w$ that can increase $D_{t}$ is $\max(\left|S_{1}\right|,\left|S_{2}\right|)\leq D_{t}(\Delta+1)$ . Then argue that eq. 1.20 holds in all cases.
•

Use this coupling to derive a polynomial bound on $\tau(\varepsilon)$ that holds for any $k\leq n/(2\Delta+2)$ .

Proof.

Consider in the optimal case, where $S_{1}$ and $S_{2}$ are $D_{t}(\Delta+1)$ large, $S_{1}\cap S_{2}=\varnothing$ , and $M$ is the 1-to-1 mapping. Let $M^{\prime}$ be the 1-to-1 mapping between $X_{t}\setminus Y_{t}$ and $Y_{t}\setminus X_{t}$ . The chain is coupled by sampling $v\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}X_{t}$ and $w\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}V$ :

•

If $v\in X_{t}\setminus Y_{t}$ , then let $v^{\prime}=M^{\prime}(v)$ for $Y_{t}$ ; otherwise, let $v^{\prime}=v$ .
•

If $w\in S_{1}$ , then let $w^{\prime}=M(w)$ for $Y_{t}$ ; if $w\in S_{2}$ , then let $w^{\prime}=M^{-1}(w)$ for $Y_{t}$ ; otherwise, let $w^{\prime}=w$ .

Perform the move removing $v$ for $w$ on $X_{t}$ and removing $v^{\prime}$ for $w^{\prime}$ on $Y_{t}$ .

When we want to remove $v\in X_{t}\cap Y_{t}$ for chain $X_{t}$ , the transition fails when $w\in\Gamma^{+}(X_{t}\setminus\{v\})$ , hence the transitions for $X_{t}$ fails when $w\in S_{1}=\Gamma^{+}(X_{t}\setminus Y_{t})$ . Symmetrically, by the mapping $M$ , if $w^{\prime}=M(w)\in S_{2}$ , transition for $Y_{t}$ fails.

Conversely, when $v\in X_{t}\cap Y_{t}$ , for chain $X_{t}$ , transition succeeds when $w\in V\setminus\Gamma^{+}(X_{t}\setminus\{v\})$ , hence the transition for $X_{t}$ succeeds when $w\in S_{2}$ . Symmetrically, by mapping $M$ , if $w^{\prime}=M^{-1}(w)\in S_{1}$ , transition for $Y_{t}$ succeeds.

In order for $D_{t+1}=D_{t}+1$ , it must be at time $t$ the vertex $v$ chosen from $X_{t}\cap Y_{t}$ , and $w$ must be chosen from $S_{2}$ , or otherwise either $w=w^{\prime}$ , or $w\in S_{1}$ fails to transition. Hence, by the same upper bound argument in example 1.12.17,

\Pr\left[D_{t+1}=D_{t}+1\right]\leq\frac{\left|X_{t}\cap Y_{t}\right|}{k}\cdot% \frac{\left|S_{2}\right|}{n}=\frac{k-D_{t}}{k}\cdot\frac{D_{t}(\Delta+1)}{n}.

Moving on the general case. We reuse previous $S_{1},S_{2},M^{\prime}$ , and let $M$ be the mapping between $S_{1}$ and $S_{2}$ , such that $S_{1}\cap S_{2}$ are mapped to itself, bijectively map elements between $S_{1}$ and $S_{2}$ as many as possible, and the remaining elements in the larger set map to itself.

In this way, if $v\in X_{t}\cap Y_{t}$ , failing moves of moving $v$ for $w\in S_{1}$ in $X_{t}$ and moving $v$ for $w^{\prime}\in S_{2}$ in $Y_{t}$ are maximally paired. WLOG let $S_{2}$ be the larger set, as the symmetric case can be analyzed in the same way.

•

If $w\in M(S_{1}\setminus S_{2})$ , then the successful moves are also maximally paired.
•

If $w\in(S_{2}\setminus S_{1})\setminus M(S_{1}\setminus S_{2})$ , then $w$ is mapped to itself because $S_{2}$ is larger, only $X_{t}$ transitions successfully.
•

Otherwise, for $w\in V\setminus(S_{1}\cup S_{2})$ , then either both chains transition to same $w$ , or neither chain transitions.

$D_{t}$ increases only in the first 2 cases for at most $\max(\left|S_{1}\right|,\left|S_{2}\right|)\leq D_{t}(\Delta+1)$ elements. Hence eq. 1.20 holds by

\Pr\left[D_{t+1}=D_{t}+1\right]\leq\frac{\left|X_{t}\cap Y_{t}\right|}{k}\cdot% \frac{\max(\left|S_{1}\right|,\left|S_{2}\right|)}{n}=\frac{k-D_{t}}{k}\cdot% \frac{D_{t}(\Delta+1)}{n}.

To decrease $D_{t}$ , it has to be $u\in X_{t}\setminus Y_{t}$ moving to $w\in V\setminus\Gamma^{+}(X_{t}\cup Y_{t}\setminus\{u,u^{\prime}\})$ in $X_{t}$ . Continuing from example 1.12.17,

\Pr\left[D_{t+1}=D_{t}-1\mid D_{t}>0\right]\geq\frac{D_{t}}{k}\cdot\frac{n-(% \Delta+1)(k+D_{t}-2)}{n}.

By the same analysis,

	$\displaystyle\operatorname*{\mathbb{E}}\left[D_{t+1}\mid D_{t}\right]$	$\displaystyle=D_{t}+\Pr\left[D_{t+1}=D_{t}+1\mid D_{t}>0\right]-\Pr\left[D_{t+% 1}=D_{t}-1\mid D_{t}>0\right]$
		$\displaystyle\leq D_{t}+\frac{k-D_{t}}{k}\cdot\frac{D_{t}(\Delta+1)}{n}-\frac{% D_{t}}{k}\cdot\frac{n-(\Delta+1)(k+D_{t}-2)}{n}$
		$\displaystyle=D_{t}\left(1-\frac{n-(\Delta+1)(2k-2)}{kn}\right),$

then by the same Markov inequality argument in example 1.12.17,

	$\displaystyle\Pr\left[D_{t}\geq 1\right]$	$\displaystyle\leq\operatorname{\mathbb{E}}\left[D_{t}\right]=\operatorname{% \mathbb{E}}\left[D_{0}\right]\left(1-\frac{n-(\Delta+1)(2k-2)}{kn}\right)^{t}$
		$\displaystyle\leq k\left(1-\frac{n-(\Delta+1)(2k-2)}{kn}\right)^{t}$
		$\displaystyle\leq k\cdot\exp\left(-t\cdot\frac{n-(\Delta+1)(2k-2)}{kn}\right),$

which converges to $0$ when $k\leq n/(2\Delta+2)$ , and we have

\tau(\varepsilon)\leq\frac{kn\ln(k/\varepsilon)}{n-(\Delta+1)(2k-2)}.

∎

Remark 1.12.21.

The 1.12.20 is a finer analysis of example 1.12.17 derived from [BD97].

Exercise 1.12.22 (Exercise 12.14 [MU17]).

Consider the following variant of shuffling a deck of $n$ cards: at each step, two cards are chosen independently and uniformly at random from the deck, and their positions are exchanged.

•

Argue the following being equivalent: at each step, a specific card is chosen uniformly at random from the deck, and a position $i\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}[1,n]$ sampled independently. The $i^{\mathrm{th}}$ card is exchanged with the specific chosen card.
•

Consider the coupling where the two choices of card and position are the same for both copies of the chain. Let $X_{t}$ be the number of cards whose positions differ in the two copies of the chain. Show $X_{t}$ is nonincreasing,

$\Pr\left[X_{t+1}\leq X_{t}-1\mid X_{t}>0\right]\geq\left(\frac{X_{t}}{n}\right% )^{2},$

and the expected time until $X_{t}=0$ is $O(n^{2})$ , regardless of the initial states of the two chains.

Proof.

It suffices to show that, for a specific card, sampling $i\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}[1,n]$ and the $i^{\mathrm{th}}$ card in the deck being this specific card has the same probability as choosing this card out of uniform randomness.

For every coupled move,

•

If the chosen card is in the same position in both decks, then $X_{t+1}=X_{t}$ .
•
Otherwise, if the chosen card is in different positions in both decks,
- –
  
  If the $i^{\mathrm{th}}$ position cards are the same in both decks, then $X_{t+1}=X_{t}$ .
- –
  
  Otherwise, the coupled move at least introduces 1 correction, hence $X_{t+1}\leq X_{t}-1$ .

Therefore the coupled move makes $X_{t}$ nonincreasing over time, and correction only happens in both the card chosen and the position chosen being in disagreeing section, hence

\Pr\left[X_{t+1}\leq X_{t}-1\mid X_{t}>0\right]\geq\left(\frac{X_{t}}{n}\right% )^{2}.

Conditioned on $X_{t}=k$ , the steps to decrease $X_{t}$ is geometrically distributed, with success probability $(k/n)^{2}$ . Let $Y_{k}$ be the steps to decrease from $k$ differences, and $Y=\sum_{k}Y_{k}$ be the steps before $X_{t}=0$ ,

\operatorname*{\mathbb{E}}\left[Y\right]\leq\sum_{k\in[1,n]}\left(\frac{n}{k}% \right)^{2}=O(n^{2}),

which completes the proof. ∎

1.12.3 Variation Distance is Nonincreasing

Lemma 1.12.23 (Optimal Coupling Lemma).

Given distribution $\sigma_{X}$ and $\sigma_{Y}$ on a state space $S$ , let $Z=(X,Y)$ be a random variable on $S\times S$ , where $X$ is distributed according to $\sigma_{X}$ and $Y$ is distributed according to $\sigma_{Y}$ . Then

\Pr\left[X\neq Y\right]\geq d_{\mathsf{TV}}\left(\sigma_{X},\sigma_{Y}\right).

Moreover, there exists a joint distribution $Z=(X,Y)$ , where $X$ is distributed according to $\sigma_{X}$ and $Y$ is distributed according to $\sigma_{Y}$ , for which the equality holds.

Proof.

The proof idea of the first part is the same as lemma 1.12.11, where we replace $\mathcal{D}_{\boldsymbol{\pi}}$ with $\sigma_{Y}$ .

Alternatively, we can prove by

	$\displaystyle\Pr\left[X=x\right]$	$\displaystyle=\Pr\left[X=x\wedge X=Y\right]+\Pr\left[X=x\wedge X\neq Y\right]$
		$\displaystyle=\Pr\left[Y=x\wedge X=Y\right]+\Pr\left[X=x\wedge X\neq Y\right]$
		$\displaystyle\leq\Pr\left[Y=x\right]+\Pr\left[X=x\wedge X\neq Y\right].$

By symmetry, we have

	$\displaystyle\Pr\left[X=x\right]-\Pr\left[Y=x\right]$	$\displaystyle\leq\Pr\left[X=x\wedge X\neq Y\right],$
	$\displaystyle\Pr\left[Y=x\right]-\Pr\left[X=x\right]$	$\displaystyle\leq\Pr\left[Y=x\wedge X\neq Y\right].$

Let $S^{+},S^{-}\subseteq S$ be the sets, such that $S^{-}=S\setminus S^{+}$ , $\forall a\in S^{+}$ , $\sigma_{X}(a)\geq\sigma_{Y}(a)$ , and $\forall a\in S^{-}$ , $\sigma_{X}(a)<\sigma_{Y}(a)$ , then

	$\displaystyle 2d_{\mathsf{TV}}\left(\sigma_{X},\sigma_{Y}\right)$	$\displaystyle=\left(\sigma_{X}(S^{+})-\sigma_{Y}(S^{+})\right)+\left(\sigma_{Y% }(S^{-})-\sigma_{X}(S^{-})\right)$
		$\displaystyle\leq\sum_{a\in S^{+}}\Pr\left[X=a\wedge X\neq Y\right]+\sum_{a\in S% ^{-}}\Pr\left[Y_{t}=a\wedge X\neq Y\right]$
		$\displaystyle\leq\Pr\left[X\neq Y\right]+\Pr\left[X\neq Y\right].$

Or alternatively, by corollary 1.12.4, for each $a\in S$ , both $X$ and $Y$ are $a$ with probability at most $m(a)$

\Pr\left[X=Y=a\right]\leq m(a),

where the equality holds by matching $X$ and $Y$ as much as possible, hence we complete the proof by corollary 1.12.4,

\Pr\left[X=Y\right]\leq m(S)=1-d_{\mathsf{TV}}\left(\sigma_{X},\sigma_{Y}% \right).

The equality case follows by the construction matching $X$ and $Y$ as much as possible in the joint distribution. If $m(S)=1$ , the equality holds by $X$ and $Y$ are same distribution. Otherwise, let $Z=(X,Y)$ ,

\Pr\left[X=x,Y=y\right]=\begin{cases}m(x)&x=y,\\ \dfrac{(\sigma_{X}(x)-m(x))(\sigma_{Y}(y)-m(y))}{1-m(S)}&x\neq y.\end{cases}

The equality holds by corollary 1.12.4,

\Pr\left[X\neq Y\right]=1-m(S)=d_{\mathsf{TV}}\left(\sigma_{X},\sigma_{Y}% \right).

The marginal distribution is preserved as follows: if $m(x)=\sigma_{X}(x)$ , then $\Pr\left[X=x\right]=\sigma_{X}(x)$ ; otherwise $m(x)=\sigma_{Y}(x)$ ,

\Pr\left[X=x\right]=m(x)+\frac{\sigma_{X}(x)-m(x)}{1-m(S)}\sum_{y\neq x}(% \sigma_{Y}(y)-m(y))=m(x)+\sigma_{X}(x)-m(x)=\sigma_{X}(x).

The case for $Y$ holds by symmetry. ∎

Corollary 1.12.24.

Let $(X_{t},Y_{t})$ be two copies of a Markov chain $M_{t}$ on a state space $S$ . For any initial states $x,y\in S$ and any time $t\geq 0$ , there exists a coupling of the two copies, such that

d_{\mathsf{TV}}\left(p_{x}^{t},p_{y}^{t}\right)=\Pr\left[X_{t}\neq Y_{t}\right].

Proof.

There exists a coupled pair of random variables $(U,V)$ of marginal distributions $p_{x}^{t}$ and $p_{y}^{t}$

\Pr\left[U\neq V\right]=d_{\mathsf{TV}}\left(p_{x}^{t},p_{y}^{t}\right)

by lemma 1.12.23. We now extend this optimal coupling of the endpoints to a coupling of full trajectories.

First sample the endpoint pair $(U,V)$ . Conditioned on $U=u$ , sample a path

X_{0},\ldots,X_{t-1},X_{t}

by the transition probability of $M_{t}$ , conditioned on the events $X_{t}=u$ and $X_{0}=x$ .

Similarly, conditioned on $V=v$ , sample a path

Y_{0},\ldots,Y_{t-1},Y_{t}

conditioned on the events $Y_{t}=v$ and $Y_{0}=y$ .

For any path $X_{0}=x,\ldots,X_{t-1}=x_{t-1},X_{t}=u$ , the conditional probability is

\Pr\left[X_{1}=x_{1},\ldots,X_{t-1}=x_{t-1}\mid X_{0}=x,X_{t}=u\right]=\frac{1% }{p_{x}^{t}(u)}\prod_{i\in[1,t]}P_{x_{i-1},x_{i}}.

Since $p_{x}^{t}(u)>0$ by $U$ having marginal distribution $p_{x}^{t}$ , the conditional probability is well-defined.

By construction, the marginal distribution of $(X_{0},\ldots,X_{t})$ is that of the chain $M_{t}$ started from $x$ , and the marginal distribution of $(Y_{0},\ldots,Y_{t})$ is that of the chain $M_{t}$ started from $y$ .

Moreover, since $X_{t}=U$ and $Y_{t}=V$ , then

\Pr\left[U\neq V\right]=\Pr\left[X_{t}\neq Y_{t}\right]=d_{\mathsf{TV}}\left(p% _{x}^{t},p_{y}^{t}\right),

and we have constructed a coupling of two copies of the Markov chain reaching optimal coupling at time $t$ . ∎

Lemma 1.12.25.

For any ergodic Markov chain, $\Delta(T+1)\leq\Delta(T)$ .

Proof.

Keep in mind that $\Delta_{x}(t)$ is a concrete deterministic value of variation distance between $p_{x}^{t}$ and $\mathcal{D}_{\boldsymbol{\pi}}$ . The proof idea is to couple optimally at time $T$ , then show that $\Delta_{x}(T+1)$ has a lower upper bound than $\Pr\left[X_{T}\neq Y_{T}\right]$ .

Fix an initial state $x\in S$ . If we sample $y\leftarrow\mathcal{D}_{\boldsymbol{\pi}}$ for the initial state of $p_{y}^{T}$ , then

\Delta_{x}(T)=d_{\mathsf{TV}}\left(p_{x}^{T},p_{y}^{T}\right).

By corollary 1.12.24, there exists a coupling for the chains such that they are optimally coupled at time $T$ , we have

\Pr\left[X_{T}\neq Y_{T}\right]=\Delta_{x}(T).

Next, we couple the chains $X_{T}$ and $Y_{T}$ by: if $X_{T}=Y_{T}$ , for all $s\geq T$ , $X_{s}=Y_{s}$ ; otherwise, they transition independently. By the sticky step-by-step coupling, since $\{X_{T}=Y_{T}\}\subseteq\{X_{T+1}=Y_{T+1}\}$ ,

\Pr\left[X_{T}\neq Y_{T}\right]\geq\Pr\left[X_{T+1}\neq Y_{T+1}\right].

Hence, $\Delta_{x}(T)$ is non-increasing by

\Delta_{x}(T)=\Pr\left[X_{T}\neq Y_{T}\right]\geq\Pr\left[X_{T+1}\neq Y_{T+1}% \right]\geq\Delta_{x}(T+1),

where the last inequality holds by lemma 1.12.11. Since it holds for all $x\in S$ , we have $\Delta(T)\geq\Delta(T+1)$ . ∎

Exercise 1.12.26 (Exercise 12.13 [MU17]).

Consider a Markov chain with state space $S$ and a stationary distribution $\mathcal{D}_{\boldsymbol{\pi}}$ . For any nonnegative integer $t$ define

\overline{\Delta}(t)=\max_{x,y\in S}d_{\mathsf{TV}}\left(p_{x}^{t},p_{y}^{t}% \right).

•

For any positive $s$ and $t$ , show $\overline{\Delta}(s+t)\leq\overline{\Delta}(s)\cdot\overline{\Delta}(t)$ .
•

For any positive $s$ and $t$ , show $\Delta(s+t)\leq\Delta(s)\cdot\overline{\Delta}(t)$ .
•

For any positive $t$ , show $\Delta(t)\leq\overline{\Delta}(t)\leq 2\Delta(t)$ .

Proof.

Fix initial states $(X_{0},Y_{0})=(x,y)$ . By corollary 1.12.24, there exists a coupling for the chains such that they are optimally coupling at time $t$ , then

\Pr\left[X_{t}\neq Y_{t}\right]=d_{\mathsf{TV}}\left(p_{x}^{t},p_{y}^{t}\right).

Consider any coupling for the chains in such a way that, whenever $X_{t}=Y_{t}$ , then $X_{t+i}=Y_{t+i}$ for all $i\geq 1$ . Then

	$\displaystyle\Pr\left[X_{t+s}\neq Y_{t+s}\right]$	$\displaystyle=\Pr\left[X_{t+s}\neq Y_{t+s}\mid X_{t}\neq Y_{t}\right]\Pr\left[% X_{t}\neq Y_{t}\right]+\Pr\left[X_{t+s}\neq Y_{t+s}\mid X_{t}=Y_{t}\right]\Pr% \left[X_{t}=Y_{t}\right]$
		$\displaystyle=\Pr\left[X_{t+s}\neq Y_{t+s}\mid X_{t}\neq Y_{t}\right]\Pr\left[% X_{t}\neq Y_{t}\right].$

Conditioned on $(X_{t},Y_{t})=(x^{\prime},y^{\prime})$ , again by corollary 1.12.24, there exists a coupling for the chains such that they are optimally coupling at time $t+s$ , then

\Pr\left[X_{t+s}\neq Y_{t+s}\mid X_{t}=x^{\prime},Y_{t}=y^{\prime}\right]=d_{% \mathsf{TV}}\left(p_{x^{\prime}}^{s},p_{y^{\prime}}^{s}\right)\leq\max_{x^{% \prime}\neq y^{\prime}\in S}d_{\mathsf{TV}}\left(p_{x^{\prime}}^{s},p_{y^{% \prime}}^{s}\right)=\overline{\Delta}(s),

(1.21)

Hence,

\Pr\left[X_{t+s}\neq Y_{t+s}\mid X_{t}\neq Y_{t}\right]\leq\overline{\Delta}(s).

(1.22)

Therefore, we prove $\overline{\Delta}(t+s)\leq\overline{\Delta}(t)\cdot\overline{\Delta}(s)$ by showing the following holds for all initial states $x$ and $y$ ,

d_{\mathsf{TV}}\left(p_{x}^{t+s},p_{y}^{t+s}\right)\leq\Pr\left[X_{t+s}\neq Y_% {t+s}\right]\leq\overline{\Delta}(s)\cdot d_{\mathsf{TV}}\left(p_{x}^{t},p_{y}% ^{t}\right)\leq\overline{\Delta}(s)\cdot\overline{\Delta}(t).

Fix initial states $(X_{0},Y_{0})=(x,y)$ , where $y\leftarrow\mathcal{D}_{\boldsymbol{\pi}}$ . Let $(X_{s},Y_{s})$ be optimally coupled at time $s$ by corollary 1.12.24, then

\Pr\left[X_{s}\neq Y_{s}\right]=\Delta_{x}(s).

Continue with the same sticky coupling after time $s$ . Conditioned on $(X_{s},Y_{s})=(x^{\prime},y^{\prime})$ , by corollary 1.12.24, there exists an optimal coupling for the next $t$ steps. Then, again by corollary 1.12.24,

\Pr\left[X_{t+s}\neq Y_{t+s}\mid X_{s}\neq Y_{s}\right]\leq\overline{\Delta}(t)

by eq. 1.21 and eq. 1.22. Hence, $\Delta(t+s)\leq\Delta(s)\cdot\overline{\Delta}(t)$ holds by the same argument.

It is immediate from the triangle inequality that $\overline{\Delta}(t)\leq 2\Delta(t)$ . To see $\Delta(t)\leq\overline{\Delta}(t)$ , by theorem 1.7.13, for any $t$

\mathcal{D}_{\boldsymbol{\pi}}(a)=\sum_{y\in S}\mathcal{D}_{\boldsymbol{\pi}}(% y)\cdot p_{y}^{t}(a),

then by lemma 1.12.2, let $S^{+}\subseteq S$ be the set of all elements in $S$ such that $p_{x}^{t}(a)\geq\mathcal{D}_{\boldsymbol{\pi}}(a)$ , we have

	$\displaystyle\Delta(t)$	$\displaystyle=p_{x}^{t}(S^{+})-\mathcal{D}_{\boldsymbol{\pi}}(S^{+})$
		$\displaystyle=p_{x}^{t}(S^{+})-\sum_{y\in S}\mathcal{D}_{\boldsymbol{\pi}}(y)% \cdot p_{y}^{t}(S^{+})=\sum_{y\in S}\mathcal{D}_{\boldsymbol{\pi}}(y)\cdot% \left(p_{x}^{t}(S^{+})-p_{y}^{t}(S^{+})\right)$
		$\displaystyle\leq\sum_{y\in S}\mathcal{D}_{\boldsymbol{\pi}}(y)\cdot d_{% \mathsf{TV}}\left(p_{x}^{t},p_{y}^{t}\right)\leq\overline{\Delta}(t).$

Alternatively, by definition 1.12.1,

	$\displaystyle\Delta(t)$	$\displaystyle=\frac{1}{2}\sum_{a\in S}\left\|p_{x}^{t}(a)-\mathcal{D}_{% \boldsymbol{\pi}}(a)\right\|$
		$\displaystyle=\frac{1}{2}\sum_{a\in S}\left\|p_{x}^{t}(a)-\sum_{y\in S}\mathcal% {D}_{\boldsymbol{\pi}}(y)\cdot p_{y}^{t}(a)\right\|=\frac{1}{2}\sum_{a\in S}% \left\|\sum_{y\in S}\mathcal{D}_{\boldsymbol{\pi}}(y)\cdot\left(p_{x}^{t}(a)-p_% {y}^{t}(a)\right)\right\|$
		$\displaystyle\leq\frac{1}{2}\sum_{a\in S}\sum_{y\in S}\left\|\mathcal{D}_{% \boldsymbol{\pi}}(y)\cdot\left(p_{x}^{t}(a)-p_{y}^{t}(a)\right)\right\|=\sum_{y% \in S}\mathcal{D}_{\boldsymbol{\pi}}(y)\cdot\frac{1}{2}\sum_{a\in S}\left\|p_{x% }^{t}(a)-p_{y}^{t}(a)\right\|$
		$\displaystyle=\sum_{y\in S}\mathcal{D}_{\boldsymbol{\pi}}(y)\cdot d_{\mathsf{% TV}}\left(p_{x}^{t},p_{y}^{t}\right)\leq\overline{\Delta}(t).$

∎

Remark 1.12.27.

The lemma 1.12.25 and 1.12.26 ¹²¹²12 Quite a bit of the unsticking came from reading Daskalakis’s https://people.csail.mit.edu/costis/6896sp11/. are deriving from [Dob40], and well noted in [LP17].

Lemma 1.12.28.

d_{\mathsf{TV}}\left(p_{x}^{t+s},p_{y}^{t+s}\right)\leq d_{\mathsf{TV}}\left(p% _{x}^{t},p_{y}^{t}\right).

Proof.

Let $A\subseteq S$ be all the elements $a\in S$ such that $p_{x}^{t+s}(a)\geq p_{y}^{t+s}(a)$ . By theorem 1.7.13, we have

d_{\mathsf{TV}}\left(p_{x}^{t+s},p_{y}^{t+s}\right)=p_{x}^{t+s}(A)-p_{y}^{t+s}% (A)=\sum_{c\in S}\left(p_{x}^{t}(c)-p_{y}^{t}(c)\right)p_{c}^{s}(A).

Let $B\subseteq S$ be all the elements $a\in S$ such that $p_{x}^{t}(a)\geq p_{y}^{t}(a)$ , then

d_{\mathsf{TV}}\left(p_{x}^{t+s},p_{y}^{t+s}\right)\leq\sum_{c\in B}\left(p_{x% }^{t}(c)-p_{y}^{t}(c)\right)p_{c}^{s}(A)\leq p_{x}^{t}(B)-p_{y}^{t}(B)=d_{% \mathsf{TV}}\left(p_{x}^{t},p_{y}^{t}\right),

where the second inequality holds by $p_{c}^{s}(A)\leq 1$ , and the last equality holds by lemma 1.12.2. ∎

1.12.4 Geometric Convergence

Theorem 1.12.29 (Geometric Convergence).

Let $\mathbf{P}$ be the transition matrix for a finite, irreducible, aperiodic Markov chain, $m_{j}$ be the smallest entry in the $j^{\mathrm{th}}$ column of $\mathbf{P}$ , and $m=\sum_{j}m_{j}$ . Then, for all $x\in S$ and $t$ ,

\Delta_{x}(t)=d_{\mathsf{TV}}\left(p_{x}^{t},\mathcal{D}_{\boldsymbol{\pi}}% \right)\leq\left(1-m\right)^{t}.

Proof.

Given $m_{j}$ is the smallest entry in the $j^{\mathrm{th}}$ column, then in one step the chain reaches state $j$ with probability at least $m_{j}$ from every state. Consider a coupling similar to the Optimal Coupling lemma 1.12.23, such that the two copies of the chain both move to state $j$ with probability $m_{j}$ . Since $\sum_{j}P_{i,j}=1$ , then $m\leq 1$ .

Concretely, a possible construction for $m<1$ follows

\Pr\left[X_{t+1}=x,Y_{t+1}=y\mid X_{t}=x^{\prime},Y_{t}=y^{\prime}\right]=% \begin{cases}m_{x}&x=y,\\ \dfrac{(P_{x^{\prime},x}-m_{x})(P_{y^{\prime},y}-m_{y})}{1-m}&x\neq y.\end{cases}

The chains couple with probability $m$ at a step, and the probability they haven’t coupled after $t$ steps is $(1-m)^{t}$ . By lemma 1.12.11, $\Delta_{x}(t)\leq\Pr\left[X_{t}\neq Y_{t}\right]=(1-m)^{t}$ . ∎

A side product for theorem 1.12.29 is the following corollary.

Corollary 1.12.30.

If $m=1$ in theorem 1.12.29, then all rows in $\mathbf{P}$ are identical, and $p_{x}^{t}=\mathcal{D}_{\boldsymbol{\pi}}$ for all $x$ and $t\geq 1$ .

Proof.

Since $m_{j}$ is the smallest entry in the $j^{\mathrm{th}}$ column, then for each column, there is no $P_{i,j}$ that is smaller than $m_{j}$ .

On the other hand, by $m=\sum_{j}m_{j}=1$ and $\sum_{j}P_{i,j}=1$ for any $i$ , there is no $m_{j}$ that is smaller than $P_{i,j}$ .

Therefore, any $m_{j}=P_{i,j}$ for all $i$ , which proves all rows in $\mathbf{P}$ are identical.

Moreover, when $m_{j}=p$ , then by the cutset, the outflowing probability is $(1-p)\pi_{j}$ , while inflowing probability is $(1-\pi_{j})p$ , and we have $\pi_{j}=p$ . Since any state reaches state $j$ with probability $P_{i,j}=m_{j}=p$ , this applies to any target state $j\in S$ , and hence reaching stationarity is only 1 step. ∎

Theorem 1.12.31 (Frobenius’s Coin Problem).

Given $m,n\in\mathbb{Z}^{+}$ with $\gcd\left(m,n\right)=1$ , every integer $k>mn-m-n$ can be represented by $am+bn$ where $a,b\in\mathbb{N}$ .

Proof.

We first show that $mn-m-n$ cannot be represented by $am+bn$ where $a,b\in\mathbb{N}$ . Suppose there are $a,b\in\mathbb{N}^{+}$ , such that $mn-m-n=am+bn$ , then

(a+1)m=(m-1-b)n.

(1.23)

But we notice that $mn-m-n<mn$ , then $a<n$ and $b<m$ . Since $m$ and $n$ are coprime, then there is no $a$ and $b$ such that $a+1\leq n$ , $m>m-1-b\geq 0$ , and eq. 1.23 is satisfied.

We now show for every $k>mn-m-n$ , there is a non-negative linear combination representation $am+bn$ . ¹³¹³13 The idea derives from https://math.stackexchange.com/a/66978/794321. Since $m$ and $n$ are coprime, then $\{cn\}_{c\in[0,m-1]}$ represents different residue classes modulo $m$ , and $(m-1)n$ is the first element among the linear representation $am+bn$ that

(m-1)n\equiv-n\pmod{m}.

Hence, for any $q\not\equiv-n\pmod{m}$ , there always exists $b\in[0,m-2]$ such that $bn\equiv q\pmod{m}$ , and $bn<(m-1)n$ . Moreover, the elements $d\in[(m-1)n-m+1,(m-1)n-1]$ lie in distinct residue classes, so for each $d$ , there is always $bn\equiv d\pmod{m}$ . Since $d<(m-1)n$ , then each $d=am+bn$ for some $a$ .

Since every $d\in[(m-1)n-m+1,(m-1)n]$ is representable, and adding $m$ preserves representability, any integer $k>mn-m-n$ is representable. ∎

Exercise 1.12.32 (Exercise 12.6 [MU17]).

The theorem 1.12.29 is useful only if there exists at least one column $j$ in the transition matrix with $m_{j}>0$ . Argue that for any finite, aperiodic, irreducible Markov chain, there exists a time $T$ such that every entry of $\mathbf{P}^{T}$ is nonzero.

Proof.

Since the chain is aperiodic, then for any state $j$ , there are 2 paths back to itself of length $\ell_{j_{0}}$ and $\ell_{j_{1}}$ , such that

\gcd\left(\ell_{j_{0}},\ell_{j_{1}}\right)=1.

By theorem 1.12.31, let $t_{j}=(\ell_{j_{0}}-1)(\ell_{j_{1}}-1)$ , then there always exist loops starting and ending in $j$ of any length $\ell\geq t_{j}$ .

Since the chain is irreducible, then all states are in the same communicating class, such that for any pair of $i\neq j$ , there is a time $t_{i,j}$ such that $i$ reaches $j$ , and $P_{i,j}^{t_{i,j}}>0$ .

Given the threshold $t_{j}$ for self looping path length and $t_{i,j}$ for $i$ to reach $j$ , then there must exist a time

T>\max_{i,j}(t_{i,j}+t_{j}),

such that all entries in $\mathbf{P}^{T}$ are positive. ∎

A more general result than theorem 1.12.29 is the following: suppose we upper-bound $\tau(c)$ for some constant $c\leq 1/2$ , then we can bootstrap a bound for $\tau(\varepsilon)$ for any $\varepsilon>0$ .

Theorem 1.12.33.

Let $M_{t}$ be a finite, irreducible, aperiodic Markov chain with $\tau(c)\leq T$ for some $c\leq 1/2$ , then for $M_{t}$ ,

\tau(\varepsilon)\leq\left\lceil\frac{\ln\varepsilon}{\ln(2c)}\right\rceil T.

Proof.

The proving strategy is similar to 1.12.26. Since for all initial states $x\in S$ , we have

\Delta_{x}(T)=d_{\mathsf{TV}}\left(p_{x}^{T},\mathcal{D}_{\boldsymbol{\pi}}% \right)\leq c,

then by the triangle inequality, $d_{\mathsf{TV}}\left(p_{x}^{T},p_{y}^{T}\right)\leq 2c$ for all $x,y\in S$ , and hence $\overline{\Delta}(T)\leq 2c$ .

Therefore, on a pair of initial states $x, y$ , we couple the copies of $M_{t}$ such that $(X_{T},Y_{T})$ are optimally coupled by

\Pr\left[X_{T}\neq Y_{T}\right]=d_{\mathsf{TV}}\left(p_{x}^{T},p_{y}^{T}\right)

from lemma 1.12.23.

Then we couple the chains such that: if $X_{T}=Y_{T}$ , they stay together onwards; otherwise, $(X_{2T},Y_{2T})$ are optimally coupled conditioned that $(X_{T},Y_{T})=(x^{\prime},y^{\prime})$ by

\Pr\left[X_{2T}\neq Y_{2T}\mid X_{T}=x^{\prime},Y_{T}=y^{\prime}\right]=d_{% \mathsf{TV}}\left(p_{x^{\prime}}^{T},p_{y^{\prime}}^{T}\right).

By induction, we have

\Pr\left[X_{kT}\neq Y_{kT}\mid X_{0}=x,Y_{0}=y\right]\leq(2c)^{k},

then $\Delta_{x}(kT)\leq(2c)^{k}$ for all $x\in S$ by lemma 1.12.10. If $(2c)^{k}=\varepsilon$ , then

k\leq\left\lceil\frac{\ln\varepsilon}{\ln\left(2c\right)}\right\rceil,

and we have $\tau(\varepsilon)\leq kT$ by lemma 1.12.10. ∎

1.12.5 Application in Approximately Sampling Proper Colorings

We now present a Markov chain Monte Carlo (MCMC) process that generates an almost uniformly at random sample of a proper coloring of a graph, then use a coupling technique to show that it is rapidly mixing.

The Markov chain on proper coloring works as follows: At each step, choose a vertex $v$ and a color $\ell$ uniformly at random. Recolor vertex $v$ with color $\ell$ if the new coloring is proper, that $v$ is not neighboring a vertex colored $\ell$ , or otherwise let the state of the chain be unchanged.

The Markov chain is aperiodic, as there exists loop of length 1 back to itself; and it is irreducible if $c\geq\Delta+2$ , as recoloring in any order can be unblocked by recoloring a later unrecolored neighbor to an unconflicting color: the degree of the graph is at most $\Delta$ , then $\left|\Gamma^{+}(v)\right|\leq\Delta+1$ for every vertex, such that the recoloring is always unblocked. Therefore, the Markov chain is ergodic and has stationary distribution being uniform distribution.

When $c\geq 4\Delta+1$ , we can use a trivial coupling for $(X_{t},Y_{t})$ by choosing the same vertex and color at each step, allowing us to almost uniformly sample colorings efficiently.

Theorem 1.12.34.

For an $n$ -vertex graph with maximum degree $\Delta$ , the mixing time of the graph-coloring Markov chain satisfies

\tau\left(\varepsilon\right)\leq\left\lceil\frac{nc}{c-4\Delta}\ln\left(\frac{% n}{\varepsilon}\right)\right\rceil,

provided that $c\geq 4\Delta+1$ .

Proof.

The proof strategy is similar to example 1.12.17. Fix initial states $x, y$ be distinct $c$ -colorings. Let $D_{t}$ be the set of vertices with different colors in the two chains at time $t$ , and let $d_{t}=\left|D_{t}\right|$ .

Consider any vertex $v\in D_{t}$ , but colored same after a move. There are at least $c-2\Delta$ colors that have not appeared on the at most $2\Delta$ neighbors among 2 chains, then

\Pr\left[d_{t+1}=d_{t}-1\mid d_{t}>0\right]\geq\frac{d_{t}}{n}\cdot\frac{c-2% \Delta}{c}.

Consider any vertex $v\in V\setminus D_{t}$ , but colored differently after a move. It has to be the case that the move succeeded in one chain, but not the other. Moreover, $v$ must have at least one neighbor in $D_{t}$ , such that the move’s color may work in one chain, but not the other. Hence, for every $w\in D_{t}$ , it can affect at most $\Delta$ neighbors with 2 colors, and

\Pr\left[d_{t+1}=d_{t}+1\mid d_{t}>0\right]\leq\frac{\Delta d_{t}}{n}\cdot% \frac{2}{c}.

By the linearity of expectation,

\operatorname*{\mathbb{E}}\left[d_{t+1}\mid d_{t}\right]\leq d_{t}+\frac{% \Delta d_{t}}{n}\cdot\frac{2}{c}-\frac{d_{t}}{n}\cdot\frac{c-2\Delta}{c}=d_{t}% \cdot\left(1-\frac{c-4\Delta}{nc}\right),

then by the Markov inequality argument,

\Pr\left[d_{t}\geq 1\right]\leq\operatorname*{\mathbb{E}}\left[d_{t}\right]% \leq\operatorname*{\mathbb{E}}\left[d_{0}\right]\cdot\left(1-\frac{c-4\Delta}{% nc}\right)^{t}\leq n\left(1-\frac{c-4\Delta}{nc}\right)^{t}\leq n\exp\left(-% \frac{c-4\Delta}{nc}\cdot t\right).

The proof is immediate by lemma 1.12.10. ∎

We then show how to improve the coupling to reduce the number of colors necessary to $2\Delta+1$ . On one hand, for $v\in D_{t}$ , if some neighboring vertices are same colored in both chains, then the color options should be much greater than $c-2\Delta$ . On the other hand, for $v\in V\setminus D_{t}$ , we can decrease the number of bad moves of increasing differences by a careful coupling.

Theorem 1.12.35.

For an $n$ -vertex graph with maximum degree $\Delta$ , the mixing time of the graph-coloring Markov chain satisfies

\tau\left(\varepsilon\right)\leq\left\lceil\frac{nc}{c-2\Delta}\ln\left(\frac{% n}{\varepsilon}\right)\right\rceil,

provided that $c\geq 2\Delta+1$ .

Proof.

The proof strategy is similar to 1.12.20.

We reuse all notions in theorem 1.12.34, and let $A_{t}=V\setminus D_{t}$ be the set of vertices that are colored same in both chains. For $v\in A_{t}$ , $d^{\prime}(v)=\left|\Gamma(v)\cap D_{t}\right|$ , that is the number of neighboring vertices colored differently in both chains; for $w\in D_{t}$ , $d^{\prime}(w)=\left|\Gamma(w)\cap A_{t}\right|$ , that is the number of neighboring vertices colored same in both chains.

Hence, we explore the invariant that

m=\sum_{v\in A_{t}}d^{\prime}(v)=\sum_{w\in D_{t}}d^{\prime}(w),

which can be viewed as the number of edges between vertices in $D_{t}$ and vertices in $A_{t}$ .

For $v\in D_{t}$ , a move on $v$ sends $v$ to $A_{t+1}$ if both chains recolor $v$ to the same valid color. Taking into account the neighbors of $v$ that are colored the same in both chains, the forbidden color options for $v$ have union size at most $2\Delta-d^{\prime}(v)$ , since those $d^{\prime}(v)$ neighbors are double-counted. Therefore,

\Pr\left[d_{t+1}=d_{t}-1\mid d_{t}>0\right]\geq\frac{1}{n}\sum_{v\in D_{t}}% \frac{c-2\Delta+d^{\prime}(v)}{c}=\frac{1}{n}\cdot\frac{d_{t}(c-2\Delta)+m}{c}.

For $w\in A_{t}$ , but colored distinctly after move by $w\in D_{t+1}$ , consider the coupling in a similar way in 1.12.20.

Suppose in the particular case where $d^{\prime}(w)=1$ , then instead of assigning $w$ the same color and causing 2 potential bad moves, on $c_{1}$ and $c_{2}$ being the disagreeing colors of neighbor $v$ of $w$ , if $w$ is assigned one of the two colors in $X_{t}$ , assign the other color to $w$ in $Y_{t}$ . In this case, 2 bad moves are halved down to 1, as either they both fail, or they both move through and cause 1 more difference.

Moving to the general case. Let $S_{1}(w)$ be the colors of neighboring vertices of $w$ over $X_{t}$ that are in $D_{t}$ , and $S_{2}(w)$ be the colors of neighboring vertices of $w$ over $Y_{t}$ that are in $D_{t}$ . Using the same strategy in 1.12.20, we pair the distinct colors between $S_{1}(w)$ and $S_{2}(w)$ as much as possible: if $c_{1}\in S_{1}(w)$ is chosen for one chain, $c_{2}\in S_{2}(w)$ is chosen for the other; otherwise they are mapped to the same color. In this way, the bad moves are reduced down to $\max\left(\left|S_{1}(w)\right|,\left|S_{2}(w)\right|\right)\leq d^{\prime}(w)$ . As a result, we have

\Pr\left[d_{t+1}=d_{t}+1\mid d_{t}>0\right]\leq\frac{1}{n}\sum_{w\in A_{t}}% \frac{d^{\prime}(w)}{c}=\frac{m}{cn}.

By the linearity of expectation,

\operatorname*{\mathbb{E}}\left[d_{t+1}\mid d_{t}\right]\leq d_{t}+\frac{m}{cn% }-\frac{1}{n}\cdot\frac{d_{t}(c-2\Delta)+m}{c}=d_{t}\cdot\left(1-\frac{c-2% \Delta}{nc}\right),

then by the Markov inequality argument,

\Pr\left[d_{t}\geq 1\right]\leq\operatorname*{\mathbb{E}}\left[d_{t}\right]% \leq\operatorname*{\mathbb{E}}\left[d_{0}\right]\cdot\left(1-\frac{c-2\Delta}{% nc}\right)^{t}\leq n\cdot\exp\left(-\frac{c-2\Delta}{nc}\cdot t\right).

The proof is immediate by lemma 1.12.10. ∎

Remark 1.12.36.

By definition 1.12.6, the theorem 1.12.34 and theorem 1.12.35 are rapidly mixing.

Remark 1.12.37.

The theorem 1.12.34 and theorem 1.12.35 are from [Jer95].

1.12.6 Path Coupling

The motivation of using “path coupling” is that, it starts with coupling between pairs of states differ in small ways, then generalize to arbitrary pairs of states. It may be easier to construct coupling of adjacent states, and any pairs of states can be connected with a path, then we couple all pairs of states along the path, such that the expected distance contracts at each step; by summing along the path, this implies contraction for any pairs of states.

Similar to example 1.12.17, 1.12.20, theorem 1.12.34, and theorem 1.12.35, we conclude by utilizing the expected-distance bound for bounding disagreement probability via a Markov inequality argument, hence bounding the mixing-time with lemma 1.12.10. Eventually, this makes coupling argument easier to be established.

Example 1.12.38 (Markov Chain for Independent Sets).

Consider a Markov chain for sampling independent sets over a graph with $\Delta\leq 4$ . Let $X_{t}$ be the independent set at time $t$ . At a step, the chain samples $(u,v)\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}E$ , and

•

With probability $1/3$ , $X_{t+1}=X_{t}\setminus\{u,v\}$ .
•

With probability $1/3$ , let $Y=X_{t}\setminus\{u\}\cup\{v\}$ . If $Y$ is an independent set, $X_{t+1}=Y$ ; otherwise, $X_{t+1}=X_{t}$ .
•

With probability $1/3$ , let $Y=X_{t}\setminus\{v\}\cup\{u\}$ . If $Y$ is an independent set, $X_{t+1}=Y$ ; otherwise, $X_{t+1}=X_{t}$ .

Similar to 1.12.16, the stationary distribution of $X_{t}$ is uniform over all independent sets: By the cutset theorem 1.7.56, the total probability of adjacent states transitioning to the current state is the same as the total probability that the current state transitioning to adjacent states. Since $P_{a,b}=(3\left|E\right|)^{-1}$ for any pair of adjacent states $(a,b)$ , then uniform distribution is a trivial solution.

We start by coupling a pair of states $(X_{t},Y_{t})$ that differ by just one vertex, and this coupling can be extended to all pairs of states. Let $Z_{t}=\left(X_{t}\setminus Y_{t}\right)\cup\left(Y_{t}\setminus X_{t}\right)$ , and we say a vertex $v$ is bad if $v\in Z$ ; otherwise $v$ is good. Let $d_{t}=\left|Z_{t}\right|$ , then $d_{t}$ is the random variable counting bad vertices.

We continue by assuming $d_{t}=1$ , and WLOG let $X_{t}=I$ , $Y_{t}=I\cup\{x\}$ . We apply a simple coupling by performing the same move on both chains, and show $\operatorname*{\mathbb{E}}\left[d_{t+1}\mid d_{t}\right]\leq d_{t}$ when $d_{t}=1$ , or equivalently, $\operatorname*{\mathbb{E}}\left[d_{t+1}-d_{t}\mid d_{t}=1\right]\leq 0$ .

Since a change in $d_{t}$ is caused only by a move involving $x$ or the neighbors of $x$ , we restrict our attention to the edges sampled adjacent to $x$ , neighbors of $x$ , or neighbors of neighbors of $x$ ¹⁴¹⁴14 Self noting: need to consider the case where an edge is chosen with one end in $I$ , and the other is a neighbor of $x$ . . Let $\delta_{z}$ be a random variable over $\{-1,1\}$ for a vertex $z$ between time $t$ and $t+1$ : $\delta_{z}=1$ when $z$ goes from good to bad, and $\delta_{z}=-1$ when $z$ goes from bad to good. By linearity of expectation,

\operatorname*{\mathbb{E}}\left[d_{t+1}-d_{t}\mid d_{t}=1\right]=\operatorname% *{\mathbb{E}}\left[\sum_{w\in\Gamma^{+}\left(\Gamma^{+}(x)\right)}\delta_{w}~{% }\middle|~{}d_{t}=1\right]=\sum_{w\in\Gamma^{+}\left(\Gamma^{+}(x)\right)}% \operatorname*{\mathbb{E}}\left[\delta_{w}\mid d_{t}=1\right].

We shall show that when $\Delta\leq 4$ , $\operatorname*{\mathbb{E}}\left[\delta_{w}\mid d_{t}=1\right]\leq 0$ . For each vertex $y\in\Gamma(x)$ :

•

If $\left|\Gamma(y)\cap I\right|\geq 2$ , only moves on edge $(x,y)$ changes $d_{t+1}-d_{t}$ , either removing $y$ and adding $x$ , or removing $\{x,y\}$ .

With probability $2\cdot(3\left|E\right|)^{-1}$ , if the $(x,y)$ edge is chosen, then $d_{i+1}-d_{i}$ decreases by 1.
•
If $\left|\Gamma(y)\cap I\right|=0$ , for moves on edges with $y$ ,
- –
  
  For increasing $d_{t+1}-d_{t}$ , for $w\in\Gamma(y)\setminus\{x\}$ , removing $w$ and adding $x$ works on $X_{t}$ but fails on $Y_{t}$ .
  
  Since $\left|\Gamma(y)\setminus\{x\}\right|\leq 3$ by $\Delta\leq 4$ , by union bound, $d_{t+1}-d_{t}$ increases with probability at most $3\cdot(3\left|E\right|)^{-1}=\left|E\right|^{-1}$ .
- –
  
  For decreasing $d_{t+1}-d_{t}$ , any option among 3 possible moves on $(x,y)$ decreases bad vertices.
  
  With probability $\left|E\right|^{-1}$ , if the $(x,y)$ edge is chosen, then $d_{t+1}-d_{t}$ decreases by 1.
Hence, for moves on edges with $y$ , $\operatorname*{\mathbb{E}}\left[d_{t+1}-d_{t}\mid d_{t}=1\right]\leq 0$ .
•
If $\left|\Gamma(y)\cap I\right|=1$ , and let $z\in I\cap\Gamma(y)$ , for moves on edges with $y$ ,
- –
  
  For increasing $d_{t+1}-d_{t}$ , removing $z$ and adding $y$ works on $X_{t}$ but not $Y_{t}$ .
  
  With probability $(3\left|E\right|)^{-1}$ , $d_{t+1}-d_{t}$ increases by 2 if $(y,z)$ edge is chosen and removes $z$ and adds $y$ .
- –
  
  For decreasing $d_{t+1}-d_{t}$ , both adding $x$ and removing $y$ , and removing $\{x,y\}$ works.
  
  With probability $2\cdot(3\left|E\right|)^{-1}$ , if the $(x,y)$ edge is chosen, then $d_{t+1}-d_{t}$ decreases by 1.
Hence, for move on edge with $y$ , $\operatorname*{\mathbb{E}}\left[d_{t+1}-d_{t}\mid d_{t}=1\right]=0$ .

Since for every pair of edge, we have

\sum_{w\in\Gamma^{+}\left(\Gamma^{+}(x)\right)}\operatorname*{\mathbb{E}}\left% [\delta_{w}\mid d_{t}=1,\text{move on edge }(a,b)\right]\leq 0,

as was shown in the previous discussion of $y\in\Gamma(x)$ , then

	$\displaystyle\operatorname*{\mathbb{E}}\left[d_{t+1}-d_{t}\mid d_{t}=1\right]$	$\displaystyle=\sum_{w\in\Gamma^{+}\left(\Gamma^{+}\left(x\right)\right)}% \operatorname*{\mathbb{E}}\left[\delta_{w}\mid d_{t}=1\right]$
		$\displaystyle=\frac{1}{\left\|E\right\|}\sum_{w\in\Gamma^{+}\left(\Gamma^{+}% \left(x\right)\right)}\sum_{(a,b)\in E}\operatorname*{\mathbb{E}}\left[\delta_% {w}\mid d_{t}=1,\text{move on edge }(a,b)\right]$
		$\displaystyle=\frac{1}{\left\|E\right\|}\sum_{(a,b)\in E}\sum_{w\in\Gamma^{+}% \left(\Gamma^{+}\left(x\right)\right)}\operatorname*{\mathbb{E}}\left[\delta_{% w}\mid d_{t}=1,\text{move on edge }(a,b)\right]\leq 0.$

We now generalize the coupling for $d_{t}>1$ case. To couple $(X_{t},Y_{t})$ where $d_{t}>1$ , we create a chain of states

Z_{0}=X_{t},\ldots,Z_{d_{t}}=Y_{t},

where neighboring pair of states $(Z_{i-1},Z_{i})$ has $\left|Z_{i-1}\setminus Z_{i}\right|+\left|Z_{i}\setminus Z_{i-1}\right|=1$ , that each successive $Z_{i}$ is obtained from $Z_{i-1}$ by either removing an element in $X_{t}\setminus Y_{t}$ or adding an element in $Y_{t}\setminus X_{t}$ .

Our coupling arises as follows. When a move is made in $Z_{0}=X_{t}$ , the coupling for $d_{t}=1$ case gives a move for the state $Z_{1}$ . This move in $Z_{1}$ can similarly be coupled with a move in state $Z_{2}$ , and so on, until the move in $Z_{d_{t}-1}$ yields a move for $Z_{d_{t}}=Y_{t}$ . Let $Z_{i}^{\prime}$ be the state after the move is made from state $Z_{i}$ , and define

\Delta\left(Z_{i-1}^{\prime},Z_{i}^{\prime}\right)=\left|Z_{i-1}^{\prime}% \setminus Z_{i}^{\prime}\right|+\left|Z_{i}^{\prime}\setminus Z_{i-1}^{\prime}% \right|.

Since $\operatorname*{\mathbb{E}}\left[d_{i+1}-d_{i}\mid d_{i}=1\right]\leq 0$ , then

\operatorname*{\mathbb{E}}\left[\Delta\left(Z_{i-1}^{\prime},Z_{i}^{\prime}% \right)\right]\leq 1.

Moreover, note that $(Z_{0}^{\prime},Z_{d_{t}}^{\prime})=(X_{t+1},Y_{t+1})$ , then by the triangle inequality for sets

\left(A\setminus C\right)\cup\left(C\setminus A\right)\subseteq\left(A% \setminus B\right)\cup\left(B\setminus C\right)\cup\left(B\setminus A\right)% \cup\left(C\setminus B\right),

as for any element $a\in A\setminus C$ , either $a\in B$ , then $a\in B\setminus C$ ; or $a\notin B$ , then $a\in A\setminus B$ . Then

\Delta\left(Z_{0}^{\prime},Z_{d_{t}}^{\prime}\right)=\left|Z_{0}^{\prime}% \setminus Z_{d_{t}}^{\prime}\right|+\left|Z_{d_{t}}^{\prime}\setminus Z_{0}^{% \prime}\right|\leq\sum_{i\in[1,d_{t}]}\left|Z_{i-1}^{\prime}\setminus Z_{i}^{% \prime}\right|+\sum_{i\in[1,d_{t}]}\left|Z_{i}^{\prime}\setminus Z_{i-1}^{% \prime}\right|,

and by linearity of expectation,

\operatorname*{\mathbb{E}}\left[d_{t+1}\mid d_{t}\right]=\operatorname*{% \mathbb{E}}\left[\Delta\left(Z_{0}^{\prime},Z_{d_{t}}^{\prime}\right)\right]% \leq\sum_{i\in[1,d_{t}]}\operatorname*{\mathbb{E}}\left[\Delta\left(Z_{i-1}^{% \prime},Z_{i}^{\prime}\right)\right]\leq d_{t},

and eventually

\operatorname*{\mathbb{E}}\left[d_{t+1}\right]=\operatorname*{\mathbb{E}}\left% [\operatorname*{\mathbb{E}}\left[d_{t+1}\mid d_{t}\right]\right]\leq% \operatorname*{\mathbb{E}}\left[d_{t}\right].

Suppose $\operatorname*{\mathbb{E}}\left[d_{t+1}\mid d_{t}\right]\leq\beta d_{t}$ for $\beta<1$ , the rest is taken over by lemma 1.12.10, given a sufficient number of steps and a Markov inequality argument.

Remark 1.12.39.

The example 1.12.38 derives from [BD97].

The example 1.12.38 illustrates the philosophy of path coupling: global distance is controlled by understanding local disagreements. Rather than constructing a coupling for arbitrary pairs of states, we first choose a pre-metric on the state space, whose edges represent elementary discrepancies between configurations.

In example 1.12.38, the natural choice is to connect two states when they differ at a vertex, so that the induced path metric is Hamming distance. Once such a pre-metric is fixed, any pair of states can be joined by a shortest path of discrepancies, and contraction on adjacent pairs propagates to contraction for all pairs. Thus the pre-metric is the structure that makes the path-coupling argument possible: it identifies the right local geometry of the state space.

Definition 1.12.40 (Pre-Metric).

A pre-metric on $\Omega$ is a positively-weighted connected undirected graph such that all edges are shortest paths. More specifically, if $(x,y)$ are adjacent in the pre-metric, the weight of the edge should be the least weight of any path from $x$ to $y$ in the pre-metric.

Theorem 1.12.41 (Path Coupling Theorem [BD97]).

Suppose there exists a coupling defined for all adjacent pair of states in the pre-metric such that for all adjacent $(X,Y)$ ,

\operatorname*{\mathbb{E}}\left[d\left(X^{\prime},Y^{\prime}\right)\mid X,Y% \right]\leq\left(1-\alpha\right)d\left(X,Y\right),

where $d$ is the shortest path metric, then this coupling can be extended to a coupling between all pair of states that also satisfy the contraction inequality.

Exercise 1.12.42 (Exercise 12.7 [MU17]).

Continuing from example 1.12.38, we have shown there is $\beta<1$ such that

\operatorname*{\mathbb{E}}\left[d_{t+1}\mid d_{t}\right]\leq\beta d_{t}.

Let $d^{\ast}$ be the maximum distance over all possible pairs of initial states for the coupling.

•

Give an upper bound for $\tau(\varepsilon)$ in terms of $\beta$ and $d^{\ast}$ .
•

Suppose we have $\operatorname*{\mathbb{E}}\left[d_{t+1}\mid d_{t}\right]\leq d_{t}$ , $d_{t+1}\in[d_{t}-1,d_{t}+1]$ , and $\Pr\left[d_{t}\neq d_{t+1}\right]\geq\gamma$ .

Give an upper bound for $\tau(\varepsilon)$ in terms of $\beta$ , $d^{\ast}$ , and $\gamma$ .
•

Show the mixing time of the graph coloring chain in theorem 1.12.34 and theorem 1.12.35, is $\mathsf{poly}(\left|V\right|,\ln(1/\varepsilon))$ , even when the number of colors is only $2\Delta$ .
•

Show the mixing time of the Markov chain for independent sets in example 1.12.38 is $\mathsf{poly}(\left|V\right|,\ln(1/\varepsilon))$ .

Proof.

Suppose we have the $\beta<1$ , that $\operatorname*{\mathbb{E}}\left[d_{t+1}\mid d_{t}\right]\leq\beta d_{t}$ , then

\operatorname*{\mathbb{E}}\left[d_{t+1}\right]=\operatorname*{\mathbb{E}}\left% [\operatorname*{\mathbb{E}}\left[d_{t+1}\mid d_{t}\right]\right]\leq\beta\cdot% \operatorname*{\mathbb{E}}\left[d_{t}\right].

Since $d^{\ast}$ is the maximum distance over all possible pairs of states for the coupling, then

\operatorname*{\mathbb{E}}\left[d_{t}\right]\leq\beta^{t}\cdot d^{\ast}.

By the same Markov inequality argument, we have

\Pr\left[d_{t}\geq 1\right]\leq\operatorname*{\mathbb{E}}\left[d_{t}\right]% \leq\beta^{t}\cdot d^{\ast}.

Supposing $\varepsilon=\beta^{t}\cdot d^{\ast}$ , then

\tau\left(\varepsilon\right)\leq\left\lceil\frac{\ln\varepsilon-\ln d^{\ast}}{% \ln\beta}\right\rceil.

If $\Pr\left[d_{t+1}\neq d_{t}\right]\geq\gamma$ , then let $p^{+}+p^{-}=\Pr\left[d_{t+1}\neq d_{t}\right]$ , where $p^{+}=\Pr\left[d_{t+1}=d_{t}+1\right]$ , and $p^{-}=\Pr\left[d_{t+1}=d_{t}-1\right]$ . Consider $d_{t}$ as a Markov chain for random walking over $[0,d^{\ast}]$ , where $d_{0}=d^{\ast}$ , state $0$ is the absorbing state, and the transition probability from state $d^{\ast}$ to state $d^{\ast}-1$ is $p^{+}+p^{-}=\Pr\left[d_{t+1}\neq d_{t}\right]$ . Let $h_{i,0}$ be the expected number of steps to be absorbed in $0$ , then we have the following linear system

	$\displaystyle(p^{+}+p^{-})h_{1,0}$	$\displaystyle=1+p^{+}h_{2,0}+p^{-}h_{0,0}$
	$\displaystyle(p^{+}+p^{-})h_{2,0}$	$\displaystyle=1+p^{+}h_{3,0}+p^{-}h_{1,0}$
		$\displaystyle\ldots$
	$\displaystyle(p^{+}+p^{-})h_{d^{\ast}-1,0}$	$\displaystyle=1+p^{+}h_{d^{\ast},0}+p^{-}h_{d^{\ast}-2,0}$
	$\displaystyle(p^{+}+p^{-})h_{d^{\ast},0}$	$\displaystyle=1+p^{+}h_{d^{\ast}-1,0}+p^{-}h_{d^{\ast}-1,0},$

where $h_{0,0}=0$ .

The chain is lazy, as it stays put with probability at most $1-\gamma$ . We continue by deriving the expected number of active moves. Let $q=\Pr\left[d_{i+1}\neq d_{i}\right]$ , then conditioned that a move is made,

	$\displaystyle q^{+}$	$\displaystyle=\Pr\left[d_{i+1}=d_{i}+1\mid d_{i+1}\neq d_{i}\right]=p^{+}/q$
	$\displaystyle q^{-}$	$\displaystyle=\Pr\left[d_{i+1}=d_{i}-1\mid d_{i+1}\neq d_{i}\right]=p^{-}/q,$

and let $g_{i,0}$ be the expected number of active moves, then

	$\displaystyle g_{1,0}$	$\displaystyle=1+q^{+}g_{2,0}+q^{-}g_{0,0}$
	$\displaystyle g_{2,0}$	$\displaystyle=1+q^{+}g_{3,0}+q^{-}g_{1,0}$
		$\displaystyle\ldots$
	$\displaystyle g_{d^{\ast}-1,0}$	$\displaystyle=1+q^{+}g_{d^{\ast},0}+q^{-}g_{d^{\ast}-2,0}$
	$\displaystyle g_{d^{\ast},0}$	$\displaystyle=1+g_{d^{\ast}-1,0},$

where $g_{0,0}=h_{0,0}=0$ . Since $q^{+}+q^{-}=1$ , and $q^{-}\geq 1/2$ , then consider a Markov chain with $q^{+}=q^{-}=1/2$ , and

g_{i,0}=(2d^{\ast}-i)i,

and therefore $g_{d^{\ast},0}=\left(d^{\ast}\right)^{2}$ . Since $q^{-}\geq 1/2$ , the real $g_{d^{\ast},0}\leq\left(d^{\ast}\right)^{2}$ .

Since $\Pr\left[d_{t+1}\neq d_{t}\right]\geq\gamma$ , then the expected wait time before an active move is at most $\gamma^{-1}$ , and therefore

h_{d^{\ast},0}\leq\gamma^{-1}\left(d^{\ast}\right)^{2}.

Hence, when $L=\left\lceil 2\gamma^{-1}\left(d^{\ast}\right)^{2}\right\rceil$ , let $T$ be the random variable for the steps before being absorbed, by Markov inequality

\Pr\left[T\geq L\right]\leq\frac{\operatorname*{\mathbb{E}}\left[T\right]}{L}% \leq\frac{1}{2}.

Similar to 1.12.19, by the Markov property, $\Pr\left[T\geq kL\right]\leq 2^{-k}$ . Then when $\varepsilon=2^{-k}$ ,

\tau\left(\varepsilon\right)\leq\left\lceil\log\frac{1}{\varepsilon}\right% \rceil L.

(1.24)

For path coupling in the Markov chain sampling graph coloring, we first show a pre-metric over all valid coloring, such that any valid pair of adjacent valid coloring differ at the color of a single vertex. Supposing that $X_{0}$ and $Y_{0}$ are disagreeing only at $v$ , let $c_{1}$ and $c_{2}$ be the colors of $v$ at $X_{0}$ and $Y_{0}$ , and apply the prior coupling in theorem 1.12.35: if we change $w\in\Gamma(v)$ in $X_{t}$ to one of the colors in $\{c_{1},c_{2}\}$ , we change $w$ in $Y_{t}$ to the other color; otherwise, apply the same move on both chains.

One thing to beware is, in theorem 1.12.34 and theorem 1.12.35, the distance function $d_{t}$ is measuring the number of disagreeing vertices, while the current $d_{t}$ is measuring the minimal number of steps to transition from one valid coloring to the other, as the pre-metric is defined on $\Omega$ of valid colorings. Therefore, after a bad move in the coupling, where $v$ is $c_{1}$ , $w$ is $c_{2}$ in $X_{t}$ , while $v$ is $c_{2}$ , $w$ is $c_{1}$ in $Y_{t}$ , the $d_{t}$ is 3 rather than 2 ¹⁵¹⁵15 Self noting: check Daskalakis’s slides https://people.csail.mit.edu/costis/6896sp11/lec7s.pdf. .

We continue bounding $\operatorname*{\mathbb{E}}\left[d_{t+1}\mid d_{t}=1\right]$ . Since $v$ can be corrected with at least $c-\Delta$ colors, then

\Pr\left[d_{t+1}=d_{t}-1\mid d_{t}=1\right]\geq\frac{1}{n}\cdot\frac{c-\Delta}% {c}.

On the other hand, a bad move happens only on $\Gamma(v)$ with 1 color configuration on both chains, hence

\Pr\left[d_{t+1}=d_{t}+2\mid d_{t}=1\right]\leq\frac{\Delta}{n}\cdot\frac{1}{c}.

Therefore,

\operatorname*{\mathbb{E}}\left[d_{t+1}\mid d_{t}=1\right]\leq 1+2\cdot\frac{% \Delta}{n}\cdot\frac{1}{c}-\frac{1}{n}\cdot\frac{c-\Delta}{c}=1-\frac{c-3% \Delta}{nc}=\beta.

Now let the maximal distance be $d^{\ast}$ , and construct a path joined by adjacent valid states over $\Omega$ with the pre-metric by $Z_{0}=X_{t}$ and $Z_{d_{t}}=Y_{t}$ . When a move is made on $Z_{i}$ , the move from coupling is made on $Z_{i+1}$ , and let $Z_{i}^{\prime}$ be the state after the move is made on state $Z_{i}$ . By linearity of expectation,

\operatorname*{\mathbb{E}}\left[d_{t+1}\mid d_{t}\right]=\operatorname*{% \mathbb{E}}\left[\Delta\left(Z_{0}^{\prime},Z_{d_{t}}^{\prime}\right)\right]% \leq\sum_{i\in[1,d_{t}]}\operatorname*{\mathbb{E}}\left[\Delta\left(Z_{i-1}^{% \prime},Z_{i}^{\prime}\right)\right]\leq d_{t}\cdot\beta,

where $\Delta(Z_{i-1}^{\prime},Z_{i}^{\prime})$ is defined as the distance between $Z_{i-1}^{\prime}$ and $Z_{i}^{\prime}$ in the pre-metric, and finally,

\operatorname*{\mathbb{E}}\left[d_{t}\right]=\operatorname*{\mathbb{E}}\left[% \operatorname*{\mathbb{E}}\left[d_{t}\mid d_{t-1}\right]\right]\leq% \operatorname*{\mathbb{E}}\left[d_{t-1}\right]\cdot\beta\leq d^{\ast}\cdot% \beta^{t},

which gives a similar result to theorem 1.12.34 and theorem 1.12.35 but $c\geq 3\Delta+1$ .

Now we use Hamming distance as pre-metric: the states along the path are not all valid states, yet it still serves as a path coupling. Let $\tilde{\Omega}$ be the set for all possible coloring states, and $\Omega\subseteq\tilde{\Omega}$ , then any adjacent states $(X_{0},Y_{0})$ are still differing at the color of a vertex, but they are not necessarily valid states.

A move is made by choosing a vertex $v$ and a color $c$ , if $c$ is not appearing in the neighboring $\Gamma(v)$ . One observation is, if $X_{0}\in\Omega$ , then the chain stays in $\Omega$ ; otherwise, the chain will turn into $\Omega$ at some time step, and it will stay in $\Omega$ . Hence, coupling any pair of $(X_{0},Y_{0})\in\Omega^{2}$ over the enlarged state space $\tilde{\Omega}$ still preserves the marginal probabilities, while the path may pass through $\tilde{\Omega}\setminus\Omega$ does not hurt the argument, because the path is only used to define the metric for the path coupling theorem.

Applying the same coupling in theorem 1.12.35, conditioned that $(X_{0},Y_{0})$ are adjacent in the Hamming metric, then on the bad move, $d_{t}$ increases by 1. Therefore, with the same probability bounds on distance changing,

\operatorname*{\mathbb{E}}\left[d_{t+1}\mid d_{t}=1\right]\leq 1-\frac{c-2% \Delta}{nc}=\beta,

and by the same path coupling argument, $\operatorname*{\mathbb{E}}\left[d_{t}\right]\leq\operatorname*{\mathbb{E}}% \left[d_{t-1}\right]\cdot\beta$ gives the same result as theorem 1.12.35 for $c\geq 2\Delta+1$ .

For $c=2\Delta$ , $\operatorname*{\mathbb{E}}\left[d_{t+1}\mid d_{t}\right]\leq d_{t}$ . We can loosely lower bound by

\Pr\left[d_{t+1}\neq d_{t}\right]\geq\gamma=(nc)^{-1},

as there is at least 1 move fixing a disagreeing vertex, then the eq. 1.24 is $\mathsf{poly}\left(\left|V\right|=n,\log\left(1/\varepsilon\right)\right)$ .

For independent set sampling in example 1.12.38, we can also loosely lower bound by

\Pr\left[d_{t+1}\neq d_{t}\right]\geq\gamma=(3n)^{-1},

as a disagreeing vertex $v$ can be removed by choosing an edge $(u,v)$ , and removing $\{u,v\}$ . By eq. 1.24, the mixing time bound is $\mathsf{poly}\left(\left|V\right|=n,\log\left(1/\varepsilon\right)\right)$ . ∎

Exercise 1.12.43 (Exercise 12.16 [MU17]).

Consider the Markov chain sampling independent set in a graph $G=(V,E)$ . On a step, sample $v\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}V$ and $b\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\{0,1\}$ . If $v\in X_{t}$ , $X_{t+1}=X_{t}\setminus\{v\}$ on $b=1$ , if $v\notin X_{t}$ and $X_{t}\cup\{v\}$ is independent, $X_{t+1}=X_{t}\cup\{v\}$ on $b=0$ ; otherwise, $X_{t+1}=X_{t}$ .

•

Show that the stationary distribution of the chain is uniform over all independent sets.
•

Consider the chain over cycles and line graphs, where a line graph over $n$ vertices is constructed by connecting vertex $1,\ldots,n$ with an edge, and a cycle graph is the same with an addition of an additional edge $(1,n)$ .

Devise a coupling $(X_{t},Y_{t})$ for the Markov chain on line graphs and cycle graphs: if $d_{t}=\left|X_{t}\setminus Y_{t}\right|+\left|Y_{t}\setminus X_{t}\right|$ , then at each step the coupling is at least as likely to reduce $d_{t}$ as to increase $d_{t}$ . Show that it is rapidly mixing.
•

For the cases of line graphs and cycle graphs, derive the exact formulas for the number of independent sets.

Proof.

The stationary argument is similar to the one in example 1.12.38: for any pair of adjacent state of independent sets, which are differing by a vertex, the transition probability $P_{a,b}=(2n)^{-1}$ , then uniform distribution is a trivial solution for stationary distribution.

We use Hamming metric as the pre-metric: though we use the enlarged state space $\tilde{\Omega}$ of all subsets of $V$ , for the initial states $(X_{0},Y_{0})\in\Omega^{2}$ , the coupling Markov chains still preserve their marginal probabilities, hence the coupling is still valid. This follows the same argument in 1.12.42. Now consider the same coupling by taking on same sampled $v$ and $b$ on both $(X_{t},Y_{t})$ chains, where $(X_{t},Y_{t})$ are adjacent states. WLOG let $w$ be the disagreeing vertex, $X_{t}=I$ , and $Y_{t}=I\cup\{w\}$ . We are interested in $v\in\Gamma^{+}(w)$ , as $v\in V\setminus\Gamma^{+}(w)$ does not change $d_{t}$ .

•

If $v=w$ , any $b$ decreases the difference, and $\operatorname*{\mathbb{E}}\left[d_{t+1}-d_{t}\mid d_{t}=1,v=w\right]=-1$ .
•
If $v\in\Gamma(w)$ , then by $\Delta\leq 2$ , we know $\left|\Gamma(v)\cap I\right|\leq 1$ .
- –
  
  If $\left|\Gamma(v)\cap I\right|=0$ , then the distance is unchanged when $b=1$ , and the distance increases by 1 when $b=0$ .
  
  Hence, conditioned that $v\in\Gamma(w)$ and $\left|\Gamma(v)\cap I\right|=0$ , $\operatorname*{\mathbb{E}}\left[d_{t+1}-d_{t}\mid d_{t}=1\right]=1/2$ .
- –
  
  If $\left|\Gamma(v)\cap I\right|=1$ , then no operation changes $d_{t}$ .
  
  Conditioned that $v\in\Gamma(w)$ and $\left|\Gamma(v)\cap I\right|=1$ , $\operatorname*{\mathbb{E}}\left[d_{t+1}-d_{t}\mid d_{t}=1\right]=0$ .

Moreover, since $\Delta\leq 2$ , then $\left|\Gamma(w)\right|\leq 2$ . Let $X$ be the random variable for the vertex to choose, then $\Pr\left[X=v\right]=n^{-1}$ . By linearity of expectation,

\operatorname*{\mathbb{E}}\left[d_{t+1}-d_{t}\mid d_{t}=1\right]=\operatorname% *{\mathbb{E}}\left[\operatorname*{\mathbb{E}}\left[d_{t+1}-d_{t}\mid d_{t}=1,X% \right]\right]\leq 0.

With the same trick from 1.12.42, we loosely lower bound by $\Pr\left[d_{t+1}\neq d_{t}\right]\geq(2n)^{-1}=\gamma$ , as there is a choice out of $2n$ choices to fix the disagreement at $w$ , then eq. 1.24 is $\mathsf{poly}\left(\left|V\right|=n,\log(1/\varepsilon)\right)$ .

For the number of independent sets in line graphs and cycle graphs, this is basically dynamic programming. Let $L_{i}$ be the number of independent sets of line graph with $i$ vertices. By including the first vertex or not, we have

L_{i}=L_{i-1}+L_{i-2}.

Let $C_{i}$ be the number of independent sets of cycle graph with $i$ vertices. If the first vertex is not chosen, then there are $L_{i-1}$ independent sets, while if the first vertex is chosen, then there are $L_{i-3}$ independent sets, hence

C_{i}=L_{i-1}+L_{i-3}.

∎

Exercise 1.12.44 (Exercise 12.18 [MU17]).

Use path coupling to simplify example 1.12.17 and 1.12.20.

Proof.

We enhance the result in 1.12.16, by showing that the Markov chain over fixed size independent sets of size $k\leq n/(2\Delta+2)$ is ergodic. Let $I=X_{t}\cap Y_{t}$ , $A_{t}=X_{t}\setminus I$ , and $B_{t}=Y_{t}\setminus I$ . Consider following 2 easier corner case:

•

If $\left|B_{t}\right|=\left|B_{t}\setminus\Gamma(A_{t})\right|$ , then $B_{t}\cap\Gamma(X_{t})=\varnothing$ , and the transition takes $\left|A_{t}\right|=\left|B_{t}\right|$ steps by moving from $A_{t}$ to $B_{t}$ .
•

If $\left|B_{t}\right|=\left|B_{t}\cap\Gamma(A_{t})\right|$ , since $\left|A_{t}\right|\leq\left|X_{t}\right|\leq k$ , then $\left|V\setminus\Gamma^{+}(X_{t})\right|\geq n/2$ , and $B_{t}$ can move to $V\setminus\Gamma^{+}(X_{t})$ .

The transition can take $2\left|A_{t}\right|$ steps by moving $A_{t}$ to an independent set in $V\setminus\Gamma^{+}(X_{t})$ , then moving back into $B_{t}$ .

In general case, $X_{t}$ can be broken into 3 parts: $I$ , $A_{t}\cap\Gamma(B_{t})$ , and $A_{t}\setminus\Gamma(B_{t})$ . Since $\left|A_{t}\right|\leq k$ and $\left|V\setminus\Gamma^{+}(X_{t})\right|\geq n/2$ , then there exists a way to move $A_{t}$ to $V\setminus\Gamma^{+}(X_{t})$ in $\left|A_{t}\right|$ steps, such that $B_{t}\setminus\Gamma(A_{t})$ are all occupied. The remaining steps are transitioning occupied vertices back into $B_{t}\setminus\Gamma(A_{t})$ .

The uniform distribution being stationary distribution argument is immediate by the cutset, that the neighboring pair of independent sets transition to each other with transition probability $1/kn$ everywhere, and the chain has odd length loop of going back to itself, hence it is aperiodic.

Let $D_{t}$ be the pre-metric over all valid $k$ -sized independent sets, which is the least number of steps to transition from $X_{t}$ to $Y_{t}$ . Conditioned that $D_{t}=1$ , let $X_{t}=I\cup\{u\}$ and $Y_{t}=I\cup\{v\}$ . At a step, sample $w\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}X_{t}$ and $x\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}V$ , and a transition happens when $w\in X_{t}$ and $\Gamma(x)\cap X_{t}=\varnothing$ .

If $w\neq u$ , $w_{x}=w_{y}=w$ ; otherwise $(w_{x},w_{y})=(u,v)$ . Let $S_{1}=\Gamma^{+}(u)$ , $S_{2}=\Gamma^{+}(v)$ , and $M$ be the mapping between $S_{1}$ and $S_{2}$ , such that elements in $S_{1}\cap S_{2}$ are mapped to themselves, elements are mapped bijectively between $S_{1}\setminus S_{2}$ and $S_{2}\setminus S_{1}$ as many as possible, bijectively map $u$ and $v$ , with the remaining mapped to itself. Hence, if $x\in S_{1}\cup S_{2}$ , $z_{x}=x$ and $z_{y}=M(x)$ ; otherwise, $z_{x}=z_{y}=x$ .

The transition step is coupled by: Try removing $w_{x}$ and adding $z_{x}$ to $X_{t}$ , and removing $w_{y}$ and adding $z_{y}$ to $Y_{t}$ . To decrease the distance, $(w_{x},w_{y})=(u,v)$ and $x\notin\Gamma^{+}(X_{t}\cup Y_{t}\setminus\{u,v\})$ , then the probability is lower bounded by

\Pr\left[D_{t+1}=D_{t}-1\mid D_{t}=1\right]\geq\frac{1}{k}\cdot\frac{n-(\Delta% +1)(k-1)}{n}.

To increase the distance, $w\in I$ and $z_{x}\in S_{2}$ , such that the number of moves where at least a chain transitions is upper bounded by $\max\left(\left|S_{1}\right|,\left|S_{2}\right|\right)\leq\Delta+1$ by 1.12.20, hence the probability is upper bounded by

\Pr\left[D_{t+1}=D_{t}+1\mid D_{t}=1\right]\leq\frac{k-1}{k}\cdot\frac{\Delta+% 1}{n}.

By linearity of expectation,

\operatorname*{\mathbb{E}}\left[D_{t+1}\mid D_{t}=1\right]\leq 1-\frac{1}{k}% \cdot\frac{n-(\Delta+1)(k-1)}{n}+\frac{k-1}{k}\cdot\frac{\Delta+1}{n}=1-\frac{% n-2(\Delta+1)(k-1)}{kn}.

Again by path coupling argument, let

Z_{0}=X_{t},\ldots,Z_{d_{t}}=Y_{t}

be a chain of states where neighboring states have pre-metric distance 1. The move in $Z_{0}$ gives a coupled move for $Z_{1}$ , and eventually leads to a coupled move for $Z_{d_{t}}$ . Let $Z_{i}^{\prime}$ be the state after the move is made from $Z_{i}$ , and let

\Delta\left(Z_{i-1}^{\prime},Z_{i}^{\prime}\right)=\left|Z_{i-1}^{\prime}% \setminus Z_{i}^{\prime}\right|.

By linearity of expectation,

\operatorname*{\mathbb{E}}\left[D_{t+1}\mid D_{t}\right]=\sum_{i\in[1,D_{t}]}% \operatorname*{\mathbb{E}}\left[\Delta\left(Z_{i-1}^{\prime},Z_{i}^{\prime}% \right)\right]\leq D_{t}\cdot\left(1-\frac{n-2(\Delta+1)(k-1)}{kn}\right),

and we conclude the proof. ∎

	$\displaystyle\Delta(t)$	$\displaystyle=\frac{1}{2}\sum_{a\in S}\left\|p_{x}^{t}(a)-\mathcal{D}_{% \boldsymbol{\pi}}(a)\right\|$
		$\displaystyle=\frac{1}{2}\sum_{a\in S}\left\|p_{x}^{t}(a)-\sum_{y\in S}\mathcal% {D}_{\boldsymbol{\pi}}(y)\cdot p_{y}^{t}(a)\right\|=\frac{1}{2}\sum_{a\in S}% \left\|\sum_{y\in S}\mathcal{D}_{\boldsymbol{\pi}}(y)\cdot\left(p_{x}^{t}(a)-p_% {y}^{t}(a)\right)\right\|$
		$\displaystyle\leq\frac{1}{2}\sum_{a\in S}\sum_{y\in S}\left\|\mathcal{D}_{% \boldsymbol{\pi}}(y)\cdot\left(p_{x}^{t}(a)-p_{y}^{t}(a)\right)\right\|=\sum_{y% \in S}\mathcal{D}_{\boldsymbol{\pi}}(y)\cdot\frac{1}{2}\sum_{a\in S}\left\|p_{x% }^{t}(a)-p_{y}^{t}(a)\right\|$
		$\displaystyle=\sum_{y\in S}\mathcal{D}_{\boldsymbol{\pi}}(y)\cdot d_{\mathsf{% TV}}\left(p_{x}^{t},p_{y}^{t}\right)\leq\overline{\Delta}(t).$