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$
  • 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 '18 at 1:27
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$
  • 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 '18 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$ – Thomas Ahle Dec 21 '18 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 '18 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$ – Thomas Ahle Dec 21 '18 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 '18 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$
  • $\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$ – stochasticboy321 Dec 23 '18 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 '18 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$ – stochasticboy321 Dec 24 '18 at 18:46
  • $\begingroup$ @stochasticboy321 If you made that an answer, I'd upvote it. $\endgroup$ – Clement C. Dec 25 '18 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$
  • $\begingroup$ That's very good to know. Thank you! $\endgroup$ – Thomas Ahle Dec 21 '18 at 18:22
  • $\begingroup$ @ThomasAhle You're welcome! $\endgroup$ – Clement C. Dec 21 '18 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
    $\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 '18 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.