$$

Ergodic chains

• irreducible: can go from any $x$ to any $y$
• aperiodic: length of cycles from $x$ to $x$ have gcd = 1
  • often you can aperiodicity via lazification: adding self-loops to every node)
    • i.e. $(1-\lambda )P-\lambda I$
    • this isguaranteed to not change the stationary distribution!

Fundamental theorem

Every ergodic chain $P\in {\mathbb{R}}^{n\times n}$ has a unique stationary distribution $\mu$, and for any starting distribution $\nu$,

$$\underset{t\to \mathrm{\infty }}{lim}\nu P^t=\mu .$$

Proof

What we need is a quantitative version of Data processing inequalities: $P$ needs to be a strong contraction. For example, if

$$d_{\mathrm{TV}}(\nu P,{\nu }^{\prime }P)\le .99d_{\mathrm{TV}}(\nu ,{\nu }^{\prime }),$$

then $\nu ,\nu P,\nu P^2,\dots$ is Cauchy:

$$d_{\mathrm{TV}}(\nu P^t,\nu P^{t^{\prime }})\le {.99}^{min(t,t^{\prime })},$$

so it converges (and also the limit can’t differ between two starting points).

But there might not initially be a strong contraction (see example in slides).

Weak contraction

There is an optimal coupling $\pi$ such that

$$d_{\mathrm{TV}}(\nu ,{\nu }^{\prime })=\underset{(\mathit{X},{\mathit{X}}^{\prime })\sim \pi }{\mathrm{Pr}}[\mathit{X}\ne {\mathit{X}}^{\prime }].$$

How the coupling evolves:

• if ${\mathit{X}}_i={\mathit{X}}_i^{\prime }$, use same transition;
• else, evolve arbitrarily.

So we get $\mathrm{Pr}[{\mathit{X}}_{i+1}\ne {\mathit{X}}_{i+1}^{\prime }]\le \mathrm{Pr}[{\mathit{X}}_i\ne {\mathit{X}}_i]$.

Strong contraction

If we know that $P(x,y)>0$ for all $x,y$, then in our coupling we’d have

$$\mathrm{Pr}[{\mathit{X}}_{i+1}\ne {\mathit{X}}_{i+1}^{\prime }]\le (1-ϵ)\mathrm{Pr}[{\mathit{X}}_i\ne {\mathit{X}}_i].$$

For general ergodic $P$, no strong contraction, but there is some $t$ such that $P^t(x,y)>0$ for all $x,y$, so just do the same thing for $P^t$ instead of $P$ (and just lose a factor $t$).

Why?

Because if the gcd of the loops is 1, then you get loops of every long enough length.