6
$\begingroup$

Define $$ \begin{align} H(p_1, \dots, p_n) &= \sum_{i=1}^n p_i\log1/p_i\\ &=\log n+\sum_{i=1}^n\sum_{k=2}^\infty (-1)^{k + 1} n^{k - 1} \frac{(p_i - 1/n)^k}{k (k - 1)}, \end{align} $$ where $p_1,\dots,p_n\ge0$ sum to $1$.

Then we have the classic inequality $H(p_1,p_2)\ge(\log2)(1-2((p_1-1/2)^2+2(p_2-1/2)^2))=(\log 2)(1-2\|p-1/2\|^2)$, and we might wonder if that could be extended for $n>2$. In particular with something like $$\begin{align} H(p_1,\dots,p_n)&\ge(\log n)(1-c_n\|p-1/n\|^2_2). \end{align}$$ From experiments with $n=3$, it seems like $c_n\ge\frac{2 n (\log n/2)}{(n-2) \log n}=2(1-O(1/\log n))$ suffices, but I don't have a proof of this. It is also slightly inconvenient that it can go below $0$, something that wasn't the case with the $n=2$ case.

Bounding the terms individually, we can get $H(p_1,\dots,p_n)\ge-2+4\sum_{i=1}^n\frac{p_i}{1+p_i}$, which is non-negative, but not as relatable to the $\ell_2$ norm. We can also bound $H\ge n/4-\|p-1/2\|_2^2$, but somehow bounding centered in $1/n$ seems more natural.

Is there a well known lower bound like this, relating $H(p)$ with $\|p\|_2$? Ideally, one that is asymptotically tight at $p_1=\dots=p_n=1/n$ and is always positive.

$\endgroup$
1
  • 2
    $\begingroup$ Not really what you want, but you have the inequality $$\log n \geq H(p) \geq \log \frac{1}{\lVert p\rVert_2^2}$$ based on the standard relation between Rényi entropies. $\endgroup$
    – Clement C.
    Dec 21, 2018 at 1:27

4 Answers 4

5
$\begingroup$

Defining $p_i=1/n+q_i$ we get (using nats):

$$\begin{align} H({\bf p}) &=-\sum p_i \log(p_i)\\ &=-\sum (1/n +q_i) \log(1/n +q_i)\\ &=-\sum ( 1/n +q_i) [\log(1/n ) + \log(1+ n q_i )]\\ &= \log(n) -\sum ( 1/n +q_i) \log(1+ n q_i)\\ &\ge \log(n) -\sum ( 1/n +q_i) n q_i\\ & = \log(n) - n\sum q_i^2\\ & = \log(n) - n \, \lVert{\bf p}- 1/n\rVert^2_2\\ \end{align}$$

Or, if you prefer

$$ H({\bf p}) \ge \log(n)\left(1 - \frac{n}{\log n}\sum q_i^2 \right) $$

Of course, the bound is useless if $\sum q_i^2\ge \frac{\log(n)}{n} $.

$\endgroup$
7
  • 2
    $\begingroup$ As a side note, $$\lVert \mathbf{p} - 1/n\rVert_2^2 = \lVert \mathbf{p}\rVert_2^2 - 1/n$$ (in case the OP insists on having $n \lVert \mathbf{p}\rVert_2^2 - 1$ instead of $n\lVert \mathbf{p} - 1/n\rVert_2^2$). $\endgroup$
    – Clement C.
    Dec 21, 2018 at 1:29
  • $\begingroup$ That's a nice derivation. I suppose I could try to use some stronger upper bounds to $\log(1+n q_i)$, but it doesn't seem like there is any hope of improving $n/\log n$ to something closer to 2? $\endgroup$ Dec 21, 2018 at 11:28
  • $\begingroup$ It seems doubtful to me... I also wonder how you could conjecture a bound like $c_n\ge\frac{2 n (\log n/2)}{(n-2) \log n}=2(1-O(1/\log n))$ experimenting only with $n=3$... $\endgroup$
    – leonbloy
    Dec 21, 2018 at 11:33
  • $\begingroup$ @leonbloy I know, it's a bit tongue in cheek, but for $n=3$ I can plot it, and it seemed that the worst case was when all $p=0$ except for two with $p=1/2$, so I optimized for that case, and then checked numerically for larger $n$. $\endgroup$ Dec 21, 2018 at 13:08
  • 1
    $\begingroup$ You can also check it $c_n$ cannot be a constant by taken another extreme example, $\mathbf{p}$ uniform on a subset of $n/2$ element (and $0$ elsewhere). Then $\lVert \mathbf{p} - 1/n\rVert_2^2 = 1/n$, so you want $$\log\frac{n}{2}\geq \log n\left(1 - \frac{c_n}{n}\right)$$ $\endgroup$
    – Clement C.
    Dec 21, 2018 at 16:34
