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.
606
questions
0
votes
0
answers
13
views
Position dependent service time in queue
Is there any literature for queuing analysis (waiting time, capacity etc.) of a queue with service time that depends on the position of the customer in the queue?
I have encountered a problem where a ...
- 11
1
vote
1
answer
58
views
Queues wait for other queues- A communication problem
I am working on a problem which involves a single server that requires multiple inputs to do a computation. Each of these inputs arrive as a Poisson process with rate $\lambda$. Hence, a situation ...
- 11
0
votes
1
answer
80
views
Reverse Pinsker's inequality for smooth density classes
Suppose we are given a class of probability density functions $\mathcal{F}$ so that for every $f \in \mathcal{F}$ we have $\alpha \leq f \leq \beta$ for some positive $\alpha, \beta \in \mathbb{R}_+$ ...
1
vote
0
answers
18
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 ...
- 11
0
votes
0
answers
123
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 ...
- 315
2
votes
0
answers
102
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 ...
0
votes
1
answer
93
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 \...
- 7
2
votes
0
answers
78
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 ...
- 729
1
vote
1
answer
156
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,150
2
votes
0
answers
69
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 \...
- 483
3
votes
1
answer
112
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 ...
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 ...
- 49
1
vote
0
answers
111
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''...
- 9,150
2
votes
1
answer
257
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{\...
- 49
1
vote
0
answers
102
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 ...
- 827
2
votes
1
answer
146
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 ...
0
votes
0
answers
75
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 ...
- 4,525
3
votes
2
answers
404
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 ...
- 73
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 ...
- 13
0
votes
0
answers
48
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(...
- 342
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}, ...
4
votes
1
answer
246
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 ...
- 311
3
votes
1
answer
193
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
3
votes
1
answer
94
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 ...
- 4,304
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{...
- 311
2
votes
0
answers
102
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
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})...
- 53
0
votes
1
answer
110
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
2
votes
1
answer
52
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
8
votes
1
answer
272
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|^...
- 700
2
votes
1
answer
234
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,809
1
vote
0
answers
80
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
119
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{...
- 310
1
vote
1
answer
109
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}&...
- 310
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
$$
...
1
vote
2
answers
189
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
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, ...
- 1,021
0
votes
1
answer
216
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,...
- 745
4
votes
1
answer
119
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 ...
- 91
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'...
- 479
2
votes
1
answer
172
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
86
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,109
0
votes
0
answers
107
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}(\...
- 578
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 ...
- 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 ...
- 193
8
votes
1
answer
302
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-...
- 159
1
vote
1
answer
101
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
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 ...
- 91
1
vote
0
answers
60
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
1
vote
1
answer
183
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 ...
- 251