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.
54 questions
9
votes
4
answers
2k
views
Is there a useful generalization of the Schmidt decomposition to the tensoring together of 3 or more vector spaces?
I've rewritten the question in math notation, and I've left the old version in physics bra-ket notation here.
Background
A simple consequence of the singular value decomposition is that any vector $...
- 846
72
votes
9
answers
30k
views
When are probability distributions completely determined by their moments?
If two different probability distributions have identical moments, are they equal? I suspect not, but I would guess they are "mostly" equal, for example, on everything but a set of measure zero. ...
- 2,649
48
votes
2
answers
14k
views
Research situation in the field of Information Geometry
I am now doing an article survey on the field of information geometry started by S.Amari and Barndorff-Nielson. I want to know some research situation in this field.
I have read (4) and parts of (3). ...
- 8,071
40
votes
5
answers
5k
views
"Entropy" proof of Brunn-Minkowski Inequality?
I read in an information theory textbook the Brunn-Minkowski inequality follows from the Entropy Power inequality.
The first one says that if $A,B$ are convex polygons in $\mathbb{R}^d$, then
$$ m(...
- 22.8k
29
votes
2
answers
3k
views
Is there a Kolmogorov complexity proof of the prime number theorem?
Lance Fortnow uses Kolmorogov complexity to prove an Almost Prime Number Theorem (https://lance.fortnow.com/papers/files/kaikoura.pdf, after theorem $2.1$): the $i$th prime is at most $i(\log i)^2$. ...
- 13.9k
17
votes
4
answers
2k
views
Geometric interpretations of the exponential of entropy
Question:
Might there be a natural geometric interpretation of the exponential of entropy in Classical and Quantum Information theory? This question occurred to me recently via a geometric inequality ...
- 3,871
13
votes
3
answers
2k
views
Hot-topics in error correcting coding related to interesting math. ?
What are topics in error-correcting coding which are related to interesting math. ?
I am primarely interested in nowdays hot topics, but old days topics are also welcome.
Let me try to mention what ...
3
votes
4
answers
2k
views
History of the Sampling Theorem
In January, 1949, Shannon publishes the paper Communication in the Presence of Noise, Proc. IRE, Vol. 37, no. 1, pp. 10-21, available here, which establishes the Information Theory. In this paper, the ...
- 1,568
37
votes
3
answers
3k
views
An entropy inequality
Let $X,Y$ be probability measures on $\{1,2,\dots,n\}$, and set $K=\sum_i\sqrt{X(i)Y(i)}$ so that $Z:=\frac{1}{K}\sqrt{XY}$ is also a probability measure on $\{1,2,\dots,n\}$. How can we prove the ...
- 11.4k
32
votes
6
answers
2k
views
What characterizations of relative information are known?
Given two probability distributions $p,q$ on a finite set $X$, the quantity variously known as relative information, relative entropy, information gain or Kullback–Leibler divergence is defined ...
- 22.3k
20
votes
2
answers
4k
views
information-theoretic derivation of the prime number theorem
Motivation:
While going through a couple interesting papers on the Physics of the Riemann Hypothesis [1] and the Minimum Description Length Principle [2], a derivation(not a proof) of the Prime Number ...
- 3,871
18
votes
2
answers
966
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 ...
- 29.2k
18
votes
3
answers
3k
views
Entropy and total variation distance
Let $X$, $Y$ be discrete random variables taking values within the same set of $N$ elements. Let the total variation distance $|P-Q|$ (which is half the $L_1$ distance between the distributions of $P$ ...
- 20.2k
15
votes
1
answer
748
views
Digital physics and "Gandy-like" machines
Various physicists, famously John Wheeler, have asserted that physical information is the central object of study in physics, in the sense that an object or concept is "physically meaningful" if it ...
- 3,612
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 ...
- 8,071
10
votes
2
answers
2k
views
Convergence of an empirical distribution w.r.t. the Hellinger distance
Let $P$ be a probability distribution on a finite set $\mathcal{X}$ and let $X_1, X_2, \ldots, X_n$ be drawn i.i.d. according to $P$. Define the empirical distribution:
$\hat{P_n}(x) = \frac{1}{n} \...
- 165
9
votes
1
answer
495
views
Higher moments of information and Renyi entropy
For a given discrete probability distribution, Shannon entropy can be though as an expectation value $\langle - \log p \rangle$ (see also: What is entropy, really?, What is the role of the logarithm ...
- 1,612
9
votes
9
answers
2k
views
Existence of unknowable algorithms ?
Here by «algorithm» I mean a (halting) Turing machine with finite alphabet and memory.
Is it possible to obtain by purely existential (i.e. non-constructive) means the existence of an algorithm ...
- 5,428
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 ...
- 3,094
8
votes
3
answers
411
views
Identifying a subset with as few tests as possible
Informal description: You are given a set of $n$ blood samples, each having probability $p$ of being infected with a disease. Your goal is to determine the set $P$ of infected samples with as few ...
- 32.5k
8
votes
3
answers
1k
views
Introduction to information geometry and/or geometric control theory
Some background: I'vebeen searching for a research project to work through my grad studies and I found information geometry like a strong candidate but the amount of work out there is overwhelming. I ...
- 81
7
votes
3
answers
330
views
Quantifying the noninvertibility of a function
Given a function $f$ from a finite set $X$ to itself, it seems natural to consider $\kappa_f := (\sum_{x \in X} |f^{-1}(x)|^2)/|X|$ as a measure of the non-invertibility of $f$: it equals 1 if $f$ is ...
- 19.7k
6
votes
2
answers
1k
views
Do binary symmetric channels maximize mutual information?
Consider the following setup: $(X, Y)$ is a doubly symmetric binary source with parameter $0 < p < 1/2$, i.e., $X \sim \text{Bernoulli}(1/2)$, $Z \sim \text{Bernoulli}(p)$ and $Y = X \oplus Z$. ...
5
votes
1
answer
237
views
Rate-Distortion theory: What is the distribution of distortion on an optimal Gaussian encoder?
If we wish to encode a gaussian source, $X\sim\mathcal{N}(0,\sigma^2)$ at rate $R$, then decode it to create an estimate $\hat{X}$, rate-distortion theory tells us that the lowest mean-squared-error ...
5
votes
1
answer
187
views
Existence of a joint distribution on Bernoulli variables with same probability of being pairwise different
Let $m\in\mathbb{N}$ and $p\in(0,1)$ be arbitrary. Is there a sequence $X_1,\dots,X_m$ of random variables with the following specs on their distribution:
Each $X_i$ is unbiased Bernoulli: $X_i\sim {\...
- 1,096
5
votes
4
answers
4k
views
Is there an inequality relation between KL-divergence and $L_2$ norm?
According to the Pinsker inequality, we have the following inequality:
\begin{equation}
\delta_{TV} (p, q)^2 \leq \frac{1}{2} D_{KL}(p,q),
\end{equation}
where $\delta_{TV} (\cdot, \cdot)$ and $D_{KL}...
- 175
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
2
answers
276
views
Binary codes with upper bound on pairwise distance
A fundamental problem in coding theory is:
Given positive integers $k\le n$, determine or bound the maximal cardinality of a set $S\subset \mathbb{F}_{2}^{n}$ such that $\forall x,y\in S: x\ne y\...
- 2,075
4
votes
1
answer
2k
views
Bounding Entropy in terms of KL-Divergence
Let $h(X)$ be the differential entropy of a continuous random variable $X$ with density $f$, and let $Y$ be another continuous random variable with density $g$. If $KL(X\mid\mid Y)$ is the Kullback-...
- 49
4
votes
8
answers
6k
views
Encoding $n$ natural numbers into one and back
I want to encode $n$ natural numbers into one natural number. Also, I should be able to decode it back. I tried Gödel's encoding scheme, but it takes a lot of space (doesn't fit into a ...
- 75
4
votes
2
answers
2k
views
Convexity and semicontinuity of the relative entropy function
There are several different definitions of relative entropy, and some of them are not equivalent. Following is the definition we will use in this question.
Let $M$ be a closed manifold and $\mathcal{...
4
votes
3
answers
9k
views
Computing channel capacities for non-symmetric channels
I'm studying information theory right now and I'm reading about channel capacities.
I know that there are known expressions for computing the capacities for some well known simple channels such as ...
- 285
4
votes
3
answers
1k
views
Incremental entropy computation
After a quick internet search I found no method for incremental entropy computation.
Question 1
Let $\{x_i\}_{i=1}^n$ and $\{x_i\}_{i=1+n}^{n+m}$ be two samples and let $S_i^j:=\sum_{k=i}^j x_k$. ...
- 161
3
votes
1
answer
3k
views
Cyclic Hamming Code
I know that Hamming codes can be arranged in cyclic form. But my question is how can I prove this.
My idea was to find a generator/primitive polynomial $p(x)$?
For example I want to show that the $[...
- 31
3
votes
1
answer
127
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{...
- 364
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
3
votes
2
answers
2k
views
Geodesic equation from Christoffel symbols
Let $\mathcal{P}:=\mathcal{P}(\mathcal{X})$ be the manifold of all (strictly positive) probability vectors (distributions) on $\mathcal{X}=\{x_0,\dots,x_n\}$,
i.e., each $p=(p(x_0),\dots,p(x_n))\in \...
- 779
3
votes
0
answers
494
views
Maximization of a total variation distance subject to another total variation distance in Markov chain
Suppose two dependent random variables $X$ and $V$ from finite alphabets $\mathcal{V}$ and $\mathcal{X}$ with known joint and marginal distributions are given. Let $P_{XV}$ and $P_X$ and $P_V$ are the ...
- 1,109
3
votes
1
answer
737
views
Exponential deconvolution using the first derivative
There is an interesting observation using the first derivative to deconvolve an exponentially modified Gaussian:
The animation is here at terpconnect.umd.edu.
The main idea is that if we have an ...
- 879
2
votes
2
answers
496
views
Nested De Bruijn sequences
A binary De Bruijn sequence of index $n$ is a circular sequence $S=a_1 a_2 \dots a_{2^n},$ with $a_i \in \{0,1\},$ and such that each of the $2^n$ binary $n$-uples occurs exactly once in $S.$
Is ...
- 283
2
votes
0
answers
264
views
Prove or disprove a mutual information inequality
I have $n$ IID Bernoulli random variables denoted by $X_1,X_2,\ldots X_n$ with parameter $p$.
I am interested in knowing if the following inequality involving mutual information holds :
$\boxed{\max_{...
- 83
2
votes
1
answer
92
views
Maximization of information over set of non-injective functions
Let $X$, $Y$, $Z$ be discrete random variables, with $Y$ and $Z$ independent. Does the following equality hold?
$$
\max_{f_{Y,Z}} \big\{ \ I(X; f_{Y,Z}(Y,Z)) \ \big\} \le \max_{f_X, f_Y} \big \{ \ I(X;...
- 189
2
votes
0
answers
1k
views
Can we pass to the limit in Poincaré-Jaynes-Bretthorst interpolation and deconvolution?
In Science and Hypothesis, chapter XI, The calculus of probabilities, Henri Poincaré deals informally with the fundamental problem of interpolation. He concludes (see http://ia600308.us.archive.org/21/...
2
votes
0
answers
413
views
Interpretation of Shannon Entropy Application
Consider a collection of increasing positive integers $\{a_i\}_{i=1}^m$ and the distribution $p_i=\frac{a_i}{\sum_{i=1}^ma_i}$. Let entropy of $\mathcal{A}=\{a_i\}_{i=1}^m$ be given
by $$H(\mathcal{A}...
- 13.9k
2
votes
1
answer
1k
views
Mutual information between continuous and discrete variables from numerical data
I am looking for references/measures to estimate the mutual information between a continuous (C) and discrete (D) variable, given a real-world (i.e. finite sample) data set. C is uniformly distributed ...
- 21
2
votes
1
answer
810
views
Set of distributions that minimize KL divergence,
Assuming that $p,q$ are probability distributions defined on the same support $\{x_i\}_{0 \leq i \leq n}$, $\epsilon$ a small real number, and $D_{KL}$ the Kullback-Leibler divergence,
is there a ...
- 167
1
vote
0
answers
428
views
When inequality in Mrs. Gerber's lemma is almost equality?
Let $X=x_1\ldots x_n$ be a random variable.
Assume that every $x_i$ takes values in $\{0,1\}$.
Assume also that for every $I \subseteq \{1,\ldots, n\}$ the Shannon entropy of random value $X_I$
[if $I ...
- 2,576
1
vote
2
answers
290
views
How many k-nomials of deg N divisible by X^16+x^12+x^5 +1 ? (Spectrum of CRC-16-CCITT erroc-correcting code ?)
Let us consider polynoms over $F_2$.
Consider the linear SUBSPACE of polynoms divisible by $x^{16}+x^{12}+x^5 +1$ and of degree less or equal $N$ (e.g. 40).
Question: How many k-nomials belong to ...
- 24.9k
1
vote
1
answer
124
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}&...
- 364
1
vote
2
answers
537
views
Is this general form of Lovasz theta function of circulant graphs?
Let $G$ be a cirulant graph with no loops at vertices and vertex degree $d$. Is the Lovasz theta function of this graph given by:
$\vartheta(G) = \max_{i}\frac{-N\epsilon_{i}}{-\epsilon_{i}+d-1}$?
...
- 13.9k