# Statistical distance and test

Here is a bit of context and definitions:

Let $\mathcal D$ and $\mathcal E$ be distributions of probability over a finite set $A$ and $X, Y$ be random variables following $\mathcal D$ and $\mathcal E$. We define the statistical distance as:

$$\textrm{dist}(\mathcal D, \mathcal E) = \frac12 \sum_{x\in A} \mathbb | P(X=x) - \mathbb P (Y=x)|.$$ (sometimes, we write $\textrm{dist}(X,Y)$ instead)

We can show:

$$\textrm{dist}(\mathcal D,\mathcal E) = \max\left\{ \mathbb P(X\in S)- P(Y\in S); S\subset A\right\} = \sum_{x\in G_{>}} \mathbb P(X=x) - \mathbb P (Y=x),$$ where $G_>= \{x\in A; \mathbb P(X=x) > P(Y=x)\}$.

$(*)$For any function $f:A \to B$, we can also show $\textrm{dist}(f(X),f(Y)) \le \textrm{dist(X,Y)}$.

We say that $t$ is a statistical test for $\mathcal D$ and $\mathcal E$ iff $t:A \to \{0,1\}$ and we call the success probability of $t$ for $\mathcal D$ and $\mathcal E$ the quantity: $$\delta = |\mathbb P(t(X) = 1) - \mathbb P(t(Y) = 1)|$$

By $(*)$, we see that $(**)$ $\delta + |\mathbb P(t(X) = 0) - \mathbb P(t(Y) = 0)| \le \textrm{dist}(X,Y)$ and so $\delta \le \textrm{dist}(X,Y)$

Question: describe a test $t$ such that $\delta = \textrm{dist}(\mathcal D, \mathcal E)$.

As a remark $(***)$, I note that for such a statistical test, by $(**)$ we have $|\mathbb P(t(X) = 0) - \mathbb P(t(Y) = 0)|= 0$.

I propose the following test : $t = \mathbb 1_ {G_>}$ (the indicator function of the set $G_>$, defined above). Hence:

\begin{aligned} \delta &= |\mathbb P(t(X) = 1) - \mathbb P(t(Y) = 1)| \\ & = |\mathbb P(X\in G_>) - \mathbb P(Y\in G_>)|\\ &= \textrm{dist}(X,Y) \end{aligned}

My problem: I don't succeed to prove that $\mathbb P(t(X)=0) = \mathbb P(t(Y)=1)$ like it should be by my remark $(***)$. Whre did I miss something?

Your mistake is in the line where you have written $\delta + |\mathbb P(t(X) = 0) - \mathbb P(t(Y) = 0)| \le \textrm{dist}(X,Y)$.
By the definition of statistical distance, your bound here is actually $2\textrm{dist}(X,Y)$.
In fact, the expression you're trying to show is $0$ can actually also be $\textrm{dist}(X,Y)$, if $G_<\cup G_>=A$.
• I don't get why δ+|ℙ(t(X)=0)−ℙ(t(Y)=0)|≤ 2dist(X,Y). Indeed, $\textrm{dist}(t(X), t(Y)) = \delta + |\mathbb P(t(X)=0) + \mathbb P(t(Y) = 0)|$, isn't it? I don't get neither your last point : $G_{\le} \cup G_{ge}=A$ is always true... – Sebastien Nov 17 '15 at 9:17
• Sorry, that should have read $G_>$ etc, I've corrected it now. Look at your definition of Dist; you've forgotten the $\frac{1}{2}$ in your above comment! – A Simmons Nov 17 '15 at 11:22