Questions tagged [it.information-theory]

Theoretical and experimental aspects of information theory and coding theory. This tag covers but is not limited to following branches: information theory, information geometry, optimal transportation theory, coding theory.

Filter by
Sorted by
Tagged with
1 vote
0 answers
25 views

Reference request for "time-reversal invariance" of conditional information entropy

Given a finite sample $S$ of symbols that can be approximated by both unconditional and conditional processes $P(X), P(X|Y)$. One can always define the "reverse" process, ie: given a symbol ...
psubodiosa's user avatar
0 votes
0 answers
16 views

A network to transform/predict one probability distribution to another

I have a random variable of a particular density (e.g., normal), and a known probability distribution (e.g., mixture Gaussian). I used a simple KL measure to predict/transform one another. Now I need ...
user524691's user avatar
0 votes
0 answers
118 views

Optimal strategy of modified Mastermind game

The following game is a modified version of the popular game Mastermind described here in which you are only given information about the total correct guesses you have made, and nothing about how many ...
wjmccann's user avatar
  • 315
2 votes
0 answers
96 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 ...
MatrixGeek1234's user avatar
0 votes
1 answer
73 views

Will the KL divergence between two distributions decrease after passing the fixed channel?

Suppose there are two continuous distributions whose pdfs are $p_1$ and $p_2$, defined on a common support $\mathcal{X}$. Suppose that there is a conditional pdf (the channel) $M:\mathcal{X}\times \...
jkfds's user avatar
  • 9
2 votes
0 answers
77 views

Joint lower semicontinuity of the Rényi divergence in all three arguments

