# Questions tagged [entropy]

The entropy tag has no usage guidance.

201
questions

**1**

vote

**0**answers

30 views

### Covering number for the unit ball in a reproducing kernel Hilbert space

I am looking for a reference for an upper bound on the covering number for the unit ball $\{ f \in \mathcal{H}: ||f||_{\mathcal{H}} || \leq 1\} $, where $\mathcal{H}$ is a reproducing kernel Hilbert ...

**4**

votes

**1**answer

119 views

### Heat flow, decay of the Fisher information, and $\lambda$-displacement convexity

In the whole post I will work in the flat torus $\mathbb T^d=\mathbb R^d/\mathbb Z^d$ and $\rho$ will stand for any probability measure $\mathcal P(\mathbb T^d)$. This question is strongly related to ...

**8**

votes

**0**answers

73 views

### Factor map between subshifts preserving topological pressure (or measure-theoretic entropy)

Let $G$ be a countable amenable group and let $X,Y$ be subshifts with finite alphabet over $G$. Suppose that $h(X) = h(Y)$ (equal topological entropy). I am interested in continuous factor maps $\pi: ...

**0**

votes

**0**answers

31 views

### Do d “moments of surprisal” determine a probability distribution on d events?

(The following question was transferred from stack-exchange with the hope of obtain a useful hint here). Consider a probability distribution on $d$ events, with the probabilities $p_j$ gathered in a ...

**2**

votes

**1**answer

75 views

### Applying the Abramov-Rokhlin skew product entropy formula to a bounded-to-one factor

Let $(X, \mathcal{B}, \mu, S)$ and $(Y, \mathcal{C}, \nu, T)$ be invertible probability-measure-preserving systems, with a measurable factor map $\pi: X \to Y$, i.e. $\pi \circ S = T \circ \pi$. ...

**1**

vote

**0**answers

49 views

### More formulas for joint entropy and for trace form entropies

Linked to some applications of entropy to combinatorics I'm looking for formulas expressing the joint entropy of two r. v. as a function of the conditional entropy . For example
For BWS extensive ...

**2**

votes

**0**answers

79 views

### Gurevich's entropy and topological entropy in a countable Markov shift

Good afternoon, I understand that Gurevich's entropy and topological entropy coincide when the countable Markov shift is topologically mixing (right?)
Does anyone know of an example or a reference ...

**1**

vote

**2**answers

94 views

### A conjecture on 'truncated joint moments' of binomial coefficients under binomial distribution

This is similar in spirit to Sum of squares of middle binomial sums or 'Truncated mean' of binomial coefficients under binomial distribution but gives some total estimates. Though the other ...

**2**

votes

**1**answer

138 views

### Sum of squares of middle binomial sums or 'Truncated mean' of binomial coefficients under binomial distribution

$\mu=1+\epsilon$ where $\epsilon>0$ holds.
1.Is there a good bound for $$T=\frac{\sum_{i=-\sqrt{\mu n\ln n}}^{\sqrt{\mu n\ln n}}\binom{n}{\frac n2 +i}^2}{2^n}?$$
This quantity can be ...

**2**

votes

**1**answer

118 views

### Tight sublinear estimates for a triple partial binomial summation

