Riemann surface
matlab

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.

.

Solution.
(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.

(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

help-assignment™是一个服务全球中国留学生的专业代写公司