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
2
votes
1
answer
168
views
Conditional entropy - solve example
Given a random variable $X$ that is uniformly distributed on $[-b,b]$ and $Y=g(X)$ with
$$g(x) = \begin{cases} 0, ~~~ x\in [-c,c] \\ x, ~~~ \text{else}\end{cases}$$
Now I want to compute the ...
2
votes
1
answer
105
views
Strong Data Processing Inequality for capped channels
Let $X$ and $Y$ be two $\rho$ correlated Gaussian vectors, such that $X,Y\sim N(0,1)^n$ and $E[X_iY_i]=\rho$.
Let $M_X = f(X)$ and $M_Y = f(Y)$ be $k$-bit functions of $X$ and $Y$, that is $H(X)=H(Y)=...
2
votes
1
answer
255
views
Information theory for uncountably infinite-dimensional continuous random variable
I'm exploring the possibility to apply information theory on an uncountably infinite-dimensional scenario. I found the concept of generalized entropy for continuous random variables defined on finite-...
0
votes
0
answers
372
views
Is there a difference between using nats and bits to express entropy?
It seems to me like questions involving decimal vs binary representations of some number are not particularly interesting: for instance $\pi$ or $\sqrt{2}$ are conjectured to be normal in every base, ...
5
votes
1
answer
840
views
Books to develop a deep understanding of Algorithmic Information Theory?
I'm mathematical physicist working with hydrodynamics modelling. Recently, I had to turn to modelling of flows with particles and some questions I have I think are related to Algorithmic Information ...
8
votes
3
answers
397
views
Identifying a subset with as few tests as possible
Informal description: You are given a set of $n$ blood samples, each having probability $p$ of being infected with a disease. Your goal is to determine the set $P$ of infected samples with as few ...
4
votes
1
answer
199
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 ...
6
votes
1
answer
525
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(x))$. What is the min of $n^{-1}H(y^n|f(x^n))$ over maps $f$ with range $\lbrace 1,\dots,\exp nR\}$, taking $n\to \infty$?
1
vote
0
answers
170
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
484
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
193
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
2
answers
274
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
88
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(...
1
vote
1
answer
263
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 ...
2
votes
1
answer
109
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
228
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
148
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
168
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
100
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$?
2
votes
1
answer
264
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 ...
4
votes
1
answer
273
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 ...
6
votes
1
answer
655
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
268
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
328
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
126
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 ...
11
votes
0
answers
292
views
Entropy, magnitude, diversity of finite metric spaces in number theory
I was reading the article by Tom Leinster, (Maximizing
diversity in biology and beyond, arXiv link), and find it very interesting.
Since I was searching for entropies of finite metric spaces I found
...
2
votes
0
answers
363
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 ...
2
votes
1
answer
314
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
199
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 ...
8
votes
3
answers
1k
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
633
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
173
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
176
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
267
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
355
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
80
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
120
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'(...
5
votes
2
answers
1k
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^{\...
2
votes
1
answer
275
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 ...
29
votes
2
answers
3k
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
165
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(...
4
votes
0
answers
180
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
193
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
90
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 $\...
11
votes
1
answer
305
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
110
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{\...
3
votes
1
answer
615
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
73
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
145
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
181
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 ...