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
    You are equating a probability **distribution**, namely $P$, and a number, namely $\frac12(1+\delta(P,Q))$.2012-07-03
  • 0
    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.2012-07-03
  • 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.

  • 0
    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}2012-07-04
  • 0
    \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}2012-07-04
  • 0
    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?2012-07-04
  • 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