Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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