Convex hull of the set of distributions with constant entropy

162 Views Asked by At

Let $H(p):=-\sum_{i=1}^n p_i \log p_i$ be the Shannon entropy defined on the set of probability distributions on $\{1,2,...,n\}$. Let $h$ be a constant such that $0\leq h \leq \log n$. The question is: $$\text{conv}[H^{-1}(h)] \stackrel{?}{=} H^{-1}(\{r:r\geq h\}),$$

where $\text{conv}[T]$ denotes the convex hull of the set $T$. One direction of inclusion $(\subseteq)$ is trivial from the concavity of $H$. My first attempt to prove the other direction was to use the majorization property and the Birkhoff's theorem, but since the order relation in temrs of entropy does not imply the majorization relation, I think this direction is futile. If the statement is not true for the Shannon entropy, then is it true for some generalizations of Shannon entorpy (e.g. Renyi entropy)?

1

There are 1 best solutions below

1
On BEST ANSWER

Suppose $H(p)> h$. We wish to prove that $p\in\mathrm{conv}[H^{-1}(h)]$.

Let $\delta_i$ be the distribution in which $i$ has probability $1$, so $H(\delta_i)=0$. Since $H$ is continuous we have by the intermediate value theorem that there's some $\lambda_i\in(0,1)$ with $H(\lambda_i p+(1-\lambda_i)\delta_i)=h$. Write $q_i$ for $\lambda_i p+(1-\lambda_i)\delta_i$. Then we have $p = \sum_ip(i)\delta_i=\sum_ip(i)\left(\frac{1}{1-\lambda_i}q_i-\frac{\lambda_i}{1-\lambda_i}p\right)$.

Rearranging this yields

$$\left(1+\sum_i\frac{\lambda_ip(i)}{1-\lambda_i}\right)p=\sum_i\frac{p(i)}{1-\lambda_i}q_i.$$

Since $1$ can be rewritten as $\sum_i\frac{p(i)-\lambda_ip(i)}{1-\lambda_i}$, we have $\left(1+\sum_i\frac{\lambda_ip(i)}{1-\lambda_i}\right) = \sum_i\frac{p(i)}{1-\lambda_i}$, and hence

$$p = \frac{\sum_i\frac{p(i)}{1-\lambda_i}q_i}{\sum_i\frac{p(i)}{1-\lambda_i}}$$

which expresses $p$ as a convex combination of the $q_i$, each of which has entropy $h$.

Diagram