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

453
questions

**4**

votes

**1**answer

111 views

### $\varepsilon$-net of a $d$-dimensional unit ball formed by power set of $V = \{+1, 0 -1\}^d$

I have a set of $d$-dimensional vectors $V = \{+1, 0, -1\}^d $. Then $P(V)$ constitutes the power set of $V$. I now construct a set of unit vectors $V_{\mathrm{sum}}$ from the power set $P(V)$ such ...

**3**

votes

**0**answers

183 views

### Can information be extracted more precisely using more random trials?

Write $n$ iid draws of $(x,y)$ as $(x^n, y^n)$. Fix $R\in (0,H(y))$. What is the min of $n^{-1}H(x^n|f(y^n))$ over $f$ with $H(f(y^n))\leq nR$, taking $n\to \infty$?

**1**

vote

**0**answers

59 views

### Manifold structure of Gaussian mixtures

Fix $l$ a positive integer. Let $\mathcal{M}$ denote the set of Gaussian mixtures of the form
$$
\sum_{i=1}^l k_i \mu_i,
$$
where $\mu_i $ is a non-degenerate Gaussian measure on $\mathbb{R}^k$ and ...

**1**

vote

**0**answers

39 views

### Bounding the total variation metric between Gaussian mixtures

Let $\mathcal{P}(\mathbb{R}^d)$ the space of probability measures on $\mathbb{R}^d$ with total variation metric $\delta$, fix $k \in \mathbb{N}$, and let $\mathcal{P}'\subset \mathcal{P}(\mathbb{R}^d)$...

**7**

votes

**1**answer

121 views

### Books to develop a unified view of statistics and information theory?

I hope to understand the connection between statistics and information theory in a deep philosophical sense.
I suppose the best place to start would be David MacKay's Information Theory, Inference, ...

**2**

votes

**0**answers

93 views

### Inequality on the Kullback-Leibler divergence

