GATE 2022 EC Q.61: solution and answer

Official answer: 1.00Source: Official answer key, GATE 2022 EC (IIT Kharagpur)

1. Read the transition probabilities from the figure. From input a: to a with $1-\alpha$, to b with $\alpha$. From input b: to b with $1-\alpha$, to c with $\alpha$. From input c: to c with $1-\alpha$, to a with $\alpha$. With rows as inputs and columns as outputs a, b, c: $$P=\left[\begin{array}{ccc}1-\alpha & \alpha & 0\\ 0& 1-\alpha & \alpha \\ \alpha & 0& 1-\alpha \end{array}\right]$$

2. Every row is a permutation of $(1-\alpha ,\alpha ,0)$, and so is every column. The channel is therefore symmetric, and the uniform input distribution $P(x)=\frac{1}{3}$ achieves capacity.

3. With a uniform input, each output has $P(y)=\frac{1}{3}\left[(1-\alpha )+\alpha +0\right]=\frac{1}{3}$. The output is uniform on three symbols, so $H(Y)={\log }_{2}3$ bits, the largest value possible.

4. For each input, the output entropy is the entropy of the row $(1-\alpha ,\alpha ,0)$, and the zero entry adds nothing: $$H(Y|X=x)=-(1-\alpha ){\log }_2(1-\alpha )-\alpha {\log }_2\alpha =h(\alpha )$$ This is the same for every $x$, so $H(Y|X)=h(\alpha )$.

5. Capacity: $$C(\alpha )={\log }_{2}3-h(\alpha )\text{bits per channel use}$$

6. $C(\alpha )$ is largest when $h(\alpha )$ is smallest. The binary entropy $h(\alpha )$ rises from $0$ at $\alpha =0$ to its maximum $1$ at $\alpha =0.5$, then falls back to $0$ at $\alpha =1$.

7. On the allowed interval $[0.25,1]$: $h(0.25)\approx 0.811$, $h(0.5)=1$, $h(1)=0$. Since $h(\alpha )\ge 0$ everywhere and equals $0$ only at $\alpha =1$ in this interval, the minimum is at $\alpha =1$.

8. At $\alpha =1$ the channel is the noiseless cyclic map $a\to b,b\to c,c\to a$, with $C={\log }_{2}3\approx 1.585$ bits. Hence capacity is maximized at $\alpha =1.00$.