Matching the Shared Mass
A coupling is a way to place two random variables on the same probability space while preserving each variable’s prescribed distribution. The coupling inequality says that the probability the variables differ bounds their total variation distance from above. A sharper question is whether one can choose a coupling whose probability of disagreement is exactly that distance. For distributions on a countable state space, matching their shared probability mass gives a direct construction.
Let \(S\) be a finite or countable set, and let \(p=(p_i)_{i\in S}\) and \(q=(q_i)_{i\in S}\) be probability distributions: \(p_i,q_i\ge 0\) and \(\sum_{i\in S}p_i=\sum_{i\in S}q_i=1\). For any \(A\subseteq S\), write \(p(A)=\sum_{i\in A}p_i\), and define total variation distance by \(d_{\mathrm{TV}}(p,q)=\sup_{A\subseteq S}|p(A)-q(A)|\). A coupling of \(p\) and \(q\) is a pair of random variables \(X,Y\) on a probability space \((\Omega,\mathcal F,\mathbb P)\) such that \(\mathbb P(X=i)=p_i\) and \(\mathbb P(Y=i)=q_i\) for every \(i\in S\).
At each state, at least one of \(u_i\) and \(v_i\) is zero: if \(p_i\le q_i\), then \(u_i=0\); if \(q_i\le p_i\), then \(v_i=0\). Thus the residual distributions have no state at which both place positive mass. This is what makes it possible to couple all the common mass on the diagonal and have every residual draw disagree.
Proof. First relate the two formulas for total variation to the common mass. Put \(c_i=p_i-q_i\). Since both distributions sum to \(1\), \(\sum_i c_i=0\). The sum of the positive \(c_i\)'s therefore equals the absolute sum of the negative \(c_i\)'s, and each equals \(\tfrac12\sum_i|c_i|\). For any \(A\subseteq S\), \(\sum_{i\in A}c_i\) is at most \(\sum_{i:c_i>0}c_i\), and its negative is at most \(\sum_{i:c_i<0}(-c_i)\). Both bounds equal \(\tfrac12\sum_i|c_i|\). Taking \(A_+=\{i:p_i>q_i\}\) attains the positive bound, so \(d_{\mathrm{TV}}(p,q)=\tfrac12\sum_i|p_i-q_i|\). Also \(\min(p_i,q_i)=\tfrac12(p_i+q_i-|p_i-q_i|)\). Summing this identity gives \(\alpha=1-\tfrac12\sum_i|p_i-q_i|\), hence \(d_{\mathrm{TV}}(p,q)=1-\alpha\). These sums are well-defined because the distributions are summable and \(|p_i-q_i|\le p_i+q_i\).
Now construct the coupling. If \(r>0\), prescribe the joint probabilities \(\mathbb P(X=i,Y=j)=a_i\mathbf 1_{\{i=j\}}+\frac{u_i v_j}{r}\). They are nonnegative. Summing over \(j\) gives \(a_i+u_i(\sum_jv_j)/r=a_i+u_i=p_i\); summing over \(i\) gives \(a_j+v_j(\sum_i u_i)/r=a_j+v_j=q_j\). Thus these are the required marginals. Since \(u_i v_i=0\) for every \(i\), the residual term puts no mass on the diagonal. Its total mass is \((\sum_i u_i)(\sum_jv_j)/r=r\), while the diagonal common mass totals \(\alpha\). Consequently \(\mathbb P(X\ne Y)=r=1-\alpha=d_{\mathrm{TV}}(p,q)\).
If \(r=0\), then \(\alpha=1\), and \(u_i=v_i=0\) for all \(i\): nonnegative residual masses sum to zero. The joint law \(\mathbb P(X=i,Y=i)=a_i\), with zero probability off the diagonal, has the required marginals and mismatch probability zero. Finally, for any coupling and any \(i\), \(\mathbb P(X=Y=i)\le p_i\) and \(\mathbb P(X=Y=i)\le q_i\), so \(\mathbb P(X=Y=i)\le a_i\). Summing over \(i\) yields \(\mathbb P(X=Y)\le\alpha\), or \(\mathbb P(X\ne Y)\ge1-\alpha=d_{\mathrm{TV}}(p,q)\). This proves both the construction and its optimality. \(\square\)
Computing the Coupling
The construction separates each distribution into two parts. The common mass \(a_i\) is assigned to the event \(X=Y=i\). If any probability remains, the residual masses are paired; the formula above pairs them independently after normalizing each to total mass one. Because the two residuals never overlap at a state, this part always produces a mismatch. If \(r=0\), no residual draw is needed; if \(r=1\), there is no common mass to match.
Worked Example: A Three-State Coupling
On \(S=\{1,2,3\}\), take \(p=(\tfrac12,\tfrac13,\tfrac16)\) and \(q=(\tfrac13,\tfrac12,\tfrac16)\). Each is a probability distribution: \(\tfrac12+\tfrac13+\tfrac16=1\) and \(\tfrac13+\tfrac12+\tfrac16=1\). Find a maximal coupling.
The common masses are \(a_1=\min(\tfrac12,\tfrac13)=\tfrac13\), \(a_2=\min(\tfrac13,\tfrac12)=\tfrac13\), and \(a_3=\min(\tfrac16,\tfrac16)=\tfrac16\). Hence \(\alpha=\tfrac13+\tfrac13+\tfrac16=\tfrac56\), and \(r=1-\tfrac56=\tfrac16\). The residual vectors are \(u=(\tfrac16,0,0)\) and \(v=(0,\tfrac16,0)\). The residual term \(u_i v_j/r\) is \(\tfrac16\) at \((i,j)=(1,2)\) and zero at every other pair. The joint distribution, with rows indexed by \(X\) and columns by \(Y\), is
Check: Its row sums are \(\tfrac13+\tfrac16=\tfrac12\), \(\tfrac13\), and \(\tfrac16\), which give \(p\). Its column sums are \(\tfrac13\), \(\tfrac16+\tfrac13=\tfrac12\), and \(\tfrac16\), which give \(q\). The only off-diagonal mass is \(\tfrac16\), so the mismatch probability is \(\tfrac16\). Independently, \(\tfrac12\sum_i|p_i-q_i|=\tfrac12(\tfrac16+\tfrac16+0)=\tfrac16\), confirming the total variation distance.
Worked Example: A Countably Infinite State Space
Let \(S=\{0,1,2,\ldots\}\), with \(p_n=2^{-(n+1)}\) for \(n\ge0\), and \(q_0=0,\ q_n=2^{-n}\) for \(n\ge1\). Both distributions sum to one: \(\sum_{n\ge0}2^{-(n+1)}=1\), and \(\sum_{n\ge1}2^{-n}=1\). Compute the common mass and describe the maximal coupling.
At state zero the common mass is \(\min(\tfrac12,0)=0\). For each \(n\ge1\), \(q_n=2^{-n}\) is larger than \(p_n=2^{-(n+1)}\), so the common mass is \(a_n=2^{-(n+1)}\). Summing over these states gives \(\alpha=\sum_{n\ge1}2^{-(n+1)}=\tfrac12\), and thus \(r=\tfrac12\). The residual masses are \(u_0=\tfrac12\), \(u_n=0\) for \(n\ge1\), and \(v_0=0\), \(v_n=2^{-n}-2^{-(n+1)}=2^{-(n+1)}\) for \(n\ge1\).
Place probability \(2^{-(n+1)}\) on \((X,Y)=(n,n)\) for every \(n\ge1\). The remaining joint mass is placed on \((0,n)\), with probability \(u_0v_n/r=(\tfrac12\cdot2^{-(n+1)})/(\tfrac12)=2^{-(n+1)}\) for every \(n\ge1\). The diagonal probabilities sum to \(\sum_{n\ge1}2^{-(n+1)}=\tfrac12\); the off-diagonal probabilities also sum to \(\tfrac12\).
Check: The \(X=0\) row has total mass \(\sum_{n\ge1}2^{-(n+1)}=\tfrac12=p_0\). For each \(n\ge1\), the \(X=n\) row has mass \(2^{-(n+1)}=p_n\). The \(Y=n\) column, for \(n\ge1\), has diagonal mass \(2^{-(n+1)}\) and off-diagonal mass \(2^{-(n+1)}\), totaling \(2^{-n}=q_n\); the \(Y=0\) column has mass zero, as required. Therefore the mismatch probability is \(\tfrac12\), which agrees with \(1-\alpha=\tfrac12\).
Worked Example: Identical Distributions
Suppose \(S=\{1,2,3\}\) and \(p=q=(\tfrac14,\tfrac12,\tfrac14)\). Each distribution sums to \(\tfrac14+\tfrac12+\tfrac14=1\). Here \(a_i=p_i=q_i\) at every state, so \(\alpha=\tfrac14+\tfrac12+\tfrac14=1\) and \(r=0\). The maximal coupling puts probabilities \(\tfrac14,\tfrac12,\tfrac14\) on \((1,1),(2,2),(3,3)\), respectively, and zero elsewhere.
Check: Both marginals are \((\tfrac14,\tfrac12,\tfrac14)\), and the mismatch probability is zero. The total variation calculation also gives \(\tfrac12(0+0+0)=0\). The case \(r=0\) is handled directly by the diagonal coupling; the residual-product formula with denominator \(r\) is not used.
Worked Example: Disjoint Supports
On \(S=\{1,2\}\), let \(p=(1,0)\) and \(q=(0,1)\). Their entries are nonnegative and each row of probabilities sums to one. At both states the minimum of the two masses is zero, so \(\alpha=0\) and \(r=1\). The residual vectors are \(u=(1,0)\) and \(v=(0,1)\). The construction assigns probability \(u_1v_2/r=1\) to \((X,Y)=(1,2)\) and zero to all other pairs.
Check: The row sums are \(1,0\), giving \(p\), and the column sums are \(0,1\), giving \(q\). The mismatch probability is \(1\). Also, \(\tfrac12(|1-0|+|0-1|)=1\), as required. This is the endpoint \(r=1\): no shared mass is available to match.
Why the Exact Value Matters
The coupling inequality gives an upper bound on total variation using the mismatch probability of any chosen coupling. A maximal coupling shows that this bound is sharp: among all possible joint arrangements with the specified marginals, the least possible mismatch probability is exactly the total variation distance. The construction is useful whenever a problem asks for a coupling with as much agreement as possible. Its ingredients are only the two marginal distributions and their common mass; no transition mechanism or process-level construction is needed here.
Common mistake. In the three-state example, the absolute differences are \(\tfrac16,\tfrac16,0\). Calling their sum \(\tfrac13\) the total variation distance gives the wrong answer. Total variation is half the sum of absolute differences, so it is \(\tfrac12(\tfrac16+\tfrac16+0)=\tfrac16\). This factor of one half is essential: the positive differences sum to the same amount as the absolute negative differences, and either side—not both sides together—is the largest possible probability difference over a set.
Another potential error is to put the residual mass on the diagonal as well. At any fixed state \(i\), at least one of \(u_i,v_i\) is zero, so the residual coupling cannot produce \((i,i)\). That property is exactly why all residual probability contributes to disagreement. If a proposed construction has residual diagonal mass, it has not separated the shared mass from the unmatched mass as specified.
Check Your Understanding
Use the common-mass construction and verify the marginal distributions in each case.
- For \(p=(\tfrac34,\tfrac14)\) and \(q=(\tfrac12,\tfrac12)\), compute each \(a_i\), the unmatched mass \(r\), and the maximal mismatch probability.
- Explain why \(u_i v_i=0\) for every state, including when \(p_i=q_i\).
- For distributions on a countable set, show that \(\sum_i\min(p_i,q_i)=1-\tfrac12\sum_i|p_i-q_i|\).
- What special construction applies when the distributions are identical, and why is the residual-product formula not used in that case?
- For any coupling \((X,Y)\), justify the bound \(\mathbb P(X=Y)\le\sum_i\min(p_i,q_i)\).