Questions tagged [entropy]
The entropy tag has no usage guidance.
289
questions
3
votes
0
answers
90
views
Does the entropy of a SDE with nondegenerate noise always increase?
Let $W$ be a standard Brownian motion, and let $X$ be the solution to the one dimensional SDE
$$dX_t = \sigma(t, X_t) \, dW_t$$
with initial condition $X_0 = x_0$ a.s. for some $x_0 \in \mathbb R$. We ...
- 2,448
0
votes
0
answers
25
views
Fischer Information and Entropy, matrix case, determinant of covariance matrix going to zero
If $X \sim \mathcal{N}(\mu, \sigma^2)$, then
\begin{equation}
\mathcal{I}\left(\mu, \sigma^2\right)=\left(\begin{array}{cc}
\frac{1}{2\mathcal{H}...
0
votes
0
answers
47
views
How to prove that pseudo entropy and topological entropy are the same with only Markov inequality and continuity?
Let $(X,\rho)$ be a compact metric space and $f:X\to X$ a homeomorphism. We say $(x_1,\ldots,x_{n})\in X^n$ is a partial $n$ orbit if $f(x_i)=x_{i+1}$. Let $Sep_{\epsilon}(X,\rho_n)$ be the maximal ...
7
votes
1
answer
186
views
Lower bound $\int_0^1 \frac{|f'(x)|^2}{f} \,\mathrm{d} x$ by $\int_0^1 |f-1|^2\, \mathrm{d} x$
Assume that $f$ is a probability density on $x \in (0,1)$, I want to obtain a bound of the following form (if it is possible at all): $$ \int_0^1 \frac{|f'|^2}{f} \,\mathrm{d} x \geq C\,\int_0^1 |f-1|^...
2
votes
1
answer
167
views
Entropy reduction?
The following is a heuristic for the situation where a decision algorithm or a human, might solve a problem by reducing the entropy of the "search space" at every computation step $i$:
Let $...
- 1,817
3
votes
1
answer
106
views
Conditions for: (local) lipschitz stability of I-projection
The following post builds on this post; I'll begin by quoting the setting.
Background from Previous Question:
$\newcommand\SS{P}\newcommand\TT{Q}$Call a Gaussian probability measure $\SS$ on $\mathbb{...
- 89
1
vote
1
answer
100
views
References: error and stability estimates for information projection
$\newcommand\SS{P}\newcommand\TT{Q}$I will call a Gaussian probability measure $\SS$ on $\mathbb{R}^d$ isotropic if its covariance matrix is diagonal with non-vanishing determinant; i.e. $\Sigma_{i,i}&...
- 89
1
vote
1
answer
178
views
Entropy upper bound for the union of uniform distributions over union-closed families
The following question is motivated by the recent breakthrough result by Justin Gilmer on the union-closed sets (aka Frankl) conjecture.
Let $\mathcal{F}\subseteq\mathcal{P}(\mathbb{N})$ be a finite, ...
- 282
1
vote
1
answer
86
views
Conditional differential entropy of sum of Gaussians
Is it possible to give an expression for the conditional differential entropy $h(A+B\mid C+D),$ where $A,B,C,D$ are normally distributed with known standard deviations $σ_A,\ldots,σ_D$ and where all ...
3
votes
1
answer
317
views
A variational estimate related to the union closed set conjecture
Let $\varphi := \frac{\sqrt{5}-1}{2}$ be the golden ratio, and $H(x):=-x\log_2 x -(1-x) \log_2(1-x)$ be the binary entropy function for a Bernoulli random variable.
Show that for all $\delta > 0$, ...
- 4,312
6
votes
1
answer
238
views
Why does non-decreasing entropy imply actual convergence to that max entropy distribution?
Let $X_n$ be i.i.d with finite variance. Let $\bar X_n=\frac 1n \sum_{i=1}^nX_i$. It is a famous result that the continuous/differential entropy of the normalized average is non-decreasing. $$\mathrm ...
- 10.2k
9
votes
1
answer
170
views
Bibliography request: Entropy for continued fractions
Given a strictly positive real number $x$ we set $e(x)=\log(1+x)$ if $x$ is an integer and
$$e(x)=\log(1+x)+\frac{1+\lbrace x\rbrace}{1+x}\left(e(1/\lbrace x\rbrace)-\log(1+\lbrace x\rbrace)\right)$$
...
- 15.9k
3
votes
1
answer
192
views
Entropy of $f^{m(x)+n}$ of full shift
Let $(X,\mu,f)$ be a two-sided full shift system. Assume that there is $t \in \mathbb{N}$ such that for every $n \in \mathbb{N}$ and $x \in X$, we can define $T(x)=f^{n+m(x)}(x)$, where $m(x) \leq t; $...
- 929
2
votes
0
answers
74
views
Generalization of the min-entropy that looks at the top $n$ probabilities
The min-entropy of a random variable $X$ can often be much easier to compute than the Shannon entropy. This is because the min-entropy is simply a function of the most probable value, and sometimes, ...
- 4,097
4
votes
2
answers
225
views
Maximal entropy of integer partitions of $n$
Let $\operatorname{Part}(n)$ be the set of integer partitions of $n$.
A partition $p \in \operatorname{Part}(n)$ has $k$ summands and $d$ distinct summand $n_i$, with $d \leq k$ and $d$ frequencies $...
7
votes
0
answers
148
views
How to categorify entropy/perplexity?
(Migrating from math.stackexchange.com per commenter suggestion)
I was reading Baez, Fritz, and Leinster's "A Characterization of Entropy in Terms of Information Loss", and wondered if, ...
- 251
15
votes
1
answer
667
views
Information inequalities
What are the feasible $2^n$-tuples of entropies $h(S) := H(X_{i_1},\dots,X_{i_{|S|}})$ where $X_1,\dots,X_n$ are discrete random variables with some (unknown) joint probability distribution as $S=\{...
- 18.8k
2
votes
0
answers
86
views
List decodability of Reed-Solomon codes beyond the Johnson bound
In a paper on a proximity test for Reed-Solomon codes the authors state an "extremely optimistical" conjecture on the list decodability of Reed-Solomon codes (over prime fields $\mathbb F_q$)...
- 81
0
votes
0
answers
45
views
Maximize entropy under Kulback-Leibler divergence
I posed this question in math.stackexchange.com, but have not received any answer. I would like to try my luck here.
In this question, it is to solve
\begin{align}
\max_p &-\int dy\,p(y)\ln p(y) \\...
- 2,169
2
votes
0
answers
114
views
Entropy of a sequence
I am reading the paper Sign Changes in Hecke Eigenvalues by Matomaki and Radziwill, and in one place they mention the following,
It would be interesting to rule out the possibility of $\lambda_f(n)$ ...
- 487
3
votes
1
answer
205
views
An inequality relating the Kullback-Leibler divergence of two discrete distributions with constant reference distribution
Suppose that $D_{KL}(p_1\parallel q)<1$ and $D_{KL}(p_2\parallel q)<1$. I'm trying to show that either $D_{KL}(p_1\parallel p_2)$ or $D_{KL}(p_2\parallel p_1)$ will have an upper bound close to ...
1
vote
1
answer
194
views
Covering numbers for products of functions from two spaces?
Exercise (HW1): Let $\mathcal{F}$ and $\mathcal{G}$ be classes of measurable function. Then for any probability measure $Q$ and any $1 \leq r \leq \infty$,
(i) $N_{[]}\left(2 \epsilon, \mathcal{F}+\...
- 79
2
votes
0
answers
105
views
Covering/Bracketing number of monotone functions on $\mathbb{R}$ with uniformly bounded derivatives
I am interested in the $\| \cdot \|_{\infty}$-norm bracketing number or covering number of some collection of distribution functions on $\mathbb{R}$.
Let $\mathcal{F}$ consist of all distribution ...
- 93
1
vote
0
answers
57
views
Finite dimensional subspaces of L^p, entropy estimates
The following follows from Proposition 9.6 in Approximation of zonoids by zonotopes, Acta Math. 162 (1989), no. 1-2, 73–141, by Bourgain, J., Lindenstrauss, J., and Milman, V.
Let $X\subset L^1(\mu)$ ...
- 111
0
votes
0
answers
43
views
Maximization of accumulated entropy of time-changed Brownian motion stopped at $\{-1/2, 1/2\}$
Let $W=(W_t)_{t\ge 0}$ be a standard Brownian motion. Define the running maximum and minimum by $S_t:=\max_{0\le u\le t}W_u$ and $I_t:=\min_{0\le u\le t}W_u$. It is known that
\begin{eqnarray}
&&...
user478492
1
vote
0
answers
44
views
A distribution $\pi \propto \exp(-f)$ satisfies log-Sobolev inequality, does $\exp(-af)$ also satisfy LSI?
Assume a distribution $\pi \propto e^{-f}$ satisfies log-Sobolev inequality (LSI)
$$\forall \rho \in P(\mathbb{R}^n), \quad KL(\rho\| \pi) \le \frac{1}{2\lambda} I(\rho \| \pi)$$
with LSI constant $\...
- 11
8
votes
2
answers
234
views
Does entropy of the random walk control the return probability
Given an infinite connected graph $G$ of bounded degree with vertex set $X$, let $P_x^n$ the time $n$ distribution of the simple random walk started at the vertex $x$ (so $P^n_x(y)$ is the probability ...
- 4,374
4
votes
1
answer
283
views
Bipartite version of Hamming bound (two families of codewords with large Hamming distance)?
Update: In light of Fedor Petrov's answer, I added an additional requirement that all strings in $A$ and $B$ have Hamming weight exactly $n/2$, which hopefully makes the question more interesting.
...
- 43
4
votes
1
answer
274
views
Fokker-Planck: equivalence between linear spectral gap and nonlinear displacement convexity?
In a smooth, bounded and convex domain $\Omega\subset \mathbb R^d$ consider the usual linear Fokker-Planck equation with Neumann (some would say Robin) boundary conditions
\begin{equation}
\label{FP}
\...
- 4,309
2
votes
1
answer
77
views
Relation between multivariate estimation error and differential entropy
On page 255 of the book "Elements of information theory" by Thomas M. Cover and Joy A. Thomas, there is a theorem: For any random variable $X$ and estimator $\hat{X}$, $$E(X-\hat{X})^2 \geq \...
- 21
1
vote
0
answers
90
views
Polynomial entropy of topological dynamical systems
For a continuous mapping $\varphi: X \to X$ on a compact Hausdorff space $X$ we define the entropy as follows:
Given open covering $\mathcal{U}$, $\mathcal{V}$ of $X$, we call $\mathcal{V}$ a ...
- 85
2
votes
0
answers
210
views
Prove or disprove a mutual information inequality
I have $n$ IID Bernoulli random variables denoted by $X_1,X_2,\ldots X_n$ with parameter $p$.
I am interested in knowing if the following inequality involving mutual information holds :
$\boxed{\max_{...
- 83
2
votes
1
answer
132
views
Mutual information between two discrete random variables
I have 2 IID random variables $X_1$ and $X_2$ with $Bern(p)$ distribution. I have another binary random variable $Y$ taking values in $\{0,1\}$.
I am interested in comparing the following 2 mutual ...
- 83
10
votes
2
answers
398
views
The origin of the natural base in statistical mechanics
In modern treatments of statistical mechanics, the natural base is conventionally used for the Gibbs and Boltzmann entropy without careful justification. While I am aware that the properties of the ...
- 3,601
5
votes
0
answers
173
views
Divergence for Bhattacharya Information matrix
The Fisher information matrix (in the scalar parameter case) can be obtained from the Kullback-Leibler divergence by
$$g(\theta) = -\frac{\partial}{\partial \theta}\frac{\partial}{\partial \theta'}D(...
- 779
2
votes
2
answers
121
views
Convexity of the exponential of the negative Renyi entropy
I would like to try my luck here for the following question after failing to elicit an answer to it on math.stackexchange.com.
For $r\ge -1$, the exponential of the negative Renyi entropy is defined ...
- 2,169
6
votes
2
answers
362
views
3-periodic point implies positive topological entropy
When I learn some basic ergodic theory, I encounter an interesting exercise. As we all know, 3-periodic point often means chaos. Therefore, when a continuous map has a 3-periodic point, it may have ...
- 61
2
votes
1
answer
109
views
Boltzmann distribution
Let's say we have n points, on which the Boltzmann distribution $P = \{p_1,p_2,...,p_n\}$ is defined. Is it generally true that $\prod_{i=1}^n p_i < \prod_{i=1}^m q_i$ if $Q = \{q_1,...,q_m \}$ is ...
- 21
1
vote
0
answers
67
views
Using maximum entropy principle for joint probability estimation
Let $X_1, \dots, X_n, Y$ be random variables, each taking values in $\{0,1\}$. Assume that we are interested in estimating, for each $v=(v_1,\dots,v_n)\in \{0,1\}^n$, the probability
$$
p(v) = P[Y=1|...
- 3,477
1
vote
0
answers
270
views
Can a lower bound for this weakening of Goldbach's conjecture be reached?
Say a non negative integer $r$ is a primality radius of $n$ if both $n-r$ and $n+r$ are prime, and that a non negative integer $w$ is a Galois radius of $m$ if $\omega(m-w)=\omega(m+w)=1$, where $\...
- 6,920
0
votes
1
answer
189
views
Metric entropy and topological entropy
It is well known that, for a dynamical system $T$ on a metric space $(X,d)$, the variational principle connects the definition of metric entropy and topological entropy. In other words,
if
$$M(X,T) := ...
3
votes
1
answer
115
views
Zero entropy and the Koopman representation
Let $T$ be a measure preserving bijection of a probability space $(X,\nu)$. Consider the Koopman representation of $\mathbb{Z}$ on $L^2(X,\nu)$ given by $[z.f](x) = f(T^{-z}(x))$. The question is: can ...
- 1,210
2
votes
0
answers
83
views
Continuity of the entropy of the solution of a parabolic PDE at $t=0$
Consider the following initial value problem for a parabolic PDE :
$$\begin{cases}
\textrm{div}\big(A\,\nabla u(t,x) + b(x)\, u(t,x)\big) \,=\,\partial_t u(t,x) \quad x\in\mathbb R^d\,,\ t>0 \\[4pt]...
- 311
6
votes
3
answers
957
views
Is there an entropy proof for bounding a weighted sum of binomial coefficients?
Given a probability $p \in (0,1)$ and parameter $\alpha \in (0,1)$, is there an entropy-based proof which yields a good upper bound for the sum
$$\sum_{\ell = 0}^{\alpha n} \binom{n}{\ell}p^\ell(1-p)^{...
- 397
2
votes
2
answers
363
views
Difference between Shannon entropy and min-entropy
I would like to construct a sequence of discrete random variable $X_2, X_3,...,X_n,...$, where $X_n \in\{0,1,2,...,n-1\}$. Given any $\epsilon \in (0,1)$, its Shannon entropy and min-entropy should ...
- 23
2
votes
1
answer
199
views
An inequality in the optimality of Bayes' theorem
$\DeclareMathOperator\Ent{Ent}\newcommand{\prior}{\mathrm{prior}}\newcommand\Data{\mathrm{Data}}$I came across this paper on the optimality of Bayes' theorem
https://sinews.siam.org/Portals/Sinews2/...
- 23
1
vote
0
answers
52
views
How does a computer program recognize shocks given data of a solution to a conservation law?
Conservation laws are PDEs of the form $u_t +j_x=0.$ A discontinuous solution (for $u$ and $j$) to an equation like this can be easily found. Let's suppose that we are working with a piecewise ...
- 1,469
0
votes
1
answer
133
views
Trying to prove an inequality (looks similar to entropy)
I'm trying to prove the following inequality (or something similar, up to a constant factor in either side of the inequality):
$$k\cdot\sum_{i=1}^{k}x_{i}\cdot\ln\left(x_{i}\right)\geq\sum_{i=1}^{k}x_{...
1
vote
1
answer
253
views
Obtaining the error term of binomial distribution's entropy from the differential entropy of a Gaussian distribution
It is known that the first order error term in the Shannon entropy formula for a binomial distribution is $1/n$ (for example, see the Wikipedia page Binomial distribution), where in the limit $n \to \...
user325283
17
votes
4
answers
2k
views
Geometric interpretations of the exponential of entropy
Question:
Might there be a natural geometric interpretation of the exponential of entropy in Classical and Quantum Information theory? This question occurred to me recently via a geometric inequality ...
- 3,601