Simple trace distance problem

I am self studying a course on information theory and came with the following question:

$A$ and $B$ represent two possibly different probability distributions representing two different independent experiments with the same outcomes. You get one random outcome from one of the two experiments. What is the probability that you guess correctly the originating experiment and what is the relation of this probability to the trace distance between $A$ and $B$?

The trace distance between two distributions defined on the same alphabet is $\delta(A,B)=\min_{P_{XX'}}p\lbrace X\neq X'\rbrace$, where the minimum is taken for all distributions with marginals $A$ and $B$.

The solution, that is the guessing success probability $p_s$, is hinted to be: $$p_s=\frac{1}{2}(1+\delta(A,B))$$ Working the exercise backwards it is easy to get:

$$p_s=\frac{1}{2}+\frac{1}{2}\min_{P_{XX'}}p\lbrace X\neq X'\rbrace$$ This sounds plausible, the guessing probability is one half increased by the probability that both distributions are different. But I am clueless about how it could be derived. Hints are preferred to the solution, but if it is too simple I'll accept also spoilers.

-
You are equating a probability distribution, namely $P$, and a number, namely $\frac12(1+\delta(P,Q))$. –  Did Jul 3 '12 at 18:45
More to the point, you seem to be using the letter $P$ for at least two different things in your question, possibly three or four. It would help if you could edit your question to reduce that ambiguity. –  Ilmari Karonen Jul 3 '12 at 20:56
Just corrected the ambiguity. Thanks for the remarks. –  Euclean Jul 3 '12 at 21:26

1 Answer

Hints:

Let $A(x)$ and $B(x)$ denote the probability of $x$ in the distribution $x$. (I'm assuming you're only interested in discrete measures.) After seeing $x$, I'd guess $A$ if $A(x)\geq B(x)$ and otherwise $B$. So the probability of success can be written as $$\frac{1}{2}\left[ \sum_{x:A(x)\geq B(x)} A(x)+\sum_{x:A(x)<B(x)} B(x)\right].$$

Now relate this to joint distributions. Show that the probability of $(x,x)$ in any coupling of $A$ and $B$ is at most $\min(A(x),B(x))$, and that this maximum can be attained.

-
From your formula it wasn't hard to derive the result: \begin{eqnarray}p_s&=&\frac{1}{2}\sum_x\max(A(x),B(x))\\&=&\frac{1}{2}\sum_x(1- \min (1-A(x),1-B(x)))\end{eqnarray} –  Euclean Jul 4 '12 at 10:02
\begin{eqnarray}&=&\frac{1}{2}\sum_x(0.5A(x)+0.5B(x)+0.5|B(x)-A(x)|)\\&=& \frac{1}{2}\sum_x(1+\delta(B,A))\end{eqnarray} –  Euclean Jul 4 '12 at 10:07
However, I understand that the guess should be A if A(x)≥B(x) and B otherwise, but why is the success probability given by the formula that you wrote? –  Euclean Jul 4 '12 at 10:09
The experiment is either $A$ or $B$, each with probability $1/2$. Given that experiment $A$ is chosen, the event of success is the same as the event that $A(x)\geq B(x)$. Given that experiment $B$ is chosen, the event of success is the same as the event that $B(x)> A(x)$. –  Colin McQuillan Jul 4 '12 at 10:49