0
$\begingroup$

For a probability vector $P = (p_1,p_2,.. p_n)$ i.e. $p_i\geq 0$ and $\sum_{i=1}^{n} p_i = 1$, define an entropy-like quantity

$$X(P) = \sum_{i=1}^n p_i\left(\log \frac{1}{p_i}\right)^2$$

Is there any upper bound (tighter than the one pointed out by Rammus) to $X(P)$ in terms of $n$? For $H(P) = \sum_{i=1}^n p_i\left(\log \frac{1}{p_i}\right)$, it is known that $H(P)\leq \log n$.

$\endgroup$
1
  • 1
    $\begingroup$ Sure, here's a simple upper bound (not tight). A single term in the sum is maximized when $p = 1/\mathrm{e}^2$ and for that we get each term is no larger than $\frac{4}{e^2}$ where $e$ is the exponent related to your logarithm. Thus the sum is bounded above by $\frac{4 n}{e^2}$. $\endgroup$
    – Rammus
    Apr 4, 2021 at 14:11

1 Answer 1

Reset to default
1
+50
$\begingroup$

Ok, here are the tight bounds. For $n=1$ we get $X(P)=0$. For the case of $n=2$ we just have a single parameter $p$ (as $p_2 = 1-p$) and we can directly optimize the quantity. We find that $X(\{p,1-p\})$ has two maxima at $$ p^* = \frac{1}{2} \pm \frac{\sqrt{e^2 - 4}}{2 e}. $$ This gives a value of $X(\{p^*,1-p^*\}) \approx 0.563$.

Things change however for $n>2$. It turns out, see Proposition 8 part 3 in this paper for details, that for $n>2$, $X(P)$ has a unique maximum which is attained by the uniform distribution. Therefore, for $n>2$ we have $$ X(P) \leq (\log n)^2. $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .