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{...
- 129
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] $...
- 445
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})...
- 53
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 ...
- 11
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 ...
- 11
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$,...
- 21
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-...
- 3,650
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{...
- 89
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}&...
- 89
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=...
- 11
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, ...
- 747
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,...
- 575
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 ...
- 71
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'...
- 479
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 ...
- 1,089
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}(\...
- 568
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 ...
- 129
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 ...
- 193
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 ...
- 439
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 ...
- 91
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)$?
- 111
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 ...
- 231
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-...
- 3
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, ...
- 189
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 ...
- 195
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 (...
- 133
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 ...
- 1,253
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 ...
- 41
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; $...
- 929
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, ...
- 4,097
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,103
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 ...
- 3,629
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\} ...
- 189
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=\{...
- 18.8k
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$)...
- 81
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))$...
- 189
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 ...
- 133
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. ...
- 133
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;...
- 189
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,...
- 129
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 ...
- 193
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. ...
- 22.6k
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)$?
- 53
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.
...
- 43