Submultiplicativity of the Coupling Contraction Coefficient

Measuring Separation Between Transition Rows

Two starting states may produce different distributions after one step, even when they use the same transition rule. A useful measure of this one-step separation is the largest total variation distance between any two rows of the transition matrix. This coefficient quantifies the strongest possible contraction of distributional differences in one transition. Its key property is multiplicative: over several steps, the coefficient is no larger than the product of the coefficients over the component blocks of steps.

Let $(X_n)_{n\ge0}$ be a Markov chain on a finite or countable state space $S$, defined on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, with transition matrix $P=(p_{ij})$. Each entry is nonnegative, and every row sums to $1$. A probability distribution on $S$ is a row vector $\mu=(\mu_i)_{i\in S}$, where $\mu_i\ge0$ and $\sum_i\mu_i=1$.

Definition: For probability distributions $\mu,\nu$ on $S$, their total variation distance is $$ \|\mu-\nu\|_{\mathrm{TV}}=\frac12\sum_{j\in S}|\mu_j-\nu_j|. $$ The coupling contraction coefficient of $P$ is $$ \delta(P)=\sup_{i,k\in S}\|P(i,\cdot)-P(k,\cdot)\|_{\mathrm{TV}} =\frac12\sup_{i,k\in S}\sum_{j\in S}|p_{ij}-p_{kj}|. $$ For finite $S$, this supremum is a maximum.

The coefficient lies between $0$ and $1$, since the total variation distance between probability distributions is at most $1$. It is $0$ precisely when all rows are identical, and it is $1$ if some pair of rows has disjoint support. The name “coupling contraction coefficient” reflects its connection with coupling arguments, but the results below follow directly from the definition and the triangle inequality.

Why the Coefficient Contracts Distributions

For distributions $\mu,\nu$, the transition step changes them to $\mu P,\nu P$. The next result shows that their distance cannot be multiplied by more than $\delta(P)$. The proof handles arbitrary distributions, not just distributions concentrated at single states.

Theorem: Let $P$ be a stochastic matrix on a finite or countable state space $S$. For any probability distributions $\mu,\nu$ on $S$, $$ \|\mu P-\nu P\|_{\mathrm{TV}} \le \delta(P)\|\mu-\nu\|_{\mathrm{TV}}. $$

Proof. Put $x=\mu-\nu$. Then $\sum_i x_i=0$. Define $x_i^+=\max(x_i,0)$ and $x_i^-=\max(-x_i,0)$. Since $x$ has total sum zero, the sums of its positive and negative parts agree; write their common value as $d$. The definition of total variation gives $d=\tfrac12\sum_i|x_i|=\|\mu-\nu\|_{\mathrm{TV}}$. If $d=0$, then $x=0$, so the claimed inequality holds. If $d>0$, define probability distributions $\alpha_i=x_i^+/d$ and $\beta_i=x_i^-/d$. Thus $x=d(\alpha-\beta)$. By matrix multiplication, $\alpha P-\beta P=\sum_{i,k}\alpha_i\beta_k\big(P(i,\cdot)-P(k,\cdot)\big)$: the coefficient of $P(i,\cdot)$ in the first part is $\alpha_i\sum_k\beta_k=\alpha_i$, and the second part follows in the same way. The triangle inequality for the sum of absolute values therefore gives $$ \|\alpha P-\beta P\|_{\mathrm{TV}} \le\sum_{i,k}\alpha_i\beta_k\|P(i,\cdot)-P(k,\cdot)\|_{\mathrm{TV}} \le\sum_{i,k}\alpha_i\beta_k\delta(P)=\delta(P). $$ For countable $S$, the sums are legitimate: all mixture weights are nonnegative with total sum $1$, and the row differences have total variation norm at most $1$, so the triangle inequality applies to the convergent mixtures. Finally, $\mu P-\nu P=d(\alpha P-\beta P)$; multiplying the bound by $d=\|\mu-\nu\|_{\mathrm{TV}}$ proves the assertion. $\square$

This inequality explains why the row-based definition controls all starting distributions. Conversely, taking $\mu$ and $\nu$ to be point masses at $i$ and $k$ shows that $\delta(P)$ is exactly the largest contraction ratio required when comparing two starting states. If the two rows agree, their distance is zero; the theorem also covers that degenerate case.

Submultiplicativity Under Matrix Products

For stochastic matrices $P$ and $R$ on the same state space, the product $PR$ is again stochastic. Its $i$th row is $P(i,\cdot)R$: first take one transition using $P$, then one using $R$. The contraction result can therefore be applied to each pair of rows of $P$.

Theorem: For stochastic matrices $P$ and $R$ on a common finite or countable state space, $$ \delta(PR)\le\delta(P)\delta(R). $$ Consequently, for every integer $n\ge1$, $$ \delta(P^n)\le\delta(P)^n. $$

