1
$\begingroup$

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: \begin{equation} p_s=\frac{1}{2}(1+\delta(A,B)) \end{equation} Working the exercise backwards it is easy to get:

\begin{equation} p_s=\frac{1}{2}+\frac{1}{2}\min_{P_{XX'}}p\lbrace X\neq X'\rbrace \end{equation} 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.

  • 0
    Just corrected the ambiguity. Thanks for the remarks.2012-07-03

1 Answers 1

1

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)

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.

  • 1
    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).2012-07-04