Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $(X_t)_{t \ge 0}$ be a finite 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\limits_{x \in \Omega}\|{1 \over t}\sum_{s=0}^{t-1}P_x^s - \pi\|$$

Let $t_m$ be the mixing time according to the Cesaro metric $c(t)$, that is $t_m(\epsilon)$ implies $c(t_m(\epsilon)) \le \epsilon$. Show $t_m(2^{-k}) \le k t_m(1/4), k \ge 1$.

I have try the following. The claim holds for $k=1$, since $t_m(\frac14)=\alpha$ implies $\alpha c(\alpha) \le \frac14 \le \frac12$. Suppose the claim holds for $k$, then for $k+1$

$$(k+1)\alpha c((k+1)\alpha) \le k\alpha c(k\alpha) + \max\limits_{x \in \Omega}\|\sum_{s=k\alpha}^{(k+1)\alpha-1}P_x^s - \pi\|$$

By the induction hypothesis, the first term is less then $k\alpha 2^{-k}$. For the second term it's bounded by $\alpha\frac14$. I can't go further.

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

share|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.