Mixing time

Suppose the assumptions to guarantee that our Markov chain converges to its invariant distribution. We now ask

How fast does it converges?

To formalize this we need a notion of distance, we use the total variation:

$$\Vert \mu -\nu {\Vert }_{TV}:=\underset{A\subseteq I}{\sup }|\mu (A)-\nu (A)|=\frac{1}{2}\sum _{x\in I}|\mu (i)-\nu (i)|$$

For a finite markov chain there exists $c_1,c_2\in (0,\infty )$ such that

$$\Vert \lambda P^n-\pi \Vert \le c_1{e}^{-c_{2}n}$$

where the constants depend on the second largest eigenvector of the transition matrix (think of the Power method).

This could depend on the starting distribution, so we define (finite markov chains)

$$d(t):=\underset{x\in I}{\max }\Vert {\delta }_x{P}^t-\pi \Vert$$

the distance at time $t$. With this we define

$$t_{mix}(ϵ):=\min \{t\ge 0:d(t)<ϵ\}$$

The following lemma is usefull for establishing bounds on the mix time

Lemma Let $(X_n{)}_{n\ge 0}\sim Markov(\mu ,P)$ and $(Y_n{)}_{n\ge 0}\sim Markov(\nu ,P)$ and let $Z_n=(X_n,Y_n)$ be a coupling of the markov chains. Then

$$d_{TV}({\mu }_n,{\nu }_n)\le P_Z(X_n\ne Y_n)$$

Proof Given any $A\subseteq I$ we have

$${\mu }_n(A)-{\nu }_n(A)=P_z(X_n\in A)-P_z(Y_n\in A)$$ $$=P_z(X_n\in A,Y_n\notin A)-P_z(Y_n\in A,X_n\notin A)$$ $$\le P_z(X_n\in A,Y_n\notin A)$$ $$\le P_z(X_n\ne Y_n)\square$$

We can use this when $Y_n$ has initial distribution $\pi$ (stationary) to bound the mixing time.

Lemma (coupling lemma) Let $Z_n$ be a coupling, if for any $x\in I$ there exists $T\ge 0$ such that

$$P_z(X_T\ne Y_T|X_0=x,Y_0=\pi )\le ϵ$$

then $t_{mix}(ϵ)\le T$.

Proof We use the previous lemma and the definition of $t_{mix}$:

$$t_{mix}(ϵ)\le T$$

since $d(T)={\max }_{x\in I}{d}_{TV}(p_x^n,\pi )\le ϵ$. $\square$

Card shuffling, r.w. lazy on hypercube

$$t_{mix}(ϵ)\le n\ln \left(\frac{n}{ϵ}\right)$$