# 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.

**6**

votes

**0**answers

148 views

### How sensitive are Neural Networks to weight change?

Let's consider the space of feedforward neural networks with a given structure: $L$ layers, $m$ neurones per layer, ReLu activation, input dimension $d$, output dimension $k$.
Which means I'm ...

**2**

votes

**0**answers

79 views

### The typical amount of lattice points in a set as dimension goes off to infinity

I have encountered a geometry-of-numbers-type problem when calculating an entropy in a lattice communications scheme:
$L^{(n)}$ is a lattice uniform over all those in $\mathbb{R}^n$ with base ...

**5**

votes

**1**answer

165 views

### Relation between the two possible KL divergences of two distributions

Given that I know $$D\left(P\parallel Q\right)<\alpha,$$ can I say anything about $D\left(Q\parallel P\right)$ in terms of an upper bound on it?
Also, given this upper bound on $D\left(P\parallel ...

**3**

votes

**0**answers

72 views

### Upper bounding the start of a distribution's CDF, given bounds on first moments

Take nonnegative random variables $X$ whose first $K$ moments have bounds:
$\mu^k\leq E[X^k]\leq c\mu^k$ for each $k=1,\dots,K$.
In this case what is an upper bound for $P(X\leq O(\mu))$?
I am ...

**2**

votes

**0**answers

39 views

### Enumerating lattice points in a product of balls, in limit with dimension

Fix $(L_n)_n$ to be a sequence of lattices, each $L_n\subset \mathbb{R}^n$, where both the effective-inradius and effective-outradius go to 1 (i.e. the Voronoi region of the lattices approach a ball ...

**4**

votes

**0**answers

188 views

### Is there a theory behind these puzzles? (communicating by modifying data)

Consider the following puzzles:
Problem 1: Alice is given two data by Zora: a binary string $w$ of length $2^r$, and a position $p$ in the string (which we can view as an integer $0\leq p<2^r$). ...

**2**

votes

**4**answers

229 views

### Apply doubly stochastic matrix M to a probability vector, then entropy increases?

Consider a vector $p =(p_1,...p_n)$, $p_i>0$, $\sum p_i = 1$
and a matrix $M_{ij}$, which is doubly stochastic: $\sum_i M_{ij} = 1, \sum_j M_{ij} = 1, M_{ij} > 0$.
Question 1 Just apply ...

**0**

votes

**0**answers

44 views

### Does lattice mod preserve direction?

For high enough dimension $n$ there are lattices $L_n$ in $\mathbb{R}^n$ whose Voronoi partition's base regions encompass all but a negligible proportion of a $(1-\varepsilon)$-ball, and also nearly ...

**0**

votes

**1**answer

110 views

### Shannon problem

Since a few days, I try in my research to model / formalize a source of Shannon a little weird, and I can't do it at all. First of all, I explain to you its operating principle and then I describe it ...

**2**

votes

**1**answer

70 views

### upper bound on power of neyman-pearson hypothesis test

Let $H_0$ and $H_1$ be two distributions. The Neyman-Pearson lemma says that of all rejection regions $R$ with fixed probability $\alpha$ under $H_0$, the one with maximal probability under $H_1$ is ...

**1**

vote

**0**answers

95 views

### Error correcting codes via random matrices: How close to the Shannon bound?

I have a vague and probably rather naive question on error correcting codes.
Suppose we want to encode binary vectors of length $k$ as binary vectors of length $n$ in such a way that differences of ...

**2**

votes

**0**answers

57 views

### What are the moments of Kolmogorov Complexity for a Random Variable?

Given a random variable $X$ distributed under some computable distribution $P$ we have,
$$0 \le E[K(X)] - H(P) \le K(P)$$
Where $H(P)$ is the entropy of $P$. I tried using Hoeffding concentration ...

**5**

votes

**0**answers

140 views

### Characterization of KL divergence for continuous variables?

This is an analog of an older question:
What characterizations of relative information are known?
With the modification that I’m interested in the case when the distribution is over something that’s ...

**2**

votes

**0**answers

83 views

### Covering a sphere with ellipsoid-products in high dimension

For $\Sigma\geq 0$ a $k\times k$ matrix and large $n$, fix $E:= \{(x_i)_{i=1}^n: \sum_i x_i^\dagger \Sigma x_i \leq n\}$. Fix $(z_m)_m$ as $M$ points iid uniform on $\mathbb{S}^{nk-1}\subset \mathbb{...

**10**

votes

**3**answers

561 views

### Entropy and total variation distance

Let $X$, $Y$ be discrete random variables taking values within the same set of $N$ elements. Let the total variation distance $|P-Q|$ (which is half the $L_1$ distance between the distributions of $P$ ...

**2**

votes

**0**answers

75 views

### Matrix Chernoff sampling with out replacement

I am interested to know if the matrix Chernoff bound (see Theorem 5.1.1 in https://arxiv.org/pdf/1501.01571.pdf) holds if one samples without replacement.
For example, the Bernstein inequality is ...

**9**

votes

**1**answer

464 views

### Is KL divergence $D(P||Q)$ strongly convex over $P$ in infinite dimension

By KL divergence I mean $D(P||Q) = \int dP \log(\frac{dP}{dQ})$. I am looking for the conditions under which this strong convexity is true and possible references. I could not find an answer for ...

**4**

votes

**2**answers

146 views

### Can the differential entropy of a continuous distribution with lebesgue integrable density be negative infinity?

Define the (differential) entropy for a density $f$ as
$$ H(f) :=-\int_{0}^{1} f(x) \log_{2}(f(x)) dx \, .$$
I am trying to find a $f \in L_{1}([0,1])$ such that $f\geq 0, \int_{0}^{1} f(x) dx = 1$...

**3**

votes

**1**answer

238 views

### Is there an integer-valued analogue of information entropy?

Let $H_n : (\langle 0,1 \rangle \cap \mathbb{Q})^n \to \langle 0,\log_2 n \rangle, \; H_n(P) = -\sum_{i=1}^n P_i \log_2 P_i, \; \sum_i P_i = 1$ be the information entropy on rationals. I am looking ...

**5**

votes

**5**answers

372 views

### Reviews of Probability in High Dimension not by Van Handel

I'm completely in love with Ramon van Handel's lecture notes Probability in High Dimension and I would like to find more learning resources. Lecture notes or reviews would be ideal as anything in this ...

**6**

votes

**1**answer

193 views

### What is the relationship between the Fisher Information and the Fisher Information metric?

It seems that there are two separate definitions for the Fisher information, and I'm wondering if there is some relationship between the two.
The first is the so-called Fisher information which ...

**7**

votes

**3**answers

350 views

### Expected cardinality of a randomly chosen element of the family of subsets of $\{1,\ldots,n\}$ with at most $k$-elements

Assume that $1\le k \le n$ and let $\mathscr{Z}$ be the family of all subsets of $\{1,\ldots,n\}$ with at most $k$ elements. Pick a random element $X$ of $\mathscr{Z}$ (we consider the probablity ...

**1**

vote

**1**answer

139 views

### Maximizing mutual information between two linearly projected random variables

Consider continous random variable $X$ with bounded support $\mathcal{X} \subset \mathbb{R}$, discrete random variable $Y$ with finite support $\mathcal{Y}$ , and constants $c_1 ,c_2 \in \mathbb{R}$. ...

**0**

votes

**0**answers

45 views

### Optimization of generalized Fisher information over space of probability measures

Assume we already have $p(\theta)$ apriori desnsity function about unknown parameter $\theta$, and we consider an optimization problem as follows:
\begin{equation} \max_{P \in \mathcal{M}} \int_{\...

**3**

votes

**0**answers

140 views

### Partitioning the coupons collected in the classical coupon collector's problem

Suppose that there is an urn containing $n$ different coupons, from which $m$ coupons are being collected, equally likely, with replacement.
Let $C(m)$ be the whole set of the $m$ collected coupons. ...

**0**

votes

**0**answers

79 views

### Conditional Mutual Information of the Sum of Random Variables

Consider the discrete random variables $X,Y,Z,W$, where $Y$ and $W$ are independent. Let $Y = f(X)$, for some function $f(\cdot)$, $Z=Y+W$, and $X \rightarrow Y \rightarrow Z$ be a Markov chain.
By ...

**4**

votes

**1**answer

232 views

### Combinatorial computational problem about 0-1 vectors and sampling algorithms

Let $M \in \{0,1\}^{m\times n}$, where $n\gg 1$ and $m\le n$. A procedure consisting of the following three steps is repeated $t\gg 1$ times:
A row $\require{amsmath} \boldsymbol{r}$ of $M$ picked in ...

**4**

votes

**0**answers

213 views

### Maximazing the joint entropy given the probability of equality

Consider 2 independent random variables $X$ and $Y$ with values in $A=\{0, 1, \ldots, q-1\}$. Suppose that $P(X=Y)$ is equal to some constant $\varepsilon$.
What is the maximal entropy $H(X, Y)$?
At ...

**5**

votes

**0**answers

187 views

### A conjecture in rate distortion theory and stochastic filtering

Let $(X_t)_{t\in T}$ be a stationary random process with known and fixed law $P_X$ describing a dynamic source.
This source is to be encoded real-time by an encoder $e$ into an encoded message $E_t$ ...

**0**

votes

**0**answers

150 views

### Can we make two random variables independent at a low cost?

Let $X$ and $Y$ be two discrete random variables with joint probability mass function $p(x,y)$ such that
$$\|p(x,y)-p(x)p(y)\|_1=\sum_{x\in\mathcal{X},y\in\mathcal{Y}}|p(x,y)-p(x)p(y)|\leq\epsilon$$
...

**1**

vote

**1**answer

82 views

### $\phi$ - Entropies - $\phi$ - Divergences and classical entropy recovery

The $\phi$ entropy is defined as $\text{Ent}_{\phi}[X]= \mathbb{E}[\phi (X)]-\phi(\mathbb{E}[ X])$ where $X$ is a random variabel and $\phi$ is a convex function ($\text{Ent}_{\phi}[X] \geq 0$). By ...

**1**

vote

**0**answers

210 views

### What is the maximum entropy distribution over the integers

Let $μ=0,σ>0$. What is the maximum entropy distribution over the integers with mean $μ$ and variance $σ^2$?
Is Skellam distribution a maximum entropy distribution? Is there a closed-form ...

**8**

votes

**2**answers

765 views

### Lower bounds on Kullback-Leibler divergence

This was originally a question on Cross Validated.
Are there any (nontrivial) lower bounds on the Kullback-Leibler divergence $KL(f\Vert g)$ between two measures / densities?
Informally, I am ...

**2**

votes

**0**answers

40 views

### Do averaged binary symmetric channels maximize mutual information?

This is a refined version of Do binary symmetric channels maximize mutual information?, which was answered negatively.
Let the random variables $(X, Y)$ be a doubly symmetric binary source with ...

**5**

votes

**1**answer

145 views

### Is there an information exchange in this game? (Bell's inequality)

This question concerns quantum mechanics experiment. But I believe it belongs here, on MathOverflow.
So, we have two players. They play a simple game and either both win or both loose, so they ...

**1**

vote

**0**answers

93 views

### Bounds on Rate of Entropy Production

Consider a real-valued random variable $X$ with mean $0$ and variance $1$ and let $Z$ be an independent standard Gaussian random variable. Now consider the stochastic process $Y(t) = \sin(t) X + \cos(...

**1**

vote

**2**answers

59 views

### Is there a feasible way to compute the number of steps between two sequences generated by a linear feedback-shift register?

Consider a full-period LSFR with a feedback polynomial of degree n. In the cyclic sequence generated by the LSFR, each n-bit sequence appears exactly once. Given two n-bit sequences, one can define ...

**4**

votes

**0**answers

207 views

### How to prove that the KL divergence is increasing with more noise

Assume I have a continuos random variable $X$, whose support is all $\mathbb R$. Let $Z$ be a standard normal independent on $X$, and let
$$Y = X + \sigma Z$$
$Y$ essentially is equal to $X$ plus "...

**1**

vote

**0**answers

35 views

### Subset with largest information gain [closed]

I am competing in a programming contest where the submission phase can be stated abstractly as follows : There is a known universe set, $U$, and a hidden target $T \subset U$. I submit $S \subset U$, ...

**1**

vote

**0**answers

123 views

### 1-bit binary secret sharing

As we know, a $(t,r,n)$-ramp scheme is described by means of two thresholds $t$ and $r$. Every set with at most $t$ participants is forbidden, while every set with at least $r$ participants is ...

**0**

votes

**0**answers

60 views

### On expected intersection of typical lattice with tensor product of cubes?

Consider $T$ tensor product of $t$ origin centered boxes $$\underbrace{[-m_i,m_i]\times\dots\times[-m_i,m_i]}_{n_i\mbox{ times}}$$ each in $\Bbb R^{n_i}$ where $i\in\{1,2,\dots,t\}$ holds.
If we ...

**3**

votes

**1**answer

171 views

### Finding a short proof for a certain information theoretic inequality

The following information theoretic inequality is needed in my work.
Let $n, m, n_1, n_2, \dots, n_k \in \mathbb{Z}^+$ such that $m < n = n_1 + n_2 + \dots + n_k$. I would like to prove that with ...

**1**

vote

**2**answers

210 views

### A corollary of Gibbs' inequality

Gibbs' inequality is equivalent to:
\begin{equation}
\sum_{i} \ln q_i^{p_i}-\ln p_i^{p_i} \leq 0
\end{equation}
where $p_i,q_i \in [0,1]$ and $\sum_i p_i = \sum_i q_i=1$.
Now, a friend of mine ...

**2**

votes

**1**answer

88 views

### Derive a theoretical bound about coding with a partial eavesdropper

This post is improved from Determine binary function $f(x)$ by partial observation of $x$. Since the form of the problem is changed in a great extent. I would like to create a new post rather than ...

**3**

votes

**1**answer

60 views

### minimum information distribution given moments of its square

Given constants $m_0,\ldots m_n$ and a measure $\mu$ on $\mathbb{R}$, how can I "recover" the integrals $\int f x^n d\mu$ of the maximum entropy distribution $f\in L^2(\mathbb{R})$ which satisfies $\...

**3**

votes

**1**answer

287 views

### Does this probability distance metric have an official name?

Let us define a distance metric between two joint probability math functions $p(x,y)$ and $q(x,y)$ as in the following
\begin{align}
\sum_{y}\sqrt{\sum_{x}p(x)\left(p(y|x)-q(y|x)\right)^2}.
\end{...

**4**

votes

**0**answers

165 views

### Determine binary function $f(x)$ by partial observation of $x$

Let $\boldsymbol{x} = (\boldsymbol{x}_1, \dots, \boldsymbol{x}_n)$ be a $n$-dimensional random vector on $\mathbb{R}$ (i.e. $\boldsymbol{x}$ is a random variable). Suppose we have a binary function
$f:...

**1**

vote

**1**answer

135 views

### On Shannon information theoretic capacity to coding distance metric translation

Shannon theory says that given a channel source variable $X$ and received variable $Y$ and channel $Y/X$ there is a capacity associated with this channel.
The notion of maximum likelihood leads from ...

**3**

votes

**0**answers

134 views

### How much can analogy between $\Bbb Z$ and $\Bbb F_q[t]$ work out to give better distance measures in information theory?

Let $x$ be transmitted symbol and $y$ be received symbol and $n$ be noise Given $y=x+n$ where symbols $x,y,n$ are in $\Bbb K$. If $\Bbb K=\Bbb Z$ then we take $|n|$ to be the magnitude of noise while ...

**1**

vote

**1**answer

70 views

### Conformal prediction for the case of single tailed events

I'll start with a motivating example and only then proceed to the question.
Consider a list of total packages of milk that were purchased on 9 consecutive days on a given store,
$z_1,\ldots,z_9 = 1,...