In Durrett's probability theory and examples:
(Exercise 5.6.3) Show that if $S$ is finite, $p$ is irreducible and aperiodic, and $T$ is the coupling time defined in the proof of Theorem 5.6.6, then $P(T>n) \le Cr^n$ for some $r < 1$ and $C < \infty$. So the convergence to equilibrium occurs exponentially rapidly in this case. Hint: First consider the case in which $p(x,y) > 0$ for all $x$ and $y$ and reduce the general case to this one by looking at a power of $p$.
(Theorem 5.6.6 (Convergence Theorem)) Suppose $p$ is irreducible, aperiodic (i.e. all states have $d_x=1$), and has stationary distribution $\pi$. Then, as $n \to \infty$, $p^n(x,y) \to \pi(y)$. (Define $T := \inf \{ n \ge 1: X_n = Y_n \}$, and $(X_n, Y_n)$ is a Markov chain with stationary distribution $\pi(x)\pi(y)$).
Lemma: If $S$ is finite and $p$ is irreducible and aperiodic, then there is an $m$ so that $p^m(x,y) > 0$ for all $x, y$.
Here's what I have so far:
Since $p$ is irreducible and aperiodic with finite S, by the above lemma, there exists $m > 0$ such that $p^m(x,y) > 0$ for all $x,y \in S$. Let $N=|S|$, and let $l := \inf_{x,y \in S} p^m(x,y)$. Then we see that
$$\sum_{z \in S} p^m(x,z) p^m(y,z) \ge \sum_{z \in S} l^2 = Nl^2$$
Then
\begin{align*}
P(X_m = Y_m) &= \sum_x \pi(x) \sum_y \pi(y) \underbrace{\sum_z p^m(x,z) p^m(y,z)}_{\ge Nl^2} \\
&\ge Nl^2 \underbrace{\sum_x \pi(x)}_{=1} \underbrace{\sum_y \pi(y)}_{=1}\\
&= Nl^2
\end{align*}
So after $m$ steps, $X_m = Y_m$ with probability at least $Nl^2$. Recall that $T := \inf \{ n \ge 1: X_n = Y_n \}$, then
$$P(T \le m) \ge P(X_m = Y_m) \ge Nl^2 \qquad P(T>m) = 1- P(T \le m) \le 1-Nl^2$$
Using the inequality $P(T>m) \le 1-Nl^2$, I can show that
$$P(T > m \cdot n) \le (1-Nl^2)^n$$
but this only works with value $m \cdot n$, and the question asks to show that for any $n$, $P(T > n) \le Cr^n$. Additionally, I'm not sure how to get $C$.
Any suggestions would be much appreciated!
Best Answer
We want to show that there exists a constant $C$ and $0<r<1$ such that for each $k$, $P(T > k) \le Cr^k$. Let $k\geq 1$. Write the Euclidean division of $k$ by $m$, that is, $k=mn+j$, where $0\leq j\leq m-1$. Then from what you got $$ \mathbb P(T>k)=\mathbb P(T>mn+j)\leq \mathbb P(T>mn)\leq (1-Nl^2)^n =(1-Nl^2)^{\frac{k-j}m}. $$ As $j\leq m-1$, $(1-Nl^2)^{-\frac{j}m}\leq (1-Nl^2)^{-\frac{m-1}m}=:C$. Now take $r=(1-Nl^2)^{\frac{1}m}$.