Markov chain convergence - coupling proof: Why $\left|\mathbb{P}(Z_n=j) - \mathbb{P}(Y_n=j)\right| \leq \mathbb{P}(Z_n \neq Y_n)$?

Question

I am trying to understand a proof of the following "convergence to equilibrium" theorem for Markov chains:

Suppose $P$ is irreducible and aperiodic, with stationary distribution $\pi$. If $(X_n, n\geq0)$ is a Markov chain with transition matrix $P$ and any initial distribution, then for all $j \in I$, $$\mathbb{P}(X_n = j) \to \pi_j \quad \text{as } n \to \infty.$$

However, I don't understand the step labelled \eqref{ref}.

---

Here is the relevant part of the proof:

Let $\lambda$ be any initial distribution, and let $X = (X_n, n\geq0)$ be Markov$(\lambda,P)$. The aim is to show that $\mathbb{P}(X_n=j) \to \pi_j$ as $n \to \infty$, for any $j$.

Consider another chain $Y=(Y_n,n \geq 0)$ which is Markov$(\pi,P)$, and which is independent of $X$. Since $\pi$ is stationary, $Y_n$ has distribution $\pi$ for all $n$.

Let $T = \inf\{n\geq0 : X_n = Y_n\}$. Assume (for now) that $\mathbb{P}(T<\infty)=1$; that is, the chains $X$ and $Y$ will meet at some point.

Then define another chain $Z$ by $$ Z_n = \begin{cases} X_n & \text{if } n < T \\ Y_n & \text{if } n \geq T \end{cases} $$ Then $Z$ is also Markov$(\lambda,P)$, since $Z_n$ starts in distribution $\lambda$ and each jump is done according to $P$, first by copying $X$ up to time $T$, and then by copying $Y$ after time $T$. We have that \begin{align} \left|\mathbb{P}(Z_n=j) - \pi_j\right| &= \left|\mathbb{P}(Z_n=j) - \mathbb{P}(Y_n=j)\right| \\ &\leq \mathbb{P}(Z_n \neq Y_n) \tag{$\ast$} \label{ref}\\ &= \mathbb{P}(T>n) \\ &\to 0 \quad \text{as } n \to \infty \end{align} So we have $\mathbb{P}(Z_n=j) \to \pi_j$. But the chains $X$ and $Z$ have the same distribution, so we have $\mathbb{P}(X_n=j) \to \pi_j$ as required.

---

Why is $\left|\mathbb{P}(Z_n=j) - \mathbb{P}(Y_n=j)\right| \leq \mathbb{P}(Z_n \neq Y_n)$ true?

Answer 1

For any subset $A$ of the state space, we have $$\begin{align}P(Z_n \in A) - P(Y_n \in A) &= [P(Z_n \in A, Z_n = Y_n) + P(Z_n \in A, Z_n \ne Y_n)] \\ &\qquad - [P(Y_n \in A, Z_n = Y_n) + P(Y_n \in A, Z_n \ne Y_n)] \\ &= P(Z_n \in A, Z_n \ne Y_n) - P(Y_n \in A, Z_n \ne Y_n) \\ &\le P(Z_n \ne Y_n). \end{align}$$ Similarly you can show $$P(Y_n \in A) - P(Z_n \in A) \le P(Z_n \ne Y_n).$$ Together this yields $$|P(Z_n \in A) - P(Y_n \in A)| \le P(Z_n \ne Y_n).$$ Your inequality is the special case where $A=\{j\}$.

---

Note that we have actually proved the even stronger inequality $$\max_A |P(Z_n \in A) - P(Y_n \in A)| \le P(Z_n \ne Y_n).$$ The quantity on the left-hand side is the total variation between the distributions of $Z_n$ and $Y_n$.