Proof. First, $PR$ is stochastic: its entries are nonnegative, and for each $i$, $\sum_j(PR)_{ij}=\sum_j\sum_k p_{ik}r_{kj}=\sum_kp_{ik}\sum_jr_{kj}=\sum_kp_{ik}=1$. For any states $i,k$, the corresponding rows of $PR$ are $P(i,\cdot)R$ and $P(k,\cdot)R$. Apply the preceding theorem with transition matrix $R$ and input distributions $P(i,\cdot)$ and $P(k,\cdot)$. It yields $$ \|(PR)(i,\cdot)-(PR)(k,\cdot)\|_{\mathrm{TV}} \le\delta(R)\|P(i,\cdot)-P(k,\cdot)\|_{\mathrm{TV}} \le\delta(R)\delta(P). $$ Taking the supremum over $i,k$ proves the product inequality. For powers, the case $n=1$ is equality. If the bound holds for $n$, then $P^{n+1}=P^nP$, so the product inequality gives $\delta(P^{n+1})\le\delta(P^n)\delta(P)\le\delta(P)^n\delta(P)=\delta(P)^{n+1}$. Induction proves the stated bound for every $n\ge1$. $\square$

A block version follows by repeated application of the same product inequality: for positive integers $m,n$, $\delta(P^{m+n})\le\delta(P^m)\delta(P^n)$. More generally, if a block of $r$ transitions has coefficient $c=\delta(P^r)$, then for integers $q\ge0$ and $0\le s<r$, $\delta(P^{qr+s})\le c^q\delta(P^s)$, where $P^0$ is the identity matrix and $\delta(P^0)\le1$. This is an algebraic statement about row separation; it requires no assumption of irreducibility, aperiodicity, or existence of a stationary distribution.

Worked Example: A Two-State Chain and Its Second Power

Consider $S=\{1,2\}$ and $$ P=\begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac14&\tfrac34\end{bmatrix}. $$ Both rows sum to $\tfrac34+\tfrac14=1$ and $\tfrac14+\tfrac34=1$. The total variation distance between the two rows is $\tfrac12(|\tfrac34-\tfrac14|+|\tfrac14-\tfrac34|)=\tfrac12(\tfrac12+\tfrac12)=\tfrac12$, while a row compared with itself has distance $0$. Hence $\delta(P)=\tfrac12$.

Compute the square by multiplying rows by $P$: $$ P^2=\begin{bmatrix} \tfrac34\cdot\tfrac34+\tfrac14\cdot\tfrac14& \tfrac34\cdot\tfrac14+\tfrac14\cdot\tfrac34\\ \tfrac14\cdot\tfrac34+\tfrac34\cdot\tfrac14& \tfrac14\cdot\tfrac14+\tfrac34\cdot\tfrac34 \end{bmatrix} =\begin{bmatrix}\tfrac58&\tfrac38\\[2pt]\tfrac38&\tfrac58\end{bmatrix}. $$ Each row of $P^2$ sums to $\tfrac58+\tfrac38=1$, and the two rows have total variation distance $\tfrac12(|\tfrac58-\tfrac38|+|\tfrac38-\tfrac58|)=\tfrac12(\tfrac14+\tfrac14)=\tfrac14$. Thus $\delta(P^2)=\tfrac14=\delta(P)^2$, verifying the bound with equality.

Check: The direct two-step probability of returning to state $1$ from state $1$ is $(\tfrac34)^2+(\tfrac14)^2=\tfrac9{16}+\tfrac1{16}=\tfrac58$, the first entry displayed in $P^2$.

Worked Example: A Three-State Product with Strict Inequality

Let $S=\{1,2,3\}$ and $$ P=\begin{bmatrix} \tfrac12&\tfrac12&0\\ 0&\tfrac12&\tfrac12\\ \tfrac14&\tfrac12&\tfrac14 \end{bmatrix}. $$ The row sums are $\tfrac12+\tfrac12+0=1$, $0+\tfrac12+\tfrac12=1$, and $\tfrac14+\tfrac12+\tfrac14=1$. The distance between rows 1 and 2 is $\tfrac12(\tfrac12+0+\tfrac12)=\tfrac12$; between rows 1 and 3 it is $\tfrac12(\tfrac14+0+\tfrac14)=\tfrac14$; and between rows 2 and 3 it is $\tfrac12(\tfrac14+0+\tfrac14)=\tfrac14$. Therefore $\delta(P)=\tfrac12$.

