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 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|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.