随机算法 (Fall 2011)/Coupling

From EtoneWiki
Revision as of 13:57, 10 August 2011 by WikiSysop (talk) (Protected "随机算法 (Fall 2011)/Coupling" ([edit=sysop] (indefinite) [move=sysop] (indefinite)))
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Coupling of Two Distributions

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

Definition (coupling)
Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle p} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle q} be two probability distributions over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Omega} . A probability distribution Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mu} over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Omega\times\Omega} is said to be a coupling if its marginal distributions are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle p} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle q} ; that is
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \begin{align} p(x) &=\sum_{y\in\Omega}\mu(x,y);\\ q(x) &=\sum_{y\in\Omega}\mu(y,x). \end{align} }

The interesting case is when Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y} are not independent. In particular, we want the probability that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X=Y} to be as large as possible, yet still maintaining the respective marginal distributions Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle p} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle q} . When Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle p} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle q} are different it is inevitable that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X\neq Y} with some probability, but how small this probability can be, that is, how well two distributions can be coupled? The following coupling lemma states that this is determined by the total variation distance between the two distributions.

Lemma (coupling lemma)
Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle p} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle q} be two probability distributions over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Omega} .
  1. For any coupling Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle (X,Y)} of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle p} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle q} , it holds that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Pr[X\neq Y]\ge\|p-q\|_{TV}} .
  2. There exists a coupling Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle (X,Y)} of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle p} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle q} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Pr[X\neq Y]=\|p-q\|_{TV}} .
Proof.
1.

Suppose Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle (X,Y)} follows the distribution Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mu} over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Omega\times\Omega} . Due to the definition of coupling,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \begin{align} p(x) =\sum_{y\in\Omega}\mu(x,y) &\quad\text{and } &q(x) =\sum_{y\in\Omega}\mu(y,x). \end{align} }

Then for any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle z\in\Omega} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mu(z,z)\le\min\{p(z),q(z)\}} , thus

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \begin{align} \Pr[X=Y] &= \sum_{z\in\Omega}\mu(z,z) \le\sum_{z\in\Omega}\min\{p(z),q(z)\}. \end{align} }

Therefore,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \begin{align} \Pr[X\neq Y] &\ge 1-\sum_{z\in\Omega}\min\{p(z),q(z)\}\\ &=\sum_{z\in\Omega}(p(z)-\min\{p(z),q(z)\})\\ &=\sum_{z\in\Omega\atop p(z)>q(z)}(p(z)-q(z))\\ &=\frac{1}{2}\sum_{z\in\Omega}|p(z)-q(z)|\\ &=\|p-q\|_{TV}. \end{align} }
2.

We can couple Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y} so that for each Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle z\in\Omega} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X=Y=z} with probability Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \min\{p(z),q(z)\}} . The remaining follows as above.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \square}

The proof is depicted by the following figure, where the curves are the probability density functions for the two distributions Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle p} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle q} , the colored area is the diference between the two distribution, and the "lower envelope" (the red line) is the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \min\{p(x), q(x)\}} .

Coupling.png

Monotonicity of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Delta_x(t)}

Consider a Markov chain on state space Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Omega} . Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \pi} be the stationary distribution, and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle p_x^{(t)}} be the distribution after Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle t} steps when the initial state is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x} . Recall that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Delta_x(t)=\|p_x^{(t)}-\pi\|_{TV}} is the distance to stationary distribution Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \pi} after Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle t} steps, started at state Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x} .

We will show that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Delta_x(t)} is non-decreasing in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle t} . That is, for a Markov chain, the variation distance to the stationary distribution monotonically decreases as time passes. Although this is rather intuitive at the first glance, the proof is nontrivial. A brute force (algebraic) proof can be obtained by analyze the change to the 1-norm of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle p_x^{(t)}-\pi} by multiplying the transition matrix Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle P} . The analysis uses eigen decomposition. We introduce a cleverer proof using coupling.

Proposition
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Delta_x(t)} is non-decreasing in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle t} .
Proof.

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_0=x} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y_0} follow the stationary distribution Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \pi} . Two chains Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_0,X_1,X_2,\ldots} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y_0,Y_1,Y_2,\ldots} can be defined by the initial distributions Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_0} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y_0} . The distributions of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_t} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y_t} are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle p_x^{(t)}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \pi} , respectively.

For any fixed Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle t} , we can couple Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_t} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y_t} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Pr[X\neq Y]=\|p_x^{t}-\pi\|_{TV}=\Delta_x(t)} . Due to the Coupling Lemma, such coupling exists. We then define a coupling between Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_{t+1}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y_{t+1}} as follows.

  • If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_t=Y_t} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_{t+1}=Y_{t+1}} following the transition matrix of the Markov chain.
  • Otherwise, do the transitions Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_t\rightarrow X_{t+1}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y_t\rightarrow Y_{t+1}} independently, following the transitin matrix.