Multiplying each row by $P$ gives $$ P^2=\begin{bmatrix} \tfrac14&\tfrac12&\tfrac14\\ \tfrac18&\tfrac12&\tfrac38\\ \tfrac3{16}&\tfrac12&\tfrac5{16} \end{bmatrix}. $$ For example, the third row is $\tfrac14P(1,\cdot)+\tfrac12P(2,\cdot)+\tfrac14P(3,\cdot)$, whose coordinates are $\tfrac18+\tfrac1{16}=\tfrac3{16}$, $\tfrac18+\tfrac14+\tfrac18=\tfrac12$, and $\tfrac14+\tfrac1{16}=\tfrac5{16}$. The row sums of $P^2$ are $\tfrac14+\tfrac12+\tfrac14=1$, $\tfrac18+\tfrac12+\tfrac38=1$, and $\tfrac3{16}+\tfrac8{16}+\tfrac5{16}=1$.

The distances between rows 1 and 2, 1 and 3, and 2 and 3 of $P^2$ are respectively $\tfrac12(\tfrac18+0+\tfrac18)=\tfrac18$, $\tfrac12(\tfrac1{16}+0+\tfrac1{16})=\tfrac1{16}$, and $\tfrac12(\tfrac1{16}+0+\tfrac1{16})=\tfrac1{16}$. Hence $\delta(P^2)=\tfrac18\le\tfrac14=\delta(P)^2$. The inequality is strict here.

Worked Example: Identical Rows and Zero Contraction

Let $S=\{1,2,3\}$, and let every row of $P$ equal $(\tfrac12,\tfrac13,\tfrac16)$. This matrix is stochastic because each row sums to $\tfrac12+\tfrac13+\tfrac16=\tfrac36+\tfrac26+\tfrac16=1$. Every pair of rows has total variation distance $0$, so $\delta(P)=0$.

Each row of $P^2$ is the same mixture of the rows of $P$, with weights $(\tfrac12,\tfrac13,\tfrac16)$. Since those rows are identical, the mixture remains $(\tfrac12,\tfrac13,\tfrac16)$. Thus $P^2=P$, its rows again sum to $1$, and $\delta(P^2)=0$. This verifies $\delta(P^2)\le\delta(P)^2$ in the zero-coefficient case: both sides are $0$.

A Common Matrix-Power Pitfall

When calculating a power, keep track of which step the multiplication represents. For the two-state matrix in the first example, its first row in $P^2$ is $(\tfrac58,\tfrac38)$. Multiplying this row by $P$ gives first coordinate $\tfrac58\cdot\tfrac34+\tfrac38\cdot\tfrac14=\tfrac{15}{32}+\tfrac3{32}=\tfrac9{16}$, and second coordinate $\tfrac58\cdot\tfrac14+\tfrac38\cdot\tfrac34=\tfrac5{32}+\tfrac9{32}=\tfrac7{16}$. These are the coordinates of the first row of $P^3$, not $P^2$.

A common incorrect calculation labels $(\tfrac9{16},\tfrac7{16})$ as the first row of $P^2$. The correction is to calculate a two-step entry directly: $(P^2)_{11}=p_{11}p_{11}+p_{12}p_{21}=(\tfrac34)^2+(\tfrac14)^2=\tfrac9{16}+\tfrac1{16}=\tfrac58$. The two-step second coordinate is $(P^2)_{12}=(\tfrac34)(\tfrac14)+(\tfrac14)(\tfrac34)=\tfrac3{16}+\tfrac3{16}=\tfrac38$. The resulting row is $(\tfrac58,\tfrac38)$, which sums to $1$. Multiplying that row by $P$ is one additional transition, so it computes $P^3$.

The coefficient is useful because it summarizes the worst-case separation of all transition rows in a single number. If it is strictly less than $1$, the contraction theorem guarantees a uniform reduction in the total variation distance between any two evolving distributions at each step. If a particular multi-step block has coefficient less than $1$, submultiplicativity lets one repeat that block and bound the separation after many transitions. The bound is a guarantee, not necessarily an equality, as the three-state example demonstrates.

Check Your Understanding

Use the definitions and results above to answer these questions. For each computation, show the row sums before using the matrix.

For a two-state transition matrix with rows $(\tfrac23,\tfrac13)$ and $(\tfrac13,\tfrac23)$, compute $\delta(P)$.
Why is the coefficient defined using the supremum on a countable state space, while it is a maximum on a finite state space?
State the distribution-contraction inequality for $\mu,\nu$, and identify the role of $\delta(P)$ in it.
If $\delta(P^3)=\tfrac25$, what bound does submultiplicativity give for $\delta(P^6)$?
What power is computed when the first row of $P^2$ is multiplied by $P$, and why is that not a calculation of a row of $P^2$?

Submultiplicativity of the Coupling Contraction Coefficient

What You'll Learn