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
8
votes
2
answers
3k
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
47
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
282
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
118
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
77
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 ...
8
votes
0
answers
956
views
How to prove that the KL divergence is increasing with more noise
Assume I have a continuous 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
49
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$, ...
2
votes
0
answers
159
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 ...
3
votes
1
answer
221
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
261
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
125
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 ...
4
votes
1
answer
122
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
326
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
174
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:...
2
votes
1
answer
161
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
144
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
115
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,...
1
vote
0
answers
115
views
Minimal entropy with constraint on $2$-norm: Finding reference
Suppose $p_1,p_2,\dots,p_n \in [0,1]$ and they satisfies
$$ \sum_{j=1}^n p_j = 1 $$
and
$$ \sum_{j=1}^n p_j^2 = C $$
with a given constant $C \in [1/n,1]$. The problem is to find the minimum of
$$ -\...
1
vote
1
answer
153
views
Minimize average bitwise entropy with given pairwise hamming distance
Suppose we have $n$ strings (or vectors) $a_1, a_2, \dots, a_n \in A^m$, where $A$ is an arbitrary set satisfies $|A| \geq n$. And we limit their pairwise hamming distance by
$$ d(a_i, a_j) \geq d_{ij}...
8
votes
1
answer
2k
views
What is the precise relation between Kolmogorov complexity and Shannon's entropy?
Consider the discrete case:
Shannon's entropy is $H(x)=-\sum\limits_i^n p(x_i) log\space p(x_i)$.
Probability based on prefix-free Kolmogorov complexity is $R(x_i)=2^{-K(x_i)}$ where $K(x_i)$ is ...
4
votes
1
answer
315
views
Measure of the rate of convergence for filtration and conditional expectations
This question is cross-posted at MSE with a soon to expire bounty that hasn't generated much discussion.
Let $(\Omega, \mathcal{F},P)$ be a probability space and $(\mathcal{F}_n)_n$ a filtration that ...
2
votes
0
answers
148
views
Min Max Equality in Information Theory
Let $\mathcal{Y}$ and $\mathcal{X}$ be finite sets and let $Q_Y$ be a fixed probability mass function on $\mathcal{Y}$. Also, let $P_{X | Y}$ be some fixed conditional distribution on $\mathcal{X} \...
3
votes
1
answer
347
views
Entropy of average of two distributions
Let $\mu,\nu$ be two distributions on the same discrete space. Is it true that
$$\mathrm{H}\left(\frac{\mu+\nu}{2}\right) \ge \mathbb{E}_{xy}-\log\left(\frac{\sqrt{\mu(x)\nu(y)}}{2} + \frac{\langle\...
4
votes
0
answers
727
views
KL Divergence - Convolution of distributions
Assume $P_1,P_2,P_3$ different to each other pmfs. We would like to find an upper bound for $D_{\text{KL}}(P_1\ast P_3||P_2 \ast P_3)$, where $D_{KL}$ is the Kullback-Leibler divergence and $*$ is ...
2
votes
0
answers
260
views
What are the best current bounds on $\times a \times b$?
Let $a,b \in \mathbb{N}_{\ge 2}$ be two integers that are multiplicatively independent (i.e., are not powers of the same integer). I have seen (Bourgain, Lindenstrauss, Michel, Venkatesh: Some ...
1
vote
1
answer
173
views
Sum of information gains is almost surely convergent?
Let $(\Omega,\mathcal{F},P)$ be a probability space, $\{\mathcal{F}_n \subseteq \mathcal{F}\}_{n \in \mathbb{N}}$ an increasing filtration, $S$ a finite set and $X: \Omega \rightarrow S$ a random ...
6
votes
1
answer
2k
views
Minimizing KL divergence: the asymmetry, when will the solution be the same?
The KL divergence between two distribution $p$ and $q$ is defined as
$$
D( q \| p)\int q(x)\log \frac{q(x)}{p(x)} dx
$$
and is known to be asymmetry: $D(q\|p)\neq D(p\|q)$.
If we fix $p$ and try to ...
3
votes
1
answer
534
views
Lovasz theta and circulant graphs
Let $\theta(G)$ denote Shannon zero error capacity of graph $G$ and $\vartheta(G)$ be Lovasz upper bound for $\theta(G)$.
Let $C_{2n+1}$ denote cycle graph with $2n+1$ nodes.
We know following two ...
14
votes
1
answer
3k
views
How is the "conformal prediction" conformal?
The question is clarified by Prof.V.Vovk. See his answer below for discussion.
Recently, early works of Gammerman, Vanpnik and Vovk[4] are rediscovered by Wasserman et.al[1] and proposed it as a ...
2
votes
1
answer
247
views
Distribution-free statistics on compact Lie groups
(Cross-listed from the math stackexchange)
Let $(X_i)_{i=1}^n$ be iid random variables with joint cdf $F$. Recall that the empirical distribution function is:
$$
F_n(x) = \frac{1}{n} \sum_{i=1}^n \...
9
votes
1
answer
901
views
A necessary condition for differential entropy to be finite
An ensemble corresponding to a probability distribution usually has finite free energy so it is not a great loss of generality to assume that the ensemble also has finite energy in following ...
0
votes
1
answer
161
views
Comparisons and sorting from point of view of information theory [closed]
Suppose we have list of numbers and make some comparisons. What is known about amount of information which we gain by certain comparisons, by certain sequences of comparisons? Is there algorithm which ...
17
votes
2
answers
912
views
Is there an axiomatic characterization of the entropy of a continuous random variable?
Let $X$ be a random variable taking values in $\{1,\ldots,n\}$, and let $p_i$ denote the probability of the event $\{X = i\}$. Shannon defined the entropy of $X$ to be the quantity
$$H(X) = -\sum_i ...
1
vote
0
answers
77
views
sufficient statistics that are irrelevant
I'm designing a lecture on hypothesis testing and want to do an example on a certain matter, but I cannot come up with a good one.
If we should decide upon $H_0$ or $H_1$ given observed data sets ${\...
2
votes
2
answers
279
views
On a number theoretic problem coming from multiuser coding?
Can Chinese remainder theorem be used to solve this problem in multiuser coding?
We have two transmitters sending integers $q,q'>0$ to a common receiver. The duty of the receiver is to recover ...
4
votes
1
answer
506
views
Backwards random codebook generation
$$X \longrightarrow \fbox{$\phantom{\int}P_{Y|X}\phantom{\int}$}\longrightarrow Y$$
The information capacity of this channel is $C=\max_{P_X} I(X;Y)$. Any rate $C-\varepsilon$ can be achieved by ...
1
vote
0
answers
61
views
Cramer Rao bound for relative estimation
I have an observed vector ${\bf y}$ from which I would like to estimate a parameter vector ${\bf c}$ (denote the estimate $\hat{{\bf c}}$).
A feature of our estimation problem is that the involved ...
1
vote
0
answers
87
views
Approximating or calculating the mutual information of certain binary random vectors
In my studies of applied probability I have recently met the following problem on which I need help:
We consider two binary random (column) vectors $ X,Y \in \{0,1\}^d $ where the mutual ...
1
vote
0
answers
89
views
Rate Distortion Function for a Particular Gaussian Field
I need to compute the rate distortion function for a random field $g(t,x)$ that arises in Geophysical modelling and that is defined below.
Let $\rho$ be zero-mean Gaussian random process with a ...
1
vote
0
answers
58
views
A possible extension of the information bottleneck principle with added equality constraint on the conditional probability
This question is related to research on Tishby's information bottleneck principle as seen here, the problem at hand is inherently an optimization problem as seen directly on page 7 section 3.2, my ...
1
vote
1
answer
458
views
Data processing inequality
Let $X,Y$ be continuous random variables with $X$ defined over $\mathcal{A}$, and let $f: \mathcal{A} \to \mathcal{A}$, $g: \mathcal{A} \to \mathcal{A}$ be any functions. Is it true that
$$
I(Y;f \...
3
votes
0
answers
214
views
Partial information decomposition for tangle machines
In (Williams and Beer, 2010), they define the partial information decomposition (PID) as a generalization of Shannon's Mutual Information for multiple information sources. Their key insight is that ...
9
votes
1
answer
624
views
Inner product over finite fields
Let $F$ be a finite field,
For every $c \in F$, let $X_1, X_2,..., X_9, Y_1,..., Y_9$ be independent non-zero random variables over $F$.
Denote $X=(X_1,...,X_9)$, $Y=(Y_1,...,Y_9)$, also let $\...
2
votes
0
answers
143
views
variational calculus problem
I have two functions $f_1(x)$ and $f_2(x)$ defined for $0\leq x \leq 1$.
Let $$L^HL = \left[\begin{array}{cc} 1 & \rho \\ \rho & 1\end{array} \right].$$
Define $$R(x) = \log\left(1 + \frac{...
4
votes
2
answers
448
views
Self-dual binary codes of Hamming weight divisible by 8?
Recall that a binary code is a subgroup $C \subset \mathbb F_2^n$; the elements of $C$ are called code words. The Hamming weight of a code word $c\in C$ is the number of $1$s in it. A binary code is ...
4
votes
2
answers
3k
views
Entropy of the multinomial distribution
What is the entropy of the multinomial distribution? To fix notation, let us define $n > 0$ as the number of trials, $p_1, \ldots, p_k$ as the probabilities of each of the $k$ possible outcomes and ...
2
votes
0
answers
52
views
Minimizer of a class of SDEs
Setup
Let $\mathscr{H}$ be a separable Hilbert space, $\mathcal{X}\triangleq \langle \Omega,\mathscr{F},\mathscr{F}_t,\mathbb{P}\rangle$ be a stochastic base and $X_t$ be an $H$-valued stochastic ...
3
votes
0
answers
144
views
How are these two multi-armed bandit problems similar?
I am reading the multi-armed bandit survey by Bubeck and Bianchi. This question is for the lower bound section (2.3) of the survey.
Let us define Kullback-Leibler divergence $kl(p, q) = p \log \frac{p}...
-4
votes
1
answer
283
views
categorification of the $\Gamma$ function? [closed]
Is there a combinatorial or information-theoretical meaning to $\Gamma(\frac{1}{2})=\sqrt{\pi}$ ?
The identity $\Gamma(n+1)=\int_0^\infty x^{n+1} e^{-x} \, dx = n!$ suggests something is being ...
3
votes
0
answers
399
views
When is the entropy of a $\sigma$-algebra finite?
Let two (countably-generated) $\sigma-$algebras $\mathscr{F,G}$ on the event space $\mathbb{R}$ be given. I believe we also need the atoms of $\mathscr{F,G}$ to be the points of $\mathbb{R}$.
Let $\...