Data processing: a Markov kernel does not increase total variation distance

Let $K$ be a Markov kernel from $\mathsf X$ to $\mathsf Y$ and let $\mu,\nu$ be probability measures on $\mathsf X$. Then

where $K\!\circ\!\mu = \int K(x,\cdot)\,\mathrm{d}\mu(x)$ is the law obtained by drawing a starting point from $\mu$ and then applying $K$.

Data processing. Randomly transforming two distributions by the same mechanism cannot make them easier to tell apart. Total variation distance is exactly the optimal error in distinguishing two distributions from one sample, and a Markov kernel is a randomized map, so this is the statement that post-processing cannot increase statistical distinguishability.

Use for Markov chains. This is the step that transports a convergence rate on the state space to a rate on path space. If $\|\lambda P^m - \pi\| \le \varepsilon$, then applying the trajectory kernel to both sides gives

i.e. the entire future of the chain started from $\lambda$ and observed from time $m$ onwards is within $\varepsilon$, in total variation, of the stationary chain. For a uniformly ergodic chain $\varepsilon = Rt^m$ decays geometrically, and this is precisely what lets a central limit theorem proved for the stationary chain be transferred to an arbitrary initial distribution — the "for every initial distribution" clause in the Markov chain CLT.

Iterating $K$ also gives the classical monotonicity $\|\mu P^{n+1} - \nu P^{n+1}\| \le \|\mu P^n - \nu P^n\|$: the distance to stationarity never increases along the chain.

Proof. For a measurable $B \subseteq \mathsf Y$, the function $g(x) = K(x,B)$ takes values in $[0,1]$ and is measurable, and by definition of composition

Hence $|(K\!\circ\!\mu)(B) - (K\!\circ\!\nu)(B)| = \bigl|\int g\,\mathrm{d}\mu - \int g\,\mathrm{d}\nu\bigr| \le \|\mu-\nu\|$, by the bound on differences of integrals of $[0,1]$-valued functions. Taking the supremum over $B$ finishes.

The essential point is that $g$ is a function, not an indicator: the total variation distance is defined by testing against sets, and the whole content of the argument is that it also controls tests against arbitrary $[0,1]$-valued functions.