Let us define the arithmetic, geometric, and harmonic means of $x,y \in \mathbb{R}$ weighted by $\alpha =(\alpha_x,\alpha_y) \in [0,1]$, respectively as
\begin{equation}
a_\alpha(x,y) = \frac{\...

**0**

votes

**0**answers

31 views

### Do d “moments of surprisal” determine a probability distribution on d events?

(The following question was transferred from stack-exchange with the hope of obtain a useful hint here). Consider a probability distribution on $d$ events, with the probabilities $p_j$ gathered in a ...

**0**

votes

**2**answers

138 views

### Statistical divergence

Does anyone know about a statistical divergence of this type?
\begin{equation}
\text{D}(P||Q) = \frac{1}{2} \left[\text{KL}(M||P) + \text{KL}(M||Q)\right]
\end{equation}
where $M = \frac{1}{2} [P+Q]$....

**0**

votes

**1**answer

49 views

### Joint typicality of sequences

I know that for two i.i.d distributions $P$ and $Q$ the probability that $Q$ will produce a length $n$ sequence that is $\epsilon$-typical according to $P$ is bounded by
$$Q(T_{P,\epsilon})\leq e^{-nD(...

**0**

votes

**1**answer

119 views

### Quantum entropy Venn diagrams

We know that in classical information theory the relation between different entropies can be depicted by Venn Diagram as given below.
Can we create such Venn-diagrams for the quantum information ...

**1**

vote

**1**answer

82 views

### Find the largest subset of all binary arrays of length $n$ with $r$ ones which have pairwise distance greater than $m$

Let $\Omega = \left\lbrace x : |x| = r \, \text{for} \, x \in \mathbb{Z}_2^n \right\rbrace$ for $r \in \mathbb{N}$. We want to find the the biggest subset of $\Omega$, $\Gamma = \left\lbrace x \in \...

**3**

votes

**2**answers

195 views

### Lower bounding decoding error in a noisy adversarial channel

Problem description
Suppose we have a finite alphabet $\mathcal{X}$, where each letter $X \in \mathcal{X}$ indexes into some fixed set of distributions, $\{P_{1},\ldots,P_{|\mathcal{X}|}\}$. For ...

**1**

vote

**1**answer

143 views

### With only two characters allowed, is it possible to efficiently reference a 256 character alphabet in a string?

Let us use 0 and 1 for the binary parallel.
You have 256 characters you need to reference, imagining a 256 character alphabet. You can only use a string to reference them that contains 0 and 1. The ...

**2**

votes

**1**answer

67 views

### Entropy rate problem of ergodic Markov process with non-ergodic joint

I have a problem with the entropy rate when two ergodic Markov processes who are independent of each other having a non-ergodic joint. More specifically let us consider two finite-state Markov ...

**1**

vote

**1**answer

52 views

### Encoding a random variable with mutual information constraints

For random variables X and Y, is there any one-bit variable $Z=f(Y)$, such that $I(X;Z)\geq I(X;Y)/B$ where $B$ is the number of bits to represent $Y$?

**1**

vote

**1**answer

115 views

### Uniform upper bound on contraction coefficient w.r.t total-variation metric, of a certain set of block-diagonal Markov kernels

Disclaimer. This is related to another question I've asked on the TCS site https://cstheory.stackexchange.com/q/46097/44644. I'm new to information theory (and other relevant fields). It's even ...

**3**

votes

**1**answer

97 views

### Given three distributions p, q and h. If KL(p||q) is large enough and KL(q||h) is small enough, does there exist a number N such that KL(p||h)>N?)

Given three distributions $p, q$ and $h$, assume we know that the Kullback-Leibler divergence obeys
$KL(p\Vert q)$ is large enough, say $KL(p\Vert q) > M$ where $M$ is large enough, and
$KL(q\Vert ...

**5**

votes

**1**answer

362 views

### Formalizing Entropy Compression (as used to constructify the Lovász Local Lemma)

In 2009, Moser published a breakthrough paper constructifying the Lovász Local Lemma (LLL). His talk at STOC was described in a blog post by Fortnow that proves a slightly weakened result using ...

**0**

votes

**1**answer

79 views

### What is the Relative Entropy between distributions $X$ and $Y$, when $Y$ is a function of $X$?

Let us say we have two probability measures, $X$ and $Y$ on sample spaces $\Sigma_X$ and $\Sigma_Y$ (which are finite sets, with the largest sigma algebra on each space) and suppose we get measure $Y$...

**7**

votes

**3**answers

288 views

### Quantifying the noninvertibility of a function

Given a function $f$ from a finite set $X$ to itself, it seems natural to consider $\kappa_f := (\sum_{x \in X} |f^{-1}(x)|^2)/|X|$ as a measure of the non-invertibility of $f$: it equals 1 if $f$ is ...

**2**

votes

**1**answer

108 views

### Maximizing entropy of summation of unknown distributions

Let the random variable $Y = X_1+X_2$, where $X_1$ follows an unknown distribution and $Y$ has finite variance.
Assuming as measurement of normality the entropy, is it correct to support that the ...

**1**

vote

**0**answers

96 views

### Connecting Wasserstein distance with mutual information?

Suppose I have Markov chains:
$$X \rightarrow f(X) \rightarrow g(X)$$
$$Y \rightarrow f(Y) \rightarrow g(Y)$$
where it is known that minimizing the $\mathbb{E}(g(X)) - \mathbb{E}(g(Y))$ minimizes the ...

**1**

vote

**1**answer

92 views

### Does a 1-Lipschitz function preserve mutual information between two random variables?

Suppose we have a 1-Lipschitz function $f$ such that 1-Lipschitzness is preserved, with $D_A(f(X), f(Y)) \leq D_B(X, Y)$ for some metric spaces $A$ and $B$.
Does this also imply that $I(f(X); f(Y)) = ...

**1**

vote

**0**answers

83 views

### Does (mutual) information always decrease in a Markov chain

Consider two functions $f: \mathcal{X} \to \mathcal{Y}$ and $g: \mathcal{X} \to \mathcal{X}$. In general, I am interested in the case where these functions have a random element, but to keep things ...

**4**

votes

**3**answers

304 views

### Introduction to information geometry and/or geometric control theory

Some background: I'vebeen searching for a research project to work through my grad studies and I found information geometry like a strong candidate but the amount of work out there is overwhelming. I ...

**2**

votes

**0**answers

126 views

### Is there any geometric interpretation for the trace of Fisher information matrix?

Consider a parametric family $p_\theta(x)$ of distributions, with parameter $\theta \in \Theta \subseteq \mathbb R^p$.
If the mapping $\theta \mapsto p_\theta(x)$ is continuously differentiable at $\...

**2**

votes

**2**answers

161 views

### If the mutual information $I(X;Y)$ is high, how can we prove that if $I(X;Z)$ is high then $I(Y;Z)$ is high too?

Let say, we have three random variables, $X$, $Y$, and $Z$, where $X$ and $Y$ have high mutual information $I(X;Y)$. Then, how can we prove that if $I(X;Z)$ is high then $I(Y;Z)$ is high too??
Any ...

**0**

votes

**1**answer

163 views

### Bounding information of expression

Cross posted to theory exchange - https://cstheory.stackexchange.com/questions/45610/bounding-information-of-expression
Suppose $u_1,\ldots,u_n$ are uniformly iid in $\{0,1\}$.
Let $x_1,\ldots,x_n$ ...

**6**

votes

**1**answer

222 views

### Guessing the number of other $1$'s in a binary sequence

I have posed the following question on math.stackexchange.com but have not received an answer. So I would like to seek experts' opinion here.
Consider the set of all binary sequence of length $n+1$, $...

**6**

votes

**0**answers

237 views

### What is the status of the Born Rule in axiomatic QM?

While physicists have tried multiple times and failed to derive the Born Rule (for example: https://arxiv.org/pdf/quant-ph/0409144.pdf). I was wondering what axiomatic Quantum Mechanics had to say ...

**1**

vote

**0**answers

60 views

### Convexity of conditional relative entropy for Markov distributions

Consider two Markov processes $p$ and $q$. The conditional relative entropy between them is
\begin{align}
D(p\parallel q)& =\sum_a p(a)\sum_b p(b\mid a)\log\frac{p(b\mid a)}{q(b\mid a)}\\
& =\...

**2**

votes

**1**answer

71 views

### Entropy of distribution with block matrix support

Let $P(X_1,X_2)$ be a discrete bivariate distribution that has the form shown in the figure below, i.e. its support can be split into blocks that do not overlap on either dimensions.
Let's build $P'(...

**2**

votes

**1**answer

115 views

### Relationship between $\alpha$-divergences?

I am working with $\alpha$-divergences and was wondering how understand the relationship between the definitions of Renyi and Amari?
Renyi:
$D_{\alpha}[p||q] = \frac{1}{\alpha - 1} \log \int p^{\...

**4**

votes

**1**answer

158 views

### Convexity of exponential family

It is known that (given a $\sigma$-finite Borel reference measure $\nu$ on $\mathbb{R}$) the parameter space of an exponential family is convex in Euclidean space. However, my question is, for an the ...

**0**

votes

**0**answers

150 views

### Non-negative interaction information for special trivariate case

Consider a discrete trivariate distribution $P(X_1, X_2, Y)$, which satisfies
$$
p(x_1, x_2, y) = \min( p(x_1,y), p(x_2,y) ),
$$
for all $x_1$ and $x_2$ for which $p(x_1, x_2) > 0$ and for all ...

**26**

votes

**2**answers

1k views

### Is there a Kolmogorov complexity proof of the prime number theorem?

Lance Fortnow uses Kolmorogov complexity to prove an Almost Prime Number Theorem (https://lance.fortnow.com/papers/files/kaikoura.pdf, after theorem $2.1$): the $i$th prime is at most $i(\log i)^2$. ...

**2**

votes

**1**answer

110 views

### Mutual information inequality

I am trying to prove three inequalities that would help me solve the proof of a larger theorem.
Let $P(X,Y)$ be a discrete bivariate distribution and
$$
I(X;Y) = \sum_{i,j} p(x_i, y_j) \log \frac{p(...

**0**

votes

**0**answers

59 views

### How to derive formula (10) norm to obtain formula (11) in Uncorrelated Group LASSO?

In Uncorrelated Group LASSO, Eq. (10) and Eq. (11) are as follows:
$J_2(W)=f(W)+\alpha Tr(W^TFW)$. (10)
$F_{ii}=\sum_{g}\frac{(I_{G_{g}})_i||W_{G_g}||_{2,1}}{||W_{G_g}^i||_2}$. (11)
where $w_{...

**3**

votes

**0**answers

105 views

### Shannon-McMillan-Breiman theorem for expander graphs: rate of convergence?

Is the following uniform SMB theorem for random walks on expander graphs true?
For simplicity, I will state it for a finite group $G=\langle S \rangle$ and a uniform probability measure $\mu$ on the ...

**2**

votes

**0**answers

179 views

### On the difference of conditional differential entropy of two correlated random variables

Problem Definition
Let $\mathbf{G}$ and $\mathbf{S}$ be jointly distributed random variables where
$\mathbf{S}$ is continuous and is related to $\mathbf{G}$ through a conditional pdf $f(s|g)$ defined ...

**1**

vote

**0**answers

78 views

### Binary search extension for determining a hyperplane splitting a set of points in $\mathbb{R}^d$

We are given a set $S$ of $n$ points in $\mathbb{R}^d$ and a (hidden) vector $\mathbf{w}\in\mathbb{R}^d$, where each point $\mathbf{v}\in S$ is associated with a binary label equal to the sign of $\...

**9**

votes

**1**answer

218 views

### Conceptual explanation for the appearance of entropy in $\frac{d}{dp}\|x\|_p$

For $x\in \mathbb{R}^d$, an elementary computation yields that
$$\frac{d}{dp}\log \|x\|_p =\frac{1}{p^2}\sum_{i=1}^d \frac{|x_i|^p}{\|x\|_p^p}\log \frac{|x_i|^p}{\|x\|_p^p}=-\frac{1}{p^2}\operatorname{...

**0**

votes

**0**answers

96 views

### Computing the partition function via one of the three methods

I am trying to compute the averaged partition function for some system (with very large $N$) and I reach this point:
\begin{equation}
\left < Z\right > =\int \prod_i^N \left (\frac{\...

**0**

votes

**0**answers

118 views

### Are all cellular automata models related to the Bekenstein bound and the holographic principle?

Cellular automata are discrete models which have a regular finite dimensional grid of cells, each in one of a finite number of states, such as on and off.
There are various scientists that have ...

**3**

votes

**1**answer

225 views

### Exponential deconvolution using the first derivative

There is an interesting observation using the first derivative to deconvolve an exponentially modified Gaussian:
The animation is here at terpconnect.umd.edu.
The main idea is that if we have an ...

**2**

votes

**0**answers

61 views

### Correspondence between information theoretic and coding theoretic language?

In information theory capacity or best rate achievement techniques are through showing existence if typical sequences of certain measure while in coding theory performance is measured by number of ...

**0**

votes

**1**answer

124 views

### Shortest possible good codes?

Good codes (those with positive rate $r=k/n$ and positive relative distance $\delta=d/n$) will achieve capacity on $BSC$ (binary symmetric channel) if the codes have lower rates than capacity where ...

**4**

votes

**1**answer

95 views

### Polynomial time decodable binary linear codes achieving $GV$ bound?

Are there explicit or random construction of linear codes that achieve the $GV$ bound with polynomial time decodable property with alphabet size $q=2$?
Tsfasman, Manin, Vladut beat the bound at ...

**3**

votes

**1**answer

125 views

### Maximal correlation and independence

Let $X$ and $Y$ be random variables. Then the maximal correlation $\rho_m(X;Y)$ is defined as
$$ \rho_m (X;Y) := \max_{(f(X),g(Y))\in S} \mathbb{E} [f(X)g(Y)] $$
where $S$ is the collection of pairs ...

**5**

votes

**0**answers

57 views

### Functional Equation of Zeta Function on Statistical Model

I've been studying [1] because I was interested in his ideas on the zeta function. I'll define it here (c.f. p. 31):
The Kullback-Leibler distance is defined as
$$
K(w)=\int q(x)f(x, w)dx\quad
f(x,w)...