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
30 votes
3 answers
5k 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 '...
Aidan Rocke's user avatar
  • 3,827
17 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 ...
Aidan Rocke's user avatar
  • 3,827
25 votes
2 answers
4k 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, ...
Carlo Beenakker's user avatar
1 vote
0 answers
397 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 ...
Alexey Milovanov's user avatar
17 votes
6 answers
6k 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
146 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} \...
Ze-Nan Li's user avatar
  • 175
1 vote
1 answer
187 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)$ ...
He Zhitong's user avatar
5 votes
4 answers
3k 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}...
Ze-Nan Li's user avatar
  • 175
2 votes
0 answers
118 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 \...
香结丁's user avatar
  • 331
1 vote
0 answers
176 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 ...
Math_Y's user avatar
  • 311
5 votes
1 answer
148 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 ...
Iosif Pinelis's user avatar
2 votes
1 answer
223 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}=\...
Math_Y's user avatar
  • 311
0 votes
1 answer
211 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 ...
qwert's user avatar
  • 89
1 vote
0 answers
72 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 ...
leo monsaingeon's user avatar
8 votes
2 answers
386 views

Maximum of the weighted binomial sum $2^{-r}\sum_{i=0}^r\binom{m}{i}$

Let $m$ be a positive integer and let $f_m(r)=2^{-r}\sum_{i=0}^r\binom{m}{i}$. Clearly $f_m(0)=f_m(m)=1$ and $f_{2r+1}(r)=2^{2r}$. Conjecture: If $m>12$, then the maximum value of $f_m(r)$ for $r\...
Glasby's user avatar
  • 1,961
1 vote
0 answers
230 views

Maximum mutual information of a matrix representation

Let $\mathbf{Z}$ be a $m\times n$ matrix with zero-mean unit-variance i.i.d complex Gaussian entries. What is the maximum value of mutual information $I(\mathbf{X}_1,\mathbf{X}_2;\mathbf{Y})$ such ...
Math_Y's user avatar
  • 311
1 vote
1 answer
117 views

KL-divergence and sub-$\sigma$-algebras