Let $X$ be a standard Borel space (I'm already interested in the case where $X$ is finite, i.e., $X=\lbrace 1,\cdots,n\rbrace$). Let $P,Q$ be probability measures on $X$ such that $P\ll Q$. Then the ...
Lau's user avatar
  • 729
1 vote
1 answer
147 views
+100

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 ...
truebaran's user avatar
  • 9,140
2 votes
0 answers
64 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 \...
John's user avatar
  • 483
3 votes
1 answer
109 views

Binary codes with upper and lower bound on pairwise distance

The Gilbert-Varshamov bound provides a lower bound for codes of length $n$ with minimum pairwise distance (say $\frac{n}8$). If we wish for the codes to also have pairwise distances bounded above (say ...
Stephen Jiang's user avatar
0 votes
1 answer
101 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 ...
Jiacai Liu's user avatar
1 vote
0 answers
110 views

Sudden drop in complexity class due to the more general correlations

Recently I was asking about the impact of the groundbreaking result MIP*=RE on logic and proof theory (see this discussion). Surprising as it is I got confused with the following: MIP* is a ,,quantum''...
truebaran's user avatar
  • 9,140
2 votes
1 answer
250 views

Does this KL divergence inequality hold?

Suppose $p$ and $q$ are two discrete distributions. Given a positive constant $\beta\in(0,1)$, we create a new discrete distribution $y$ such that $$ \frac{y\left( x \right)}{p\left( x \right)}=\frac{\...
Jiacai Liu's user avatar
1 vote
0 answers
101 views

Generalization of error-correcting codes

If you have a binary single-error correcting code with n-bit codewords, then it is the case that taking only a fixed n-1 out of the n bits gives an “approximate” code with the property that, for any ...
Joe Shipman's user avatar
2 votes
1 answer
131 views

Estimating means of multiple Gaussians

Let's say we have two Gaussian distributions $\mathcal{N}(\mu_1, \sigma^2I_d)$ and $\mathcal{N}(\mu_2, \sigma^2I_d)$. We are trying to get estimators $\hat \mu_1, \hat \mu_2$ to minimize the following ...
Kumar Kshitij Patel's user avatar
0 votes
0 answers
72 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 ...
Mike Battaglia's user avatar
3 votes
2 answers
315 views

A general inequality for KL divergence of functions of variables

The question concerns a very general setting and a very general inequality about KL divergence. I'm writing this thread to verify whether my intuition is correct. Let $E_1, E_2$ be two measurable ...
Daniel Goc's user avatar
0 votes
0 answers
46 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 ...
tim523's user avatar
  • 13
0 votes
0 answers
46 views

Sharpened versions of the Fisher information inequality?

Let $X, Y$ be two independent random vectors in $\mathbb{R}^d$. In the paper [1, see ineq. (11)], the following convolution inequality is proven for the Fisher information: $$ I(X + Y) \preceq \Big(I(...
Drew Brady's user avatar
2 votes
0 answers
67 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}, ...
Matthew Barber's user avatar
4 votes
1 answer
245 views

Does a subset with small cardinality represent the whole set?

Assume that we have heavy-tailed distribution $F(x)$ such that \begin{align} F(x)=\mathbb{P}[X\geq x]=x^{-0.5}. \end{align} Then, we produce $N$ independent samples $X_1,X_2,\ldots,X_N$ from this ...
Math_Y's user avatar
  • 311
3 votes
1 answer
192 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 ...
aleph's user avatar
  • 503
3 votes
1 answer
93 views

Question about equivalence of two expressions for the Quantum Fourier transformation

The Quantum Fourier transformation on $n$ qubits is just the discrete Fourier transformation, $$ |j \rangle \mapsto \frac 1 {\sqrt 2^n}\sum_{k=0}^{2^n-1}e^{2\pi ijk/2^n}|k\rangle. $$ In binary ...
Konrad Waldorf's user avatar
4 votes
2 answers
288 views

Effect of small change in probability distribution on error probability

Let $X$ be a random variable and $Y=f(X)$ where $f$ is a deterministic function. Moreover, assume that there exists a deterministic function $g(.)$ such that the following probability is small. \begin{...
Math_Y's user avatar
  • 311
2 votes
0 answers
98 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] $...
aleph's user avatar
  • 503
1 vote
1 answer
57 views

Upper bound of $I(Y; X_{1}, ..., X_{N})$ when we have $I(Y;X_{i}) < B$ for all $i$ $(1 \leq i \leq N)$

Let $I(Y;X)$ denote the mutual information between $Y$ and $X$. If we have $I(Y;X_{i}) < B$ for all $i \quad (1 \leq i \leq N)$, could we also get the upper-bound of $I(Y; X_{1}, X_{2}, ..., X_{N})...
Koukyosyumei's user avatar
0 votes
1 answer
107 views

Does the Plotkin bound mean that one can not achieve the Singleton bound asymptotically?

I am a little confused with the relationship between various bounds for error correcting codes. Does the Plotkin bound mean that one can not achieve the Singleton bound asymptotically? That is, is ...
liu_c_6's user avatar
  • 11
2 votes
1 answer
50 views

Bounding the difference of mutual information between input-output pairs

Let $X_1$ and $X_2$ be discrete random variables with distributions $p_{X_1}$ and $p_{X_2}$ such that the total variation distance between the two distributions is upper bounded by a constant $\delta$,...
Yuanxin Guo's user avatar
8 votes
1 answer
266 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|^...
Fei Cao's user avatar
  • 700
2 votes
1 answer
222 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-...
Bill Bradley's user avatar
  • 3,809
1 vote
0 answers
78 views

Min-sum belief propagation not working on a chain model with equal unary potentials

Given is a chain factor graph as presented in the image below with the following properties: Each node can take values 0 or 1 All unary potentials are equal (e.g. $U(a)=0$) for every node $a$ All ...
Uros Isakovic's user avatar
3 votes
1 answer
118 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{...
Math_Newbie's user avatar
1 vote
1 answer
108 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}&...
Math_Newbie's user avatar
3 votes
0 answers
86 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 $$ ...
Aaron Hendrickson's user avatar
1 vote
2 answers
186 views

Limit of a countable separable is countable separable?

Let $\rho$ be a positive trace class operator on $H\otimes H$, where $H$ is a separable Hilbert space (not necessarily finite dimensional). We say that $\rho$ is countable separable if $\rho=\sum_{i=...
Deva's user avatar
  • 11
2 votes
0 answers
45 views

Moduli spaces of 'generalized mutually unbiased bases'

Mutually unbiased bases in $\mathbb{C}^n$ with a chosen inner product are collections of orthonormal bases such that for each pair of orthonormal bases $e_i,f_i$, $i=1,\ldots,n$ we have $|\langle e_i, ...
Sergey Guminov's user avatar
0 votes
1 answer
207 views

Maximal mutual information between a continuous and a discrete random variables

Let $X\sim \mathcal{N}(\mu,\sigma^2)$ be a Gaussian random variable with random mean $\mu\sim {\sf Bernoulli}(p)$, i.e., $\mu=1$ with probability $p$ and $\mu=0$ with probability $1-p$. In other words,...
Augusto Santos's user avatar
2 votes
0 answers
80 views

Riemannian submanifolds of $2$-Wasserstein space

In the article "Wasserstein Geometry Of Gaussian Measures" by Asuka Takatsu the author shows how the space of d-dimensional Gaussian probability measures with non-singular covariance ...
Annie's user avatar
  • 71
3 votes
0 answers
64 views

Does this information theoretical thought experiment have a name or corresponding area of research?

I came up with the following thought experiment in my research in order to better understand the way Turing machines can transfer information through their tapes (the motivation is detailed below, isn'...
exfret's user avatar
  • 479
2 votes
1 answer
171 views

Can information theory characterise a (topological) space?

Consider an objective function f: $\mathbb{R}^n\rightarrow\mathbb{R}$, with a vector of variables $\theta$, i.e. $f(\theta)$, $\theta \in \mathbb{R}^n$. Depending on $f$, there can be interesting ...
Tessa van der Heiden's user avatar
1 vote
1 answer
85 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 ...
math-Student's user avatar
  • 1,109
0 votes
0 answers
105 views

Wasserstein compactness of sublevel sets of relative entropy

Let $\mathcal{P}({\mathbb{R}^d})$ denote the set of Borel probability measures on $\mathbb{R}^d$, and let $\pi \in \mathcal{P} (\mathbb{R}^d)$. It is known that the sets $\{ \mu \in \mathcal{P}(\...
pseudocydonia's user avatar
1 vote
1 answer
75 views

Does bounding mutual information restrict the defined meter?

Suppose $I(X;Y)$ denotes mutual information and on the other hand there is a relationship as follows. \begin{align} |p(y)-p(y|x)|<\delta p(y),\qquad\forall x,y. \end{align} Then we can say about ...
Math_Y's user avatar
  • 311
9 votes
4 answers
2k views

Computational complexity theoretic incompleteness: is that a thing?

Has anyone done research in an area that I have not heard of but that I want to call "Computational complexity theoretic incompleteness", which would mean not absolute incompleteness in the ...
Hank Igoe's user avatar
  • 193
8 votes
1 answer
289 views

Upper-bound on the Fisher-Rao distance between multivariate Gaussian measures by the KL-divergence

Let $\mu$ and $\nu$ be two multivariate Gaussian measures on $\mathbb{R}^d$ with non-singular covariance matrices. Can the Fisher-Rao distance $d(\mu,\nu)$ computed on the information manifold of non-...
Justin_other_PhD's user avatar
1 vote
1 answer
100 views

Support of Fourier transform of random characteristic function

Let $\chi_X:\{-1,1\}^n\to \{0,1\}$ be the characteristic function of a subset $X\subseteq \{-1,1\}^n$, which is randomly drawn from all subsets with exactly $k$ elements. Is the support of the Fourier ...
BGJ's user avatar
  • 439
1 vote
0 answers
46 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 ...
user134977's user avatar
1 vote
0 answers
57 views

Question about canonical divergence on a dually flat manifold

I am reading "Methods of Information geometry by Shun-Ichi-Amari" (chapter 3 sec 3.4) and I am stuck here, can someone explain or give any resource about how we got equation $(3.53)$?
Andyale's user avatar
  • 111
1 vote
1 answer
174 views

Invariance of mutual information under injective functions

Let $X\colon \Omega\to\mathcal X$ and $Y\colon \Omega\to \mathcal Y$ be two random variables. In M.S. Pinkser's Information and information stability of random variables and processes mutual ...
Paweł Czyż's user avatar
0 votes
1 answer
267 views

Dose density matrix with off-diagonal elements equal to zero has maximum von-Neumann entropy?

von-Neumann entropy I know von-Neumann entropy on density matrix $S=-{\rm Tr}(\rho \ln\rho)$ is similar to Shannon entropy $S=-\sum_i p_i\ln p_i$ in classical mechanics. And I want to get Bose-...
lbyshare's user avatar
0 votes
1 answer
130 views

Adding an independent variable does not increase conditional information

Given $P(X, Y, \hat{Y})$ discrete with $\hat{Y}$ independent of both $X$ and $Y$, one would thus expect that the following relationship holds $$ \max_{f}I(X;Y,\hat{Y} \mid f(Y,\hat{Y})) = \max_{f_1, ...
Cesare's user avatar
  • 189

1
2 3 4 5
13