Skip to main content

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
1 vote
0 answers
28 views

From a constraint satisfaction problem (CSP) to a sudoku grid

one of the existing methods of solvin a sudoku grid is via constraints satisfaction (CSP), but can we do the inverse ie convert a CSP problem into a sudoku grid and then solve it ?
youssef Lmourabite's user avatar
0 votes
0 answers
13 views

Efficient compression techniques for low-rank matrix $A$ to maintain multiplication compatibility?

Suppose we have a large low-rank matrix $A$ and an input matrix $X$ (where $X$ is a tall, skinny matrix). We need to compute the product $AX$. To reduce computational cost and data transfer when ...
oleotiger's user avatar
1 vote
1 answer
68 views

Probabilistic 2D cellular automata with memory lifetime increasing like $e^{L^2}$

Consider 2-state probabilistic cellular automata on an $L\times L$ torus square lattice which has the all-$0$ and all-$1$ configurations as fixed points, thinking of something similar to Toom's rule ...
Andi Bauer's user avatar
  • 2,911
1 vote
1 answer
74 views

Channel Capacity & Dependency Graph

A single-input-single-output communication channel is to be used repetitively. Denote by $X_i \in \mathcal X$ the input at time $i$ and by $Y_i \in \mathcal Y$ the output at time $i$. Assume the ...
Euclid's user avatar
  • 15
0 votes
0 answers
11 views

What are examples of $\epsilon$-extractable uniform randomness $H_{\rm ext}^\epsilon(\cal P)$?