4
$\begingroup$

Let $(X,\upsilon)$ be a finite measure space. Let $\sigma=\frac{\upsilon}{V}$ be the uniform probability distribution on $X$ ($V=\upsilon(X)$). Let $\rho$ be an absolutely continuous probability distribution with density $p$. Then the inequality $$\begin{align}-h(p)+\ln V&\leq V\lVert p-\tfrac{1}{V}\rVert_2^2\\ h(p)&\stackrel{\mathrm{def}}{=}-\int_X p(x)\ln p(x)\mathrm{d}\upsilon_{x}\\ \lVert p-q\rVert^2_2&\stackrel{\mathrm{def}}{=}\int_X\lvert p(x)-q(x)\rvert^2\mathrm{d}\upsilon_x \end{align}$$ is exactly the inequality between the $\chi^2$-divergence and the KL divergence $$\begin{align}D(\rho\parallel\sigma)&\leq \chi^2(\rho\parallel\sigma)\text{,}\\ D(\rho\parallel\sigma)&\stackrel{\text{def}}{=}\int_X\left(\frac{\mathrm{d}\rho}{\mathrm{d}\sigma}\ln\frac{\mathrm{d}\rho}{\mathrm{d}\sigma}-\frac{\mathrm{d}\rho}{\mathrm{d}\sigma}+1\right)\mathrm{d}\sigma_x\\ \chi^2(\rho\parallel\sigma)&\stackrel{\text{def}}{=}\int_X\left(\frac{\mathrm{d}\rho}{\mathrm{d}\sigma}-1\right)^2\mathrm{d}\sigma_x\text{;} \end{align}$$ this inequality in turn follows from $$t\ln t - t + 1 \leq (t-1)^2\text{.}$$

$\endgroup$
4
  • $\begingroup$ Doesn't then using $KL \le \log(1 + \chi^2)$ lead to something stronger? Presumably one should get something like $H(P) \ge - \log \|P\|_2^2.$ $\endgroup$ Dec 23, 2018 at 0:37
  • $\begingroup$ @stochasticboy321 that would be the Rényi entropy inequality mentioned in a comment under the OP. It's not really stronger though, more like a different bound. $\endgroup$
    – Clement C.
    Dec 23, 2018 at 22:18
  • 2
    $\begingroup$ @ClementC. Oh, missed that. It is strictly an improvement though. One way to see this is by simply noting by the above that the bound correponds to $KL\le \chi^2,$ which is looser than $KL \le \log 1+ \chi^2$. Also, on noting that $( P -\mathbf{1}/n ) \perp \mathbf{1}/n$, one can rearrange this to $H(P) \ge \log n - \log(1 + \| nP - \mathbf{1}\|_2^2)$. This has the nice advantage of the base of the log not affecting the bound. Of course for $P \approx \mathbf{1}/n$ these are equivalent, and your tightness analysis stands. $\endgroup$ Dec 24, 2018 at 18:46
  • $\begingroup$ @stochasticboy321 If you made that an answer, I'd upvote it. $\endgroup$
    – Clement C.
    Dec 25, 2018 at 0:04
4
$\begingroup$

