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.

$\endgroup$
1
$\begingroup$

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)}. $$

$\endgroup$
  • $\begingroup$ Your proof taugh me a lot. It links many concepts, and makes them accessible to me know. Thank you. $\endgroup$ – user14108 Nov 16 '11 at 18:53
  • $\begingroup$ You are welcome. Which context do you read MCMT in? $\endgroup$ – Did Nov 16 '11 at 18:55
  • $\begingroup$ I'm taking a class on mixing times, and we use this book. $\endgroup$ – user14108 Nov 16 '11 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy