All Questions
Tagged with inequalities it.information-theory
38 questions
0
votes
0
answers
51
views
Upper bound on expectation of a convolution
Given probability densities $f, g\in L^p(\mathbb{R}^3), \ \forall p\geq 1$, with the same first and second moments
\begin{align} & \int_{\mathbb{R}^3} v f(v)\,dv = \int_{\mathbb{R}^3} v g(v)\,dv, \...
- 43
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
138
views
How to lower bound the absolute value of the difference of two Kullback-Leibler divergences given the constrains below?
Given that $\min (D[p_1||p_3],D[p_2||p_4])=a$, how to find a lower bound of the difference $\left \vert D[p_1\parallel p_2]-D[p_3\parallel p_4] \right\vert$ with respect to $a$? If the condition is ...
- 31
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
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
2
votes
0
answers
118
views
Inequality for log-likelihood ratio
Let $ p, q $ be two probability densities on $ [0,1] $, strictly positive over $ (0,1) $. Let $ P $ be the cumulative function of $ p $, i.e., $ P(x) = \int_0^x p(x') \, \mathrm{d}x' $, $ x \in [0,1] $...
- 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
1
vote
1
answer
92
views
Lower bound $L_{1}$-metric with $L_{2}$-metric for bounded pdfs, on common support
Setup
To clarify, let constants $0 < a < b < \infty$, and $p \in \mathbb{N}$ be fixed. Further let $B \subset \mathbb{R}^{p}$ be a fixed compact support. We then define the space of bounded (...
- 133
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
1
vote
1
answer
296
views
Lower bound for KL divergence of bounded densities and $L_{2}$ metric
I am currently reading "Smoothing of Multivariate Data" by Klemela. It contains Lemma 11.6, which upper and lower bounds the KL-divergence of two densities in terms of the $L_{2}$-metric. ...
- 133
1
vote
1
answer
224
views
A question about mutual information
Let $A$ and $B$ be two, possibly dependent, random variables, and let $X$ be a random variable independent of $(A,B)$. For simplicity, let's concern ourselves with discrete random variables. Is the ...
- 63
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
5
votes
4
answers
4k
views
Is there an inequality relation between KL-divergence and $L_2$ norm?
According to the Pinsker inequality, we have the following inequality:
\begin{equation}
\delta_{TV} (p, q)^2 \leq \frac{1}{2} D_{KL}(p,q),
\end{equation}
where $\delta_{TV} (\cdot, \cdot)$ and $D_{KL}...
- 175
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
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
4
votes
1
answer
358
views
Bound for type of correlation measure
Assume you have a finite, discrete probability distribution for a joint random variable and such that $P(X=i,Y=j) = p_{i,j}$ for $i \in \{1, \dots, |X|\},j \in \{1, \dots, |Y|\}$. The marginal ...
- 51
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
0
votes
0
answers
250
views
Can we make two random variables independent at a low cost?
Let $X$ and $Y$ be two discrete random variables with joint probability mass function $p(x,y)$ such that
$$\|p(x,y)-p(x)p(y)\|_1=\sum_{x\in\mathcal{X},y\in\mathcal{Y}}|p(x,y)-p(x)p(y)|\leq\epsilon$$
...
- 287
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
3
votes
1
answer
226
views
Finding a short proof for a certain information theoretic inequality
The following information theoretic inequality is needed in my work.
Let $n, m, n_1, n_2, \dots, n_k \in \mathbb{Z}^+$ such that $m < n = n_1 + n_2 + \dots + n_k$. I would like to prove that with ...
- 1,551
1
vote
2
answers
275
views
A corollary of Gibbs' inequality
Gibbs' inequality is equivalent to:
\begin{equation}
\sum_{i} \ln q_i^{p_i}-\ln p_i^{p_i} \leq 0
\end{equation}
where $p_i,q_i \in [0,1]$ and $\sum_i p_i = \sum_i q_i=1$.
Now, a friend of mine ...
- 3,871
3
votes
1
answer
330
views
Does this probability distance metric have an official name?
Let us define a distance metric between two joint probability math functions $p(x,y)$ and $q(x,y)$ as in the following
\begin{align}
\sum_{y}\sqrt{\sum_{x}p(x)\left(p(y|x)-q(y|x)\right)^2}.
\end{...
- 287
3
votes
1
answer
370
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\...
- 83
2
votes
1
answer
280
views
How much can KL divergence decrease by diluting the reference distribution
Let $\Omega$ be a countable set and $\mu,\nu\colon\Omega\to[0,1]$ be distributions on $\Omega$, that is we have $\sum_{x\in\Omega}\mu(x)=1$ and likewise for $\nu$. The Kullback-Leibler divergence of $\...
- 83
4
votes
1
answer
346
views
Sharpened Pinsker inequality for special case
Let $B(p)$ denote the Bernoulli distribution over $\{0,1\}$ and $B(p)^n$ the corresponding product distribution over $\{0,1\}^n$. For $n>1$ and $0<x<1$, define
$$P_n(x):=B(\frac12+\frac x2)^n$...
- 6,541
8
votes
2
answers
486
views
concentration inequality for entropy from sample
Consider a measure $\mu$ on a finite set, and let $x_1, \ldots, x_n$ be i.i.d samples from $\mu$. Then the expression $S_n = -\frac{1}{n} \sum_{i=1}^n \log \mu(x_i)$ converges by a.s. to the entropy $...
- 83
3
votes
0
answers
234
views
Will relative entropy increase with majorization?
Suppose that three probability distributions have the relation $P\succ Q\succ R$, then do the following relations between their relative entropy valid? (assume that $p_1\geq p_2\geq\cdots \geq p_n$ ...
- 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
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 ...
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
16
votes
7
answers
6k
views
Understanding Gibbs's inequality
Short version
Gibbs's inequality is a simple inequality for real numbers, usually
understood information-theoretically. In the jargon, it states that
for two probability measures on a finite set, ...
- 27.7k
5
votes
1
answer
790
views
Upper bound on joint Renyi entropy
Renyi entropy of a random pair $(X,Y)$ with probability distribution $p_{X,Y}$ is defined by
\begin{equation}
H_\alpha(X,Y) = \frac{1}{1-\alpha}\log\sum_{x,y} p_{X,Y}(x,y)^\alpha.
\end{equation}
...
- 61
12
votes
2
answers
2k
views
Proving a messy inequality
EDIT:
After much work I was able to reduce the inequality to a single variable function which I need to show is non-positive. That function is (for $0\leq p\leq\frac{1}{2}$)
$$\frac{p^2(\log(p))^2 - (...
- 1,034
4
votes
1
answer
1k
views
Generalizing inequality relating Euclidean distance & Frobenius norm to Bregman divergences such as relative entropy & von Neumann divergence
Motivation- A Special Case
Supposing $A,B\in\mathbb{S}^{m\times m}$ are symmetric positive semi-definite (SPD) matrices and $\mathbf{x}\in\mathbb{R}^m$ is a unit vector where $\|\mathbf{x}\|=1$, we ...
- 607
9
votes
2
answers
462
views
Entropy conjecture for distributions over $\mathbb{Z}_n$
Suppose we have two independent random variables $X$ (with distribution $p_X$) and $Y$ (with distribution $p_Y$) which take values in the cyclic group $\mathbb{Z}_n$. Let $Z = X +Y$, where the ...
- 1,034
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
2
votes
3
answers
593
views
l^p space inequality related to compressed sensing
I'm trying to read Donoho's 2004 paper Compressed Sensing and am having trouble with a supposedly trivial statement (equation 1.2 on page 3).
He makes the sparsity assumption on $\theta \in \mathbb{R}...
- 198