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.
633 questions
0
votes
0
answers
36
views
Contribution of Fisher information near jump points in convolved probability distributions
I am trying to compute the contribution to the Fisher information from jump points $b_i(\theta)$ in the convolved function $f(x; \theta)$ with respect to the parameter $\theta$. I am unsure whether it ...
- 99
1
vote
0
answers
92
views
How to optimize parametric information-theoretic bounds?
I am faced with an information-theoretic upper bound, such as
\begin{align}
\sqrt{\alpha'}2^{I_\alpha(X;Y)},
\end{align}
where $I_\alpha(X;Y)$ is the Rényi mutual information with parameter $\alpha>...
- 287
0
votes
0
answers
53
views
General formula for Fisher information matrix reparameterization?
Prefacing apology for likely having unclear notation in the question and possible unclear concepts, because I'm not a mathematician.
The Fisher Information Matrix (FIM) for a multivariate normal ...
- 75
1
vote
0
answers
45
views
Existence of optimal entropic weights for empirical modeling
Let $\mathcal{X} = [0,1]^n$ be the input space and $\mathcal{Y} = \{1, ..., n_c\}$ be a discrete output space. Let $D = \{(x_i, y_i)\}_{i=1}^N \subset \mathcal{X} \times \mathcal{Y}$ be a training ...
- 111
16
votes
1
answer
398
views
Examples of problems in statistics accessible only using information geometry
I am just curious if there are some examples of problems in statistics that are indeed accessible using information geometry while proofs completely avoiding geometry are unknown. In other words, ...
- 269
0
votes
0
answers
32
views
Why standardized LDPC codes, such 5G NR, have 4 cycles in its parity check matrix?
We all know that short cycles in Tanner Graph are detrimental in error performance. So, Why standardized 5G NR LDPC codes have 4-cycles? 3rd generation Partnership Project (3GPP) had announced Base ...
- 1
1
vote
1
answer
197
views
Probability distribution on Python-dictionary-like objects?
I would like to examine information-theoretical properties of random variables that take as values objects which are akin to dictionaries in the Python programing language.
That is, each sample of the ...
- 11
1
vote
0
answers
55
views
Combinatorial structure of the entanglement spectrum and quantum error correction in finite vector spaces
Let $V$ be a finite-dimensional vector space over $\mathbb{C}$ with dimension $d$. Consider a subspace $S \subset V^{\otimes n}$ representing the code subspace of a quantum error correcting code. We ...
- 11
8
votes
2
answers
698
views
Information theoretical interpretation of Free Energy
When exploring the concept of free energy from an information-theoretic perspective, I often come across statements like:
"Free energy measures the degree of surprise an agent experiences when ...
- 253
1
vote
1
answer
58
views
Proving one one condition for the Gaussian mixture model
$\textbf{Question:}$ Consider the following matrix representation for a two-component bivariate Gaussian Mixture Model (GMM):
$S = \begin{bmatrix}
A & X \\
X' & B
\end{bmatrix}$
where
$A = \...
- 123
0
votes
0
answers
120
views
Is there an existing problem related to inferring a hidden node in a graph from its neighbors
My original question was a bit too ambiguous, so I updated it as follows:
Consider a graph $G=(V,E)$. A vertex in $G$ is chosen uniformly at random; then a neighbor $x$ of $v$ is chosen uniformly at ...
- 109
0
votes
0
answers
51
views
Minimizer of forward and reverse Kullback-Leibler divergence with sum constraints on marginals
Consider minimization of the Kullback Leibler divergence between two discrete distributions $p$ and $q$:
\begin{align*}
D_{KL} \left( p \parallel q \right) = \sum_i p_i \log \left( \frac{p_i}{q_i} \...
0
votes
0
answers
31
views
What is the Fisher information matrix of the von Mises-Fisher distribution?
Assuming the von Mises-Fisher distribution as
$$f_{p}(\mathbf{x}; \boldsymbol{\mu}, \kappa) = C_{p}(\kappa) \exp \left( {\kappa \boldsymbol{\mu}^\mathsf{T} \mathbf{x} } \right),$$
where $\kappa \ge 0$,...
- 287
0
votes
0
answers
51
views
Upper bound on expectation of a convolution
Given probability densities $f, g\in L^p(\mathbb{R}^3), \ \forall p\geq 1$, with the same first and second moments
\begin{align} & \int_{\mathbb{R}^3} v f(v)\,dv = \int_{\mathbb{R}^3} v g(v)\,dv, \...
- 43
0
votes
0
answers
30
views
Why is the $\alpha$-divergence unique in positive measure space $\mathcal{M}$?
In this article https://bsi-ni.brain.riken.jp/database/file/298/303.pdf (S. Amari 2009), it is said that a $f$-divergence (eq. 17) which can be written by a decomposable Bregman divergence (eq. 53) ...
- 1
1
vote
1
answer
137
views
Gelfand–Yaglom–Perez Theorem for product space
In On a Gel'fand-Yaglom-Peres theorem for f-divergences, Gilardoni proved the Gelfand–Yaglom–Perez Theorem for general $f$-divergence, i.e. $f$-divergence between two probability measures $P$ and $Q$ ...
- 113
0
votes
3
answers
185
views
The approximated function of $\mathbb{E}\left\{ \ln\left(1+X\right)\right\}$, where $X\sim\operatorname{Gamma}\left(\kappa\ge1,\theta>0\right)$
Given $X \sim \operatorname{Gamma}(\kappa, \theta)$ with CDF $F_X(\kappa, \theta)$, where $\kappa \geq 1$ and $\theta > 0$, the expected value of $\mathbb{E} \left\{ \ln(1+X) \right\}$ is ...
- 41
0
votes
0
answers
85
views
When is a family of distributions "closed" with respect to minimal sufficient statistics?
As in the title, I am interested in understanding how to express the idea that a parametric family of distribution is "closed" with respect to minimal sufficient statistics. Before giving ...
3
votes
0
answers
81
views
Seeking strong bounds on KL-divergence and martingales for a hypothesis-testing inequality
Let's say we have a finite set $\mathcal{O}$ of observations, and let $\mathcal{C}(\Delta\mathcal{O})$ denote the space of closed convex sets of probability distributions.
We have two hypotheses which ...
- 353
1
vote
0
answers
40
views
From a constraint satisfaction problem (CSP) to a sudoku grid [closed]
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 ?
1
vote
1
answer
91
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 ...
- 3,001
1
vote
1
answer
82
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 ...
- 115
0
votes
0
answers
14
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\...
- 342
1
vote
1
answer
164
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 ...
0
votes
0
answers
179
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 ...
- 127
0
votes
0
answers
34
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}}-\...
- 31
3
votes
0
answers
69
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$ ...
- 131
2
votes
1
answer
139
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 ...
- 31
0
votes
0
answers
18
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 ...
- 13
1
vote
1
answer
80
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 ...
- 13
0
votes
1
answer
130
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}_+$ ...
1
vote
0
answers
35
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 ...
- 11
0
votes
0
answers
193
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 ...
- 315
2
votes
0
answers
120
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 ...
1
vote
1
answer
185
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 \...
- 31
2
votes
0
answers
99
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 ...
- 769
1
vote
1
answer
182
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 ...
- 9,340
2
votes
0
answers
92
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 \...
- 503
4
votes
1
answer
194
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 ...
- 141
0
votes
1
answer
107
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 ...
- 49
1
vote
0
answers
116
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''...
- 9,340
2
votes
1
answer
275
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{\...
- 49
1
vote
0
answers
125
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 ...
- 827
2
votes
1
answer
215
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 ...
0
votes
0
answers
85
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 ...
- 4,907
3
votes
2
answers
1k
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 ...
- 83
0
votes
0
answers
53
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 ...
- 13
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}, ...
4
votes
1
answer
250
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 ...
- 287
3
votes
1
answer
205
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 ...
- 503