To complement Leon Bloy's answer and show the bound he (and K B Dave) obtained cannot be significantly improved upon (i.e., that $c_n = \Omega\!\left(\frac{n}{\log n}\right)$ is necessary): Fix $\varepsilon \in (0,1]$, and assume without loss of generality that $n=2m$ is even. Define $\mathbf{p}^{(\varepsilon)}$ as the probability mass function (over $\{1,\dots,n\}$) such that $$ \mathbf{p}^{(\varepsilon)}_i = \begin{cases} \frac{1+\varepsilon}{n} & \text{ if } i \leq m \\ \frac{1-\varepsilon}{n} & \text{ if } i > m \end{cases} $$ Note that $$\begin{align} H(\mathbf{p}^{(\varepsilon)}) &= \sum_{i=1}^m \frac{1+\varepsilon}{n}\log \frac{n}{1+\varepsilon} + \sum_{i=m+1}^n \frac{1-\varepsilon}{n}\log \frac{n}{1-\varepsilon} \\ &= \log n - \frac{1}{2}\left((1+\varepsilon)\log(1+\varepsilon) + (1-\varepsilon)\log(1-\varepsilon)\right) \\ &= \log n - \frac{\varepsilon^2}{2} + o(\varepsilon^3) \tag{1} \end{align}$$ while $$ \lVert \mathbf{p}^{(\varepsilon)} - \mathbf{u}_n\rVert_2^2 = \frac{\varepsilon^2}{n} \tag{2} $$ so that $$ H(\mathbf{p}^{(\varepsilon)}) = \log n \left(1 - \left(1/2+o_\varepsilon(1)\right)\cdot\frac{n}{\log n}\lVert \mathbf{p}^{(\varepsilon)} - \mathbf{u}_n\rVert_2^2\right) \tag{3} $$

If you want to avoid the asymptotics as $\varepsilon \to 0$, you can still fix $\varepsilon = 1$ (for instance) and get that $$H(\mathbf{p}^{(\varepsilon)}) = \log n \left(1 - c'_\varepsilon\frac{n}{\log n}\lVert \mathbf{p}^{(\varepsilon)} - \mathbf{u}_n\rVert_2^2\right)$$ for some constant $c'_\varepsilon > 0$.

$\endgroup$
2
  • $\begingroup$ That's very good to know. Thank you! $\endgroup$ Dec 21, 2018 at 18:22
  • $\begingroup$ @ThomasAhle You're welcome! $\endgroup$
    – Clement C.
    Dec 21, 2018 at 18:23
3
$\begingroup$

This is just scribbling down some observations in the comments, to have them more, well, visible.


As observed by K B Dave, the inequality of leonbloy is an instance of $\mathrm{KL} \le \chi^2.$ This can thus be improved by using a tighter inequality of this form. Note that the resulting inequality was mentioned by Clement in the original comments.

We have $$\mathrm{KL}(P\|Q) = \int \log \frac{\mathrm{d}P}{\mathrm{d}Q} \,\mathrm{d}P \le \log \int \left( \frac{\mathrm{d}P}{\mathrm{d}Q}\right) \,\mathrm{d}P = \log \int \left( \frac{\mathrm{d}P}{\mathrm{d}Q}\right)^2 \,\mathrm{d}Q = \log (1 + \chi^2(P\|Q)), $$ where the inequality follows by the concavity of $\log$ and Jensen's inequality. Applying the above to this case yields $$H(P) = \log n - \mathrm{KL}(P\|\mathbf{1}/n) \ge \log n - \log(1 + \sum_x \frac{(P_x - 1/n)^2}{1/n}) = \log n - \log (1 + n\|P - \mathbf{1}/n\|_2^2).$$

Note that if $n\|P - \mathbf{1}/n\|_2^2 \ll 1,$ we may use $\log (1 + x) \approx x$ for small values of $x$ to recover the original bound.

We may also state the above bound in the following equivalent way: Observe that $1 + \chi^2(P\|Q) = \mathbb{E}_Q[ ({\mathrm{d}P}/{\mathrm{d}Q})^2].$ Again plugging in $Q$ uniform on $n$ letters yields that the latter expectation is simply $n\|P\|_2^2,$ and we get that

$$ H(P) \ge - \log \|P\|_2^2,$$ the form stated by Clement. Note that $\|P\|_2 \le 1$ for every distribution, so the form above makes it obvious that the inequalities are non-trivial (in that the RHS is $\ge$ 0) for every $P$.

$\endgroup$
1
  • 1
    $\begingroup$ As a side terminology note, $H(P)$ is the Shannon entropy (Rényi entropy for $\alpha=1$) while $-\log \lVert P\rVert_2^2$ is the Rényi entropy of order $\alpha=2$. Thus, the inequality follows from monotonicity of Rényi entropies. $\endgroup$
    – Clement C.
    Dec 27, 2018 at 12:54

You must log in to answer this question.

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