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.

Filter by
Sorted by
Tagged with
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 ...
user avatar
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)$?
user avatar
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. ...
user avatar
  • 43
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 ...
user avatar
  • 13
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 \...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 5,576
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)$ ...
user avatar
  • 139
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 {\...
user avatar
  • 1,076
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_{...
user avatar
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 ...
user avatar
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'...
user avatar
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 ...
user avatar
  • 33
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 ...
user avatar
  • 33
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 ...
user avatar
  • 41
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 ...
user avatar
  • 3,203
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}\...
user avatar
  • 231
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$) ...
user avatar
  • 451
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$....
user avatar
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 ...
user avatar
  • 153
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(...
user avatar
  • 769
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:\...
user avatar
  • 630
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\...
user avatar
  • 17.1k
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 ...
user avatar
  • 3,203
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 ...
user avatar
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) ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 433
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),...
user avatar
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^{-\...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 2,475
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 $...
user avatar
  • 2,475
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 ...
user avatar
  • 173
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/...
user avatar
  • 23
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 ...
user avatar
  • 3,203
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 '...
user avatar
  • 3,203
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 ...
user avatar
  • 3,203
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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 3,203
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} \...
user avatar
  • 135
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)$ ...
user avatar
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}...
user avatar
  • 135
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 \...
user avatar
  • 173
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 ...
user avatar
  • 129
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 ...
user avatar
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}=\...
user avatar
  • 129
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 ...
user avatar
  • 91
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 ...
user avatar

1
2 3 4 5
11