Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 1 down vote accepted


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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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