It is easy to see that the marginal distributions of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_{t+1}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y_{t+1}} both follow the original Markov chain, and

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Pr[X_{t+1}\neq Y_{t+1}]\le \Pr[X_t\neq Y_{t}]. }

In conclusion, it holds that

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Delta_x(t+1)=\|p_x^{(t+1)}-\pi\|_{TV}\le\Pr[X_{t+1}\neq Y_{t+1}]\le \Pr[X_t\neq Y_{t}]=\Delta_x(t), }

where the first inequality is due to the easy direction of the Coupling Lemma.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \square}

Rapid Mixing by Coupling

Consider an ergodic (irreducible and aperiodic) Markov chain on state space Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Omega} . We want to upper bound its mixing time. The coupling technique for bounding the mixing time can be sumerized as follows:

Consider two random walks starting at state Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle y} in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Omega} . Each individual walk follows the transition rule of the original Markov chain. But the two random walks may be "coupled" in some way, that is, may be correlated with each other. A key observation is that for any such coupling, it always holds that
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Delta(t) \le\max_{x,y\in\Omega}\Pr[\text{ the two } \mathit{coupled} \text{ random walks started at }x,y\text{ have not met by time }t] }
where we recall that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Delta(t)=\max_{x\in\Omega}\|p_x^{(t)}-\pi\|_{TV}} .
Definition (coupling of Markov chain)
A coupling of a Markov chain with state space Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Omega} and transition matrix Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle P} , is a Markov chain Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle (X_t,Y_t)} with state space Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Omega\times\Omega} , satisfying
  1. each of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_t} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y_t} viewed in isolation is a faithful copy of the original Markov chain, i.e.
    Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Pr[X_{t+1}=v\mid X_t=u]=\Pr[Y_{t+1}=v\mid Y_{t}=u]=P(u,v)} ;
  2. once Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_t} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y_t} reaches the same state, they make identical moves ever since, i.e.
    Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_{t+1}=Y_{t+1}} if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_t=Y_t} .
Lemma (coupling lemma for Markov chains)
Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle (X_t,Y_t)} be a coupling of a Markov chain Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle M} with state space Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Omega} . Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Delta(t)} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle M} is bounded by
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Delta(t) \le\max_{x,y\in\Omega}\Pr[X_t\neq Y_t\mid X_0=x,Y_0=y]} .
Proof.

Due to the coupling lemma (for probability distributions),

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Pr[X_t\neq Y_t\mid X_0=x,Y_0=y] \ge \|p_x^{(t)}-p_y^{(t)}\|_{TV}, }

where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle p_x^{(t)},p_y^{(t)}} are distributions of the Markov chain Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle M} at time Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle t} , started at states Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x, y} .

Therefore,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \begin{align} \Delta(t) &= \max_{x\in\Omega}\|p_x^{(t)}-\pi\|_{TV}\\ &\le \max_{x,y\in\Omega}\|p_x^{(t)}-p_y^{(t)}\|_{TV}\\ &\le \max_{x,y\in\Omega}\Pr[X_t\neq Y_t\mid X_0=x,Y_0=y]. \end{align} }
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \square}


Corollary
Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle (X_t,Y_t)} be a coupling of a Markov chain Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle M} with state space Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Omega} . Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \tau(\epsilon)} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle M} is bounded as follows:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \max_{x,y\in\Omega}\Pr[X_t\neq Y_t\mid X_0=x,Y_0=y]\le \epsilon\quad\Longrightarrow\quad\tau(\epsilon)\le t} .

Geometric convergence

Consider a Markov chain on state space Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Omega} . Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \pi} be the stationary distribution, and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle p_x^{(t)}} be the distribution after Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle t} steps when the initial state is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x} . Recall that

  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Delta_x(t)=\|p_x^{(t)}-\pi\|_{TV}} ;
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Delta(t)=\max_{x\in\Omega}\Delta_x(t)} ;
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \tau_x(\epsilon)=\min\{t\mid\Delta_x(t)\le\epsilon\}} ;
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \tau(\epsilon)=\max_{x\in\Omega}\tau_x(\epsilon)} ;
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \tau_{\mathrm{mix}}=\tau(1/2\mathrm{e})\,} .

We prove that

Proposition
  1. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Delta(k\cdot\tau_{\mathrm{mix}})\le \mathrm{e}^{-k}} for any integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k\ge1} .
  2. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \tau(\epsilon)\le\tau_{\mathrm{mix}}\cdot\left\lceil\ln\frac{1}{\epsilon}\right\rceil} .
Proof.
1.

