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
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 ...
Phobos's user avatar
  • 131
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)=...
Thomas Dybdahl Ahle's user avatar
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-...
mw19930312's user avatar
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, ...
Ryan's user avatar
  • 176
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 ...
Gro-Tsen's user avatar
  • 29.8k
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 ...
usercsw's user avatar
  • 41
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$?
Christian Chapman's user avatar
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)$...
ABIM's user avatar
  • 5,019
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, ...
inhaler18's user avatar
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{\...
Apprentice's user avatar
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]$....
Apprentice's user avatar
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(...
Student88's user avatar
  • 503
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 ...
Chetan Waghela's user avatar
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 \...
Bartosz Bartmanski's user avatar
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 ...
user124784's user avatar
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 ...
Bane Williams's user avatar
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 ...
Yi Huang's user avatar
  • 333
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$?
Saber Saleh's user avatar
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 ...
dohmatob's user avatar
  • 6,716
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 ...
user1388672's user avatar
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 ...
sbnietert's user avatar
  • 103
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$...
Ben Sprott's user avatar
  • 1,281
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 ...
James Propp's user avatar
  • 19.4k
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 ...
Ioannis Papoutsidakis's user avatar
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 ...
user avatar
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 ...
minimore99's user avatar
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)) = ...
minimore99's user avatar
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 ...
tnecniv's user avatar
  • 11
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 ...
Santiago Gil's user avatar
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 $\...
dohmatob's user avatar
  • 6,716
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 ...
Rui Zhao's user avatar
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$ ...
Andy's user avatar
  • 515
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$, $...
Hans's user avatar
  • 2,169
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 ...
More Anonymous's user avatar
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)}\\ & =\...
doubleG's user avatar
  • 11
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'(...
Cesare's user avatar
  • 189
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^{\...
nico's user avatar
  • 91
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 ...
ABIM's user avatar
  • 5,019
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$. ...
Turbo's user avatar
  • 13.7k
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(...
Cesare's user avatar
  • 189
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 ...
Narutaka OZAWA's user avatar
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 ...
Xi Chen's user avatar
  • 31
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 $\...
Penelope Benenati's user avatar
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{...
tmh's user avatar
  • 685
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{\...
Sam's user avatar
  • 11
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 ...
AChem's user avatar
  • 803
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 ...
Turbo's user avatar
  • 13.7k
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 ...
Turbo's user avatar
  • 13.7k
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 ...
Turbo's user avatar
  • 13.7k

1 2 3
4
5
13