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

540
questions

0
votes

0
answers

30
views

### How can one compute schema quality using information theory?

I initially asked this question on math.SE (linked here). It has been more than a week since the question was posted and I have received no answers even though I offered a 200 reputation bounty (the ...

0
votes

0
answers

26
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

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

1
vote

1
answer

78
views

### A question about mutual information

Let $A$ and $B$ be two, possibly dependent, random variables, and let $X$ be a random variable independent of $(A,B)$. For simplicity, let's concern ourselves with discrete random variables. Is the ...

0
votes

0
answers

30
views

### Relation between multivariate estimation error and differential entropy

On page 255 of the book "Elements of information theory" by Thomas M. Cover and Joy A. Thomas, there is a theorem: For any random variable $X$ and estimator $\hat{X}$, $$E(X-\hat{X})^2 \geq \...

1
vote

0
answers

44
views

### Are the derivatives of the differential entropy power alternating?

Let $X$ be a random vector in $\mathbb {R}^d$ and $X_t = X + \sqrt {t} N$, $t >0$, where $N$ is an independent
standard normal vector; set
$$
H(X_t) = - \int f_t \ln f_t dx
$$
where $f_t$ is ...

1
vote

1
answer

77
views

### Given iid samples from the joint distribution $P$ of pair of r.v.'s $(X,Y)$, how to get iid samples from independence coupling $P_X \otimes P_Y$?

Let $(X,Y)$ be a pair of random variables on a measure space $\mathcal T \subseteq \text{"subsets of }\mathbb R^2\text{"}$, with joint probability distribution $P$.
We don't assume $X$ and $Y$ are ...

13
votes

2
answers

690
views

### Question about information measurement for continuous random variable

I have a question about the information measurement for continuous random variables. Maybe it is some basic question, but it really drives me crazy.
Suppose we have a random variable $x \sim N(0, 1)$ ...

4
votes

1
answer

118
views

### Existence of a joint distribution on Bernoulli variables with same probability of being pairwise different

Let $m\in\mathbb{N}$ and $p\in(0,1)$ be arbitrary. Is there a sequence $X_1,\dots,X_m$ of random variables with the following specs on their distribution:
Each $X_i$ is unbiased Bernoulli: $X_i\sim {\...

2
votes

0
answers

194
views

### Prove or disprove a mutual information inequality

I have $n$ IID Bernoulli random variables denoted by $X_1,X_2,\ldots X_n$ with parameter $p$.
I am interested in knowing if the following inequality involving mutual information holds :
$\boxed{\max_{...

2
votes

1
answer

73
views

### Mutual information between two discrete random variables

I have 2 IID random variables $X_1$ and $X_2$ with $Bern(p)$ distribution. I have another binary random variable $Y$ taking values in $\{0,1\}$.
I am interested in comparing the following 2 mutual ...

2
votes

0
answers

31
views

### Concentration of posterior probability around a tiny fraction of the prior volume

In the context of approximating the evidence $Z$ in a Bayesian inference setting
$$
Z = \int d\theta \mathcal L (\theta)\pi (\theta)
$$
with $\mathcal L$ the likelihood, $\pi$ the prior, John Skilling'...

2
votes

1
answer

91
views

### Fisher Information of variance of difference between random variable and gaussian

I'm reading through the following paper: https://arxiv.org/pdf/0704.1751.pdf
I'm stuck in the middle of page 8, at the statement:
$$E[||S(X)-S^*(X)||^2] = J(X) - J(X^*)$$
Where $S(X)$ is the score of ...

1
vote

1
answer

40
views

### Covariance matrix of score of random vector with independent entries is diagonal

I've been trying to read through the following paper:
https://arxiv.org/pdf/0704.1751.pdf
And I've been stuck on the proposition in the middle of page 8 which says that if a r.v. $X$ has independent ...

2
votes

0
answers

45
views

### What is the set variable corresponding to a random variable?

I stumbled upon an interesting looking work by R. Yeung that shows an interesting relation between information and measure theory called A New Outlook on Shannon’s Information Measures. In this work ...

10
votes

2
answers

304
views

### The origin of the natural base in statistical mechanics

In modern treatments of statistical mechanics, the natural base is conventionally used for the Gibbs and Boltzmann entropy without careful justification. While I am aware that the properties of the ...

8
votes

1
answer

545
views

### Is the square root of the Kullback-Leibler divergence a convex map?

$\newcommand{\KL}{\operatorname{KL}}$Let $X$ be a Polish metric space and $P(X)$ the space of probability measures on $X$. Given $\mu, \nu\in P(X)$, recall that
$$\KL(\mu\parallel\nu) = \begin{cases}\...

0
votes

0
answers

14
views

### sample complexity of hypothesis testing with non-uniform prior

Given two hypothesis $$\mathcal{H}_0:\; x_i\underset{iid}{\sim} p_0(x), i=1,\cdots,n\\ \mathcal{H}_1:\; x_i\underset{iid}{\sim} p_1(x), i=1,\cdots,n$$
with priors $p$ and $1-p$ ($p<1/2$) ...

0
votes

0
answers

34
views

### Prove the statistical rate lower bound of a given complicated statistics

Given a i.i.d. sequence of random variables $\{Z_i\}_{i=1}^n$ who has mean zero. Two i.i.d. sequence of random vectors $\{X_i\}_{i=1}^n$, $\{Y_i\}_{i=1}^n$ who have the same covariance matrix $\Sigma$....

1
vote

0
answers

27
views

### Correlating two matrices $A,B$ with stochastic dependency structure imposed by cross-validation

Consider a labelled data set
$$D = \{(x_1, y_1),...,(x_n, y_n)\} $$
on which we want to evaluate a machine learning algorithm using $k$-fold cross validation with $m$ different random seeds. This ...

5
votes

1
answer

120
views

### Divergence for Bhattacharya Information Matrix

The Fisher information matrix (in the scalar parameter case) can be obtained from the Kullback-Leibler divergence by
$$g(\theta) = -\frac{\partial}{\partial \theta}\frac{\partial}{\partial \theta'}D(...

4
votes

0
answers

53
views

### Exponential families closed under affine transformations

Let $(\Omega,\Sigma,\mu)$ be a probability space and let $\mathcal{M}$ be an exponential family of probability distributions for $\mu$ of the following form: There are $\varphi_1,\dots,\varphi_n:\...

4
votes

1
answer

140
views

### Coding over very noise channel

Suppose that I want to send a message (consisting of bits) over a channel where from $n$ transferred bits as many as $n/2-\varepsilon n$ might be flipped, i.e., the distance of the code is $n-2\...

3
votes

0
answers

108
views

### Maximum entropy methods for probabilistic number theory

Might there be a good survey paper on the application of maximum entropy inference for non-trivial problems in probabilistic number theory?
So far I am aware of the work of Ioannis Kontoyiannis, an ...

1
vote

1
answer

102
views

### Derive KL divergence from Bregman divergence

I know that KL divergence is a form of Bregman divergence for multinomial distributions.
Is there some derivation of KL divergence from functional Bregman divergence or some generalized Bregman ...

2
votes

1
answer

113
views

### What journal(s) do you recommend for submitting a paper on a topic that spans information theory and estimation theory?

I've written a paper that a) demonstrates an equivalence between conditional complexity $K$($Y$|$X$) in information theory and the random component of an effect size estimate $r_{xy}$, and then b) ...

3
votes

0
answers

100
views

### Bounds on the entropy of the 2D Ising model

I am interested in good estimators of (or analytical bounds on) the entropy $\mathsf{H}_\beta:=-\sum_{\mathbf{x}} P(\mathbf{x})\log_2(P(\mathbf{x}))$ of the two-dimensional Ising model (with no ...

0
votes

2
answers

83
views

### Exponential decay of Fisher information along the OU semigroup

I read from a paper that there is a "well-known" exponential decay of Fisher information along the OU semigroup, that is $$J(\nu^t\mid\gamma)\leq e^{-2t}J(\nu\mid\gamma),$$
where $\gamma$ is ...

4
votes

0
answers

61
views

### Does minimum mean-square error characterize distribution?

Let $X$ be a real random variable, and, for each $t \geq 0$, let $X_t = X + \sqrt {t}Y$ where $Y$ is a standard normal independent of $X$. The quantity
$$
R(t) = E \big ( [ X - E (X |X_t)]^2 \big),...

0
votes

0
answers

49
views

### Find the parameter maximizing the binary channel capacity

I have a Binary channel with the probability transition matrix as given below:
$\left[\begin{array}{ccc}
1-e^{-\frac{\tau^{2}}{\sigma_{w}^{2}}} & e^{-\frac{\tau^{2}}{\sigma_{w}^{2}}} \\
1-e^{-\...

2
votes

1
answer

76
views

### information theoretic lower bound for hashing functions [closed]

The literature on minimal perfect hashing functions (mphf) says that the best function we can do will have to store $\frac1{\ln(2)}$ (~1.44) bits per key. There are some sets though that require 0 ...

1
vote

1
answer

91
views

### Is Toom's rule robust under local but non-on-site noise?

Toom's rule is a 2-dimensional cellular automaton which is known to have two distinct stationary measures in the thermodynamic limit, even after small perturbations to a probabilistic cellular ...

3
votes

0
answers

69
views

### Are there (probablistic) uniform 1D cellular automata which can fault-tolerantly store one bit?

In two dimensions, "Toom's rule" is known to be a cellular automaton which can fault-tolerantly store one bit of information. This means that, if we start with the all-0 configuration on an $...

0
votes

0
answers

81
views

### KL divergence between two sequences

Let us have a random sequence $(X_1, Y_1,\ldots,X_n,Y_n)$, where $X_t$ takes value in some set $\mathcal{X}$ and $Y_i$ are scalars. The sequence is generated by the following process: $X_i$ is chosen ...

2
votes

1
answer

135
views

### An inequality in the optimality of Bayes' theorem

$\DeclareMathOperator\Ent{Ent}\newcommand{\prior}{\mathrm{prior}}\newcommand\Data{\mathrm{Data}}$I came across this paper on the optimality of Bayes' theorem
https://sinews.siam.org/Portals/Sinews2/...

3
votes

1
answer

308
views

### Has the von Neumann entropy ever been used in classical mechanics?

After going through an application of the von Neumann entropy(from quantum information theory) to certain problems in computational neuroscience [2], it occurred to me that this entropy might have ...

19
votes

2
answers

3k
views

### John von Neumann's remark on entropy

According to Claude Shannon, von Neumann gave him very useful advice on what to call his measure of information content [1]:
My greatest concern was what to call it. I thought of calling it '...

14
votes

4
answers

2k
views

### Geometric interpretations of the exponential of entropy

Question:
Might there be a natural geometric interpretation of the exponential of entropy in Classical and Quantum Information theory? This question occurred to me recently via a geometric inequality ...

21
votes

1
answer

3k
views

### Who is Mrs. Gerber?

This question on a theorem in information theory called Mrs. Gerber's lemma piqued my curiosity. Who is this individual, and why the "mrs." ? A quick Google search was not informative, ...

1
vote

0
answers

311
views

### When inequality in Mrs. Gerber's lemma is almost equality?

Let $X=x_1\ldots x_n$ be a random variable.
Assume that every $x_i$ takes values in $\{0,1\}$.
Assume also that for every $I \subseteq \{1,\ldots, n\}$ the Shannon entropy of random value $X_I$
[if $I ...

16
votes

6
answers

5k
views

### Revisiting the unreasonable effectiveness of mathematics

Question:
On balance, with theoretical advances in algorithmic information theory and Quantum Computation it appears that the remarkable effectiveness of mathematics in the natural sciences is quite ...

0
votes

0
answers

54
views

### Relationship between $L_1$ and $L_2$ distances of two Gaussian Mixture models

Given two Gaussian mixture models with
\begin{equation}
\begin{aligned}
f(x) &=\sum_{k=1}^{K} \pi_{k} \mathcal{N}\left(x \mid \mu_{k}, \sigma_{k}\right), \\
g(x) &=\sum_{i=1}^{N} \lambda_{i} \...

0
votes

1
answer

100
views

### Mutual Information of the summation of a Chi-square random variable and a Gaussian variable

As the title, $X$ is an random variable subject to $N(0,1)$, $N$ is an random variable subject to $N(0,\sigma^2)$, and $X$ and $N$ are independent. I want to calculate the mutual information $I(X,Y)$ ...

3
votes

2
answers

638
views

### Is there an inequality relation between KL-divergence and $L_2$ norm?

According to the Pinsker inequality, we have the following inequality:
\begin{equation}
\delta_{TV} (p, q)^2 \leq \frac{1}{2} D_{KL}(p,q),
\end{equation}
where $\delta_{TV} (\cdot, \cdot)$ and $D_{KL}...

2
votes

0
answers

77
views

### A result of the covering number

Suppose $\mathcal{F} = \{f_x : x \in \mathbb{R}^d \}$ and each $f_x$ shares the same law $P$. If $\mathcal{F}$ is a class of uniformly bounded functions satisfying $L_r$-continuity, i.e. $\forall f \...

1
vote

0
answers

165
views

### Maximum mutual information of random unitary transformation

Let $\mathbf{U}$ and $\mathbf{V}$ be random unitary matrices independent of random input vector $\mathbf{x}$. Moreover, $\mathbf{z}$ be random iid complex Gaussian vector with zero mean and identity ...

5
votes

1
answer

137
views

### Kullback–Leibler chains

The following question was asked and then deleted by the post author:
Let $P$ and $Q$ be two probability distributions defined over the same space, with $KL(P \parallel Q) < \infty$. For $\epsilon ...

2
votes

1
answer

202
views

### Mutual Information after Applying Random Unitary Matrix

Let $\mathbf{U}$ be a random unitary matrix and $\mathbf{z}$ be a random i.i.d complex Gaussian vector (unitary invariant). Assume that the following relation is satisfied:
\begin{align}
\mathbf{y}=\...

1
vote

1
answer

133
views

### paper only available in Russian (Kozachenko Leonenko entropy estimator)

this paper is only available in Russian: http://www.mathnet.ru/links/9f144b1d16e600dac49acbfe5acf938f/ppi797.pdf According to MathSciNet, there is no link to the English article or journal publication ...

1
vote

0
answers

63
views

### intuition about Gaussian processes over a finite space

In a paper that I am reading the authors defines $\mathbb P(n,q)$ the space of covariance tensors for $\mathbb R^q$-valued Gaussian processes on an abstract finite space $K=\{x_1,\dots,x_n\}$. In his ...