All Questions
41 questions
37
votes
3
answers
3k
views
An entropy inequality
Let $X,Y$ be probability measures on $\{1,2,\dots,n\}$, and set $K=\sum_i\sqrt{X(i)Y(i)}$ so that $Z:=\frac{1}{K}\sqrt{XY}$ is also a probability measure on $\{1,2,\dots,n\}$. How can we prove the ...
- 11.4k
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
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
18
votes
2
answers
966
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 ...
- 29.2k
18
votes
1
answer
2k
views
Gini Coefficient and Renyi Entropy
Gini coefficient (aka Gini Index) is a quantity used in economics to describe income inequality. It is 0 for uniformly distributed income, and approaches 1 when all income is in hands of one ...
- 1,612
18
votes
2
answers
1k
views
An Entropy Inequality (generalized)
Let $X,Y$ be probability measures on $\{1,2,\dots,n\}$. For $0\le \alpha \le 1$, set $K=\sum_i X(i)^\alpha Y(i)^{1-\alpha}$ so that $Z:=\frac{1}{K}X^\alpha Y^{1-\alpha}$ is also a probability measure ...
- 351
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
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
9
votes
2
answers
1k
views
Expected centered entropy of the binomial distribution
In short, the function I am interested in is the following:
$$I_n(p) = \sum_{k=0}^n \binom{n}{k} p^k (1-p)^{n-k} \left[h(p) - h\left(\tfrac{k}{n}\right)\right],$$
where $h(x) \triangleq -x \log x - (1-...
- 733
8
votes
2
answers
540
views
Maximum entropy priors in infinite dimensional spaces
Is there an extension of maximum entropy probability distributions for function spaces?
For $\mathbb{R}^n$ and discrete spaces, there is much literature about this problem under names such as "non-...
- 1,160
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
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
6
votes
2
answers
1k
views
Do binary symmetric channels maximize mutual information?
Consider the following setup: $(X, Y)$ is a doubly symmetric binary source with parameter $0 < p < 1/2$, i.e., $X \sim \text{Bernoulli}(1/2)$, $Z \sim \text{Bernoulli}(p)$ and $Y = X \oplus Z$. ...
6
votes
0
answers
342
views
Maximizing Renyi entropy for a certain channel
The channel under consideration is $T = A + B$, where $A$ and $B$ take on values in $\{0, 1\}$ according to a probability mass function. Let (joint) random vector $(A_1, A_2,\ldots, A_n)$ be denoted ...
5
votes
1
answer
778
views
Calculate channel capacity of general channel under constraint
Given a conditional distribution $P_{Y\mid X}$ I'd like to find the prior distribution $P_X$ that maximizes the mutual information $I(X;Y)$ with $P_Y(y)=\int P_{Y\mid X}(y\mid x)P_X(x) \, \text{d}x$ (...
- 59
4
votes
3
answers
1k
views
Incremental entropy computation
After a quick internet search I found no method for incremental entropy computation.
Question 1
Let $\{x_i\}_{i=1}^n$ and $\{x_i\}_{i=1+n}^{n+m}$ be two samples and let $S_i^j:=\sum_{k=i}^j x_k$. ...
- 161
4
votes
1
answer
555
views
Information theory from negative probability
Szekely provides a convincing argument of negative probability here:
http://www.wilmott.com/pdfs/100609_gjs.pdf
What does a reformulation of classical information theory built from negative ...
- 13.9k
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
4
votes
0
answers
573
views
An inequality involving conditional variance and its connection to information theory
Given absolutely continuous random variables $(X, Y)$ with joint distribution $P_{XY}$, we construct $Z:=\sqrt{\gamma} Y+N_\mathsf{G}$ where $N_\mathsf{G}\sim N(0, 1)$ and is independent of $(X,Y)$ ...
- 1,109
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
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
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
3
votes
1
answer
517
views
Simple reason that a mathematician cannot do better than random when guessing contents of a box?
I have a question about the finite analog of the puzzle proposed here involving mathematicians guessing the contents of boxes.
Specifically, suppose there are $k$ unopened boxes each containing a ...
- 271
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
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
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
1
answer
294
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
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
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
306
views
About Renyi entropy
If one is given a joint probability distribution over a finite set of discrete random variables then I guess there a notion of $\alpha-$Renyi entropy defined for it as $S_\alpha (X_1,..,X_n) = \frac{...
- 2,246
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
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
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 ...
1
vote
4
answers
3k
views
Differential Entropy of Random Signal
Prove that the Normal (Gaussian) Distribution with a given Variance $ {\sigma}^{2} $ maximizes the Differential Entropy among all distributions with defined and finite 1st Moment and Variance which ...
- 115
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
1
vote
1
answer
304
views
Entropy on a draw from a random distribution.
Suppose I am attempting to calculate the entropy of a continuous, normally distributed random variable $X$, from the distribution $\mathcal{N}(\mu, \sigma)$. This is easy to to do - I just calculate
$...
- 229
1
vote
1
answer
135
views
order of convergence of the conditional entropy (2)
Let $X_n$ be a random variable distributed on $A_n:=\{1, \ldots, n\}$ and $g_n\colon A_n \to A_n$ such that $\Pr\big(X_n \neq g_n(X_n)\big) \to 0$. Putting $Y_n=g_n(X_n)$, then by Fano's inequality $$\...
- 2,560
1
vote
1
answer
1k
views
Coupon Collector Problem for Non-Uniform Coupons: Bound on the number of missed Coupons
Suppose $\mathcal B=\{1,2,..,b\}$ is the set of all possible coupons, with $\mathbf p = ( p_1,p_2,...,p_b)$ assigning the probability of occurrence for all coupons in $\mathcal B$.
The "traditional ...
- 27
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
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
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