I am trying to understand if the following claim is true: Let $P$, $Q$ be probability measures on $\mathcal{X}$. For any $\sigma$-algebra $\mathcal{G}$, with countably many atoms (sets with $\...
T.T.'s user avatar
  • 13
1 vote
1 answer
105 views

Almost-parallel corners of the hypercube in high dimensions

Say I would like a collection of k "almost-parallel" boolean vectors $X_1,...,X_k \in \{\pm 1\}^n$, such that $(X_i,X_j)/n \approx 1-\epsilon$ for some small $\epsilon$. How many ways are ...
DJA's user avatar
  • 425
2 votes
1 answer
215 views

Simple non-asymptotic upper-bound for packing number of a hamming cube

Looking for a simple upper-bound for the packing number of hamming cube, I'm led to consider the following. Fix $p \in (0,1/2]$. For a positive integer $n$, define $S_n(p) := \sum_{i=1}^{\lfloor np\...
dohmatob's user avatar
  • 6,716
6 votes
1 answer
782 views

reverse KL-divergence: Bregman or not?

I am having a little trouble getting my head around the two "directions" of the Kullback-Leibler divergence: Definition (Kullback-Leibler divergence) For discrete probability distributions $...
jw7642's user avatar
  • 91
6 votes
0 answers
101 views

Computing the zeta transform of a Boolean function: Space-time tradeoff

Let $f : \mathbb{F}_2^n \to \mathbb{F}_2$ be a Boolean function in $n$ variables. The zeta transform of $f$ is the Boolean function $\zeta_f : \mathbb{F}_2^n \to \mathbb{F}_2$ defined by $$\zeta_f(y) :...
Oslow's user avatar
  • 71
0 votes
0 answers
165 views

A basic property of maximal correlation

Let $𝑋$ and $𝑌$ be random variables. Then the maximal correlation $\rho_{m}(X;Y)$ is defined as: $$\rho_{m}(X;Y):=\max_{f,g}\mathbb{E}[f(X)g(Y)],$$ where the maximization is taken over real-valued ...
Vince_maths's user avatar
1 vote
0 answers
63 views

Normalizing constants preserve metric entropy

Suppose $\mathcal{F}=\left\{f\in L^2([a,b]): 0<\underline{c}\leq f\leq\overline{c} \right\}$. Consider the following transformation $$\tilde{\mathcal{F}} := \left\{\frac{f}{\int f d\mu}: f\in \...
lucaszz's user avatar
  • 11
1 vote
1 answer
313 views

Are there any results on concentration bounds of Wasserstein distances between empirical measures?

I know there are concentration bounds on $W(\mu,\hat{\mu})$ where $\mu$ and $\hat{\mu}$ are true and empirical distributions respectively, but is there anything out there on $W(\mu,\nu)$ versus $W(\...
Kashif's user avatar
  • 343
20 votes
2 answers
4k views

information-theoretic derivation of the prime number theorem

Motivation: While going through a couple interesting papers on the Physics of the Riemann Hypothesis [1] and the Minimum Description Length Principle [2], a derivation(not a proof) of the Prime Number ...
Aidan Rocke's user avatar
  • 3,827
2 votes
1 answer
165 views

Monotonicity of Dirichlet form of Markov chain

Consider a continuous-time, irreducible Markov chain $X_t$ on a finite state space $E$. Assume the jump rates are $R(x,y)$ for $x,y\in E$, the generator is $L$, i.e for any function $f$ on E, $$Lf(x)=\...
Tiago's user avatar
  • 59
1 vote
1 answer
241 views

Parameterization of exponential family

Let $\{\mathbb{P}_{\theta}\}_{\theta}$ be an exponential family of probability measures, all with finite mean. Under what conditions is the parameterization map $\theta\mapsto \mathbb{P}_{\theta}$ ...
ABIM's user avatar
  • 5,019
2 votes
1 answer
198 views

Do enough permutations of an initial set probably cover most permutations?

Fix $\alpha, \epsilon \in(0,1)$. Take $(S_n)_n$ to be any sequence of sets with each $S_n$ containing $ \lceil (n!)^\alpha\rceil$ permutations of $n$ elements. Also build another sequence of sets $(...
Christian Chapman's user avatar
5 votes
2 answers
718 views

Comparison of Information and Wasserstein Topologies

There are many possible metrics one can place on the space of Gaussian probability measures on $\mathbb{R}^n$, with strictly positive definite co-variance matrices. Let's denote this space by $X$. I'...
Catologist_who_flies_on_Monday's user avatar
0 votes
1 answer
484 views

Integrability of $\int \log(f(x)) f(x) dx$ for a probability density function $f$

I am looking for weak conditions when a probability density function $f$ on $\mathbb{R}^d$ has a finite integral $$ \int_{\mathbb{R}^d} \log(f(x)) f(x) dx. $$ Any references would be appreciated.
Austin's user avatar
  • 3
2 votes
0 answers
150 views

The uniform “probability” on $\mathbf{N}$: What occurs beyond logarithmic density?

This is a follow-up to Question #47134. There is obviously no uniform probability distribution on $\mathbf{N}$ (or $\mathbf{Z}$); however, using the notion of amenability, you can show that any ...
Rémi Peyre's user avatar
8 votes
1 answer
584 views

Probability of a deviation when Jensen’s inequality is almost tight

This is a cross-post to a yet unanswered question in Math StackExchange https://math.stackexchange.com/questions/3906767/probability-of-a-deviation-when-jensen-s-inequality-is-almost-tight Let $X>0$...
Luis L.'s user avatar
  • 183
1 vote
0 answers
104 views

A variant of Huffman code

Given an alphabet of $n$ symbolswith probabilities $p_i$ for symbol $i$, we need to encode the symbols (in a prefix-free way) to binary codewords $c(i)$ with length $\ell(c(i))$ to minimize the ...
lchen's user avatar
  • 459
0 votes
1 answer
149 views

Lower bound for reduced variance after conditioning

Let $X$ be a random variable with variance $\tau^2$ and $Y$ be another random variable such that $Y-X$ is independent of $X$ and has mean zero and variance $\sigma^2$. (One can think of $Y$ as a noisy ...
Nima's user avatar
  • 3
1 vote
1 answer
407 views

error correcting huffman code [closed]

I am looking for a code that can correct errors with variable and limited length like huffman code. I am not an expert in coding theory. Is there any code or related literature on this?
lchen's user avatar
  • 459
0 votes
1 answer
132 views

Encoding numbers with relationship into one and back

Given a set of many variables $S=\{x_1,x_2, ...., x_i\}$, and any subset $S'$ of $S$, I need a function $f$ which maps $S'$ to a value $x$ and a function $f'$ which maps $x$ back to set $S'$. I know ...
Rise of Kingdom's user avatar
4 votes
1 answer
303 views

Information monotonicity of divergence => function of $f$-divergence

It is well-known that $f$-divergences defined on $\mathcal P(\mathcal X)$ where $\mathcal X$ is a measure space with $\sigma$-algebra $\mathcal B$ satisfy the property of information monotonicity: ...
Lance's user avatar
  • 203
5 votes
3 answers
480 views

Is there a quantum analog of Kolmogorov Complexity?

Kolmogorov Complexity (interpreted in terms of shortest program computing a string) and Shannon Entropy are quite similar. Since there is a quantum entropy is it reasonable to ask if there is quantum ...
Turbo's user avatar
  • 13.7k
8 votes
1 answer
454 views

The entropy of a partition of unity

A partition of unity can be thought of as a blurred out set partition: identify the fibers of the set partition with their indicator functions; the sum of these indicators is $1$. I would like to ...
Yakov Shklarov's user avatar
2 votes
0 answers
656 views

Linear independence of Vandermonde matrix in systematic Reed-Solomon code

My question is about using a Vandermonde matrix vs a Cauchy matrix in erasure coding. In the Reed-Solomon (RS) code, encoding is done by multiplying a $N\times K$ ($N>K$) matrix with the code words ...
Avi's user avatar
  • 21
2 votes
0 answers
76 views

Finding k elements with count queries

Given a 'count in range' query access to an array of $N$ elements, our goal is to find $K$ missing elements with as few queries as possible (worst case, deterministic). To clarify, we can query how ...
Mar Blonde's user avatar
0 votes
1 answer
237 views

Entropy of a refinement of a partition

We consider a probability space $(X, B, \mu)$. Let $\alpha$ and $\beta$ be countable partitions of X. We suppose $\beta$ is a refinement of $\alpha$, ie that every set in $\alpha$ is a union of sets ...
catbow's user avatar
  • 41
6 votes
2 answers
450 views

Shannon entropy and doubly stochastic matrices

Suppose that $A$ is a stochastic matrix. We know that if $A$ is doubly stochastic, then $H(Ap)\geq H(p)$ where $H$ is Shannon entropy and $p$ is a probability vector. Is the converse true? i.e., if $H(...
Aram's user avatar
  • 109
9 votes
0 answers
442 views

Measuring the randomness of texts

The question concerns statistic properties of random words in a finite alphabet $A$. By $A^{<\omega}$ we denote the set of all words in the alphabet $A$, i.e. finite sequences of elements of $A$. ...
Taras Banakh's user avatar
  • 40.8k
2 votes
0 answers
226 views

An inequality of KL Divergence for two different distributions passing through a same channel

Let $X$ be a random variable which takes values in $\mathcal{X}$. Assume that we pass $X$ through two independent conditional pdf $p_{X_1|X}$ and $p_{X_2|X}$ and choose $X_1$ with probability $\lambda$...
Math_Y's user avatar
  • 311
6 votes
1 answer
157 views

Smallest $\mathrm{D}(Q\|P)$ given fixed marginals $\mathrm{D}(Q_X\|P_X)$ and $\mathrm{D}(Q_Y\|P_Y)$

Let $P$ be a distribution on a set $U\times V$ with marginal distributions $P_X$ and $P_Y$. Suppose we have two values $d_x, d_y\in\mathbb R$, and we want to find the distribution $Q$ absolutely ...
Thomas Dybdahl Ahle's user avatar
1 vote
1 answer
127 views

How much reduction in expected variance can we get from a single bit?

Consider the following protocol: Alice has a number $X$, chosen according to a known distribution $\mathcal D$ (e.g., $X\sim U[0,1]$). She can send a bit to Bob, giving him more information about $X$ (...
M A's user avatar
  • 127
3 votes
1 answer
245 views

Trace entropies

I'm studying relationships between trace entropy functionals and combinatorics and I'm faced with the following problem. Lets $\mathcal {D}$ be the following differential operator $1 -x\cdot \cfrac{d}{...
Gianfranco's user avatar
5 votes
1 answer
204 views

Information density of proofs?

I am a CS person so please excuse the hand-waving. Given a set of machine-represented proofs, each different (but not necessarily proving a different thing), what sort of information-theoretic ...
user318904's user avatar
1 vote
0 answers
194 views

A new notion of probability coupling

Let $X$ and $Y$ be two discrete random variables distributed according to $\mu$ and $\nu$, respectively. Consider the following optimization problems $$\inf_{\pi\in \Pi(\mu, \nu)}\Pr(X\neq Y),$$ ...
math-Student's user avatar
  • 1,109

1 2
3
4 5
13