Skip to main content
26 votes
Accepted

Geometric interpretations of the exponential of entropy

With apologies for promoting my own work, there's a whole book on the mathematics of the exponentials of various entropies: Tom Leinster, Entropy and Diversity: The Axiomatic Approach. Cambridge ...
Tom Leinster's user avatar
  • 27.4k
21 votes
Accepted

Entropy of composition

There is a good reason you were having difficulties in proving this. This was an old question of Rohlin (MR0126526) which was first disproved in the topological setting by Goodwyn (MR0314023) and ...
Nishant Chandgotia's user avatar
21 votes
Accepted

Information inequalities

Yes. The set of $2^n$ (or $2^n-1$ excluding the empty set) dimensional vectors formed by entropies is called the entropic region [1]. Inequalities on the entropic region not implied by the ...
Cheuk Ting Li's user avatar
16 votes
Accepted

Relative Entropy and p-norm

The argument below is not very elegant,but it is, indeed, a standard exercise. Let $g=\max(f-1,0)$. We shall prove that $$ f\log f\le 2g+\frac 2{p-1}g^p\,. $$ The integration and Holder then give the ...
fedja's user avatar
  • 60.6k
14 votes
Accepted

What is (approximately) the expected value of $X\log{ X}$ where $X$ is binomial (or Poisson)?

$\newcommand{\ep}{\varepsilon} $ Let $X$ be any nonnegative random variable (r.v.) with finite mean $\mu>0$ and variance $\sigma^2<\infty$. For any real $u>0$, we have $\ln\frac xu\le\frac xu-...
Iosif Pinelis's user avatar
13 votes

What's the motivation of entropy as a combinatorical tool? What problems is it able to solve?

I'll only attempt to answer question 1. Let's say you have 10 objects, divided into three blocks of respective sizes 2, 5 and 3. What's the probability that a random endomorphism of your set of ...
Tom Leinster's user avatar
  • 27.4k
13 votes
Accepted

The Euler-Mascheroni constant and entropy

The earliest reference I have found for this result is Entropy and maximal spacings for random partitions (E. Slud, 1978). Theorem 2.2 states that the entropy $W_n=-\sum_{i=1}^n p_i \ln p_i$ of the ...
Carlo Beenakker's user avatar
13 votes
Accepted

The origin of the natural base in statistical mechanics

As Matt F. points out, we could just absorb a change of base of the logarithm into the coefficient. The reason that is not convenient in physics is that we would like the same coefficient $k$ to ...
Carlo Beenakker's user avatar
13 votes

