# Questions tagged [entropy]

The entropy tag has no usage guidance.

**5**

votes

**1**answer

144 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

27 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

232 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

57 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$...

**5**

votes

**0**answers

140 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 ...

**10**

votes

**3**answers

567 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

216 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

147 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$...

**3**

votes

**1**answer

238 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

185 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

136 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

161 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$-...

**6**

votes

**2**answers

138 views

### Handel's Theorem for surfaces with boundary

Handel's Theorem(Entropy and semi-conjugacy in dimension two, 1987): let $M$ denote a closed surface. Let $\vartheta$ be a pseudo-Anosov (orientation-presrv.) homeomorphism of $M$ and $g$ be an (...

**3**

votes

**1**answer

95 views

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

Let $\Omega$ be the set of all infinite binary sequences $(x_i)_{i\ge 0}$ endowed with the product topology coming from discrete topology on $\{0,1\}$.
Consider $0<\alpha<1$ and let $$K_\alpha=\{...

**3**

votes

**1**answer

269 views

### Unclear construction in a paper of Ornstein and Weiss

I originally posted this on math.stack, but no one answered, so im posting here:
I need help understanding the following construction (Taken from the paper "Entropy and isomorphism theorems for ...

**1**

vote

**0**answers

84 views

### Existence of moment-constrained maximum entropy distribution with support $[0,1]^n$

Given a finite set of moment values $\{\mu_1,\ldots,\mu_N\}$, for which the multi-dimensional finite Hausdorff moment problem is determined. That is, we know that at least one distribution $\mathcal{D}...

**1**

vote

**0**answers

143 views

### Functional Taylor expansion for differential entropy

Consider an continuous distribution $F$ with density $f$. The (differential) Shannon entropy of $f$ is
$h(f)=-\int f(x)\log f(x) dx$.
In the literature of differential entropy estimation, ...

**3**

votes

**0**answers

153 views

### What is a natural way to extend a function from a subset of vertices to faces?

Let $n$ be a positive integer, and suppose $f$ is a probability distribution on the $2^n$ subsets of $[\![n]\!] := \{1,\ldots,n\}$. What is a "natural" way to extend $f$ to a distribution $\bar{f}$ on ...

**4**

votes

**0**answers

213 views

### Maximazing the joint entropy given the probability of equality

Consider 2 independent random variables $X$ and $Y$ with values in $A=\{0, 1, \ldots, q-1\}$. Suppose that $P(X=Y)$ is equal to some constant $\varepsilon$.
What is the maximal entropy $H(X, Y)$?
At ...

**3**

votes

**1**answer

311 views

### Kullback–Leibler divergence of product distributions

Say the KL divergence between two distributions $A$ and $B$ is $\varepsilon$. Can we give bounds, or a precise computation, of the KL divergence between $A^k$ and $B^k$ (the product distributions)?

**3**

votes

**0**answers

95 views

### Diffeomorphisms preserving “nice” smooth functions

Let $\mathbb{R}^2\supset D=\{(x,y)\in\mathbb{R}^2|x^2+y^2<1\}$ be the open unit disc, and $U\subset\mathbb{R}^2$ be the interior of Koch's snowflake, as constructed in Falconer's book Fractal ...

**0**

votes

**1**answer

99 views

### How to compute the entropy of a random variable with values in a metric space? [closed]

I have a cloud of points, and I want to compute its 'diversity'. Variance is not appropriate, because a cloud clustering around few points can still have a large variance.
To that end, I see the ...

**12**

votes

**1**answer

338 views

### Entropy of composition

I asked this at math.stackexchange.com, but got no answers.
Let $(X,B,\mu)$ be a probability space. Let $T,S:X→X$ be two measurable measure preserving maps that commute (i.e $TS=ST$). Let $A$ be a (...

**28**

votes

**5**answers

1k views

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

I am interested in using Shannon's entropy in combinatorics. It is often presented with a motivation of how much information can be passed, but assume I am not interested in that, I want to understand ...

**1**

vote

**0**answers

210 views

### What is the maximum entropy distribution over the integers

Let $μ=0,σ>0$. What is the maximum entropy distribution over the integers with mean $μ$ and variance $σ^2$?
Is Skellam distribution a maximum entropy distribution? Is there a closed-form ...

**1**

vote

**1**answer

159 views

### the “observable” space of a measure space [closed]

For a measure space $(X,\mathcal{A},\mu)$, the space of "observables" with respect to finite set $F$ which is endowed with counting measure on all of its subsets, is defined as follows:
$$obs (X, \mu,...

**2**

votes

**1**answer

184 views

### Entropy x Complexity - Shannon x Kolmogorov [closed]

This is a very common question but I think I’m posting it in a different way.
Suppose that we have 256 different possible messages with uniform distribution to be represented in a binary code. Then ...

**2**

votes

**0**answers

40 views

### Do averaged binary symmetric channels maximize mutual information?

This is a refined version of Do binary symmetric channels maximize mutual information?, which was answered negatively.
Let the random variables $(X, Y)$ be a doubly symmetric binary source with ...

**1**

vote

**0**answers

35 views

### Subset with largest information gain [closed]

I am competing in a programming contest where the submission phase can be stated abstractly as follows : There is a known universe set, $U$, and a hidden target $T \subset U$. I submit $S \subset U$, ...

**3**

votes

**1**answer

62 views

### minimum information distribution given moments of its square

Given constants $m_0,\ldots m_n$ and a measure $\mu$ on $\mathbb{R}$, how can I "recover" the integrals $\int f x^n d\mu$ of the maximum entropy distribution $f\in L^2(\mathbb{R})$ which satisfies $\...

**1**

vote

**0**answers

41 views

### is the dependence of approximate entropy on the length of compared runs just bias or an evidence that implies different information in the time series

Approximate entropy is heavily dependent on the length of time series ($L$), the length of compared runs ($m$) which is generally set to 2, and the criterion of similarity ($r$).
Definition of ...

**4**

votes

**2**answers

392 views

### Gaussian distribution, maximum entropy and the heat equation

I have asked this question on MathSE, but I got no replies, so I thought of trying here.
Consider the Gaussian distribution on $\mathbb{R}$ with mean $m$ and variance $t=\sigma^2$. This has the ...

**1**

vote

**1**answer

56 views

### Properties of Relative Entropies

I'm looking at a paper by Arnold et al. (CPDE, 2001), in which they make use of convex functions in the context of relative entropies. There, they assume that on $(0,\infty)$, their entropy function ...

**4**

votes

**0**answers

73 views

### What is the entropy of binomial decay?

Let's play a game. I start with $N$ indistinguishable tokens, and I wait $T$ turns. Every turn, each token has probability $p$ of disappearing. I want an analytic formula for the entropy of this ...

**2**

votes

**1**answer

96 views

### Is $H_f$ injective in $f$?

Let $f \ge 1$ be a multiplicative arithmetic function and $F_f(n) = F(n)= \sum_{d|n}f(d)$.
Define the entropy of $n$ with respect to $f$ to be
$H_f(n) = -\sum_{d|n} \frac{f(d)}{F(n)}\log(\frac{f(d)}{...

**1**

vote

**1**answer

110 views

### How to deduce the following inequality by use of the Shannon-McMillan-Breiman theorem?

My question is how to deduce the red inequality from the Shannon-McMillan-Breiman theorem?
First I state some lemmas which will be used in the QUESTION:
the proceeding lemmas are in the setting where ...

**3**

votes

**1**answer

202 views

### Entropy of average of two distributions

Let $\mu,\nu$ be two distributions on the same discrete space. Is it true that
$$\mathrm{H}\left(\frac{\mu+\nu}{2}\right) \ge \mathbb{E}_{xy}-\log\left(\frac{\sqrt{\mu(x)\nu(y)}}{2} + \frac{\langle\...

**4**

votes

**1**answer

165 views

### Asymptotics for 'generalized" Kasteleyn's formula

A follow up on an earlier MO question.
Kasteleyn's formula for the number of domino tilings of a $2n\times 2n$ square
$\prod_{j=1}^n\prod_{k=1}^n \left( 4\cos^2(\pi j/(2n+1))+4\cos^2(\pi k/(2n+1))\...

**8**

votes

**2**answers

335 views

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

Let $X$ be a random variable taking values in $\{1,\ldots,n\}$, and let $p_i$ denote the probability of the event $\{X = i\}$. Shannon defined the entropy of $X$ to be the quantity
$$H(X) = -\sum_i ...

**0**

votes

**0**answers

119 views

### Maximum entropy with constraint on CDF

I would like to know whether the following problem is well posed, and whether there is a solution. Let me make it clear that I have no pretentions of rigor here.
Given a continuum random variable $x$...

**0**

votes

**1**answer

110 views

### Bounding difference of two mutual information with different distributions on random variables

Let $A$, $B$ and $C$ be three random variables and $p_{A,B,C}=p_Ap_Bp_{C|A,B}$ and $q_{A,B,C}=p_Aq_{B|A}p_{C|A,B}$ be two distributions on them. Then, we can conclude that?
\begin{align*}
\lvert I_p(A,...

**3**

votes

**0**answers

103 views

### How large do $r$-dimensional “Kasteleyn-Temperley-Fisher” numbers grow?

I brought up a couple of combinatorial and number-theoretic items with this MO question. Now, I shall inquire on growth estimates. Recall
$$K_r(n):=\prod_{\ell_1=1}^n\cdots\prod_{\ell_r=1}^n\left(
4\...

**3**

votes

**1**answer

271 views

### Mathematical links between entropy and moments of a given distribution

Under some conditions, a distribution is determined by all of its moments. Furthermore, there is a certain value of entropy for a given distribution. So my question is:
1.Can I say that its entropy ...

**1**

vote

**1**answer

156 views

### Computation of metric Entropy by another metric which is induced by a homeomorphism

First let me explain problem in general case
If $T:\mathbb R^n\to \mathbb R^n$ and $S:\mathbb R^n\to \mathbb R^n$ are two conjugated linear Dynamical Systems which means there exist homeomorphism $...

**4**

votes

**1**answer

371 views

### Question about mean sojourn time on non compact space

I'm reading a paper by Micheal Handel, Bruce Kitchens and Daniel J. Rudolph on Entropy http://link.springer.com/article/10.1007/BF02761650 I have some problem
I couldnt show that $\mu(\bigcup_{N\...

**4**

votes

**1**answer

257 views

### Maximum entropy distribution with constrained quantiles

Suppose we have a continuous probability distribution with density function $f$ whose support is $[a,b]$ and we know that for some finite set of values $\{ v_i \}_{i=1}^n$ between $a$ and $b$ that the ...

**7**

votes

**1**answer

165 views

### Entropy of chain decompositions of posets

Let $P$ be a finite poset and let $\,\mathcal{C}=(C_1,\ldots,C_\ell)\,$ be its decomposition into chains. We can define
$$
f(\mathcal{C}) = |C_1|! \, \cdots \,|C_\ell|!
$$
and ask for what $\mathcal{...

**3**

votes

**0**answers

53 views

### Is the extension of flows from the product of a system with a K system to itself relatively K?

Let $(X,\mathcal{B},\mu,T)$ be a probability measure preserving system. It is said to be a K-system if any non-trivial factor of it has positive entropy. Also we can define the notion of relatively K ...

**1**

vote

**1**answer

322 views

### Analysis of a partition algorithm

EDIT:
I realized that if $J$ is not a solution so is $J^c$. I updated the algorithm because of this.
Given some positive integers $x_1,\cdots, x_n$.
The following algorithm is for solving the ...