Entropy Lower Bound in Terms of $\ell_2$ norm

Question

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.

Answer 1

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} $.

Answer 2

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{.}$$

Answer 3

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$.

Answer 4

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$.