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
4
votes
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
2answers
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
1answer
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
1answer
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
3answers
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
1answer
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
0answers
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
1answer
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
0answers
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
3answers
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
0answers
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
2answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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)...

1
2 3 4 5
10