# Cesaro mixing time and mixing time: show $t_m(1/4) \le 6s_m(1/8)$

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.

-

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)}.$$
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9976245164871216, "perplexity": 62.778778521798046}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-18/segments/1430455166292.61/warc/CC-MAIN-20150501043926-00036-ip-10-235-10-82.ec2.internal.warc.gz"}