Show $\alpha_{m+n}\leq \alpha_m\alpha_n$ for a Markov chain on a finite state space This problem is from Durrett's Probability: Theory and Examples, 5/E, Exercise 5.6.4(or 6.6.3 in earlier editions).

For any transition matrix $p$, define $$\alpha_n=\sup_{i,j}\frac{1}{2}\sum_k|p^n(i,k)-p^n(j,k)|.$$ The 1/2 is there because for any $i$ and $j$ we can define r.v.'s $X$ and $Y$ so that $P(X=k)=p^n(i,k),$ $P(Y=k)=p^n(j,k)$, and $$P(X\neq Y)=(1/2)\sum_k|p^n(i,k)-p^n(j,k)|.$$ Show that $\alpha_{m+n}\leq \alpha_n\alpha_m$.

My attempt: I first looked at this answer, but I found that the coupling provided in the answer does not satisfy the property we want. For a counterexample, consider a state space with only two states and every transition probability is 1/2.
My instructor provided a hint that we should use the 'maximal coupling', the coupling satisfying $P(X\neq Y)=\alpha_n$, but I have no idea how to construct that kind of coupling. I found some papers and lecture notes dealing with maximal coupling, but I could not understand them since it deals with too general cases.
Does anyone have ideas?
Thanks in advance!
 A: Write $\| \mu - \nu \|_{TV} := \frac{1}{2}\sum_{i \in S} |\mu(i) - \nu(i)|$ for the total-variation distance between two measures $\mu$ and $\nu$ on the countable state space $S$. We know the following facts:

Fact. Let $X, Y$ be RVs with marginal distributions $\mu$ and $\nu$ under $\mathbf{P}$, respectively. Then
  $$ \| \mu - \nu \|_{TV} \leq \mathbf{P}(X \neq Y). $$
  Moreover, the equality can be achieved for some coupling $(X, Y)$, which we call an optimal coupling.

Now let $m, n \geq 0$ and $i, j \in S$ be given, and consider a probability law $\mathbf{P}$ under which the followings hold:


*

*$(X, Y)$ is an optimal coupling corresponding to $\mu(\cdot) = p^m(i, \cdot) $ and $\nu(\cdot) = p^m(j, \cdot)$.

*$\{(\tilde{X}_x, \tilde{Y}_y) : x, y \in S\}$ is a family of RVs, independent of $(X, Y)$, such that each $(\tilde{X}_x, \tilde{Y}_y)$ is an optimal coupling corresponding to $\mu(\cdot) = p^n(x, \cdot) $ and $\nu(\cdot) = p^n(y, \cdot)$.
Then it is easy to check that $\tilde{X}_X$ has distribution $p^{m+n}(i,\cdot)$ and $\tilde{Y}_Y$ has distribution $p^{m+n}(j, \cdot)$. So
\begin{align*}
\| p^{m+n}(i, \cdot) - p^{m+n}(j, \cdot) \|_{TV}
&\leq \mathbf{P}(\tilde{X}_X \neq \tilde{Y}_Y) \\
&= \sum_{x, y \in S} \mathbf{P}(X = x, Y = y) \mathbf{P}(\tilde{X}_x \neq \tilde{Y}_y) \\
&= \sum_{x, y \in S} \mathbf{P}(X = x, Y = y) \| p^n(x, \cdot) - p^n(y, \cdot)\|_{TV} \\
&\leq \sum_{x, y \in S} \mathbf{P}(X = x, Y = y) \alpha_n \mathbf{1}[ x \neq y ] \\
&= \mathbf{P}(X \neq Y) \cdot \alpha_n \\
&\leq \alpha_m \alpha_n.
\end{align*}
In the fourth step, we used the fact that $\| p^n(x, \cdot) - p^n(y, \cdot) \|_{TV} \leq \alpha_n$ and is zero if $x = y$. Finally, taking supremum over $i, j \in S$ proves the desired inequality.
