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.
604
questions
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 '...
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 ...
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, ...
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 ...
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} \...
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)$ ...
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}...
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 \...
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 ...
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 ...
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}=\...
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 ...
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 ...
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\...
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 ...
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 $\...
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 ...
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\...
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 $...
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) :...
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 ...
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 \...
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(\...
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 ...
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)=\...
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}$ ...
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 $(...
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'...
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.
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 ...
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$...
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 ...
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 ...
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?
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 ...
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:
...
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 ...
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 ...
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 ...
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 ...
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 ...
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(...
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$.
...
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$...
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 ...
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$ (...
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}{...
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 ...
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),$$
...