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.
196 questions with no upvoted or accepted answers
24
votes
0
answers
1k
views
conjectures regarding a new Renyi information quantity
In a recent paper http://arxiv.org/abs/1403.6102, we defined a quantity that we called the "Renyi conditional mutual information" and investigated several of its properties. We have some open ...
- 483
15
votes
0
answers
476
views
Any references on zeta-function like sums of inverse determinants over lattices of matrices?
I'm sorry for the title, it was little difficult to phrase..
Let us consider a matrix lattice $L\subset M_n(\mathbb{C})$. By this I mean a discrete additive group in $M_n(\mathbb{C})$. Let us ...
- 201
11
votes
0
answers
307
views
Entropy, magnitude, diversity of finite metric spaces in number theory
I was reading the article by Tom Leinster, (Maximizing
diversity in biology and beyond, arXiv link), and find it very interesting.
Since I was searching for entropies of finite metric spaces I found
...
user6671
11
votes
0
answers
638
views
Uncertainty principle in Entropy terms
Math Questions:
Consider Hilbert space $L_2(\mathbb{R})$ with a standard norm
$
||\psi|| = ( \int_{\mathbb{R}}{ |\psi(t)|^2 dt } )^{1/2},
$
and Fourier transform
$
(F\psi)(\xi) =
\int_{\...
- 580
9
votes
0
answers
467
views
Measuring the randomness of texts
The question concerns statistic properties of random words in a finite alphabet $A$.
By $A^{<\omega}$ we denote the set of all words in the alphabet $A$, i.e. finite sequences of elements of $A$.
...
- 41.8k
9
votes
0
answers
245
views
De Bruijn sequence inside De Bruijn sequence
A binary De Bruijn sequence of index $n$ is a circular sequence $S=a_1a_2\ldots a_{2^n}$, with $a_i∈\{0,1\}$, and such that each of the $2^n$ binary $n$-tuples occurs exactly once in $S$.
What is ...
- 12.3k
9
votes
0
answers
223
views
Cramer's theorem in Hilbert spaces
I am interested under what conditions Cramer's theorem applies in random variables taking values in Hilbert spaces. Following these lecture notes, but using a Hilbert space:
Let $X_1,X_2,\cdots$, be ...
- 619
8
votes
0
answers
1k
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 "...
- 361
7
votes
0
answers
142
views
Ideals, subalgebras, subgroups as error-correcting codes?
Context: roughly speaking the construction of a error correcting code is a problem to choose some subset in a metric space, such that the points of the subset pairwise as far-distant as possible. ...
- 24.9k
7
votes
0
answers
216
views
irregular LDPC code construction algorithm
I want to construct a sparse random binary matrix ${{\bf{H}}_{m \times n}}$ that has the following properties
1- Faction of columns of weight $i$ is ${v_i}$ .
2- Fraction of rows of weight $i$...
- 275
6
votes
0
answers
105
views
Computing the zeta transform of a Boolean function: Space-time tradeoff
Let $f : \mathbb{F}_2^n \to \mathbb{F}_2$ be a Boolean function in $n$ variables. The zeta transform of $f$ is the Boolean function $\zeta_f : \mathbb{F}_2^n \to \mathbb{F}_2$ defined by
$$\zeta_f(y) :...
- 71
6
votes
0
answers
360
views
What is the status of the Born Rule in axiomatic QM?
While physicists have tried multiple times and failed to derive the Born Rule (for example: https://arxiv.org/pdf/quant-ph/0409144.pdf). I was wondering what axiomatic Quantum Mechanics had to say ...
- 237
6
votes
0
answers
120
views
Functional Equation of Zeta Function on Statistical Model
I've been studying [1] because I was interested in his ideas on the zeta function. I'll define it here (c.f. p. 31):
The Kullback-Leibler distance is defined as
$$
K(w)=\int q(x)f(x, w)dx\quad
f(x,w)...
- 429
6
votes
0
answers
585
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$). ...
- 32.5k
6
votes
0
answers
578
views
Maximal Correlation versus Correlation Coefficient When one RV is Gaussian
Let a pair of random variables $(X,Y)$ be continuous random variables (i.e., they both have density with respect to Lebesgue measure) with joint distribution $P_{XY}$. The maximal correlation $\rho_m(...
- 1,109
6
votes
0
answers
206
views
$q$-deformations of fundamental equation of information and entropies
Classical information theory: fundamental equation of information
In classical information theory, the information $I(A)$ of an event $A$ (any element of the $\sigma$-algebra $\mathcal F$ of a given ...
- 326
6
votes
0
answers
342
views
Maximizing Renyi entropy for a certain channel
The channel under consideration is $T = A + B$, where $A$ and $B$ take on values in $\{0, 1\}$ according to a probability mass function. Let (joint) random vector $(A_1, A_2,\ldots, A_n)$ be denoted ...
6
votes
0
answers
337
views
Chernoff bound in the not-quite-sub-exponential case
In Terry Tao's notes on Concentration of measure, Exercise 7 indicates that the Chernoff bound can be generalized to sub-exponential random variables:
http://terrytao.wordpress.com/2010/01/03/254a-...
- 7,633
5
votes
0
answers
191
views
Divergence for Bhattacharya Information matrix
The Fisher information matrix (in the scalar parameter case) can be obtained from the Kullback-Leibler divergence by
$$g(\theta) = -\frac{\partial}{\partial \theta}\frac{\partial}{\partial \theta'}D(...
- 779
5
votes
0
answers
247
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$ ...
- 1,675
5
votes
0
answers
202
views
Mutual Information - Correlation, Continuous Random Variables
For the Gaussian case $I(X,Y)=f( \varrho )$ where $\varrho $ is the correlation coefficient, and $f$ is a known increasing function. Is there any known joint distribution where the $f$ is not strictly ...
- 153
5
votes
0
answers
183
views
On Rényi entropy/divergence
The Rényi entropy for a probability density function $f$ with dominating measure $\mu$ of order $\alpha>0$ is defined as
$$H_\alpha(f)={1 \over {\alpha-1}}\log\int f^\alpha d\mu.$$
If $f$ is ...
- 599
5
votes
0
answers
137
views
Large Deviations: Exponential decay in normed spaces
Let $(X_1,X_2,\cdots)$ be a sequence of independent and identically distributed random variables taking values in some general normed space $(V,||\cdot||)$. Denote $\mu=E[X_1]$ and $S_n=\frac{1}{n}[...
- 619
5
votes
0
answers
293
views
The partition function of a discrete memoryless channel at capacity
Suppose we have a discrete memoryless channel with input and output alphabets each composed of $n$ symbols $\{x_j\}$ and $\{y_k\}$, respectively, and specified by the matrix $W_{jk} := \mathbb{P}(y_k|...
- 15.4k
4
votes
0
answers
362
views
Upper bound of conditional mutual information
Given random variables $X$,$Y$ with a joint distribution $P(X,Y)$ and another random variable $Z$, it is known that there are cases when the conditional mutual information $I(X;Y|Z)$ is greater than ...
- 41
4
votes
0
answers
144
views
Exponential families closed under affine transformations
Let $(\Omega,\Sigma,\mu)$ be a probability space and let $\mathcal{M}$ be an exponential family of probability distributions for $\mu$ of the following form: There are $\varphi_1,\dots,\varphi_n:\...
- 5,405
4
votes
0
answers
214
views
Maximum entropy methods for probabilistic number theory
Might there be a good survey paper on the application of maximum entropy inference for non-trivial problems in probabilistic number theory?
So far I am aware of the work of Ioannis Kontoyiannis, an ...
- 3,871
4
votes
0
answers
83
views
Does minimum mean-square error characterize distribution?
Let $X$ be a real random variable, and, for each $t \geq 0$, let $X_t = X + \sqrt {t}Y$ where $Y$ is a standard normal independent of $X$. The quantity
$$
R(t) = E \big ( [ X - E (X |X_t)]^2 \big),...
4
votes
0
answers
190
views
Shannon-McMillan-Breiman theorem for expander graphs: rate of convergence?
Is the following uniform SMB theorem for random walks on expander graphs true?
For simplicity, I will state it for a finite group $G=\langle S \rangle$ and a uniform probability measure $\mu$ on the ...
- 10.1k
4
votes
0
answers
228
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 ...
- 41
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:...
- 1,551
4
votes
0
answers
807
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 ...
- 153
4
votes
0
answers
573
views
An inequality involving conditional variance and its connection to information theory
Given absolutely continuous random variables $(X, Y)$ with joint distribution $P_{XY}$, we construct $Z:=\sqrt{\gamma} Y+N_\mathsf{G}$ where $N_\mathsf{G}\sim N(0, 1)$ and is independent of $(X,Y)$ ...
- 1,109
4
votes
0
answers
390
views
Fully Homomorphic Error Correction?
Consider a field $F$. Suppose we have two vectors $a,b\in F^n$, and an invertible matrix $G\in F^{n\times n}$. Let $c\in F^n$ be the point-wise product of $a$ and $b$, that is, $c_i=a_ib_i$. Let $x=...
- 3,979
4
votes
0
answers
779
views
Compressed Sensing with an Unusual Basis
I'm wondering if compressed sensing can be applied to a problem I have in the way I describe, and also whether it should be applied to this problem (or whether it's simply the wrong tool).
I have a ...
- 2,383
4
votes
1
answer
839
views
A balls into bins problem with combinatorial constraints
We are given $m$ balls and $n$ bins, with $m \ge n$. Each bin can contain at most $c$ balls (we assume that $c$ is an even integer). In a sequential fashion, at each time step, one ball is placed into ...
- 1,677
3
votes
0
answers
80
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
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
3
votes
0
answers
93
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
$$
...
3
votes
0
answers
68
views
Does this information theoretical thought experiment have a name or corresponding area of research?
I came up with the following thought experiment in my research in order to better understand the way Turing machines can transfer information through their tapes (the motivation is detailed below, isn'...
- 509
3
votes
0
answers
148
views
Bounds on the entropy of the 2D Ising model
I am interested in good estimators of (or analytical bounds on) the entropy $\mathsf{H}_\beta:=-\sum_{\mathbf{x}} P(\mathbf{x})\log_2(P(\mathbf{x}))$ of the two-dimensional Ising model (with no ...
- 111
3
votes
0
answers
138
views
Are there (probablistic) uniform 1D cellular automata which can fault-tolerantly store one bit?
In two dimensions, "Toom's rule" is known to be a cellular automaton which can fault-tolerantly store one bit of information. This means that, if we start with the all-0 configuration on an $...
- 3,001
3
votes
1
answer
358
views
Does a 1-Lipschitz function preserve mutual information between two random variables?
Suppose we have a 1-Lipschitz function $f$ such that 1-Lipschitzness is preserved, with $D_A(f(X), f(Y)) \leq D_B(X, Y)$ for some metric spaces $A$ and $B$.
Does this also imply that $I(f(X); f(Y)) = ...
- 67
3
votes
0
answers
185
views
Lattice points in a rotated product-of-balls
Fix $U$ unitary over $\mathbb{R}^{K},$ take $U_n=I_{n\times n}\otimes U$ and denote the unit ball at 0 in $\mathbb{R}^n$ as $B^n$. For $d_1,\dots,d_K>0$, fix $S_n:=U_n\left(\prod_{k=1}^K d_k B^n\...
3
votes
0
answers
166
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 ...
- 221
3
votes
0
answers
178
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. ...
- 1,677
3
votes
0
answers
145
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 ...
- 13.9k
3
votes
0
answers
219
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 ...
- 211
3
votes
0
answers
158
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}...
- 145
3
votes
0
answers
428
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 $\...
- 2,680