Let $p(\cdot | \cdot)$ and $q(\cdot | \cdot)$ be two known channels from alphabet $X$ to $Y$. What is the optimal strategy to distinguish between them if you are allowed to use the channel only once, and what is the corresponding success probability? (Note that you can choose which probability distribution you want to use as input).

My thoughts: Since we can choose which probability distribution we want to use as input, we'll choose one with $P(x)=1$ $(x \in X)$. If $x$ goes through a channel ($p$ or $q$), and what comes out is $y \in Y$, then we will guess the channel was $p$ if $p(y|x)>q(y|x)$ and we will guess $q$ otherwise. I have a feeling that the success probability will be related to the statistical distance $\delta (p,q)=\frac{1}{2}\sum\limits_{y}|p(y|x)-q(y|x)|$. Am I correct? It makes sense that if probability distributions $p$ and $q$ are very different, the probability of guessing correctly will be large, just like the statistical distance. But how is it related?

Any help and comments would be much appreciated.

  • $\begingroup$ Two questions that would probably determine the answers you receive - how much detection theory do you know, and do you have priors on the channels? $\endgroup$ – stochasticboy321 Feb 11 at 16:12
  • $\begingroup$ I'm gonna say none and no. The question is part of the foundation needed for a quantum information theory course. No prior knowledge of information theory was required to sign up for the course. $\endgroup$ – M. B. Feb 11 at 16:42
  • 1
    $\begingroup$ Note that these questions are usually discussed in a probability class (at least in EE departments), not information theory. Further, note that without priors, you can't really define a probability of success, and have to work with the two differerent types of error you can make - mistaking $P$ for $Q$ and the other way around (which are events that are studied under different measures). In any case, you might want to look up the Neyman-Pearson lemma, and the setup required for it. Your particular setup should use this at the heart and include an optimisation over $x$ at the end. $\endgroup$ – stochasticboy321 Feb 11 at 18:37
  • $\begingroup$ Once you;ve looked the above up - one common measure of risk for this setup is the sum risk - $R:= \mathbb{P}(\textrm{False Alarm}) + \mathbb{P}(\textrm{Missed Detecton})$. Working with the N-P lemma a little will show that the optimal sum risk is $1 - d_{TV}(P,Q)$. In your case, suppose you used the input distribution $\pi_x$ on the $x$s. Then the relevant null and alternate distributions are $\pi P$ and $\pi Q$ respectively, and you want to minimize $1 - d_{TV}(\pi P, \pi Q)$ over $\pi$. The obvious solution is to push $x$s that maximise TV distance, just as you suspected. $\endgroup$ – stochasticboy321 Feb 11 at 18:42
  • $\begingroup$ On the other hand, if you were concerned with the minimum error rate for a given probability of false alarm (in statistical parlance the best power for a given size,) this starts to be controlled by expressions of the form $\exp(-D(P\|Q)),$ so is a fair bit different. $\endgroup$ – stochasticboy321 Feb 11 at 18:45

Your Answer

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

Browse other questions tagged or ask your own question.