Is there tight estimates for the following logarithmic summation ($\gamma,\gamma'\in(0,1)$ and $\mu,\mu'>0$)
$$\log_2\Bigg(\sum_{t=\frac{n^{}}2-n^\gamma\sqrt{\mu\ln n}}^{\frac{n^{}}2+n^\gamma\sqrt{...

**1**

vote

**1**answer

143 views

### With only two characters allowed, is it possible to efficiently reference a 256 character alphabet in a string?

Let us use 0 and 1 for the binary parallel.
You have 256 characters you need to reference, imagining a 256 character alphabet. You can only use a string to reference them that contains 0 and 1. The ...

**0**

votes

**1**answer

83 views

### Terminology and approximation to logarithm of a sum of products of binomial coefficients

Denote $$T(m)=\sum_{1\leq n_m\leq n_{m-1}\leq\dots\leq n_2\leq n_1\leq m}\prod_{i=1}^{m}\binom{n_i}{n_{i+1}}.$$
Is there a name for this kind of summation and is there a good estimate for $\ln T(m)$ ...

**0**

votes

**2**answers

189 views

### Interpolating asymptotic expression for logarithm of middle binomial sums

Define $S(k,2n)=\sum_{i=-k}^k\binom{2n}{n+i}$ at every $k\in\{0,\dots,n\}$.
We know $$\ln(S(\gamma\mbox{ } n^\gamma,2n))\asymp(2n\ln2-\frac12\ln\pi-\frac12\ln n)$$ at $\gamma\rightarrow0$ and $$\ln(S(...

**7**

votes

**3**answers

364 views

### Asymptotics of multinomial coefficients

Binomial coefficients have a well known asymptotics (https://en.wikipedia.org/wiki/Binomial_coefficient#Bounds_and_asymptotic_formulas) given by $$\binom nk\sim\binom{n}{\frac{n}{2}} e^{-d^2/(2n)} \...

**6**

votes

**2**answers

288 views

### Do mixing homeomorphisms on continua have positive entropy?

I am trying to understand relations between various measures of topological complexity. I have read that expansive homeomorphisms on continua, for example, have positive entropy. But I do not know ...

**8**

votes

**1**answer

220 views

### Connection between entropy and the set of factors of a sequence

Let $a = (a_n)_{n=0}^\infty$ be a bounded real-valued sequence. By a factor of $a$ I mean a finite block $w \in \mathbb R^l$ that appears in $a$, that is, there exists $n \geq 0$ such that $a_n a_{n+1}...

**0**

votes

**1**answer

163 views

### Bounding information of expression

Cross posted to theory exchange - https://cstheory.stackexchange.com/questions/45610/bounding-information-of-expression
Suppose $u_1,\ldots,u_n$ are uniformly iid in $\{0,1\}$.
Let $x_1,\ldots,x_n$ ...

**2**

votes

**0**answers

118 views

### The topological complexity of polytopes

Polytopes arise naturally when modelling fundamental structures in Biology such as RNA and proteins [1,2]. Recently, it occurred to me that a complexity measure on the topology of polytopes might be ...

**1**

vote

**0**answers

60 views

### Convexity of conditional relative entropy for Markov distributions

Consider two Markov processes $p$ and $q$. The conditional relative entropy between them is
\begin{align}
D(p\parallel q)& =\sum_a p(a)\sum_b p(b\mid a)\log\frac{p(b\mid a)}{q(b\mid a)}\\
& =\...

**6**

votes

**0**answers

96 views

### Countable-to-one factors of measure preserving systems do not change entropy

It is known that if $\psi$ is a factor map between probability measure preserving systems $(X,\mathscr{X},\mu,T)$ and $(Y,\mathscr{Y},\nu,S)$ is countable-to-one almost everywhere, then $h(\mu,T)=h(\...

**1**

vote

**0**answers

18 views

### Number and different kinds of spnning trees in a weighted graph

We know that for a unweighted graph the number $\tau(\mathcal{G})$ of unique spanning trees of $\mathcal{G}$ is $$\tau(\mathcal{G})=\det L_\mathcal{G}^{\{n-1\}},$$ where $L_\mathcal{G}^{\{n-1\}}$ is ...

**1**

vote

**1**answer

224 views

### Entropy of probability distributions on a sphere

I have a family of probability distributions on the $n$-dimensional sphere $\mathbb S^n \subset \mathbb R^{n+1}$ defined in the following way:
$D_0$ is the uniform distribution, which is constructed ...

**1**

vote

**0**answers

86 views

### Example shows that entropy is not upper semi continuous

Let $(X, \beta, \mu)$ be probabilty space of compact space $X$. Let $T:X \rightarrow X$ be continuous function, and expansive. It is well known that entropy $\mu \mapsto h_{\mu}$ is upper semi ...

**4**

votes

**1**answer

420 views

### Does multiplication increase entropy?

Does multiplication increase entropy?
The Shannon entropy of a number $k$ in binary digits is defined as
$$ H = -\log(\frac{a}{l})\cdot\frac{a}{l} - \log(1-\frac{a}{l})\cdot (1-\frac{a}{l})$$
where $...

**2**

votes

**0**answers

87 views

### Can entropy of a network be written as a polynomial?

In my research, I met a problem here.
Consider a weighted graph Laplacian matrix
$$\mathcal{L}_w(\mathcal{G}) = DWD^T,$$ where $D$ is a incidence matrix and $W$ is diagonal with each diagonal ...

**1**

vote

**0**answers

143 views

### Minimising an Integrated Relative Entropy Functional

Suppose I am given
A probability distribution on $\mathbf R^d$, with density $\pi (x)$.
A family of transition kernels $\{ q^0 (x \to \cdot) \}_{x \in \mathbf R^d}$ on $\mathbf R^d$, with densities $...

**4**

votes

**1**answer

95 views

### Polynomial time decodable binary linear codes achieving $GV$ bound?

Are there explicit or random construction of linear codes that achieve the $GV$ bound with polynomial time decodable property with alphabet size $q=2$?
Tsfasman, Manin, Vladut beat the bound at ...

**0**

votes

**0**answers

152 views

### Topological entropy of logistic map $f(x) = \mu x (1-x)$, $f:[0,1] \to [0,1]$ for $\mu \in (1,3)$

As stated in the question, I want to find the topological entropy of the logistic map on the interval $[0,1]$ for a "nice" range of the parameter $\mu$, namely $\mu \in (1,3)$. I think the fact that $...

**1**

vote

**0**answers

101 views

### Entropy of endpoints of a random walk in a dense graph

Let $p\in[0,1]$ be a constant and let $G$ be a graph with $n$ vertices and $\approx p\binom{n}{2}$ edges. If you'd like, consider $p=1/2$.
Let $X$ be a random vertex of $G$ chosen proportional to ...

**2**

votes

**2**answers

172 views

### Lower bound Renyi divergence between two discrete probability distributions

I am trying to understand the proof of Lemma 1 in this paper (Section 9.2).
The proof shows that given a discrete probability distribution $P=(p_1,p_2,...,p_k)$ where $p_1 \geq p_2 \geq ... \geq p_k$,...

**5**

votes

**0**answers

195 views

### Looking for a counterexample for Ruelle's inequality on compact manifold

Let $M$ be a compact differentiable manifold, and $f:M\to M$ be a $C^1$- smooth diffeomorphism.
If Assume that $\mu$ be a $f$-invariant probability measure on $M$.
Then D.Ruelle proved that
$$
h_\...

**3**

votes

**3**answers

261 views

### Asymptotic value of the Shannon entropy

I would like to evaluate the asymptotic value of the following sum:
$$f(N)=\frac{1}{2^N}\sum_{n=0}^{N} \binom{N}{n} \log_{2} \binom{N}{n}$$
This is related to the computation of the Shannon entropy. ...

**2**

votes

**0**answers

69 views

### Is Colding-Minicozzi entropy continuous w.r.t. $C^\infty$ convergenge?

For an hypersurface $\Sigma^n \subseteq \mathbb{R}^{n+1}$ the entropy introduced by Colding and Minicozzi (see their paper) is defined as
$$
\lambda(\Sigma) := \sup_{x_0 \in \mathbb{R}^{n+1} \\ t_0 \...

**3**

votes

**0**answers

54 views

### Sharp asymptotic behavior of the metric entropy for the unit ball in Besov space

For $s>0$ and $1 \leq p,q \leq \infty$ let $B^s_{p,q}$ be the Besov space defined on $[0,1]^d$, and assume $ s > d( \frac 1 p - \frac 1 2)_+$, such that $B^s_{p,q}$ is compactly embedded in $L^2(...

**1**

vote

**1**answer

66 views

### Good UPPER bounds for $\log(\sum_{i=1}^n p_ie^{z_i})-\sum_{i=1}^np_iz_i$ where $(p_i)_i$ is a probability vector

Let $x=(z_1,\ldots,z_n)$ be real vector and $(p_1,\ldots,p_n)$ be a probability vector.
Question
$\log(\sum_{i=1}^n p_ie^{z_i})-\sum_{i=1}^np_iz_i \le ???$
Observation
This paper allows us to ...

**23**

votes

**1**answer

621 views

### The Euler-Mascheroni constant and entropy

I would like to know if I have discovered or merely rediscovered the following pretty fact.
A partition of $[0,1]$ into intervals of lengths $p_{i, i=1\ldots n}$ induces a probability distribution ...

**5**

votes

**2**answers

705 views

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

Let $X$ follow a binomial distribution with parameters $n$ and $p$. Are there any known bounds for the expected value of $X\log{X}$, for large $n$ and small (but fixed) $p$? A Poisson approximation ...

**5**

votes

**1**answer

175 views

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

If $p(x)$ is a discrete probabilistic density function, one could construct another discrete probabilistic density function proportional to $p(x)[1-p(x)]$ with a corresponding partition function to ...

**1**

vote

**0**answers

38 views

### Show a convolution of distributions ε-close to min-entropy k is ε^t-close to min-entropy k

Assume $X_1,...,X_t$ are independent distributions on $\mathbb{Z}_2^n$ s.t. each $X_i$ is $\epsilon$-close to min-entropy $k$; i.e. there exist distributions $Y_1,...,Y_t$ on $\mathbb{Z}_2^n$ s.t:
$$ \...

**2**

votes

**4**answers

557 views

### Apply doubly stochastic matrix M to a probability vector, then entropy increases?

Consider a vector $p =(p_1,...p_n)$, $p_i>0$, $\sum p_i = 1$
and a matrix $M_{ij}$, which is doubly stochastic: $\sum_i M_{ij} = 1, \sum_j M_{ij} = 1, M_{ij} > 0$.
Question 1 Just apply ...

**2**

votes

**0**answers

75 views

### What are the moments of Kolmogorov Complexity for a Random Variable?

Given a random variable $X$ distributed under some computable distribution $P$ we have,
$$0 \le E[K(X)] - H(P) \le K(P)$$
Where $H(P)$ is the entropy of $P$. I tried using Hoeffding concentration ...

**1**

vote

**0**answers

43 views

### Example/counterexample of distribution $P$ such that $D(P\parallel Q) <\infty$ where $Q$ is Gaussian, but $E_P[X^2]=\infty$

I am looking for an example or a counterexample of a distribution $P$ such that
\begin{align}
D(P\parallel Q) <\infty
\end{align}
where $Q$ is standard Gaussian, but $E[X^2]=\infty$ where $X \sim P$...

**6**

votes

**0**answers

175 views

### Characterization of KL divergence for continuous variables?

This is an analog of an older question:
What characterizations of relative information are known?
With the modification that I’m interested in the case when the distribution is over something that’s ...

**14**

votes

**3**answers

1k views

### Entropy and total variation distance

Let $X$, $Y$ be discrete random variables taking values within the same set of $N$ elements. Let the total variation distance $|P-Q|$ (which is half the $L_1$ distance between the distributions of $P$ ...

**3**

votes

**1**answer

304 views

### Updating Geman and Geman (1984) on image restoration

I am reading the seminal paper
Stuart Geman and Donald Geman, Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images, IEEE Transactions on Pattern Analysis and Machine ...

**4**

votes

**2**answers

288 views

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

Define the (differential) entropy for a density $f$ as
$$ H(f) :=-\int_{0}^{1} f(x) \log_{2}(f(x)) dx \, .$$
I am trying to find a $f \in L_{1}([0,1])$ such that $f\geq 0, \int_{0}^{1} f(x) dx = 1$...

**4**

votes

**1**answer

255 views

### Is there an integer-valued analogue of information entropy?

Let $H_n : (\langle 0,1 \rangle \cap \mathbb{Q})^n \to \langle 0,\log_2 n \rangle, \; H_n(P) = -\sum_{i=1}^n P_i \log_2 P_i, \; \sum_i P_i = 1$ be the information entropy on rationals. I am looking ...

**4**

votes

**1**answer

247 views

### Distribution of longest run locations in a random string

Let x be a random n-bit string, and let $I ={i_1,i_2,...,i_n}$ be the starting indexes of the longest 0-runs of x, sorted in decreasing order (so $i_1$ is the starting index of the longest (~$\log n$) ...

**0**

votes

**3**answers

191 views

### Single quantum particle entropy

Consider a wave function of a single particle in free space, whose evolution is described by the (non-dimensional) linear Schrodinger equation $$i\psi _t (t,\underline{x}) + \Delta \psi=V(\underline{x}...

**2**

votes

**1**answer

699 views

### Covering number of Lipschitz functions

What do we know about the covering number of $L$-Lipschitz functions mapping say, $\mathbb{R}^n \rightarrow \mathbb{R}$ for some $L >0$?
Only 2 results I have found so far are,
That the $\infty$-...