Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [entropy]

The tag has no usage guidance.

5
votes
1answer
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
0answers
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
4answers
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
0answers
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
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$...
5
votes
0answers
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
3answers
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
1answer
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
2answers
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
1answer
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
1answer
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
3answers
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
1answer
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
2answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
5answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
2answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
2answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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 ...