Suppose $X\sim P$ is a random variable taking values on an alphabet $\mathcal{A}=\{1,\dots,m\}$, such that $p:=P(1)>P(k)$ for $k\neq1$. The minimum-probability-of-error predictor of $X$ is $\hat{X}=1$, with probability of error $P_e=1-p$. Find the maximal entropy $H(X)$ subject to the above conditions, for a fixed $p\in(0,1)$, and use it to obtain a bound on $P_e$ in terms of $H(X)$.
My attempt so far: For a fixed $p$, I'm quite sure that the entropy will be maximised if the PMF is distributed uniformly among the $m-1$ remaining possible values, leading to a maximal entropy (call it $M$), of $$M=-p\log p-(1-p)\log\left(\frac{1-p}{m-1}\right).$$ Then we must have that $H(X)\leq$ the left hand side, and rearranging, the best I can obtain is $$\left(\frac{P_e}{m-1}\right)^{P_e}(1-P_e)^{1-P_e}\leq2^{-H(X)},$$ which does not seem satisfactory but I'm fairly sure that this can't be solved explicitly. If someone could lead me to where I've gone wrong in my efforts, that would be greatly appreciated, thanks!
Best Answer
$M$ can also be written (and obtained directly using this) as $M =h(p) + (1-p) \log(m-1)$ where $h(p)$ is the binary entropy function.
Then we have $$H(X) \le h(p) + (1-p) \log(m-1)=h(P_e) + P_e \log(m-1)$$
This, which is already a form of Fano's inequality, gives already a bound of $P_e$ in terms of $H(X)$, but, as you have noticed, it cannot be expressed in simple closed form. It should be evaluated numerically.
Alternatively, we can obtain a less tight bound by noting that $h(P_e)\le 1$ . Then
$$P_e \ge \frac{H(X)-1}{\log(m-1)}$$