# 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.

583
questions

4
votes

2
answers

271
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{...

2
votes

0
answers

65
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] $...

1
vote

1
answer

50
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})...

0
votes

0
answers

54
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 ...

1
vote

0
answers

31
views

### When the sum of the power distribution coefficients in NOMA is 1, will the total power exceed the rated power? [closed]

I have some questions about power allocation in the following paper. In this paper, the signals to be transmitted by the base station to users are superimposed at the base station, and the sum of the ...

2
votes

1
answer

37
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$,...

7
votes

1
answer

191
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|^...

1
vote

1
answer

90
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-...

1
vote

0
answers

58
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 ...

3
votes

1
answer

106
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{...

1
vote

1
answer

100
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}&...

3
votes

0
answers

78
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

2
answers

152
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=...

2
votes

0
answers

36
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, ...

0
votes

1
answer

158
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,...

2
votes

0
answers

49
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 ...

3
votes

0
answers

59
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'...

2
votes

1
answer

156
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 ...

1
vote

1
answer

66
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 ...

0
votes

0
answers

76
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}(\...

1
vote

1
answer

73
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 ...

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 ...

7
votes

1
answer

167
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-...

1
vote

1
answer

85
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 ...

1
vote

0
answers

42
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 ...

1
vote

0
answers

42
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)$?

0
votes

1
answer

65
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 ...

0
votes

1
answer

114
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-...

0
votes

1
answer

80
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, ...

1
vote

1
answer

142
views

### KL divergence between gaussian with uniform prior

I have 2 normal distributions $\mathcal{N}(\mu_1, \mathbb{I}_d)$ where $\mu_1$ is a fixed vector in $\mathbb{R}^d$ and $\mathcal{N}(\mu_2, \mathbb{I}_d)$, where $\mu_2$ is $\mu_1 + V$, where $V$ is ...

1
vote

1
answer

50
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 (...

3
votes

1
answer

96
views

### Mutual information in large deviation theory

Many information theoretic quantities such as entropy and relative entropy appear in rate functions in large deviation theory (LDT). Is there any result in LDT that relates mutual information and rate ...

4
votes

0
answers

131
views

### Upper bound of conditional mutual information

Given random variables $X$,$Y$ with a joint distribution $P(X,Y)$ and another random variable $Z$, it is known that there are cases when the conditional mutual information $I(X;Y|Z)$ is greater than ...

3
votes

1
answer

192
views

### Entropy of $f^{m(x)+n}$ of full shift

Let $(X,\mu,f)$ be a two-sided full shift system. Assume that there is $t \in \mathbb{N}$ such that for every $n \in \mathbb{N}$ and $x \in X$, we can define $T(x)=f^{n+m(x)}(x)$, where $m(x) \leq t; $...

4
votes

1
answer

251
views

### Minimum of random walks

Let $M$ independent and identical random walks that follow the chi-squared distribution, i.e. in each step, a $X^2_1$ random variable is added. I am interested in the minimum random walk at each step. ...

2
votes

0
answers

74
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, ...

1
vote

0
answers

91
views

### Reference request: Time and proofs of shared pasts

Is there research about structures for notions of time with distributed systems of information, as with blockchains?
I am thinking of tuples $(I, T, P, A, \prec, s, \eta, u)$ where
$I$, $T$ and $P$ ...

3
votes

2
answers

509
views

### Kolmogorov's approach to probability theory

Question:
Did Kolmogorov develop a set of axioms for probability theory motivated by Algorithmic Information Theory in the 1960s?
Context:
In 1965, Andrey Kolmogorov considered three approaches to ...

1
vote

2
answers

118
views

### Maximization of information over set of non-injective functions (Equality)

Let $X$, $Y$, $Z$ be discrete random variables, with $Y$ and $Z$ independent. Does the following equality hold if $Z$ is independent also of $X$?
$$
\max_{f_{Y,Z}} \big\{ \ I(X; f_{Y,Z}(Y,Z)) \ \big\} ...

15
votes

1
answer

667
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=\{...

2
votes

0
answers

87
views

### List decodability of Reed-Solomon codes beyond the Johnson bound

In a paper on a proximity test for Reed-Solomon codes the authors state an "extremely optimistical" conjecture on the list decodability of Reed-Solomon codes (over prime fields $\mathbb F_q$)...

2
votes

1
answer

68
views

### Mutual information and bivariate function of independent variables

Let $X, Y, Z$ be discrete random variables with $X$ and $Y$ independent of $Z$, while $X$ and $Y$ can be dependent. For the mutual information, we have $I(X; Y,Z) = I(X;Y)$. Now consider $I(X; f(Y,Z))$...

5
votes

2
answers

218
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 ...

1
vote

1
answer

112
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. ...

2
votes

1
answer

82
views

### Maximization of information over set of non-injective functions

Let $X$, $Y$, $Z$ be discrete random variables, with $Y$ and $Z$ independent. Does the following equality hold?
$$
\max_{f_{Y,Z}} \big\{ \ I(X; f_{Y,Z}(Y,Z)) \ \big\} \le \max_{f_X, f_Y} \big \{ \ I(X;...

0
votes

1
answer

138
views

### Constructing Markov chain

Let $(A_1,B_1)$ and $(A_2,B_2)$ be two random variables with the joint distributions $p_{A_1B_1}$ and $p_{A_2B_2}$, respectively. Moreover, we have
$$\mathbb{P}[(A_1,B_1)\neq (A_2,B_2)]=\alpha.$$
Then,...

6
votes

0
answers

2k
views

### Information theory, a categorical perspective [closed]

Note: B-variables were called streams in a previous version -> you won't understand the comments otherwise
Definition of $B$-variables
Theorem: Let $l_1\leq \dots\leq l_n$ be the lengths of a set ...

7
votes

0
answers

115
views

### Ideals, subalgebras, subgroups as error-correcting codes?

Context: roughly speaking the construction of a error correcting code is a problem to choose some subset in a metric space, such that the points of the subset pairwise as far-distant as possible. ...

1
vote

0
answers

49
views

### Extension of Data Processing Inequality: If $X \rightarrow Z \rightarrow Y$, $I(X, ZY) \geq I(X, Y)$?

If we have the Markov chain $X \rightarrow Z \rightarrow Y$, we can say $I(X, Z) \geq I(X, Y)$ from the data processing inequality. Then, can we say that $I(X, ZY) \geq I(X, Y)$?

4
votes

1
answer

283
views

### Bipartite version of Hamming bound (two families of codewords with large Hamming distance)?

Update: In light of Fedor Petrov's answer, I added an additional requirement that all strings in $A$ and $B$ have Hamming weight exactly $n/2$, which hopefully makes the question more interesting.
...