Lower bound $\int_0^1 \frac{|f'(x)|^2}{f} \,\mathrm{d} x$ by $\int_0^1 |f-1|^2\, \mathrm{d} x$

First of all such a Csiszar–Kullback-Pinsker inequality or whatever cannot possibly be true since $x^2$ explodes faster than $x\log x$ so you can make a local adjustment so that the right-hand side is ...
Aleksei Kulikov's user avatar
12 votes

Entropy and total variation distance

Claim. If $\|P-Q\|\leq\varepsilon\leq\frac{1}{2}$, then $|H(P)-H(Q)| \leq H(\varepsilon) + \varepsilon\log N$. Proof. Let $\varepsilon':=\|P-Q\|$. Let $(X,Y)$ be an optimal coupling of $P$ and $Q$, ...
Algernon's user avatar
  • 1,714
11 votes

Discrete entropy of the integer part of a random variable

Using (say) decimal notation, ASCII encoding, and a delimiter symbol such as a space or comma, as well as the law of large numbers, one can almost surely encode $N$ independent copies of $\lfloor X \...
Terry Tao's user avatar
  • 112k
11 votes
Accepted

Bipartite version of Hamming bound (two families of codewords with large Hamming distance)?

If the Hamming distance between $A$ and $B$ is at least $d$, it yields that $B$ is disjoint from the $(d-1)$-neighborhood of $A$. By isoperimetric inequality for a Boolean cube (Harper's theorem), the ...
Fedor Petrov's user avatar
10 votes

Is there an axiomatic characterization of the entropy of a continuous random variable?

$\newcommand{\Si}{\Sigma}\newcommand{\PP}{\mathscr P}\newcommand{\PPP}{\mathfrak P}$Let $X$ be a discrete random variable (r.v.) taking distinct values $x_1,x_2,\dots$, and let $p_i:=P(X = x_i)$. ...
Iosif Pinelis's user avatar
10 votes
Accepted

Explanation for why an ideal fluid doesn't have increasing entropy?

This is a very important issue, to which an answer must be made in mathematical terms, rather than by waving hands. Yes, the Euler system (conservation of mass, momentum and energy) is time-reversible....
Denis Serre's user avatar
  • 51.8k
10 votes

Is there an entropy proof for bounding a weighted sum of binomial coefficients?

By the Chernoff–Hoeffding theorem, the sum in question is $\le\exp(-nD(a||p))$ for $a\le p$, where $a:=\alpha$ and $$D(a||p):=a\ln\frac ap+(1-a)\ln\frac{1-a}{1-p},$$ the Kullback–Leibler divergence ...
Iosif Pinelis's user avatar
9 votes
Accepted

Gaussian distribution, maximum entropy and the heat equation

Both the Gaussian maximum entropy distribution and the Gaussian solution of the diffusion equation (heat equation) follow from the central limit theorem, that the limiting distribution of the sum of i....
Carlo Beenakker's user avatar
9 votes

What's the motivation of entropy as a combinatorical tool? What problems is it able to solve?

Three tutorial lectures on entropy and counting by David Galvin (2014) provides an answer to Q1: The key property of Shannon’s entropy that makes it useful as an enumeration tool is that over all ...
Carlo Beenakker's user avatar
9 votes
Accepted

Asymptotics of multinomial coefficients

Suppose that $k$ is a fixed natural number, $n\to\infty$, and \begin{equation*} a_i=\frac nk+o(n^{2/3}) \end{equation*} for each $i$; here in what follows, $i\in\{1,\dots,k\}$. Let \begin{...
Iosif Pinelis's user avatar
8 votes

What's the motivation of entropy as a combinatorical tool? What problems is it able to solve?

Entropy arguments are part of the toolkit of the probabilistic method. So the first step in answering the question of how someone just interested in combinatorics might be led to entropy is to ask ...
Timothy Chow's user avatar
  • 79.5k
8 votes
Accepted

Shannon entropy of $p(x)(1-p(x))$ is no less than entropy of $p(x)$

Denote $f(p)=p(1-p)$, $H(p)=-p\log p$, let $p_1,\dots,p_n$ denote all positive probabilities of our distribution, then $\sum p_i=1$, finally denote $s=\sum_i f(p_i)$. Then we need to prove the ...
Fedor Petrov's user avatar
8 votes

Discrete entropy of the integer part of a random variable

$\newcommand{\fx}{\lfloor X\rfloor}$ $\newcommand\Z{\mathbb{Z}}$ We shall prove more than requested: that $H(\fx)<\infty$ if $E\ln(1+|X|)<\infty$. Indeed, let $$p_n:=P(\fx=n),$$ so that $$H(\fx)=...
Iosif Pinelis's user avatar
7 votes
Accepted

Covering number of Lipschitz functions

Here is a reference to a more general result: Lipschitz functions over a doubling metric space (rather than $[0,1]^d$). The $||\cdot||_\infty$ $\epsilon$-metric entropy of such functions is, ...
Aryeh Kontorovich's user avatar
7 votes

Can the differential entropy of a continuous distribution with lebesgue integrable density be negative infinity?

For $x\in(0,1)$, let \begin{equation} f(x):=\frac1{x\ln^2\frac ex}. \tag{1} \end{equation} Then $f\ge0$ and $\int_0^1f(x)\,dx=1$. On the other hand, $\ln f(x)\sim\ln\frac ex$ as $x\downarrow0$. So,...
Iosif Pinelis's user avatar
7 votes
Accepted

Discrete entropy of the integer part of a random variable

Since $\lfloor X\rfloor$ has finite entropy if and only if $|\lfloor X\rfloor|$ has finite entropy, it suffices to consider random variables taking values in the natural numbers. Write $p_n$ for $\...
Anthony Quas's user avatar
  • 22.6k
7 votes

Geometric interpretations of the exponential of entropy

If I may broaden the question somewhat to include other interpretations of the exponential of entropy, it is commonly used in ecology to measure how many different species there are in a community. In ...
Carlo Beenakker's user avatar
7 votes
Accepted

Is there an entropy proof for bounding a weighted sum of binomial coefficients?

Yes, if $\alpha<p$ (if $\alpha>p$, the sum is almost 1). To see this, write $$ \sum_{\ell = 0}^{\alpha n} \binom{n}{\ell}p^\ell(1-p)^{n-\ell}\leqslant t^{-\alpha n}(pt+(1-p))^n $$ for every $t\...
Fedor Petrov's user avatar
7 votes

3-periodic point implies positive topological entropy

The result you are looking for is contained as a particular case in Theorem 4.58, point ii), in the very nice reference work by Sylvie Ruette on interval topological dynamics. I add some (hopefully) ...
Alessandro Della Corte's user avatar
7 votes
Accepted

Fokker-Planck: equivalence between linear spectral gap and nonlinear displacement convexity?

One has the ordering of the three $\lambda$'s, i.e. $$ \lambda_{\text{convex}} \leq \lambda_{\text{LSI}} \leq \lambda_{\text{SG}}, $$ where $\lambda_{\text{convex}}$ is the one from convexity, $\...
André Schlichting's user avatar
7 votes
Accepted

Relative entropy equality for a sequence of Bernoulli random variables

This equality does not hold in general. E.g., suppose that $n=2$, $$\big(P_p(X_1=i,X_2=j)\colon\; i=0,1,\,j=0,1\big)= \frac1{30}\,\begin{pmatrix} 4 & 9 \\ 9 & 8 \\ \end{pmatrix},$$ and $$\...
Iosif Pinelis's user avatar
6 votes
Accepted

Measures maximizing entropy in a set of measures with fixed average for some observable

In the setting you describe, for each $\alpha \in (0,1)$ the $(1-\alpha,\alpha)$-Bernoulli measure is the unique measure achieving the maximum. The function $\alpha \mapsto \eta(\alpha)$ is the ...
Vaughn Climenhaga's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible