All Questions
Tagged with it.information-theory reference-request
51 questions
7
votes
1
answer
757
views
compression of a Turing machine run sequence
consider a Turing machine with a set of states $s_n$ and alphabet symbols $a_n$. now consider a "run sequence" generated from a starting input in the following sense. the run sequence is defined as ...
CommunityBot
- 1
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 ...
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
17
votes
6
answers
6k
views
Revisiting the unreasonable effectiveness of mathematics
Question:
On balance, with theoretical advances in algorithmic information theory and Quantum Computation it appears that the remarkable effectiveness of mathematics in the natural sciences is quite ...
- 19.6k
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 ...
0
votes
0
answers
52
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 ...
CommunityBot
- 1
6
votes
2
answers
813
views
Kolmogorov's approach to probability theory
Question:
Did Kolmogorov develop a set of axioms for probability theory motivated by Algorithmic Information Theory in the 1960s?
Context:
In 1965, Andrey Kolmogorov considered three approaches to ...
- 3,871
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}&...
- 128k
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 ...
- 2,600
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, ...
- 7,633
3
votes
1
answer
152
views
Mutual information in large deviation theory
Many information theoretic quantities such as entropy and relative entropy appear in rate functions in large deviation theory (LDT). Is there any result in LDT that relates mutual information and rate ...
- 1,904
1
vote
0
answers
95
views
Reference request: Time and proofs of shared pasts
Is there research about structures for notions of time with distributed systems of information, as with blockchains?
I am thinking of tuples $(I, T, P, A, \prec, s, \eta, u)$ where
$I$, $T$ and $P$ ...
CommunityBot
- 1
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 ...
- 10.5k
2
votes
1
answer
222
views
Given iid samples from the joint distribution $P$ of pair of r.v.'s $(X,Y)$, how to get iid samples from independence coupling $P_X \otimes P_Y$?
Let $(X,Y)$ be a pair of random variables on a measure space $\mathcal T \subseteq \text{"subsets of }\mathbb R^2\text{"}$, with joint probability distribution $P$.
We don't assume $X$ and $Y$ are ...
- 128k
10
votes
2
answers
547
views
The origin of the natural base in statistical mechanics
In modern treatments of statistical mechanics, the natural base is conventionally used for the Gibbs and Boltzmann entropy without careful justification. While I am aware that the properties of the ...
- 63.9k
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
3
votes
1
answer
524
views
Has the von Neumann entropy ever been used in classical mechanics?
After going through an application of the von Neumann entropy(from quantum information theory) to certain problems in computational neuroscience [2], it occurred to me that this entropy might have ...
- 3,871
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 ...
- 8,659
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
2
votes
1
answer
199
views
Do enough permutations of an initial set probably cover most permutations?
Fix $\alpha, \epsilon \in(0,1)$. Take $(S_n)_n$ to be any sequence of sets with each $S_n$ containing $ \lceil (n!)^\alpha\rceil$ permutations of $n$ elements. Also build another sequence of sets $(...
5
votes
1
answer
863
views
Turing machines and Ising model
I have currently started a new research line aiming to prove a mapping between a 2-symbol Turing machine and the one dimensional Ising model. The connection is seen by recognizing that a set of ...
- 236k
0
votes
0
answers
171
views
A basic property of maximal correlation
Let $𝑋$ and $𝑌$ be random variables. Then the maximal correlation $\rho_{m}(X;Y)$ is defined as:
$$\rho_{m}(X;Y):=\max_{f,g}\mathbb{E}[f(X)g(Y)],$$
where the maximization is taken over real-valued ...
- 11
1
vote
0
answers
438
views
Chain rule for maximal correlation
Let a pair of random variables $(X,Y)$ be defined over finite alphabet $\mathcal{X}\times \mathcal{Y}$ with joint distribution $P_{XY}$. The maximal correlation $\rho(X;Y)$ between $X$ and $Y$ is ...
- 11
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). ...
- 6,001
2
votes
1
answer
539
views
What is the sum capacity of a scalar gaussian broadcast channel?
"On the Achievable Throughput of a Multiantenna Gaussian Broadcast Channel" by Giuseppe Carie and Shlomo Shamai talks, in part, about the following type of link (paraphrasing):
A transmitter with $...
- 13.9k
12
votes
6
answers
11k
views
Two reference requests: Pinsker's inequality and Pontryagin duality
Sorry for such a newbie post and for asking two unrelated references in one shot.
First, I am interested in any proof of Pinsker's inequality.
Second, I wonder what is the best place to read about ...
- 1,372
4
votes
1
answer
362
views
Information monotonicity of divergence => function of $f$-divergence
It is well-known that $f$-divergences defined on $\mathcal P(\mathcal X)$ where $\mathcal X$ is a measure space with $\sigma$-algebra $\mathcal B$ satisfy the property of information monotonicity:
...
- 695
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 ...
CommunityBot
- 1
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
23
votes
1
answer
767
views
The Euler-Mascheroni constant and entropy
I would like to know if I have discovered or merely rediscovered the following pretty fact.
A partition of $[0,1]$ into intervals of lengths $p_{i, i=1\ldots n}$ induces a probability distribution ...
- 188k
2
votes
1
answer
2k
views
Shannon's proof of the entropy power inequality
In Shannon's paper on information theory, found here, he asserts the entropy power inequality in appendix 6, found on page 52. I was reading his proof and it seems like there is a gap. Through his ...
- 13.9k
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 ...
1
vote
0
answers
135
views
Error correcting codes via random matrices: How close to the Shannon bound?
I have a vague and probably rather naive question on error correcting codes.
Suppose we want to encode binary vectors of length $k$ as binary vectors of length $n$ in such a way that differences of ...
- 10.4k
7
votes
3
answers
790
views
Expected cardinality of a randomly chosen element of the family of subsets of $\{1,\ldots,n\}$ with at most $k$-elements
Assume that $1\le k \le n$ and let $\mathscr{Z}$ be the family of all subsets of $\{1,\ldots,n\}$ with at most $k$ elements. Pick a random element $X$ of $\mathscr{Z}$ (we consider the probablity ...
- 1,658
2
votes
1
answer
130
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 ...
- 76
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
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
$$ -\...
- 1,551
9
votes
1
answer
966
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 ...
CommunityBot
- 1
2
votes
1
answer
280
views
How much can KL divergence decrease by diluting the reference distribution
Let $\Omega$ be a countable set and $\mu,\nu\colon\Omega\to[0,1]$ be distributions on $\Omega$, that is we have $\sum_{x\in\Omega}\mu(x)=1$ and likewise for $\nu$. The Kullback-Leibler divergence of $\...
- 83
4
votes
1
answer
152
views
Enumerator Polynomials for Linear Anytime Codes
Let $C = \{c \in \mathbb{F}^n_2 : Hc=0\}$ be a binary linear code where $H \in \mathbb{F}^{k \times n}_2$ is a block lower-triangular matrix of full rank called the parity-check matrix of $C$. Clearly ...
- 85.6k
3
votes
1
answer
306
views
Mutual information decrease with coarse-graining
Let $X,A,Y,B,C,D$ be random binary variables. $D$ is independent from $X,A,C$ and $C$ is independent from $Y,B,D$.
Is it true that:
If $I(Y:B|D=0)\leq \epsilon$ then $I(X\oplus Y:A\oplus B|C=0,D=0)\...
CommunityBot
- 1
2
votes
3
answers
629
views
Asking for an English version of a paper
I have been looking for the paper
"almost independence and secrecy capacity" by Csiszar. But all I could find was a Russian version published in Problems of Information Transmission.
I am wondering ...
- 139
3
votes
0
answers
140
views
Applications of list decoding
This is citation from http://en.wikipedia.org/wiki/List_decoding:
Algorithms developed for list decoding of several interesting code families have found interesting applications in computational ...
- 2,576
8
votes
2
answers
567
views
Where should I learn about Kolmogorov complexity of overlapping substrings?
I would like to know more about the relationship between the Kolmogorov complexity of a string and that of its substrings. The relation that up to an additive constant, $K(x,y) = K(x) + K(y\ |\ x, K(...
- 236k
2
votes
0
answers
156
views
Looking for Camion - Abelian codes
I am looking for a copy of the old report "Paul Camion - Abelian codes", Technical Report 1059, University of Wisconsin 1971. I have asked Paul himself, but he could not help me. Anyone out there has ...
CommunityBot
- 1
4
votes
3
answers
723
views
Good codes in practice for correcting combination of errors and erasures
In practice, both errors and erasures might be introduced in the channel. Could you point me to some good codes for correcting such combinations. Also what are their correction capabilities?
- 3,692
3
votes
5
answers
1k
views
n-widths and Kolmogorov's entropy
Most of the authors of research papers in compressed sensing use n-widths and Kolmogorov's entropy extensively, which are kind of hard for me to understand. Any suggestion on books or expository ...
- 959
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
0
votes
1
answer
399
views
Information Theory of "decision machines"
Hello, everyone. I am considering the following type of situation.
Suppose I have a decision machine (DM) that I can ask any yes/no question and I want to use this to measure an n-ary random variable....
CommunityBot
- 1
14
votes
4
answers
3k
views
Shannon's communication paper and finite differences
In Shannon's 1948 paper "A Mathematical Theory of Communication", early on he derives the equation $$N(t)=N(t-t_1)+N(t-t_2)+\ldots+N(t-t_n).$$
He then says "according to a well-known result in finite ...
- 5,721