All Questions
73 questions
40
votes
5
answers
5k
views
"Entropy" proof of Brunn-Minkowski Inequality?
I read in an information theory textbook the Brunn-Minkowski inequality follows from the Entropy Power inequality.
The first one says that if $A,B$ are convex polygons in $\mathbb{R}^d$, then
$$ m(...
- 22.8k
20
votes
1
answer
4k
views
Using Fisher Information to bound KL divergence
Is it possible to use Fisher Information at p to get a useful upper bound on KL(q,p)?
KL(q,p) is known as Kullback-Liebler divergence and is defined for discrete distributions over k outcomes as ...
- 2,242
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
16
votes
1
answer
397
views
Examples of problems in statistics accessible only using information geometry
I am just curious if there are some examples of problems in statistics that are indeed accessible using information geometry while proofs completely avoiding geometry are unknown. In other words, ...
- 269
15
votes
2
answers
3k
views
Bounding sum of multinomial coefficients by highest entropy one
When does the following hold?
$$\sum_{(i_1,\ldots,i_k)\in E}
\frac{n!}{i_1! \ldots i_k!}
\le \exp(n H^*)$$
where $H^*=\max_{(i_1,\ldots,i_k)\in E} -(\frac{i_1}{n}\log \frac{i_1}{n}+\ldots +\frac{...
14
votes
1
answer
3k
views
How is the "conformal prediction" conformal?
The question is clarified by Prof.V.Vovk. See his answer below for discussion.
Recently, early works of Gammerman, Vanpnik and Vovk[4] are rediscovered by Wasserman et.al[1] and proposed it as a ...
- 8,071
10
votes
2
answers
2k
views
Convergence of an empirical distribution w.r.t. the Hellinger distance
Let $P$ be a probability distribution on a finite set $\mathcal{X}$ and let $X_1, X_2, \ldots, X_n$ be drawn i.i.d. according to $P$. Define the empirical distribution:
$\hat{P_n}(x) = \frac{1}{n} \...
- 165
9
votes
1
answer
385
views
A Generalized Version of Maximal Correlation and Hypercontractivity of Conditional Expectation Operator
Given a pair of random variables $(X,Y)$ over a product space $\mathcal{X}\times \mathcal{Y}$, the maximal correlation coefficient is defined as
$$\rho_2(X;Y):=\sup\frac{\mathbb{E}[f(X)g(Y)]}{||f||_2||...
- 1,109
8
votes
2
answers
4k
views
Lower bounds on Kullback-Leibler divergence
This was originally a question on Cross Validated.
Are there any (nontrivial) lower bounds on the Kullback-Leibler divergence $KL(f\Vert g)$ between two measures / densities?
Informally, I am ...
- 710
8
votes
1
answer
3k
views
An Inequality of KL Divergence
Given two probability distributions $P$ and $Q$ defined over a finite set $\mathcal{X}$, one can define the KL divergence between $P$ and $Q$ as
$$D(P||Q):=\sum_{x\in \mathcal{X}}P(x)\log\frac{P(x)}{...
- 1,109
7
votes
1
answer
1k
views
reverse KL-divergence: Bregman or not?
I am having a little trouble getting my head around the two "directions" of the Kullback-Leibler divergence:
Definition (Kullback-Leibler divergence) For discrete probability distributions $...
- 101
7
votes
2
answers
2k
views
What is the maximum entropy distribution on the natural numbers?
On the reals $\mathbb{R}$, the maximum entropy distribution with a given mean and variance is the Gaussian distribution.
Let $\mu, \sigma > 0$. What is the maximum entropy distribution on the ...
- 171
7
votes
1
answer
231
views
Relation between the two possible KL divergences of two distributions
Given that I know $$D\left(P\parallel Q\right)<\alpha,$$ can I say anything about $D\left(Q\parallel P\right)$ in terms of an upper bound on it?
Also, given this upper bound on $D\left(P\parallel ...
- 503
6
votes
1
answer
2k
views
Minimizing KL divergence: the asymmetry, when will the solution be the same?
The KL divergence between two distribution $p$ and $q$ is defined as
$$
D( q \| p)\int q(x)\log \frac{q(x)}{p(x)} dx
$$
and is known to be asymmetry: $D(q\|p)\neq D(p\|q)$.
If we fix $p$ and try to ...
- 185
6
votes
2
answers
344
views
Entropy & difference between max and min values of probability mass
Let $X$ be a random variable with probability mass function $p(x) = \mathbb{P}[X = x]$.
I know entropy $H(X)$ of $X$ measures the uncertainty of $X$ and
a large value of $H(X)$ means $p(x)$ is nearly ...
- 163
6
votes
1
answer
527
views
Can information be extracted more precisely using more random trials?
Write $n$ iid draws of $(x,y)$ as $(x^n, y^n)$. Fix $R\in (0,H(x))$. What is the min of $n^{-1}H(y^n|f(x^n))$ over maps $f$ with range $\lbrace 1,\dots,\exp nR\}$, taking $n\to \infty$?
6
votes
0
answers
578
views
Maximal Correlation versus Correlation Coefficient When one RV is Gaussian
Let a pair of random variables $(X,Y)$ be continuous random variables (i.e., they both have density with respect to Lebesgue measure) with joint distribution $P_{XY}$. The maximal correlation $\rho_m(...
- 1,109
5
votes
2
answers
1k
views
Inequality involving probability measures [closed]
I have been working on a problem(alternate minimization) where I want to establish an inequality in which I am stuck.
An $\alpha$- parameterized version of the divergence(Kullback-Leibler) takes the ...
- 779
5
votes
1
answer
150
views
Kullback–Leibler chains
The following question was asked and then deleted by the post author:
Let $P$ and $Q$ be two probability distributions defined over the same space, with $KL(P \parallel Q) < \infty$. For $\epsilon ...
- 128k
5
votes
1
answer
497
views
Size of KL-divergence neighbourhoods
I am new here. I was reading another
post
here and this got me wondering what can be said about the size of the following kl divergence neighborhoods.
Consider these two kl-divergence neighbourhood ...
- 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
203
views
Can samples be compressed?
The Fisher information of a random variable $Y$ about a parameter $\theta$ upon which the probability of $Y$ depends is:
$\mathcal{I}_Y(\theta)= -E\left[\left.\strut \frac{\partial^2}{\partial \theta^...
- 22.1k
4
votes
1
answer
312
views
Given three distributions p, q and h. If KL(p||q) is large enough and KL(q||h) is small enough, does there exist a number N such that KL(p||h)>N?)
Given three distributions $p, q$ and $h$, assume we know that the Kullback-Leibler divergence obeys
$KL(p\Vert q)$ is large enough, say $KL(p\Vert q) > M$ where $M$ is large enough, and
$KL(q\Vert ...
- 77
4
votes
1
answer
361
views
Information monotonicity of divergence => function of $f$-divergence
It is well-known that $f$-divergences defined on $\mathcal P(\mathcal X)$ where $\mathcal X$ is a measure space with $\sigma$-algebra $\mathcal B$ satisfy the property of information monotonicity:
...
- 203
4
votes
0
answers
144
views
Exponential families closed under affine transformations
Let $(\Omega,\Sigma,\mu)$ be a probability space and let $\mathcal{M}$ be an exponential family of probability distributions for $\mu$ of the following form: There are $\varphi_1,\dots,\varphi_n:\...
- 5,405
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
4
votes
1
answer
839
views
A balls into bins problem with combinatorial constraints
We are given $m$ balls and $n$ bins, with $m \ge n$. Each bin can contain at most $c$ balls (we assume that $c$ is an even integer). In a sequential fashion, at each time step, one ball is placed into ...
- 1,677
3
votes
2
answers
1k
views
Tightness of probabilty distributions
Let $\mathcal{P}(\mathbb{N})$ be the set of all probability mass functions on $\mathbb{N}=\{1,2,\dots \}$. Let $E$ be a closed(with respect to pointwise convergence, or equivalently the total ...
- 779
3
votes
1
answer
167
views
Maximal correlation and independence
Let $X$ and $Y$ be random variables. Then the maximal correlation $\rho_m(X;Y)$ is defined as
$$ \rho_m (X;Y) := \max_{(f(X),g(Y))\in S} \mathbb{E} [f(X)g(Y)] $$
where $S$ is the collection of pairs ...
- 33
3
votes
1
answer
196
views
Uniform Convergence for Vectors
$\textbf{Problem statement:}$
Let $\mathcal H:\mathcal X \rightarrow \{0,1\}$ be a class of Boolean functions for $\mathcal X \subset \mathbb R^n$, and let the VC Dimension of $\mathcal H$ be $VC_{...
- 197
3
votes
1
answer
306
views
Mutual information decrease with coarse-graining
Let $X,A,Y,B,C,D$ be random binary variables. $D$ is independent from $X,A,C$ and $C$ is independent from $Y,B,D$.
Is it true that:
If $I(Y:B|D=0)\leq \epsilon$ then $I(X\oplus Y:A\oplus B|C=0,D=0)\...
- 585
3
votes
1
answer
673
views
convex combination of two covariance estimates
I am interested in covaraince matrix estimation. In brief: I have two estimates of the covariance matrix, and now I want to form a bona fide convex combination of the two.
Background: I have studied ...
3
votes
0
answers
80
views
Seeking strong bounds on KL-divergence and martingales for a hypothesis-testing inequality
Let's say we have a finite set $\mathcal{O}$ of observations, and let $\mathcal{C}(\Delta\mathcal{O})$ denote the space of closed convex sets of probability distributions.
We have two hypotheses which ...
- 353
3
votes
0
answers
93
views
Asymptotic approximation of Fisher information matrix for small Gaussian perturbation
Let
$$
X=Y/a+b+\epsilon Z,
$$
where $Y\sim\operatorname{Poisson}(\lambda)$ and $Z\sim\mathcal N(0,1)$ are independent. Also define $\theta=(\lambda,a,b,\epsilon)$. The Fisher information matrix
$$
...
3
votes
1
answer
355
views
Upper bounding the start of a distribution's CDF, given bounds on first moments
Take nonnegative random variables $X$ whose first $K$ moments have bounds:
$\mu^k\leq E[X^k]\leq c\mu^k$ for each $k=1,\dots,K$.
In this case what is an upper bound for $P(X\leq O(\mu))$?
I am ...
3
votes
0
answers
178
views
Partitioning the coupons collected in the classical coupon collector's problem
Suppose that there is an urn containing $n$ different coupons, from which $m$ coupons are being collected, equally likely, with replacement.
Let $C(m)$ be the whole set of the $m$ collected coupons. ...
- 1,677
3
votes
0
answers
158
views
How are these two multi-armed bandit problems similar?
I am reading the multi-armed bandit survey by Bubeck and Bianchi. This question is for the lower bound section (2.3) of the survey.
Let us define Kullback-Leibler divergence $kl(p, q) = p \log \frac{p}...
- 145
3
votes
0
answers
698
views
How does Jensen Shannon divergence and KL divergence correlate?
I am wondering if there is way to derive the correlation between Jensen Shannon divergence and KL divergence for two distributions: P and Q, in order to show that if JSD(P,Q) decreases, KLD(P,Q) ...
- 31
3
votes
0
answers
494
views
Maximization of a total variation distance subject to another total variation distance in Markov chain
Suppose two dependent random variables $X$ and $V$ from finite alphabets $\mathcal{V}$ and $\mathcal{X}$ with known joint and marginal distributions are given. Let $P_{XV}$ and $P_X$ and $P_V$ are the ...
- 1,109
3
votes
0
answers
108
views
"Soft" Voronoi cells or statistical criterias
It is probably some basic statistics question, but...
Informally 1: How to choose "criteria", such that it will guarantee that error decision probability is less than "epsilon", and maximize ...
- 24.9k
3
votes
0
answers
213
views
Find a minimum entropy code for a simple gibbs random field.
Just to make precise what I am talking about, I will include the definition of a minimum entropy code. I will then define the precise markov random field I am asking about.
In the rest of this ...
- 131
3
votes
0
answers
125
views
Is a parametric family which is universally consistent for multiple quantiles impossible?
Suppose I am dead-set on using Bayesian inference on independent and identically distributed data, but I'm lazy and insist on using a parametric likelihood function come what may. I'd be reassured to ...
- 2,791
3
votes
0
answers
143
views
finding rank-3 tensors compatible with a rank-2 tensor projection
I am interested in the following problem: Consider a rank-3 symmetric tensor $\boldsymbol{\sigma}$ with $\sigma_{ijk}$ where $\sigma_{ijk}$ can be 0 or 1, and the symmetry is with respect to any ...
- 41
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
790
views
Is there some generalization of the "Maximum Coverage Problem" for information in random variables?
Say I have a set $X=x_1,x_2,\ldots,x_n$ of random variables, and would like to find a size $k\leq|X|$ subset that contains as much information as possible. This is complicated because the variables ...
- 155
2
votes
1
answer
415
views
Bounding Kullback-Leibler
Suppose we have a probability distribution $P$ on a finite set $S$. We draw $N$ i.i.d. samples according to $P$ and use these samples to define an empirical distribution $R$. We measure the Kullback-...
- 3,979
2
votes
1
answer
1k
views
Derivative of a random process
Consider $w(t)$ as Guassian random process, with $w(t)$ being $\mathcal{N}(\mu,\sigma)$ and i.i.d for all t.
I consider applying a (stochastic)derivative operation to the random process. What is the ...
- 151
2
votes
2
answers
624
views
Measuring the independence between the components of a stochastic process
In a context of blind source separation (e.g. you want to extract the voice of a singer from a song), many approaches consist in maximizing the independence between the components of a certain ...
- 103
2
votes
1
answer
269
views
Distribution-free statistics on compact Lie groups
(Cross-listed from the math stackexchange)
Let $(X_i)_{i=1}^n$ be iid random variables with joint cdf $F$. Recall that the empirical distribution function is:
$$
F_n(x) = \frac{1}{n} \sum_{i=1}^n \...
- 5,759
2
votes
1
answer
250
views
An Inequality Regarding the Squared Conditional Variance
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