Let $p_{1}, \ldots, p_{n}$ be a probability distribution, with $p^{*}=\max _{i}\left[p_{i}\right]$. Prove that

$$\begin{aligned} &(i)-\sum_{i} p_{i} \log p_{i} \geqslant-p^{*} \log p^{*}-\left(1-p^{*}\right) \log \left(1-p^{*}\right) \\ &(\text { ii })-\sum_{i} p_{i} \log p_{i} \geqslant \log \left(1 / p^{*}\right) ; \text { and } \\ &(\text { iii })-\sum_{i} p_{i} \log p_{i} \geqslant 2\left(1-p^{*}\right) \end{aligned}$$

All logarithms are to base 2 .

[Hint: To prove (iii), it is convenient to use (i) for $p^{*} \geqslant \frac{1}{2}$ and (ii) for $p^{*} \leqslant \frac{1}{2}$.]

Random variables $X$ and $Y$ with values $x$ and $y$ from finite 'alphabets' $I$ and $J$ represent the input and output of a transmission channel, with the conditional probability $p(x \mid y)=\mathbb{P}(X=x \mid Y=y)$. Let $h(p(\cdot \mid y))$ denote the entropy of the conditional distribution $p(\cdot \mid y), y \in J$, and $h(X \mid Y)$ denote the conditional entropy of $X$ given $Y$. Define the ideal observer decoding rule as a map $f: J \rightarrow I$ such that $p(f(y) \mid y)=\max _{x \in I} p(x \mid y)$ for all $y \in J$. Show that under this rule the error probability

$$\pi_{\mathrm{er}}(y)=\sum_{\substack{x \in I \\ x \neq f(y)}} p(x \mid y)$$

satisfies $\pi_{\mathrm{er}}(y) \leqslant \frac{1}{2} h(p(\cdot \mid y))$, and the expected value satisfies

$$\mathbb{E} \pi_{\mathrm{er}}(Y) \leqslant \frac{1}{2} h(X \mid Y)$$