Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
Your proof taugh me a lot. It links many concepts, and makes them accessible to me know. Thank you. –  Nicolas Essis-Breton Nov 16 '11 at 18:53
    
You are welcome. Which context do you read MCMT in? –  Did Nov 16 '11 at 18:55
    
I'm taking a class on mixing times, and we use this book. –  Nicolas Essis-Breton Nov 16 '11 at 19:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.