Maximal Coupling Total Variation

Worked example: Maximal coupling of P and Q

Consider the sample space {0, 1, 2} and two distributions:

• P = (0.5, 0.3, 0.2)
• Q = (0.2, 0.5, 0.3)

We first calculate the element-wise minimums (the overlapping probability mass):

1. For outcome 0: min(0.5, 0.2) = 0.2
2. For outcome 1: min(0.3, 0.5) = 0.3
3. For outcome 2: min(0.2, 0.3) = 0.2

The total sum of these minimums is s = 0.2 + 0.3 + 0.2 = 0.7. This is the maximum agreement probability.

The total variation distance is the remaining probability mass: TV = 1 - s = 0.3.

The maximal coupling joint distribution J is constructed by placing the minimums on the diagonal, and distributing the residual mass proportionally among the off-diagonal elements:

J_i,j = δ_i,j * m_i + (P_i - m_i)(Q_j - m_j) / (1 - s)

For example, for state i=0 and j=1:

J_0,1 = 0 + (0.5 - 0.2)(0.5 - 0.3) / 0.3 = 0.3 * 0.2 / 0.3 = 0.2

Reproduce the calculation in the module

Open the Maximal Coupling Total Variation experiment to explore how the joint probability matrix is constructed for different distributions.

1. Set First law to P and Second law to Q. Set First state to 0 and Second state to 1.
2. Observe that the selected joint probability P(0, 1) is exactly 0.200000, matching our calculation.
3. The maximum agreement probability is 0.700000, which corresponds to the sum of the diagonal elements of the joint matrix.
4. Change First state to 1 and leave Second state as 1. The selected joint probability becomes 0.300000, which is the minimum of P(1)=0.3 and Q(1)=0.5, because the diagonal element takes the full overlapping mass.
5. Change Second law to Point zero, meaning Q is deterministic at state 0: Q = (1.0, 0.0, 0.0). Keep First law as P, and set states to 0 and 1. The maximum agreement is now 0.500000, because P and Q only overlap at state 0 with probability 0.5.
6. Change Second law to P to couple identical laws. The maximum agreement becomes exactly 1.000000, and the total variation distance is 0.000000. All probability mass is on the diagonal, meaning the two random variables will always be equal with probability 1.

Limitations

This construction (known as the maximal coupling or optimal coupling) explicitly builds a joint distribution that minimizes the probability of the two variables differing. However, it is not the only maximal coupling; when the residual probability mass is distributed, any valid joint distribution for the residuals will maintain the same total variation distance and maximum agreement.

Furthermore, this module focuses exclusively on discrete, finite sample spaces. While the concept extends to continuous variables and infinite spaces, constructing the exact joint density involves Radon-Nikodym derivatives and cannot be represented by a simple finite matrix.

Sources

Probability 3/4 (Durham University) explains the formal construction of maximal couplings and their relationship to total variation distance, demonstrating that the residual supports are disjoint.