Estimation of Shannon differential entropy: An extensive comparative review

It is proven that a conjecture of Tao (2010) holds true for log-concave random variables on the integers: For every $n \geq 1$, if $X_1,\ldots,X_n$ are i.i.d. integer-valued, log-concave random variables, then $$ H(X_1+\cdots+X_{n+1}) \geq H(X_1+\cdots+X_{n}) + \frac{1}{2}\log{\Bigl(\frac{n+1}{n}\Bigr)} - o(1) $$ as $H(X_1) \to \infty$, where $H$ denotes the (discrete) Shannon entropy. The problem is reduced to the continuous setting by showing that if $U_1,\ldots,U_n$ are independent continuous uniforms on $(0,1)$, then $$ h(X_1+\cdots+X_n + U_1+\cdots+U_n) = H(X_1+\cdots+X_n) + o(1) $$ as $H(X_1) \to \infty$, where $h$ stands for the differential entropy. Explicit bounds for the $o(1)$-terms are provided.

Let G = (G, +) be an additive group. The sumset theory of Plünnecke and Ruzsa gives several relations between the size of sumsets A + B of finite sets A, B, and related objects such as iterated sumsets kA and difference sets A − B, while the inverse sumset theory of Freiman, Ruzsa, and others characterizes those finite sets A for which A + A is small. In this paper we establish analogous results in which the finite set A ⊂ G is replaced by a discrete random variable X taking values in G, and the cardinality |A| is replaced by the Shannon entropy H(X). In particular, we classify those random variables X which have small doubling in the sense that H(X1 + X2) = H(X) + O(1) when X1, X2 are independent copies of X, by showing that they factorize as X = U + Z, where U is uniformly distributed on a coset progression of bounded rank, and H(Z) = O(1). When G is torsion-free, we also establish the sharp lower bound $\Ent(X+X) \geq \Ent(X) + \frac{1}{2} \log 2 - o(1)$ , where o(1) goes to zero as …

You may colour the sides of each die in any way you wish, but there is one restriction: you are not allowed to use the same colour more than once on the sides of a die. Any other colouring is allowed. Let X X be the number of different colours that you see after rolling the dice. How should you colour the sides of the dice in order to maximize the Shannon entropy of X X ? In this article we investigate this question. We show that the entropy of X X is at most 1 2 ​ log ⁡ ( n ) + O ⁡ ( 1 ) \frac{1}{2}\log(n)+O(1) and that the bound is tight, up to a constant additive factor, in the case of there being equally many coins and colours. Our proof employs the differential entropy bound on discrete entropy, along with a lower bound on the entropy of binomial random variables whose outcome is conditioned to be an even integer.

The sumset and inverse sumset theories of Freiman, Plünnecke, and Ruzsa, give bounds connecting the cardinality of the sumset A + B = {a + b; a ∈ A, b ∈ B} of two discrete sets A, B, to the cardinalities (or the finer structure) of the original sets A, B. For example, the sum-difference bound of Ruzsa states that, |A + B| |A| |B| |A - B|3, where the difference set A - B = {a - b; a ∈ A, b ∈ B}. Interpreting the differential entropy h(X) of a continuous random variable X as (the logarithm of) the size of the effective support of X, the main contribution of this paper is a series of natural information-theoretic analogs for these results. For example, the Ruzsa sum-difference bound becomes the new inequality, h(X+Y)+h(X)+h(Y) ≤ 3h(X-Y), for any pair of independent continuous random variables X and Y. Our results include differential-entropy versions of Ruzsa's triangle inequality, the Plünnecke-Ruzsa inequality, and the Balog-Szemerédi-Gowers lemma. In addition, we give a differential en …

We revisit the problem of the estimation of the differential entropy$H(f)$of a random vector$X$in$R^{d}$with density$f$, assuming that$H(f)$exists and is finite. In this note, we study the consistency of the popular nearest neighbor estimate$H_{n}$of Kozachenko and Leonenko. Without any smoothness condition we show that the estimate is consistent ($E\{|H_{n} - H(f)|\} \to 0$as$n \to \infty $) if and only if${\mathbb E}\{ \log (\| X \| + 1)\} < \infty $. Furthermore, if$X$has compact support, then$H_{n} \to H(f)$almost surely.