Questions tagged [entropy]
The entropy tag has no usage guidance.
311
questions
1
vote
0
answers
25
views
Reference request for "time-reversal invariance" of conditional information entropy
Given a finite sample $S$ of symbols that can be approximated by both unconditional and conditional processes $P(X), P(X|Y)$. One can always define the "reverse" process, ie: given a symbol ...
0
votes
0
answers
22
views
Metric entropy of mixed norm spaces with exponent-free bounds
Suppose $\mathcal{F}\subset L^p([0,1]^d)$ is a subset with the following property: The $L^q$-covering number of $\mathcal{F}$ is independent of $q$, for all $1\le q\le\infty$. An example of $\mathcal{...
-2
votes
0
answers
161
views
Don't understand a line in a paper by Horibe [migrated]
This question pertains to "A Entropy view of Fibonacci Trees" (1982) by Yasuichi Horibe, Zbl 0491.94009. Horibe defines a binary tree where a node has a left branch with probability x and a ...
0
votes
1
answer
184
views
Reference request: log Sobolev inequality for uniform measure (uniform distribution over discrete set)
Suppose that $N \in \mathbb N_+$ is fixed and denote by $\mu = (\mu_0,\ldots,\mu_N)$ the uniform distribution on the set $\{0,1,\ldots,N\}$ (i.e., $\mu_n = \frac{1}{N+1}$ for each $0\leq n\leq N$). I ...
2
votes
0
answers
96
views
Information inequality for Renyi divergences
Let $X^1 \ldots X^n$ be random variables on $\mathbb{R}^d$ with an arbitrary joint probability distribution $\mu$ on $\mathbb{R}^{n \times d}$. Let $\nu = \nu^1 \times \ldots \times \nu^n$ be a ...
0
votes
0
answers
45
views
Constants in the entropy number of the Sobolev space
For a Sobolev space with $W^s(\Omega)$, where $\Omega\subset R^d$ is a compact space with smooth boundary, we know that the entropy number satisfies $e(\delta, W^s(\Omega, 1),\|\cdot\|_{L_\infty})\leq ...
1
vote
1
answer
147
views
+100
Inequalities involving entropy: quantum discord and mutual information
My question is inspired by the following paper of Olivier and Żurek but for this question to be self-contained I will recall all the necessary definitions: for a quantum state $\rho$ we define the ...
1
vote
1
answer
132
views
Is the Boltzmann entropy continuous in the supremum norm?
We define $U : [0, +\infty) \to [0, +\infty)$ by $U(0) := 0$ and $U (s) := s \log s$ for $s >0$. Then $U$ is strictly convex. Let $D$ be the set of all bounded non-negative continuous functions $\...
1
vote
0
answers
63
views
Estimating the entropy of the solution to an SDE
Forgive me for the poorly researched question. I'm currently working on a computer science project involving training a neural stochastic differential equation, and I've run into a problem while ...
1
vote
1
answer
113
views
Does every proximal dynamical system have zero topological entropy?
A dynamical system is proximal if $$\:\forall (x,y) \in X \times X, \: \liminf_{n \rightarrow \infty} d(f^{n}(x),f^{n}(y)) = 0 $$ (where $X$ is a compact metric space with metric $d$). Is it true that ...
0
votes
1
answer
78
views
Can we lower bound this entropy by $\int_{\mathbb R^d} \rho^k (x) \, \mathrm d x$ and $\int_{\mathbb R^d} |x|^2\rho (x) \, \mathrm d x$?
We define $U : [0, \infty) \to [0, \infty)$ by $U(0) := 1$ and $U (s) := s \log s + (1-s)$ for $s >0$. Then $U$ is strictly convex. The minimum of $U$ is $0$ and is attained at $s=1$. Let $\mathcal ...
1
vote
2
answers
196
views
Is the Boltzmann entropy lower semi-continuous in the weak topology induced by $C_b (\mathbb R^d)$?
For Lebesgue-absolutely continuous probability measures $\rho\ll \mathcal{L}^d$ in the whole space $\mathbb{R}^d$ with finite second moments (i-e $\rho\in \mathcal{P}^2_{ac}(\mathbb{R}^d)$), let
$$
\...
0
votes
0
answers
64
views
"Calculus" of metric entropy: How does metric entropy behave with respect to binary operators?
This is a general question, more of a reference request. tl;dr: Is there a "calculus" for computing metric entropy bounds?
Given a function space $\mathcal{F}$, we may define its metric ...
2
votes
0
answers
69
views
Let $\mu : [0, T] \to \mathcal P_2^a (\mathbb R^d), t \mapsto \mu_t$ be absolutely continuous. Is $t \mapsto \mathcal H (\mu_t)$ continuous?
We endow the space $\mathcal P_2^a (\mathbb R^d)$ of absolutely continuous probability measures with finite second moment with the Wasserstein distance $W_2$. Let $\mathcal H (\mu)$ be the relative ...
1
vote
1
answer
84
views
Does convergence of Radon transforms of a sequence of probability distributions implies convergence of the distributions themselves?
Let $P_1,P_2,\ldots $ be a sequence of absolutely continuous probability measures on $\mathbb R^n$, and let
$f_j:\mathbb R^n\to\mathbb R$ be their PDFs. Assume that $\operatorname{E}P_j = 0$ and $\...
1
vote
1
answer
123
views
Maximal entropy distribution on three variables knowing its marginals on any two
Observation 0: Given a finite set $X$, the probability distribution on $X$ with highest entropy is the uniform one. This is well known.
Observation 1: Given two finite sets $X,Y$ and two probability ...
0
votes
0
answers
72
views
Does there exist an established name for the exponential of surprisal (e.g. the reciprocal of probability?)
There are several different names that I know of for the exponential of the entropy of which "diversity" and "perplexity" are fairly well-established. Tom Leinster has a very ...
3
votes
1
answer
352
views
Relative entropy equality for a sequence of Bernoulli random variables
We are given two joint probability distributions, $p$ and $q$, of $n$ Bernoulli random variables $X_1, X_2, \ldots, X_n$.
We denote by $p(x_k\mid x^{k-1})$ the probability $\mathbb{P}_p(X_k=x_k\mid ...
3
votes
0
answers
105
views
Differential entropy of random Gibbs measure
There is a question I have been wondering about for a while, which I have thus far not been able to resolve. The problem revolves around random Gibbs measures. I am not very well-versed in the more ...
2
votes
1
answer
107
views
Morse-Hedlund\Coven-Hedlund theorem for non-Abelian groups
There is a well know theorem by Coven and Hedlund, in Sequences with minimal block growth, stating that the complexity function of an aperiodic sequence\configuration $\omega\in \mathcal{A}^{\mathbb{Z}...
3
votes
1
answer
192
views
Bound on an integral representing a difference of two relative entropies
Let $ f : [0,1] \to \mathbb{R} $ be a function satisfying: 1.) $ |f(x)| \leqslant a $ for some $ a < 1 $, and 2.) $ \int_0^1 f(x) {\mathrm d}x = 0 $. I would like to know whether the following ...
2
votes
2
answers
782
views
Defining a measure of uniformity for measurable subsets of $[0,1]^2$ w.r.t dimension $\alpha\in[0,2]$
Let $(X,d)$ be a metric space. If set $A\subseteq X$, let $H^{\alpha}$ be the $\alpha$-dimensional Hausdorff measure on $A$, where $\alpha\in[0,2]$ and $\text{dim}_{\text{H}}(A)$ is the Hausdorff ...
1
vote
1
answer
67
views
Example of finite closed cover with entropy strictly greater than topological entropy
I'm reading "Topological entropy bounds measure-theorettic entropy", by L.W. Goodwyn.
enter link description here
After Proposition 2, he mentions that "finite closed cover can yield ...
5
votes
1
answer
270
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 ...
0
votes
0
answers
38
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
57
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 ...
8
votes
1
answer
266
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
202
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 $...
3
votes
1
answer
118
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{...
1
vote
1
answer
108
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}&...
1
vote
1
answer
230
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, ...
1
vote
1
answer
126
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
357
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$, ...
7
votes
1
answer
269
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
votes
1
answer
267
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)$$
...
3
votes
1
answer
201
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; $...
2
votes
0
answers
94
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
votes
2
answers
269
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 $...
8
votes
0
answers
195
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, ...
15
votes
1
answer
683
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=\{...
2
votes
0
answers
121
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$)...
0
votes
0
answers
51
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
votes
0
answers
130
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)$ ...
3
votes
1
answer
412
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
421
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}+\...
2
votes
0
answers
231
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 ...
1
vote
0
answers
71
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)$ ...
1
vote
0
answers
52
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 $\...
8
votes
2
answers
303
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
votes
1
answer
308
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.
...