# Coupling and Total variational distance

Suppose we have two distributions: $\mu$ and $\upsilon$ on $\{1,2,3\}$. $\mu(1) = 1/2, \mu(2) = 1/3, \mu(3) = 1/6,\upsilon(1) = 1/3, \upsilon(2) = 1/6, \upsilon(3) = 1/2$. Could anyone explain to me (as simply as possible since I'm at a beginner level in stats) how I can compute the total variation distance of $\mu$ and $\upsilon$? Also, how one should go about constructing a coupling $(X,Y)$ of $\mu$ and $\upsilon$ such that $P(X\not=Y)$ is equal to the total variational distance between $\mu$ and $\upsilon$? Much thanks for helping me understand the concept and problem.

There are at least 2 ways to compute the total variation distance. The first is by using the definition of Total variation distance:

$TV(\mu,\nu)=\sup_{ A\in \mathcal{F}}\left|\mu(A)-\nu(A)\right|,$

where $\mathcal{F}$ is the sigma-algebra. In this (finite) case, you can think of the sigma-algebra as the power-set of your sample space $\Omega =\{1,2,3\}$, if you are unfamiliar with sigma-algebras or measure theoretic language more generally. The sigma-algebra (power-set) is $\{\{\varnothing\}, \{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\} \}$. Now if we take each of these sets 1-by-1 we calculate:

$$\left|\mu(\varnothing)-\nu(\varnothing)\right| =| 0 -0|=0,$$ $$\left|\mu(1)-\nu(1)\right| =|1/2-1/3|=1/6,$$ $$\left|\mu(2)-\nu(2)\right| =|1/3-1/6|=1/6,$$ $$\left|\mu(3)-\nu(3)\right| =|1/6-3/6|=1/3,$$ $$\left|\mu(1,2)-\nu(1,2)\right| =|(3+2)/6-(2+1)/6|=1/3,$$ $$\left|\mu(1,3)-\nu(1,3)\right| =|4/6-5/6|=1/6,$$ $$\left|\mu(2,3)-\nu(2,3)\right| =|3/6-4/6|=1/6,$$ $$\left|\mu(1,2,3)-\nu(1,2,3)\right| =|1-1|=0.$$ Now we see by inspection there are 2 sets that achieve the maximum, $\{3\}$ and $\{1,2\}$, the complement of the set $\{1,2\}$. We'll see in a brief moment why the supremum is achieved on a set and the set's complement always for total variation distance.

The second method to calculate the total variation distance uses the following result:

$$TV(\mu,\nu)=\sup_{ A\in \mathcal{F}}\left|\mu(A)-\nu(A)\right|=\frac{1}{2}\sum_{i=1}^n\left| \mu(i) -\nu(i)\right|.$$

This can be seen by partitioning the sets $A\in \mathcal{F}$ into 2 groups; those with $\{\mu(A)>\nu(A)\}$ and those with $\{\mu(A)\leq\nu(A)\}$. Now appealing to the symmetry of the absolute value function the two sets will have the same supremum value and therefore the total variation distance will be counted twice. To account for the double counting we divide by 2. Unfortunately, whether or not to divide by 2 is not standardized so some authors omit the division by 2. Using the summation formula instead of the supremum formula,

$$TV(\mu,\nu)= \sum_{i=1}^n\left|\mu(i) -\nu(i)\right| =\frac{|1/2-1/3|+|1/3-1/6|+|1/6-1/2|}{2} = \frac{2}{3}\frac{1}{2}=\frac{1}{3}.$$ The two quantities agree and this latter formula is much more amenable to computation (taking linear time on a discrete set rather than exponential time). Often times this latter formula is taken as the definition and the supremum is not even discussed. Note that in the continuous case you replace the sum with an integral over the two measures. Clearly the smallest value of the total variation distance is $0$ if the two measures are the same. If the two measures share no support in common (e.g. $\mu(1) =1$, and $\nu(2)=1$. Then the total variation distance will be $1$ and no larger value can be achieved.

This answers the first part of your question; how to calculate the total variation distance on this set.

The second part of the questions asks about the coupling construction so that $\Pr(X\neq Y)=TV(\mu, \nu)$ where $X\sim\mu$ and $Y\sim\nu$. Now define the cost function $c(X,Y) =\mathbb{1}_{X\neq Y}$ where $\mathbb{1}_A$ is the indicator (sometimes called characteristic in other branches of math) of the set $A$ taking the value $1$ when the argument to the indicator function is in the set $A$. The coupling construction of total variation states

$$TV(\mu,\nu)=\inf_{ \pi\in X\times Y} \mathbb{E}(c(X,Y)),$$ and the product space $X\times Y$ is required to have the given marginals $\mu$ and $\nu$ for $X$ and $Y$ respectively. A graph depiction of the solution

shows the amount you must move from $i$th element of $\mu$ to $j$th element of $\nu$. To achieve this on a discrete set of points like this you construct a joint probability function on the space of $X\times Y$ via a linear program with

$$C = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{bmatrix},$$ is your cost matrix, $C_{ij} = c(X_i, Y_j)$. Secondly your joint probability space will be $$P = \begin{bmatrix} p_{11} & p_{12} & p_{13} \\ p_{21} & p_{22} & p_{23} \\ p_{31} & p_{32} & p_{33} \\ \end{bmatrix}.$$ Also you'll need to define $$\vec{b} = \begin{bmatrix} \mu(1) \\ \mu(2) \\ \mu(3) \\ \nu(1) \\ \nu(2) \\ \nu(3) \\ \end{bmatrix},$$ and finally the matrix $A$, $$A = \begin{bmatrix} 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ \end{bmatrix}.$$ Now solving the linear program

$$min_{P}( vec(C)^T vec(P) \vert Avec(P) = \vec{b}),$$ will give you the total variation distance (the objective function value at optimality) and the join probability $P$ (arguments at optimality). Note here that $vec()$ denotes the $vec()$ matrix operator which takes a matrix and returns the vector that results from stacking the columns from left to right of the matrix to obtain a single column vector.

The values of $C$ are not arbitrary any number instead of $1$ for all non-diagonal entries would require you need to rescale the objective function at optimality by the constant. Running the linear program through lpSolve() in R yields the same value $1/3$ for the objective function.

library(lpSolve)

f.obj <- c(0, 1, 1, 1, 0, 1, 1, 1, 0)

f.con <- matrix (c(1, 0, 0, 1, 0, 0, 1, 0, 0,
0, 1, 0, 0, 1, 0, 0, 1, 0,
0, 0, 1, 0, 0, 1, 0, 0, 1,
1, 1, 1, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 1, 1, 0, 0, 0,
0, 0, 0, 0, 0, 0, 1, 1, 1
), nrow=6, byrow=TRUE)
f.dir <- c("=", "=", "=", "=", "=", "=")
f.rhs <- c(1/2, 1/3, 1/6, 1/3, 1/6,1/2)
# Now run.
lpSoln <- lp ("min", f.obj, f.con, f.dir, f.rhs)
lpSoln
Success: the objective function is 0.3333333
lpSoln$solution [1] 0.3333333 0.0000000 0.0000000 0.0000000 0.1666667 0.0000000 0.1666667 0.1666667 [9] 0.1666667  In words the solution is intrpreted as: 1. move$1/3$from state$1$to state$1$. 2. move$1/6$from state$2$to state$2$. 3. move$1/6$from state$3$to state$3$. 4. move$1/6$from state$1$to state$3$. 5. move$1/6$from state$2$to state$3$. So that the optimal matrix $$P=\begin{bmatrix} 1/3& 0 & 1/6 \\ 0 & 1/6 & 1/6 \\ 0 & 0 & 1/6 \\ \end{bmatrix}.$$ In any finite space this sort of construction, although tedious, will get you to the total variation distance. • is$\{1,2\}$the union of the events$\{1\}$and$\{2\}$or the intersection? – rtrtrt May 25 '19 at 18:58 •$\{ 1,2\} \$ is the set containing both events, so the union. – Lucas Roberts May 25 '19 at 19:14