Riemann surface











问题 1.

Exercise 1. Distinguishing channels
The setting is the following: With equal probabilities you are given either the identity channel I on some finite alphabet $\mathcal{X}$ or an arbitrary channel $W$ on the same alphabet, without knowing which. In terms of conditional probability distributions the channels are described by
I\left(x \mid x^{\prime}\right)=\delta_{x x^{\prime}} \text { and } W\left(x \mid x^{\prime}\right),
for $x, x^{\prime} \in \mathcal{X}$. You are allowed to use the given channel once, possibly with a stochastic (randomized) input, and then asked which channel was used.
(a) The error probability of a channel $W$ is defined as $P_{\text {error }}(W):=\max _{x \in \mathcal{X}}(1-W(x \mid x))$. Argue why this is a sensible definition.


(a) For some specific $x \in \mathcal{X}$ the error probability of $W$ is the probability that the output differs from the input which is equal to 1 minus the probability that the output equals the input, i.e. $P_{\text {error }}(W$ on $x)=1-W(x \mid x)$. The ‘overall’ error probability of $W$ is then just the maximum error probability of $W$ on the inputs,
P_{\text {error }}(W)=\max {x \in \mathcal{X}} P{\text {error }}(W \text { on } x)=\max _{x \in \mathcal{X}}(1-W(x \mid x)) .
Notice, however, that a high error probability according to this definition does not mean that the channel is useless! This way of defining the error probability merely compares the channel to the identity channel.

问题 2.

(b) Using properties of the trace distance of probability distributions previously derived in Exercise Sheet 1, Exercise 1(c), show that the probability of guessing the channel correctly in the above scenario is
P_{\text {guess }}(I \text { vs. } W)=\frac{1}{2}\left(1+P_{\text {error }}(W)\right)

(b) According to the setting, the only thing we will have access to at the end is the output of the channel, so what we will be confronted with is the problem of distinguishing two probability distributions from one sample. This is exactly the setting considered in the mentioned exercise in Exercise Sheet 1. Furthermore, we have not specified the input distribution. Calling the chosen input $\mathrm{RV} X$, distributed $P_X$, and denoting the output RV if $W$ is applied by $X^{\prime}:=W(X)$, distributed $P_{X^{\prime}}$, we see that
P_{\text {guess }}(I \text { vs. } W)=\max {P_X} P{\text {guess }}\left(X \text { vs. } X^{\prime}\right)=\max {P_X} \frac{1}{2}\left(1+\delta\left(P_X, P{X^{\prime}}\right)\right) .
We can express $P_{X^{\prime}}$ in terms of $P_X$ and $W(\cdot \mid \cdot)$ as
P_{X^{\prime}}\left(x^{\prime}\right)=\sum_{x \in \mathcal{X}} P_X(x) W\left(x^{\prime} \mid x\right)

E-mail: help-assignment@gmail.com  微信:shuxuejun



您的电子邮箱地址不会被公开。 必填项已用*标注