Maximum value of $-\sum_{i=1}^{n}p_i \log_2(p_i)$ for $\sum_{i=1}^{n}p_i=P<1$

104 Views Asked by At

It is known that the entropy $$H=-\sum_{i=1}^{n}p_i \log_2(p_i)$$ Is maximized when $p_i=1/n$.

However, this is under the assumption that $\sum_{i=1}^{n}p_i=1$. Does this still hold true if the sum of probabilities is $0<P<1$? That is, if $$\sum_{i=1}^{n}p_i=P$$ Note that this can happen because my goal is to optimize a wordle solver, and for that I need to get an upper bound for the entropy after part of the information has already been summed.

2

There are 2 best solutions below

0
On BEST ANSWER

No, but you can still go back to the usual case. Just apply the standard case with $p_i$ replaced by ${p_i \over P}$. The entropy becomes $${1\over P} \sum p_i \log_2(p_i/P)= {1\over P} \sum p_i \log_2(p_i) -\sum p_i \log_2(P) = {1\over P} \sum p_i \log_2(p_i) -P \log_2(P).$$ Hence the maximum is attained when ${p_i \over P} = {1\over n}$.

0
On

Let $q_i=p_i/P$ be a discrete pmf.

$$H_p = - \sum p_i \log p_i = - \sum P q_i \log (Q q_i) = P H_q -P \log P$$

Here, $H_q$ is a proper entropy ($H_p$ is not). For a fixed $P$, this is maximized for uniform $q_i=1/n$ (hence also uniform $p_i = P/n$). And the maximized value for $H_p$ is

$$ P \log \frac{n}{P}$$