We denote that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \tau=\tau_{\mathrm{mix}}\,} . We construct a coupling of the Markov chain as follows. Suppose Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle t=k\tau} for some integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k} .

  • If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_t=Y_t} then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_{t+i}=Y_{t+i}} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle i=1,2,\ldots,\tau} .
  • For the case that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_t=u, Y_t=v} for some Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle u\neq v} , we couple the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_{t+\tau}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y_{t+\tau}} so that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Pr[X_{t+\tau}\neq Y_{t+\tau}\mid X_t=u,Y_t=v]=\|p_u^{(t)}-p_v^{(t)}\|_{TV}} . Due to the Coupling Lemma, such coupling does exist.

For any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle u,v\in\Omega} that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle u\neq v} ,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \begin{align} \Pr[X_{t+\tau}\neq Y_{t+\tau}\mid X_t=u,Y_t=v] &=\|p_u^{(t)}-p_v^{(t)}\|_{TV}\\ &\le \|p_u^{(\tau)}-\pi\|_{TV}+\|p_v^{(\tau)}-\pi\|_{TV}\\ &= \Delta_u(\tau)+\Delta_v(\tau)\\ &\le \frac{1}{\mathrm{e}}. \end{align} }

Thus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Pr[X_{t+\tau}\neq Y_{t+\tau}\mid X_t\neq Y_t]\le \frac{1}{\mathrm{e}}} by the law of total probability. Therefore, for any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x,y\in\Omega} ,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \begin{align} &\quad\, \Pr[X_{t+\tau}\neq Y_{t+\tau}\mid X_0=x,Y_0=y]\\ &= \Pr[X_{t+\tau}\neq Y_{t+\tau}\mid X_t\neq Y_t]\cdot \Pr[X_{t}\neq Y_{t}\mid X_0=x,Y_0=y]\\ &\le \frac{1}{\mathrm{e}}\Pr[X_{t}\neq Y_{t}\mid X_0=x,Y_0=y]. \end{align} }

Then by induction,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Pr[X_{k\tau}\neq Y_{k\tau}\mid X_0=x,Y_0=y]\le \mathrm{e}^{-k}, }

and this holds for any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x,y\in\Omega} . By the Coupling Lemma for Markov chains, this means Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Delta(k\tau_{\mathrm{mix}})=\Delta(k\tau)\le\mathrm{e}^{-k}} .

2.

By the definition of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \tau(\epsilon)} , the inequality is straightforwardly implied by (1).

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \square}

Random Walk on the Hypercube

A Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n} -dimensional hypercube is a graph on vertex set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \{0,1\}^n} . For any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x,y\in\{0,1\}^n} , there is an edge between Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle y} if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle y} differ at exact one coordinate (the hamming distance between Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle y} is 1).

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

Random Walk on Hypercube
At each step, for the current state Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x\in\{0,1\}^n} :
  1. with probability Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle 1/2} , do nothing;
  2. else, pick a coordinate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle i\in\{1,2,\ldots,n\}} uniformly at random and flip the bit Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x_i} (change Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x_i} to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle 1-x_i} ).

This is a lazy uniform random walk in an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n} -dimensional hypercube. It is equivalent to the following random walk.

Random Walk on Hypercube
At each step, for the current state Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x\in\{0,1\}^n} :
  1. pick a coordinate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle i\in\{1,2,\ldots,n\}} uniformly at random and a bit Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle b\in\{0,1\}} uniformly at random;
  2. let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x_i=b} .

It is easy to see the two random walks are the same. The second form hint us to couple the random choice of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle i} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle b} in each step. Consider two copies of the random walk Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_t} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y_t} , started from arbitrary two states Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_0} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y_0} , the coupling rule is:

  • At each step, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_t} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y_t} choose the same (uniformly random) coordinate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle i} and the same (uniformly random) bit Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle b} .

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

For arbitrary Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x,y\in\{0,1\}^n} , started at Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_0=x, Y_0=y} , the event Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_t=Y_t} occurs if everyone of the coordinates on which Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle y} disagree has been picked at least once. In the worst case, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle y} disagree on all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n} coordinates. The time Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle T} that all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n} coordinates have been picked follows the coupon collector problem collecting Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n} coupons, and we know from the coupon collector problem that for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle c>0} ,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Pr[T\ge n\ln n+cn]\le \mathrm{e}^{-c}. }

Thus for any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x,y\in\{0,1\}^n} , if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle t\ge n\ln n+cn} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Pr[X_t\neq Y_t\mid X_0=x,Y_0=y]\le \mathrm{e}^{-c}} . Due to the coupling lemma for Markov chains,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Delta(n\ln n+cn)\le \mathrm{e}^{-c},}

which implies that

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \tau(\epsilon)=n\ln n+n\ln\frac{1}{\epsilon}} .

So the random walk achieves a polynomially small variation distance Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \epsilon=\frac{1}{\mathrm{poly}(n)}} to the stationary distribution in time Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle O(n\ln n)} .

Note that the number of states (vertices in the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n} -dimensional hypercube) is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle 2^n} . Therefore, the mixing time is exponentially small compared to the size of the state space.