[Renner and Wolf 2004] introduces the notion of $\epsilon$-smooth Renyi entropies as $$H_\alpha^\epsilon(P) \equiv \frac{1}{1-\alpha} \inf_{Q\in \mathcal B^\epsilon(P)}\log\left(\sum_z Q(z)^\alpha\...
glS's user avatar
  • 340
1 vote
1 answer
125 views

trying to get intuition into why Cross Entropy will always be greater or equal to the Entropy

I understand what entropy measures and cross entropy is the same except it is uses another distribution $q$ to compare it against $p.$ Is it because the log function is concave down so the predictions ...
Chris Blodgett's user avatar
2 votes
0 answers
117 views

Exp-Hamming distance in $\{0,1\}^k$

Let integer $k>0$ and let $\{0,1\}^k$ denote the set of all $1\times k$-dim vectors whose every coordinate is eithor 0 or 1, for example, $(0,1,1,0,\dots,1,0,0,1)$. For any such vector $\alpha$, ...
bc a's user avatar
  • 155
0 votes
0 answers
164 views

About the monotonicity of the exponential entropy

This question was previously posted on MSE at About the monotonicity of the exponential entropy. In the paper The Unifying Frameworks of Information Measures the conditional exponential entropy (see ...
Upax's user avatar
  • 127
0 votes
0 answers
29 views

Does the definition of mixing time work for general non-Markovian processes?

A definition of the mixing time for Markov chains is given by \begin{equation} \tau_{\text{mix}}\equiv\inf{\{t>0: \sup_i\left\vert \frac{\boldsymbol{p}(t|p_j(0)=\delta_{ij})}{\boldsymbol{\pi}}-\...
Richard Ben's user avatar
3 votes
0 answers
55 views

Wasserstein bounds of interpolation measures

Assume we are given two densities, $p_0$ and $p_1$ on $\mathbb{R}^d$, and define (up to the normalization constant) the interpolation $p_t \propto p_0^{1-t} p_1^t$, which interpolates between $p_0$ ...
mathguy23123's user avatar
2 votes
1 answer
113 views

How to lower bound the absolute value of the difference of two Kullback-Leibler divergences given the constrains below?

Given that $\min (D[p_1||p_3],D[p_2||p_4])=a$, how to find a lower bound of the difference $\left \vert D[p_1\parallel p_2]-D[p_3\parallel p_4] \right\vert$ with respect to $a$? If the condition is ...
Richard Ben's user avatar
0 votes
0 answers
16 views

Position dependent service time in queue

Is there any literature for queuing analysis (waiting time, capacity etc.) of a queue with service time that depends on the position of the customer in the queue? I have encountered a problem where a ...
Ishan's user avatar
  • 13
1 vote
1 answer
69 views

Queues wait for other queues- A communication problem

I am working on a problem which involves a single server that requires multiple inputs to do a computation. Each of these inputs arrive as a Poisson process with rate $\lambda$. Hence, a situation ...
Ishan's user avatar
  • 13
0 votes
1 answer
90 views

Reverse Pinsker's inequality for smooth density classes

Suppose we are given a class of probability density functions $\mathcal{F}$ so that for every $f \in \mathcal{F}$ we have $\alpha \leq f \leq \beta$ for some positive $\alpha, \beta \in \mathbb{R}_+$ ...
spacetimewarp's user avatar
1 vote
0 answers
24 views

A network to transform/predict one probability distribution to another

I have a random variable of a particular density (e.g., normal), and a known probability distribution (e.g., mixture Gaussian). I used a simple KL measure to predict/transform one another. Now I need ...
user524691's user avatar
0 votes
0 answers
145 views

Optimal strategy of modified Mastermind game

The following game is a modified version of the popular game Mastermind described here in which you are only given information about the total correct guesses you have made, and nothing about how many ...
wjmccann's user avatar
  • 315
2 votes
0 answers
106 views

Information inequality for Renyi divergences

Let $X^1 \ldots X^n$ be random variables on $\mathbb{R}^d$ with an arbitrary joint probability distribution $\mu$ on $\mathbb{R}^{n \times d}$. Let $\nu = \nu^1 \times \ldots \times \nu^n$ be a ...
MatrixGeek1234's user avatar
0 votes
1 answer
122 views

Will the KL divergence between two distributions decrease after passing the fixed channel?

Suppose there are two continuous distributions whose pdfs are $p_1$ and $p_2$, defined on a common support $\mathcal{X}$. Suppose that there is a conditional pdf (the channel) $M:\mathcal{X}\times \...
jkfds's user avatar
  • 21
2 votes
0 answers
84 views

Joint lower semicontinuity of the Rényi divergence in all three arguments

Let $X$ be a standard Borel space (I'm already interested in the case where $X$ is finite, i.e., $X=\lbrace 1,\cdots,n\rbrace$). Let $P,Q$ be probability measures on $X$ such that $P\ll Q$. Then the ...
Lau's user avatar
  • 749
1 vote
1 answer
172 views

Inequalities involving entropy: quantum discord and mutual information

My question is inspired by the following paper of Olivier and Żurek but for this question to be self-contained I will recall all the necessary definitions: for a quantum state $\rho$ we define the ...
truebaran's user avatar
  • 9,210
2 votes
0 answers
81 views

Construct a Bregman divergence from Wasserstein distance

I was wondering whether one has studied the Bregman divergence arising from a squared Wasserstein distance. More precisely, let $\Omega\subset \mathbb{R}^d$ be a compact set and $c\in \Omega\times \...
John's user avatar
  • 483
3 votes
1 answer
128 views

Binary codes with upper and lower bound on pairwise distance

The Gilbert-Varshamov bound provides a lower bound for codes of length $n$ with minimum pairwise distance (say $\frac{n}8$). If we wish for the codes to also have pairwise distances bounded above (say ...
Stephen Jiang's user avatar
0 votes
1 answer
102 views

What's the lower bound for this quantity?

Suppose $p$ is a discrete distribution with $n$ values and the random variable $x$ satisfies $\mathbb{E}_p[x] = 0$ and $|x| < \infty$. Given $\alpha \in (0,1)$, does there exist a lower bound for ...
Jiacai Liu's user avatar
1 vote
0 answers
112 views

Sudden drop in complexity class due to the more general correlations

Recently I was asking about the impact of the groundbreaking result MIP*=RE on logic and proof theory (see this discussion). Surprising as it is I got confused with the following: MIP* is a ,,quantum''...
truebaran's user avatar
  • 9,210
2 votes
1 answer
262 views

Does this KL divergence inequality hold?

Suppose $p$ and $q$ are two discrete distributions. Given a positive constant $\beta\in(0,1)$, we create a new discrete distribution $y$ such that $$ \frac{y\left( x \right)}{p\left( x \right)}=\frac{\...
Jiacai Liu's user avatar
1 vote
0 answers
110 views

Generalization of error-correcting codes

If you have a binary single-error correcting code with n-bit codewords, then it is the case that taking only a fixed n-1 out of the n bits gives an “approximate” code with the property that, for any ...
Joe Shipman's user avatar
2 votes
1 answer
168 views

Estimating means of multiple Gaussians

Let's say we have two Gaussian distributions $\mathcal{N}(\mu_1, \sigma^2I_d)$ and $\mathcal{N}(\mu_2, \sigma^2I_d)$. We are trying to get estimators $\hat \mu_1, \hat \mu_2$ to minimize the following ...
Kumar Kshitij Patel's user avatar
0 votes
0 answers
76 views

Does there exist an established name for the exponential of surprisal (e.g. the reciprocal of probability?)

There are several different names that I know of for the exponential of the entropy of which "diversity" and "perplexity" are fairly well-established. Tom Leinster has a very ...
Mike Battaglia's user avatar
3 votes
2 answers
580 views

A general inequality for KL divergence of functions of variables

The question concerns a very general setting and a very general inequality about KL divergence. I'm writing this thread to verify whether my intuition is correct. Let $E_1, E_2$ be two measurable ...
Daniel Goc's user avatar
0 votes
0 answers
51 views

Classifier-specific lower bounds on the misclassification rate in binary classification

Consider a binary classification problem for $(X,Y)$, and let $\hat{f}$ be a proposed classifier. We wish to bound the misclassification rate $P(\hat{f}(X)\ne Y)$. There are many known lower bounds on ...
tim523's user avatar
  • 13
0 votes
0 answers
49 views

Sharpened versions of the Fisher information inequality?

Let $X, Y$ be two independent random vectors in $\mathbb{R}^d$. In the paper [1, see ineq. (11)], the following convolution inequality is proven for the Fisher information: $$ I(X + Y) \preceq \Big(I(...
Drew Brady's user avatar
2 votes
0 answers
68 views

What is an efficient non-adaptive group testing scheme if the number of defectives, $d$, grows proportionally to the number of items, $n$?

Suppose that for some $p \in \left(0, 1\right)$ and some $n \in \mathbb{N}$, we have $n$ independent Bernoulli random variables, $X_{1}, X_{2}, \dots, X_{n}$, each with mean $p$. We shall call $X_{1}, ...
Matthew Barber's user avatar
4 votes
1 answer
247 views

Does a subset with small cardinality represent the whole set?

Assume that we have heavy-tailed distribution $F(x)$ such that \begin{align} F(x)=\mathbb{P}[X\geq x]=x^{-0.5}. \end{align} Then, we produce $N$ independent samples $X_1,X_2,\ldots,X_N$ from this ...
Math_Y's user avatar
  • 311
3 votes
1 answer
195 views

Bound on an integral representing a difference of two relative entropies

Let $ f : [0,1] \to \mathbb{R} $ be a function satisfying: 1.) $ |f(x)| \leqslant a $ for some $ a < 1 $, and 2.) $ \int_0^1 f(x) {\mathrm d}x = 0 $. I would like to know whether the following ...
aleph's user avatar
  • 503
3 votes
1 answer
98 views

Question about equivalence of two expressions for the Quantum Fourier transformation

The Quantum Fourier transformation on $n$ qubits is just the discrete Fourier transformation, $$ |j \rangle \mapsto \frac 1 {\sqrt 2^n}\sum_{k=0}^{2^n-1}e^{2\pi ijk/2^n}|k\rangle. $$ In binary ...
Konrad Waldorf's user avatar
4 votes
2 answers
290 views

Effect of small change in probability distribution on error probability

Let $X$ be a random variable and $Y=f(X)$ where $f$ is a deterministic function. Moreover, assume that there exists a deterministic function $g(.)$ such that the following probability is small. \begin{...
Math_Y's user avatar
  • 311
2 votes
0 answers
106 views

Inequality for log-likelihood ratio

Let $ p, q $ be two probability densities on $ [0,1] $, strictly positive over $ (0,1) $. Let $ P $ be the cumulative function of $ p $, i.e., $ P(x) = \int_0^x p(x') \, \mathrm{d}x' $, $ x \in [0,1] $...
aleph's user avatar
  • 503
1 vote
1 answer
57 views

Upper bound of $I(Y; X_{1}, ..., X_{N})$ when we have $I(Y;X_{i}) < B$ for all $i$ $(1 \leq i \leq N)$

Let $I(Y;X)$ denote the mutual information between $Y$ and $X$. If we have $I(Y;X_{i}) < B$ for all $i \quad (1 \leq i \leq N)$, could we also get the upper-bound of $I(Y; X_{1}, X_{2}, ..., X_{N})...
Koukyosyumei's user avatar
0 votes
1 answer
112 views

Does the Plotkin bound mean that one can not achieve the Singleton bound asymptotically?

I am a little confused with the relationship between various bounds for error correcting codes. Does the Plotkin bound mean that one can not achieve the Singleton bound asymptotically? That is, is ...
liu_c_6's user avatar
  • 11
3 votes
1 answer
64 views

Bounding the difference of mutual information between input-output pairs

Let $X_1$ and $X_2$ be discrete random variables with distributions $p_{X_1}$ and $p_{X_2}$ such that the total variation distance between the two distributions is upper bounded by a constant $\delta$,...
Yuanxin Guo's user avatar
8 votes
1 answer
282 views

Lower bound $\int_0^1 \frac{|f'(x)|^2}{f} \,\mathrm{d} x$ by $\int_0^1 |f-1|^2\, \mathrm{d} x$

Assume that $f$ is a probability density on $x \in (0,1)$, I want to obtain a bound of the following form (if it is possible at all): $$ \int_0^1 \frac{|f'|^2}{f} \,\mathrm{d} x \geq C\,\int_0^1 |f-1|^...
Fei Cao's user avatar
  • 720
2 votes
1 answer
269 views

Bounding Kullback-Leibler

Suppose we have a probability distribution $P$ on a finite set $S$. We draw $N$ i.i.d. samples according to $P$ and use these samples to define an empirical distribution $R$. We measure the Kullback-...
Bill Bradley's user avatar
  • 3,819
1 vote
0 answers
81 views

Min-sum belief propagation not working on a chain model with equal unary potentials

Given is a chain factor graph as presented in the image below with the following properties: Each node can take values 0 or 1 All unary potentials are equal (e.g. $U(a)=0$) for every node $a$ All ...
Uros Isakovic's user avatar
3 votes
1 answer
120 views

Conditions for: (local) lipschitz stability of I-projection

The following post builds on this post; I'll begin by quoting the setting. Background from Previous Question: $\newcommand\SS{P}\newcommand\TT{Q}$Call a Gaussian probability measure $\SS$ on $\mathbb{...
Math_Newbie's user avatar
1 vote
1 answer
113 views

References: error and stability estimates for information projection

$\newcommand\SS{P}\newcommand\TT{Q}$I will call a Gaussian probability measure $\SS$ on $\mathbb{R}^d$ isotropic if its covariance matrix is diagonal with non-vanishing determinant; i.e. $\Sigma_{i,i}&...
Math_Newbie's user avatar
3 votes
0 answers
86 views

Asymptotic approximation of Fisher information matrix for small Gaussian perturbation

Let $$ X=Y/a+b+\epsilon Z, $$ where $Y\sim\operatorname{Poisson}(\lambda)$ and $Z\sim\mathcal N(0,1)$ are independent. Also define $\theta=(\lambda,a,b,\epsilon)$. The Fisher information matrix $$ ...
Aaron Hendrickson's user avatar
1 vote
2 answers
191 views

Limit of a countable separable is countable separable?

Let $\rho$ be a positive trace class operator on $H\otimes H$, where $H$ is a separable Hilbert space (not necessarily finite dimensional). We say that $\rho$ is countable separable if $\rho=\sum_{i=...
Deva's user avatar
  • 11
2 votes
0 answers
45 views

Moduli spaces of 'generalized mutually unbiased bases'

Mutually unbiased bases in $\mathbb{C}^n$ with a chosen inner product are collections of orthonormal bases such that for each pair of orthonormal bases $e_i,f_i$, $i=1,\ldots,n$ we have $|\langle e_i, ...
Sergey Guminov's user avatar
0 votes
1 answer
233 views

Maximal mutual information between a continuous and a discrete random variables

Let $X\sim \mathcal{N}(\mu,\sigma^2)$ be a Gaussian random variable with random mean $\mu\sim {\sf Bernoulli}(p)$, i.e., $\mu=1$ with probability $p$ and $\mu=0$ with probability $1-p$. In other words,...
Augusto Santos's user avatar
4 votes
1 answer
145 views

Riemannian submanifolds of $2$-Wasserstein space

In the article "Wasserstein Geometry Of Gaussian Measures" by Asuka Takatsu the author shows how the space of d-dimensional Gaussian probability measures with non-singular covariance ...
Annie's user avatar
  • 91

1
2 3 4 5
13