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
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 ...
JohnA's user avatar
  • 680
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 ...
Georg Pichler's user avatar
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 ...
lesnik's user avatar
  • 153
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(...
Abhishek Shetty's user avatar
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 ...
seba's user avatar
  • 170
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 "...
Ant's user avatar
  • 361
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$, ...
Josh Brown Kramer's user avatar
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 ...
Lwins's user avatar
  • 1,531
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 ...
Lwins's user avatar
  • 1,531
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 ...
Aidan Rocke's user avatar
  • 3,827
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 ...
Lwins's user avatar
  • 1,531
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 $\...
David Lehavi's user avatar
  • 4,299
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{...
Math_Y's user avatar
  • 311
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:...
Lwins's user avatar
  • 1,531
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 ...
Turbo's user avatar
  • 13.7k
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 ...
Turbo's user avatar
  • 13.7k
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,...
mvc's user avatar
  • 153
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 $$ -\...
Lwins's user avatar
  • 1,531
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}...
Lwins's user avatar
  • 1,531
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 ...
XL _At_Here_There's user avatar
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 ...
aduh's user avatar
  • 839
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} \...
R.G.'s user avatar
  • 121
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\...
boinkboink's user avatar
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 ...
Cauchy's user avatar
  • 153
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 ...
john mangual's user avatar
  • 22.6k
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 ...
Vanessa's user avatar
  • 1,368
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 ...
Sung-En Chiu's user avatar
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 ...
Turbo's user avatar
  • 13.7k
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 ...
Henry.L's user avatar
  • 7,951
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 \...
Daniel Miller's user avatar
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 ...
Henry.L's user avatar
  • 7,951
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 ...
DSblizzard's user avatar
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 ...
Paul Siegel's user avatar
  • 28.8k
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 ${\...
F Researcher's user avatar
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 ...
Turbo's user avatar
  • 13.7k
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 ...
Christian Chapman's user avatar
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 ...
Sancho Panza's user avatar
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 ...
groupoid's user avatar
  • 580
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 ...
Iconoclast's user avatar
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 ...
groupoid's user avatar
  • 580
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 \...
user avatar
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 ...
momeara's user avatar
  • 211
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 $\...
MObremski's user avatar
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{...
Tom Steiglitz's user avatar
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 ...
Theo Johnson-Freyd's user avatar
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 ...
PianoEntropy's user avatar
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 ...
ABIM's user avatar
  • 5,019
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}...
Shishir Pandey's user avatar
-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 ...
john mangual's user avatar
  • 22.6k
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 $\...
Chill2Macht's user avatar
  • 2,622

1
4 5
6
7 8
13