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

  • $\begingroup$ 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... $\endgroup$ – Sebastien Nov 17 '15 at 9:17
  • $\begingroup$ 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! $\endgroup$ – A Simmons Nov 17 '15 at 11:22
  • $\begingroup$ what a noob... Thank you. $\endgroup$ – Sebastien Nov 17 '15 at 15:05
  • $\begingroup$ It happens to the best of us! $\endgroup$ – A Simmons Nov 17 '15 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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