# Maximizing entropy under constraint

How do I prove that entropy is maximal for $$P(A_2) = \cdots = P(A_n) = (1-a) /(n-1)$$ while $$P(A_1) = a$$ (a fixed number) and $$A_1,…, A_n$$ is a partition of the sample space?

• Try to use convexity/concavity. There are also other ways. Oct 9 '18 at 21:03

Suppose that $$X$$ is a random variable over the set $$\{1,\ldots,n\}$$ satisfying $$\Pr[X=1] = a$$. Let $$Y$$ be the indicator of the event $$X=1$$. Then \begin{align*} H(X) &\stackrel{(1)} = H(Y) + H(X|Y) \\ &\stackrel{(2)}= h(a) + aH(X|Y=1) + (1-a)H(X|Y=0) \\ &\stackrel{(3)}\leq h(a) + (1-a) \log (n-1). \end{align*} Here (1) is the chain rule (using $$H(X) = H(X,Y)$$, since $$Y$$ is determined by $$X$$), (2) follows from $$\Pr[Y=1]=a$$ and the definition of $$H(X|Y)$$, and (3) follows from $$H(X|Y=1) = 0$$ (since when $$Y=1$$ we have $$X=1$$) and $$H(X|Y=0) \leq \log (n-1)$$ (since when $$Y=0$$, the r.v. $$X$$ only attains the values $$2,\ldots,n$$).
Furthermore, assuming $$a \neq 1$$, equality holds only if $$X|Y=0$$ is uniform, that is, if $$\Pr[X=i|Y=0] = 1/(n-1)$$ for $$2 \leq i \leq n$$, or in other words, if $$\Pr[X=i] = (1-a)/(n-1)$$ for $$2 \leq i \leq n$$.