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

617
questions

1
vote

0
answers

28
views

### From a constraint satisfaction problem (CSP) to a sudoku grid

one of the existing methods of solvin a sudoku grid is via constraints satisfaction (CSP), but can we do the inverse ie convert a CSP problem into a sudoku grid and then solve it ?

0
votes

0
answers

13
views

### Efficient compression techniques for low-rank matrix $A$ to maintain multiplication compatibility？

Suppose we have a large low-rank matrix $A$ and an input matrix $X$ (where $X$ is a tall, skinny matrix). We need to compute the product $AX$. To reduce computational cost and data transfer when ...

1
vote

1
answer

68
views

### Probabilistic 2D cellular automata with memory lifetime increasing like $e^{L^2}$

Consider 2-state probabilistic cellular automata on an $L\times L$ torus square lattice which has the all-$0$ and all-$1$ configurations as fixed points, thinking of something similar to Toom's rule ...

1
vote

1
answer

74
views

### Channel Capacity & Dependency Graph

A single-input-single-output communication channel is to be used repetitively. Denote by $X_i \in \mathcal X$ the input at time $i$ and by $Y_i \in \mathcal Y$ the output at time $i$.
Assume the ...

0
votes

0
answers

11
views

### What are examples of $\epsilon$-extractable uniform randomness $H_{\rm ext}^\epsilon(\cal P)$?

[Renner and Wolf 2004] introduces the notion of $\epsilon$-smooth Renyi entropies as
$$H_\alpha^\epsilon(P) \equiv \frac{1}{1-\alpha} \inf_{Q\in \mathcal B^\epsilon(P)}\log\left(\sum_z Q(z)^\alpha\...

1
vote

1
answer

125
views

### trying to get intuition into why Cross Entropy will always be greater or equal to the Entropy

I understand what entropy measures and cross entropy is the same except it is uses another distribution $q$ to compare it against $p.$ Is it because the log function is concave down so the predictions ...

2
votes

0
answers

117
views

### Exp-Hamming distance in $\{0,1\}^k$

Let integer $k>0$ and let $\{0,1\}^k$ denote the set of all $1\times k$-dim vectors whose every coordinate is eithor 0 or 1, for example, $(0,1,1,0,\dots,1,0,0,1)$. For any such vector $\alpha$, ...

0
votes

0
answers

164
views

### About the monotonicity of the exponential entropy

This question was previously posted on MSE at About the monotonicity of the exponential entropy.
In the paper The Unifying Frameworks of Information Measures the conditional exponential entropy (see ...

0
votes

0
answers

29
views

### Does the definition of mixing time work for general non-Markovian processes?

A definition of the mixing time for Markov chains is given by
\begin{equation}
\tau_{\text{mix}}\equiv\inf{\{t>0: \sup_i\left\vert \frac{\boldsymbol{p}(t|p_j(0)=\delta_{ij})}{\boldsymbol{\pi}}-\...

3
votes

0
answers

55
views

### Wasserstein bounds of interpolation measures

Assume we are given two densities, $p_0$ and $p_1$ on $\mathbb{R}^d$, and define (up to the normalization constant) the interpolation $p_t \propto p_0^{1-t} p_1^t$, which interpolates between $p_0$ ...

2
votes

1
answer

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

0
votes

0
answers

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

1
vote

1
answer

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

0
votes

1
answer

90
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

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

0
votes

0
answers

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

2
votes

0
answers

106
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

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

2
votes

0
answers

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

1
vote

1
answer

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

2
votes

0
answers

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

3
votes

1
answer

128
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

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

1
vote

0
answers

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

2
votes

1
answer

262
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{\...

1
vote

0
answers

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

2
votes

1
answer

168
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

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

3
votes

2
answers

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

0
votes

0
answers

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

0
votes

0
answers

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

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

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

3
votes

1
answer

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

3
votes

1
answer

98
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
votes

2
answers

290
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

106
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

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

0
votes

1
answer

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

3
votes

1
answer

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

8
votes

1
answer

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

2
votes

1
answer

269
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

81
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

120
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

113
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

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

191
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

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

0
votes

1
answer

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

4
votes

1
answer

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