All Questions
73 questions
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, ...
- 6,001
0
votes
0
answers
85
views
When is a family of distributions "closed" with respect to minimal sufficient statistics?
As in the title, I am interested in understanding how to express the idea that a parametric family of distribution is "closed" with respect to minimal sufficient statistics. Before giving ...
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
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/...
2
votes
0
answers
92
views
Construct a Bregman divergence from Wasserstein distance
I was wondering whether one has studied the Bregman divergence arising from a squared Wasserstein distance.
More precisely, let $\Omega\subset \mathbb{R}^d$ be a compact set and $c\in \Omega\times \...
- 503
0
votes
1
answer
107
views
What's the lower bound for this quantity?
Suppose $p$ is a discrete distribution with $n$ values and the random variable $x$ satisfies $\mathbb{E}_p[x] = 0$ and $|x| < \infty$. Given $\alpha \in (0,1)$, does there exist a lower bound for ...
- 128k
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 ...
- 6,367
0
votes
0
answers
52
views
Classifier-specific lower bounds on the misclassification rate in binary classification
Consider a binary classification problem for $(X,Y)$, and let $\hat{f}$ be a proposed classifier. We wish to bound the misclassification rate $P(\hat{f}(X)\ne Y)$. There are many known lower bounds on ...
CommunityBot
- 1
2
votes
0
answers
68
views
What is an efficient non-adaptive group testing scheme if the number of defectives, $d$, grows proportionally to the number of items, $n$?
Suppose that for some $p \in \left(0, 1\right)$ and some $n \in \mathbb{N}$, we have $n$ independent Bernoulli random variables, $X_{1}, X_{2}, \dots, X_{n}$, each with mean $p$. We shall call $X_{1}, ...
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-...
- 2,183
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 ...
- 2,600
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
$$
...
1
vote
1
answer
93
views
An inequality relating $\ell_1$ distance of input and output of a Markov krnel
Let $K$ be a Markov kernel from $\mathcal{X}$ to $\mathcal{Y}$, i.e., $K(\cdot|x)$ is a probability measure on $\mathcal{Y}$ for all $x\in \mathcal{X}$.
Let $\mu$ and $\nu$ be two probability measures ...
- 17k
1
vote
0
answers
48
views
Sample complexity of estimating a doubly stochastic matrix
Let $P\in\mathbb{R}^{n\times n}$ be a doubly-stochastic matrix. That is:
$$P(x,y)\geq 0,\quad \sum_xP(x,y)=1,\quad \sum_yP(x,y)=1.$$
I would like to know if lower and upper bounds on the sample ...
- 111
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$?
- 716
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 ...
- 128k
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} \...
- 35.5k
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:\...
- 6,367
1
vote
1
answer
105
views
What is the distribution of a Cartesian power of a collection of iid uniform points? (renewed)
The following question was asked recently at https://mathoverflow.net/questions/326631/what-is-the-distribution-of-a-cartesian-power-of-a-collection-of-iid-uniform-poi :
Take a rectangle with ...
CommunityBot
- 1
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(...
- 716
2
votes
1
answer
199
views
Do enough permutations of an initial set probably cover most permutations?
Fix $\alpha, \epsilon \in(0,1)$. Take $(S_n)_n$ to be any sequence of sets with each $S_n$ containing $ \lceil (n!)^\alpha\rceil$ permutations of $n$ elements. Also build another sequence of sets $(...
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
1
vote
1
answer
135
views
KL-divergence and sub-$\sigma$-algebras
I am trying to understand if the following claim is true:
Let $P$, $Q$ be probability measures on $\mathcal{X}$. For any $\sigma$-algebra $\mathcal{G}$, with countably many atoms (sets with $\...
- 128k
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 $...
- 128k
0
votes
0
answers
171
views
A basic property of maximal correlation
Let $𝑋$ and $𝑌$ be random variables. Then the maximal correlation $\rho_{m}(X;Y)$ is defined as:
$$\rho_{m}(X;Y):=\max_{f,g}\mathbb{E}[f(X)g(Y)],$$
where the maximization is taken over real-valued ...
- 11
1
vote
0
answers
438
views
Chain rule for maximal correlation
Let a pair of random variables $(X,Y)$ be defined over finite alphabet $\mathcal{X}\times \mathcal{Y}$ with joint distribution $P_{XY}$. The maximal correlation $\rho(X;Y)$ between $X$ and $Y$ is ...
- 11
1
vote
0
answers
65
views
Normalizing constants preserve metric entropy
Suppose $\mathcal{F}=\left\{f\in L^2([a,b]): 0<\underline{c}\leq f\leq\overline{c} \right\}$. Consider the following transformation
$$\tilde{\mathcal{F}} := \left\{\frac{f}{\int f d\mu}: f\in \...
- 11
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:
...
- 695
1
vote
0
answers
212
views
A new notion of probability coupling
Let $X$ and $Y$ be two discrete random variables distributed according to $\mu$ and $\nu$, respectively. Consider the following optimization problems
$$\inf_{\pi\in \Pi(\mu, \nu)}\Pr(X\neq Y),$$
...
- 1,109
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 ...
CommunityBot
- 1
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 ...
- 128k
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 ...
- 128k
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
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
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_{...
- 63.9k
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 ...
- 128k
1
vote
1
answer
514
views
Showing non-attainment of supremum
This is just an extension of my previous question Tightness of probabilty distributions
Let $\mathcal{P}(\mathbb{N})$ be the set of all PMF's on $\mathbb{N}=\{1,2,\dots \}$. Let $E$ be a convex ...
- 60.5k
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 ...
CommunityBot
- 1
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
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{...
- 1,228
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 ...
- 128k
1
vote
1
answer
146
views
Conformal prediction for the case of single tailed events
I'll start with a motivating example and only then proceed to the question.
Consider a list of total packages of milk that were purchased on 9 consecutive days on a given store,
$z_1,\ldots,z_9 = 1,...
2
votes
0
answers
149
views
Min Max Equality in Information Theory
Let $\mathcal{Y}$ and $\mathcal{X}$ be finite sets and let $Q_Y$ be a fixed probability mass function on $\mathcal{Y}$. Also, let $P_{X | Y}$ be some fixed conditional distribution on $\mathcal{X} \...
- 8,071
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 ...
- 12.7k
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}...
- 8,071
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 \...
CommunityBot
- 1
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) ...
CommunityBot
- 1
2
votes
1
answer
160
views
Do product distributions (or graph products) eventually cluster as more products are taken?
Say we have a joint distribution on a finite alphabet $\mathcal{X}\times \mathcal{Y}$. It could be a communication link where we want to send a random message $X$ over a channel, but it gets garbled ...
CommunityBot
- 1
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^...
- 5,971
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 ...
CommunityBot
- 1