1
$\begingroup$

Let $(X_t)_{t \ge 0}$ be a finite irreducible and aperiodic Markov chain with state space $\Omega$, transition matrix $P$ and stationary distribution $\pi$. Let $\| \cdot \|$ denote the total variation distance and define 

$c(t)=\max_{x \in \Omega}\|{1 \over t}\sum_{s=0}^{t-1}P_x^s - \pi\|$

$d(t)=\max_{x \in \Omega}\|P_x^t-\pi\|$

Suppose $t_m$ is the mixing time according to the Cesaro metric $c(t)$, and $s_m$ the mixing time according to the total variation distance $d(t)$. Show $t_m({1 \over 4}) \le 6s_m({1 \over 8})$, where $t_m(\epsilon)$ implies $c(t_m(\epsilon)) \le \epsilon$

I've learn many results that touch this problem, but I can't link them together to do the proof. I know we can define $p(t)=\max_{x,y \in \Omega}\|P_x^t-P_y^t\|$ and that $d(t) \le p(t)$. Also, $p(kt) \le p(t)^k$. Coupling can be used to bound total variation distance. But I don't see a coupling that will be usefull here.

This is exercise 10.12 from Markov Chains and Mixing Times, 2009, Levin, Perez, Wilmer.

1 Answers 1

1

The $6$ should probably be $7$.

By the triangular inequality, $tc(t)\leqslant\sum\limits_{s=0}^{t-1}d(s)$. Assume that $s_m(\frac18)\leqslant k$, that is, that $d(k)\leqslant\frac18$. Then, $d$ is nonincreasing and bounded by $1$ hence $d(s)\leqslant1$ for every $s\lt k$ and $d(s)\leqslant\frac18$ for every $s\geqslant k$. Thus, $7kc(7k)\leqslant k\cdot1+6k\cdot\frac18=\frac74k$, that is, $c(7k)\leqslant\frac14$, in particular $t_m(\frac14)\leqslant7k$.

This proves that $t_m(\frac14)\leqslant7s_m(\frac18)$. More generally, for every $\color{red}{u\lt v\lt 1}$, $ \color{red}{t_m(v)\leqslant\frac{1-u}{v-u}\cdot s_m(u)}. $

  • 0
    I'm taking a class on mixing times, and we use this book.2011-11-16