# Total variation distance equality

I'm trying to show that the equality is possible in: $P(X = Y) \le 1 -1/2 \operatorname{DTV} (X,Y)$

where DTV = total variation distance.

For any pair $X,Y$ there exists a pair $X', Y'$ having the same marginal distributions as $X,Y$ s.t. $P(X'=Y') = 1 -1/2 \operatorname{DTV}(X,Y)$

I thought of using the fact that If f is probability density function and $(U, V )$ is a point chosen uniformly at random from the region $\{(u, v) : -\infty < u < \infty,\ 0 \le v \le f(u)\}$ then rndm variable $U$ has probability density function $f$.

-
This is a pretty funny question because this is, word for word, the question off of my current problem set for Stat 150 at UC Berkeley. In fact, everything following the comment, "I thought of using the fact that", is the exact hint that the professor wrote for us on the problem set. Even the "I" in "If" is still capitalized, just as it is in the problem set. What a coincidence! –  user23673 Jan 25 '12 at 22:47

Let $\mu$ denote the distribution of $X$ and $\nu$ the distribution of $Y$. Consider the total variation distance $d(\mu,\nu)=\max_B\mu(B)-\nu(B)$, hence $0\leqslant d(\mu,\nu)\leqslant1$ (and $d$ is probably one half of your DTV). There exists a unique maximal positive measure, usually denoted $\mu\wedge\nu$, such that $\mu-(\mu\wedge\nu)$ and $\nu-(\mu\wedge\nu)$ are mutually singular nonnegative measures. Call $s$ the total mass of $\mu\wedge\nu$, then $d(\mu,\nu)=1-s$ is the common total mass of both measures $\mu-(\mu\wedge\nu)$ and $\nu-(\mu\wedge\nu)$. Define the pair $(X',Y')$ as follows.
Let $S$ denote a Bernoulli random variable with parameter $s=\mathrm P(S=1)=1-\mathrm P(S=0)$. Let $U$, $V$ and $W$ denote independent random variables, independent on $S$, with distributions $$\mathrm P_U=(1-s)^{-1}(\mu-(\mu\wedge\nu)),\quad \mathrm P_V=(1-s)^{-1}(\nu-(\mu\wedge\nu)),\quad \mathrm P_W=s^{-1}(\mu\wedge\nu).$$ Define $$X'=SW+(1-S)U,\qquad Y'=SW+(1-S)V.$$ In words, if $S=1$, $X'=Y'=W$ while, if $S=0$, $X'=U$ and $Y'=V$.
Then $\mathrm P_U$ and $\mathrm P_V$ are mutually singular hence $\mathrm P(U=V)=0$. Thus, $[X'=Y']=[S=1]$, which implies $\mathrm P(X'=Y')=s=1-d(\mu,\nu)$.