Putting Two Distributions on One Probability Space
Total variation distance compares probability distributions by asking how differently they assign probability to events. A coupling offers a different way to make that comparison: place random variables with the two prescribed distributions on a shared probability space, then measure how often their values disagree. The central fact is that no event can distinguish the two variables more often than the variables themselves disagree. This gives a useful bound even when the coupling is not especially efficient.
Let \(S\) be a nonempty finite or countable state space, and let \(\mu\) and \(\nu\) be probability distributions on \(S\). Write \(\mu_i=\mu(\{i\})\) and \(\nu_i=\nu(\{i\})\). For this tutorial, total variation distance is defined by
Here \(\mu(A)=\sum_{i\in A}\mu_i\), and likewise for \(\nu(A)\). The supremum includes the empty set and \(S\), which both give difference zero. On a countable state space, an equivalent expression is
Why the two expressions agree. Set \(a_i=\mu_i-\nu_i\). The series of absolute differences is finite because \(|a_i|\leq \mu_i+\nu_i\), so \(\sum_i|a_i|\leq2\). Also \(\sum_i a_i=0\), since both distributions have total mass one. The sum of the positive \(a_i\)'s therefore equals the sum of the absolute values of the negative \(a_i\)'s, and each equals \(\tfrac12\sum_i|a_i|\). For any \(A\), \(\sum_{i\in A}a_i\) lies between the negative of this quantity and this quantity, so its absolute value is at most \(\tfrac12\sum_i|a_i|\). Taking \(A=\{i:a_i\geq0\}\) attains the upper bound. This proves the equivalence, including when some or all of the differences are zero.
A coupling is not a claim that \(X\) and \(Y\) are independent, nor does it prescribe a unique joint distribution. Many joint distributions can have the same two marginals. The freedom to choose their dependence is what makes couplings useful. The coupling inequality applies to every such choice.
Proof. Fix any subset \(A\subseteq S\). Because \(X\) and \(Y\) have the specified marginals, \(\mu(A)-\nu(A)=\mathbb{E}[\mathbf{1}_{\{X\in A\}}-\mathbf{1}_{\{Y\in A\}}]\). For any integrable random variable \(Z\), \(|\mathbb{E}Z|\leq\mathbb{E}|Z|\), so \[ |\mu(A)-\nu(A)| \leq\mathbb{E}\bigl|\mathbf{1}_{\{X\in A\}}-\mathbf{1}_{\{Y\in A\}}\bigr|. \] The absolute difference of these two indicators is one precisely when exactly one of \(X,Y\) lies in \(A\), and is zero otherwise. If exactly one lies in \(A\), then \(X\neq Y\). Thus the absolute difference is at most \(\mathbf{1}_{\{X\neq Y\}}\) at every outcome. Taking expectations gives \(|\mu(A)-\nu(A)|\leq\mathbb{P}(X\neq Y)\). The right-hand side does not depend on \(A\), so taking the supremum over all subsets proves the stated inequality. \(\square\)
The proof has a useful event-by-event form: the difference in probabilities of any particular event \(A\) is bounded by the probability that the coupled variables disagree. The total variation distance takes the largest such event difference, so it inherits the same bound. The inequality does not say that every coupling gives a tight bound. The examples below show both loose and sharp bounds.
Worked Example: The Independent Coupling Can Give a Loose Bound
Let \(S=\{a,b,c\}\), with \(\mu=(\tfrac12,\tfrac13,\tfrac16)\) and \(\nu=(\tfrac13,\tfrac13,\tfrac13)\), in that order. Couple \(X\) and \(Y\) independently. Compute their disagreement probability and compare it with total variation distance.
Independence means the joint probability at \((i,j)\) is \(\mu_i\nu_j\). The full joint table is
| \(X\backslash Y\) | \(a\) | \(b\) | \(c\) | Row sum |
|---|---|---|---|---|
| \(a\) | \(\tfrac16\) | \(\tfrac16\) | \(\tfrac16\) | \(\tfrac12\) |
| \(b\) | \(\tfrac19\) | \(\tfrac19\) | \(\tfrac19\) | \(\tfrac13\) |
| \(c\) | \(\tfrac1{18}\) | \(\tfrac1{18}\) | \(\tfrac1{18}\) | \(\tfrac16\) |
| Column sum | \(\tfrac13\) | \(\tfrac13\) | \(\tfrac13\) | \(1\) |
The row sums are \(\tfrac12,\tfrac13,\tfrac16\), as required for \(X\). Each column has sum \(\tfrac16+\tfrac19+\tfrac1{18}=\tfrac3{18}+\tfrac2{18}+\tfrac1{18}=\tfrac13\), as required for \(Y\). The diagonal is the event \(X=Y\), so
Meanwhile, the coordinate differences are \(\tfrac12-\tfrac13=\tfrac16\), \(\tfrac13-\tfrac13=0\), and \(\tfrac16-\tfrac13=-\tfrac16\). Therefore
The coupling inequality checks as \(\tfrac16\leq\tfrac23\). The gap is substantial: independence creates many disagreements that are not needed to account for the difference between the marginals.
Worked Example: A Coupling with a Sharp Bound
Let \(S=\{0,1\}\), with \(\mu=(\tfrac12,\tfrac12)\) and \(\nu=(\tfrac34,\tfrac14)\). Consider the joint table below, whose rows specify \(X\) and columns specify \(Y\).
| \(X\backslash Y\) | \(0\) | \(1\) | Row sum |
|---|---|---|---|
| \(0\) | \(\tfrac12\) | \(0\) | \(\tfrac12\) |
| \(1\) | \(\tfrac14\) | \(\tfrac14\) | \(\tfrac12\) |
| Column sum | \(\tfrac34\) | \(\tfrac14\) | \(1\) |
The row sums give \(\mathbb{P}(X=0)=\tfrac12\) and \(\mathbb{P}(X=1)=\tfrac14+\tfrac14=\tfrac12\). The column sums give \(\mathbb{P}(Y=0)=\tfrac12+\tfrac14=\tfrac34\) and \(\mathbb{P}(Y=1)=\tfrac14\). Thus the table is a coupling of the stated distributions, and its entries sum to one. Its disagreement probability is the sum of the off-diagonal entries, \(0+\tfrac14=\tfrac14\). The total variation distance is
Here the coupling inequality holds with equality: both quantities are \(\tfrac14\). This example verifies that the bound can be sharp for a particular coupling; the inequality itself does not require equality.
Worked Example: Disagreement and Event Disagreement Are Different
Let \(S=\{1,2,3,4\}\), and assign joint probability \(\tfrac14\) to each of \((X,Y)=(1,1),(1,2),(3,3),(3,4)\), with probability zero to all other pairs. Find both marginals, the probability of disagreement, and the probability that the event \(A=\{1,2\}\) has different membership for \(X\) and \(Y\).
The row sums give \(\mu_1=\mathbb{P}(X=1)=\tfrac14+\tfrac14=\tfrac12\), \(\mu_3=\mathbb{P}(X=3)=\tfrac14+\tfrac14=\tfrac12\), and \(\mu_2=\mu_4=0\). The column sums give \(\nu_1=\tfrac14,\nu_2=\tfrac14,\nu_3=\tfrac14,\nu_4=\tfrac14\). Both marginal distributions sum to one. The two diagonal outcomes have total probability \(\tfrac14+\tfrac14=\tfrac12\), so \(\mathbb{P}(X\neq Y)=1-\tfrac12=\tfrac12\).
For \(A=\{1,2\}\), \(\mu(A)=\tfrac12+0=\tfrac12\) and \(\nu(A)=\tfrac14+\tfrac14=\tfrac12\). Hence the event-probability difference is zero. In fact, the indicators of membership in \(A\) agree on all four outcomes: \((1,1)\) and \((1,2)\) have both values in \(A\), while \((3,3)\) and \((3,4)\) have neither value in \(A\). Thus the event-specific bound is \(0\leq\tfrac12\). The total variation distance, however, is
So the full coupling inequality is also checked, with \(\|\mu-\nu\|_{\mathrm{TV}}=\mathbb{P}(X\neq Y)=\tfrac12\), even though this particular event detects no difference. Disagreement of values is a stronger event than disagreement about membership in one fixed set.
How to Use the Inequality—and a Common Error
To apply the coupling inequality, first identify the two marginal distributions being compared. Then specify a joint distribution with those marginals, verify its row and column sums (or the corresponding marginal sums), and calculate \(\mathbb{P}(X\neq Y)\). The result is an upper bound on total variation distance. If the probability of agreement is high, the bound is small; if the coupling often disagrees, the bound may still be valid but uninformative.
In applications to a stochastic process, one may compare two distributions at a fixed time by finding random variables with those time-\(n\) distributions on one probability space. The inequality then bounds their total variation distance by their disagreement probability. This statement concerns the distributions at that fixed time; it does not by itself specify how to construct a useful joint evolution or provide a convergence rate.
Common mistake. It is incorrect to treat the disagreement probability of an arbitrary coupling as equal to total variation distance. In the independent coupling of the first example, \(\mathbb{P}(X\neq Y)=\tfrac23\), while the direct calculation gives \(\|\mu-\nu\|_{\mathrm{TV}}=\tfrac16\). The correct conclusion is \(\tfrac16\leq\tfrac23\), not equality. The coupling inequality is a one-sided bound for each chosen coupling; its proof only shows that event differences cannot exceed the disagreement probability.
Another useful check is to compute the same quantity in two ways when possible. For finite \(S\), calculate total variation both as half the sum of absolute coordinate differences and as the probability difference for a set attaining the positive coordinate differences. If the results disagree, recheck the factor \(\tfrac12\) or the selected set. In the second example, the set \(\{0\}\) gives \(|\mu(\{0\})-\nu(\{0\})|=|\tfrac12-\tfrac34|=\tfrac14\), matching the half-sum calculation.
Check Your Understanding
For each question, identify the relevant marginal or joint probabilities before comparing distributions.
- In the first worked example, what is the probability of the event \(X=a\), \(Y=b\), and how is it obtained from independence?
- For the coupling in the second example, calculate \(\mathbb{P}(X=Y)\) and verify that it is one minus the disagreement probability.
- Explain why \(|\mu(A)-\nu(A)|\leq\mathbb{P}(X\neq Y)\) holds for a fixed subset \(A\), using the two membership indicators.
- For the third example, compute \(\mu(\{1,2\})\) and \(\nu(\{1,2\})\). Why can they be equal even though \(X\) and \(Y\) disagree with positive probability?
- Suppose a proposed joint probability table has the correct row sums but a column sum differs from the claimed second marginal. Can it be a coupling of the claimed distributions? Explain.