Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
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
add comment

1 Answer

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)$.

This construction is a classical application of the coupling method and is explained, if I remember correctly, in the first chapter of Lindvall's book.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.