All Questions
Tagged with it.information-theory entropy
93 questions
0
votes
0
answers
14
views
What are examples of $\epsilon$-extractable uniform randomness $H_{\rm ext}^\epsilon(\cal P)$?
[Renner and Wolf 2004] introduces the notion of $\epsilon$-smooth Renyi entropies as
$$H_\alpha^\epsilon(P) \equiv \frac{1}{1-\alpha} \inf_{Q\in \mathcal B^\epsilon(P)}\log\left(\sum_z Q(z)^\alpha\...
- 342
1
vote
1
answer
163
views
trying to get intuition into why Cross Entropy will always be greater or equal to the Entropy
I understand what entropy measures and cross entropy is the same except it is uses another distribution $q$ to compare it against $p.$ Is it because the log function is concave down so the predictions ...
0
votes
0
answers
179
views
About the monotonicity of the exponential entropy
This question was previously posted on MSE at About the monotonicity of the exponential entropy.
In the paper The Unifying Frameworks of Information Measures the conditional exponential entropy (see ...
- 127
2
votes
0
answers
120
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 ...
1
vote
1
answer
182
views
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 ...
- 9,330
0
votes
0
answers
85
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 ...
- 4,897
3
votes
1
answer
205
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 ...
- 503
8
votes
1
answer
314
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|^...
- 730
3
votes
1
answer
127
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{...
- 364
1
vote
1
answer
124
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}&...
- 364
3
votes
1
answer
211
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; $...
- 1,043
2
votes
0
answers
111
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,897
15
votes
1
answer
703
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=\{...
- 19.7k
2
votes
0
answers
142
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$)...
- 81
4
votes
1
answer
330
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.
...
- 43
2
votes
1
answer
129
views
Relation between multivariate estimation error and differential entropy
On page 255 of the book "Elements of information theory" by Thomas M. Cover and Joy A. Thomas, there is a theorem: For any random variable $X$ and estimator $\hat{X}$, $$E(X-\hat{X})^2 \geq \...
- 21
2
votes
0
answers
264
views
Prove or disprove a mutual information inequality
I have $n$ IID Bernoulli random variables denoted by $X_1,X_2,\ldots X_n$ with parameter $p$.
I am interested in knowing if the following inequality involving mutual information holds :
$\boxed{\max_{...
- 83
2
votes
1
answer
292
views
Mutual information between two discrete random variables
I have 2 IID random variables $X_1$ and $X_2$ with $Bern(p)$ distribution. I have another binary random variable $Y$ taking values in $\{0,1\}$.
I am interested in comparing the following 2 mutual ...
- 83
10
votes
2
answers
547
views
The origin of the natural base in statistical mechanics
In modern treatments of statistical mechanics, the natural base is conventionally used for the Gibbs and Boltzmann entropy without careful justification. While I am aware that the properties of the ...
- 3,871
5
votes
0
answers
191
views
Divergence for Bhattacharya Information matrix
The Fisher information matrix (in the scalar parameter case) can be obtained from the Kullback-Leibler divergence by
$$g(\theta) = -\frac{\partial}{\partial \theta}\frac{\partial}{\partial \theta'}D(...
- 779
2
votes
1
answer
294
views
An inequality in the optimality of Bayes' theorem
$\DeclareMathOperator\Ent{Ent}\newcommand{\prior}{\mathrm{prior}}\newcommand\Data{\mathrm{Data}}$I came across this paper on the optimality of Bayes' theorem
https://sinews.siam.org/Portals/Sinews2/...
- 23
17
votes
4
answers
2k
views
Geometric interpretations of the exponential of entropy
Question:
Might there be a natural geometric interpretation of the exponential of entropy in Classical and Quantum Information theory? This question occurred to me recently via a geometric inequality ...
- 3,871
1
vote
0
answers
428
views
When inequality in Mrs. Gerber's lemma is almost equality?
Let $X=x_1\ldots x_n$ be a random variable.
Assume that every $x_i$ takes values in $\{0,1\}$.
Assume also that for every $I \subseteq \{1,\ldots, n\}$ the Shannon entropy of random value $X_I$
[if $I ...
- 2,576
2
votes
0
answers
132
views
A result of the covering number
Suppose $\mathcal{F} = \{f_x : x \in \mathbb{R}^d \}$ and each $f_x$ shares the same law $P$. If $\mathcal{F}$ is a class of uniformly bounded functions satisfying $L_r$-continuity, i.e. $\forall f \...
- 331
0
votes
1
answer
582
views
Integrability of $\int \log(f(x)) f(x) dx$ for a probability density function $f$
I am looking for weak conditions when a probability density function $f$ on $\mathbb{R}^d$ has a finite integral
$$
\int_{\mathbb{R}^d} \log(f(x)) f(x) dx.
$$
Any references would be appreciated.
- 3
5
votes
3
answers
533
views
Is there a quantum analog of Kolmogorov Complexity?
Kolmogorov Complexity (interpreted in terms of shortest program computing a string) and Shannon Entropy are quite similar.
Since there is a quantum entropy is it reasonable to ask if there is quantum ...
- 13.9k
8
votes
1
answer
486
views
The entropy of a partition of unity
A partition of unity can be thought of as a blurred out set partition: identify the fibers of the set partition with their indicator functions; the sum of these indicators is $1$. I would like to ...
- 181
0
votes
1
answer
260
views
Entropy of a refinement of a partition
We consider a probability space $(X, B, \mu)$. Let $\alpha$ and $\beta$ be countable partitions of X. We suppose $\beta$ is a refinement of $\alpha$, ie that every set in $\alpha$ is a union of sets ...
- 41
6
votes
2
answers
502
views
Shannon entropy and doubly stochastic matrices
Suppose that $A$ is a stochastic matrix. We know that if $A$ is doubly stochastic, then $H(Ap)\geq H(p)$ where $H$ is Shannon entropy and $p$ is a probability vector. Is the converse true? i.e., if $H(...
- 109
3
votes
1
answer
247
views
Trace entropies
I'm studying relationships between trace entropy functionals and combinatorics and I'm faced with the following problem. Lets $\mathcal {D}$ be the following differential operator $1 -x\cdot \cfrac{d}{...
- 131
2
votes
1
answer
181
views
Conditional entropy - solve example
Given a random variable $X$ that is uniformly distributed on $[-b,b]$ and $Y=g(X)$ with
$$g(x) = \begin{cases} 0, ~~~ x\in [-c,c] \\ x, ~~~ \text{else}\end{cases}$$
Now I want to compute the ...
- 131
2
votes
1
answer
293
views
Information theory for uncountably infinite-dimensional continuous random variable
I'm exploring the possibility to apply information theory on an uncountably infinite-dimensional scenario. I found the concept of generalized entropy for continuous random variables defined on finite-...
- 263
0
votes
0
answers
404
views
Is there a difference between using nats and bits to express entropy?
It seems to me like questions involving decimal vs binary representations of some number are not particularly interesting: for instance $\pi$ or $\sqrt{2}$ are conjectured to be normal in every base, ...
- 226
1
vote
1
answer
149
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 ...
11
votes
0
answers
307
views
Entropy, magnitude, diversity of finite metric spaces in number theory
I was reading the article by Tom Leinster, (Maximizing
diversity in biology and beyond, arXiv link), and find it very interesting.
Since I was searching for entropies of finite metric spaces I found
...
user6671
0
votes
1
answer
181
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$ ...
- 515
1
vote
0
answers
83
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)}\\
& =\...
- 11
4
votes
1
answer
196
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 ...
- 13.9k
3
votes
2
answers
323
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$,...
3
votes
3
answers
392
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. ...
- 31
23
votes
1
answer
767
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 ...
- 17.6k
3
votes
4
answers
1k
views
Apply doubly stochastic matrix M to a probability vector, then entropy increases?
Consider a vector $p =(p_1,\dots,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 ...
- 24.9k
2
votes
0
answers
92
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 ...
8
votes
1
answer
363
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 ...
- 928
18
votes
3
answers
3k
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$ ...
- 20.2k
5
votes
2
answers
848
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
283
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 ...
- 283
4
votes
0
answers
228
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 ...
- 41
1
vote
0
answers
432
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 ...
2
votes
0
answers
50
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 ...
