Questions tagged [entropy]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
2answers
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
1answer
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
1answer
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
1answer
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
1answer
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
2answers
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
3answers
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
2answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
2answers
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
0answers
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
3answers
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
0answers
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
0answers
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
1answer
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
1answer
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
2answers
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
1answer
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
0answers
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
4answers
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
0answers
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
0answers
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
0answers
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
3answers
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
1answer
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
2answers
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
1answer
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
1answer
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
3answers
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
1answer
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$-...

1
2 3 4 5