Questions tagged [it.information-theory]
Questions in Information Theory
189
questions
0
votes
0
answers
30
views
Given a sequence, how can we define its information content? [closed]
For example, if we take the following sequence:
1113333442
what is its information content?
- 1
-4
votes
0
answers
48
views
HYPOTHESIS TESTING DIVEGENCE (CHANNEL CODING THEOREM)
Using Hypothesis testing divergence, Show that if we transmit at rate \ $R\leq D^\frac{\epsilon}{2}_{H}(P_{XY}||P_X P_Y) + \log(\frac{\epsilon}{2})$ then $Pr(M\neq\widehat{M})\leq\epsilon$.
Where M is ...
- 1
0
votes
0
answers
52
views
Interesting statistical experiment concerning data compression
I want to present the following statistical experiment concerning data compression, on which I will ask you to predict the result obviously justifying the choice made.
The statistical experiment is ...
- 1
3
votes
1
answer
138
views
Maximal uniquely decodable codes
This question is about the Kraft-McMillan inequality:
If $w_1,\ldots,w_n$ are words of lengths $l_1,\ldots,l_n$ from an alphabet with $r$ letters, which form a uniquely decodable code, then
$$ \sum_{i=...
- 33
0
votes
1
answer
53
views
meaning of "algorithms that do not resample points" in the algorithms that do not resample points theorem
The No Free Lunch theorems for search and optimization demonstrate that for search/optimization problems in a limited search space, where the points being searched through are not resampled, the ...
- 101
0
votes
1
answer
106
views
Can theoretical computer science be combined with mechanism and information design and applications in financial markets
I am considering to take a position as a phd student in a computer science department. I am a mathematician with a master degree in finance and my research interests are mainly focused in game theory. ...
4
votes
0
answers
201
views
Maximize the mutual information between 2 discrete random variables
I have two random variables $X$ and $Y$. $X$ follows Poisson-Binomial distribution with parameters $\{q_1, \ldots, q_k\}$. Thus, $X$ can take values in the set $\{0,1,\ldots,k\}$.
$Y$ is a binary ...
- 99
2
votes
0
answers
81
views
Approximate (in hamming distance) subset representation
Let us have a set $S$ and a subset $T \subseteq S$. I want to find an approximate representation of $T$, i.e. I want to represent (exactly) a set $T'$ that is close to $T$. That is, I want the ...
- 600
8
votes
0
answers
157
views
"Looking for help understanding a proof by Gossner (1998)."
Although there is no use of cryptographic protocols in Gossner (1998), the author refers to protocols of communication and he has a main result that I struggle to prove, because he does not use a ...
- 199
1
vote
0
answers
107
views
Does any physical process constitute a "computation"? [closed]
I am trying to sharpen the convex hull of what seems like a (surprisingly) stubborn concept to enclose based on answers here, as well as conversations with others, around the nature of what actually ...
- 27
5
votes
1
answer
204
views
Upper bound on the expected number of correct bits via a "lossy compression"
Consider the following "compression problem" for a pair $(C,D)$ of algorithms: $C$ receives a uniformly random $x \in \{0,1\}^n$ and outputs a smaller bit string $y \in \{0,1\}^s$. Algorithm ...
2
votes
2
answers
135
views
Information and Coding Theory Texts
I am coming from a pure mathematics (in analysis) background and am curious to learn some information and coding theory. I am after some recommendations on texts. Due to my personal background I am ...
- 121
4
votes
1
answer
200
views
Does this notion of entropy have a name?
Recently I stumbled upon the following notion of entropy which seems quite natural to me. I am looking for its "real" name and/or any references where it might come up. I tried searching ...
- 300
1
vote
0
answers
52
views
sophistication or logical depth to detect intelligent extra-terrestrial species
From my understanding, Algorithmic information theory (AIT) gives some ways to define the amount of « structure » in a string: for example sophistication or logical depth (see for instance [1]), can ...
- 21
1
vote
0
answers
113
views
Deterministic one way communication complexity for message with arbitrary length
Let Alice have a binary string of length $n$ that it wants to send to Bob along a one-bit communication channel. However, Bob does not know the length of the message.
I have been looking into ...
- 11
0
votes
0
answers
165
views
Error in entropy properties in Mathematical Theory of Cryptography by Claude E. Shannon
I am reading this classic paper by Claude E. Shannon and I think there may be a couple of errors in his description of the properties of Entropy/Uncertainty. The screenshot shown at the bottom of this ...
10
votes
1
answer
414
views
Is subtractive dithering the optimal algorithm for sending a real number using one bit?
Consider the problem of sending a real number $x\in[0,1]$ using a single bit $X\in\{0,1\}$ in an unbiased manner.
We assume that the sender and receiver have access to shared randomness $h\sim U[-1/2,...
- 9,378
0
votes
1
answer
104
views
Why isn’t information-probability relationship linear? [closed]
I am completely new to information theory.
I was learning about information content but couldn’t make sense of why the relationship between information content and probability isn’t linear? And why it ...
- 133
3
votes
1
answer
151
views
Converting a Bernoulli to a Gaussian
It is not hard to see that, given one sample from a univariate unit-variance Gaussian $X\sim \mathcal{N}(\mu,1)$ with unknown $\mu$ s.t. $0<|\mu|\leq 1$, one can simulate one draw from a
"...
- 4,331
0
votes
0
answers
12
views
Capacity of spike-based neuronal code
Assume that a neuronal population $A$ is connected to a neuronal population $B$ by a bunch of synapses - one-directional channels that propagate spikes. For simplicity assume that the current ...
- 101
3
votes
1
answer
176
views
Generating $k$ random bits from a pdf with entropy $H(p) = k$
All the sources online say that, intuitively, a distribution with entropy $k$ has $k$ bits of pure randomness in it.
So can we formalize this as follows? Suppose I can only sample from my distribution,...
- 557
2
votes
0
answers
94
views
Damerau–Levenshtein distance with transposition of non-adjacent characters?
Wondering if it's possible to calculate Damerau–Levenshtein distance with transposition of non-adjacent characters (DL distance allows transposition of immediately adjacent characters only). I want ...
- 21
1
vote
0
answers
75
views
Difference between a lossy encoder and a noisy channel in Information Theory
$S \to X \to Y \to \hat{S}$
$\text{source} \to \text{input} \to \text{output} \to \text{target}$
In information theory introductory books, an encoder is usually defined as a deterministic function $f:\...
- 133
1
vote
1
answer
189
views
Explicit Bits-back Coding (a.k.a. Free Energy Coding) applied to Gaussian mixtures
I've been trying to understand Bits-back coding (Frey, B. J., and G. E. Hinton. 1997.) a bit more (pun intended), which can be used to encode data with latent variable models. This tutorial by Pieter ...
- 129
1
vote
1
answer
114
views
Data processing inequality for interaction information
The interaction information is defined as $I(X;Y)-I(X;Y|Z)$. Let $Z-(X, Y) -(X', Y')$ be a Markov chain. Is there an inequality similar to the data processing inequality, relating $I(X';Y')-I(X';Y'|Z)...
- 131
2
votes
1
answer
133
views
Why Asymptotic Equipartition Property theorem proofs assume the source is memoryless?
I do not understand the assumption $X_1, X_2, \cdots$ are i.i.d. ~p(x) in the AEP proofs I have seen. I have read some different sources for understanding the Asymptotic Equipartition Property. Using ...
- 133
5
votes
1
answer
187
views
Kolmogorov Complexity of a Decidable Language
The Kolmogorov Complexity (KC) of a string $y$ is the size of the smallest program $f$ and input $x$ that: $y = f(x)$. Let's define a variation of Kolmogorov's complexity$^1$. Suppose a decidable ...
- 543
-1
votes
1
answer
61
views
Notation in proof for Asymptotic Equipartition Property
In the following lecture notes chapter 3, page 12-13, they state the following
We begin by introducting some important notation:
- For a set $\mathcal{S},|\mathcal{S}|$ denotes its cardinality (...
- 131
0
votes
1
answer
127
views
Volume of elements mapped to the same codeword is $2^{H(X|\hat{X})}$
In this paper by Tishby, Pereira and Bialek they mention on page 4 in the Relevant quantization chapter the setting is the following; Given some signal space $X \sim p(x)$ and a quantized codebook $\...
- 131
0
votes
1
answer
107
views
Notation of sequences in rate distortion theory
I have been reading whatever sources I could get my hands on today, regarding this problem.
Most notes online about rate distortion theory come from the book Elements of Information Theory by Thomas ...
- 131
7
votes
1
answer
213
views
Expected vs worst-case communication complexity
In the set disjointness problem of 2-party communication complexity, Alice and Bob are both given an $n$-bit string as input; denoted by $X$ for Alice's input, and $Y$ for Bob's input. They need to ...
4
votes
0
answers
89
views
Strong data-processing inequality: bound $TV(T_{\#}P_0,T_{\#}P_1)$ if $\|T(x)-x\|_\infty \le \varepsilon;\forall x \in \mathbb R^p$
Disclaimer. I've moved this question from MO hoping that here is the right venue. Also, this is my first post on this channel, so please have some patience.
So, Iet $X = (X,d)$ be a Polish space, ...
- 217
2
votes
0
answers
105
views
Representing data with Shannon entropy predicted bits
Let us assume a file based on a character set where each character has equal probability of occurance. This will result in the maximum entropy for that character set. On calculating the entropy, let ...
- 121
4
votes
1
answer
411
views
Maximization of Mutual Information
Let $X\in\{0,1\}^d$ be a Boolean vector and $Y, Z\in\{0,1\}$ are Boolean variables. Assume that there is a joint distribution $\mathcal{D}$ over $Y, Z$ and we'd like to find a joint distribution $\...
- 43
1
vote
0
answers
239
views
Minimum number of hours of speech needed to train a neural net to recognize speech [closed]
From a theoretical computer science point of view, is there a lower limit on the number of hours of speech needed to train a neural net to translate speech to text? An estimate from CMU is 3000-5000 ...
- 107
1
vote
1
answer
849
views
Chain rule for KL divergence
Is there an inequality to relate the KL divergence of two joint distribution and the sum of the KL divergence of their marginals? Or in particular, is there a proof or a counter example for the ...
- 223
2
votes
1
answer
159
views
Why not include private randomness in internal communication information definition?
I am using https://www.cs.toronto.edu/~toni/Courses/CommComplexity2014/Lectures/lecture12.pdf as a reference.
This isn't exactly a research question but I can't find a good place to ask it.
Suppose ...
- 23
4
votes
0
answers
107
views
Expected vs actual amount of information leaked by an $l$-bits message
Say we have a random variable $X$ that contains $k$ bits of information, and a message $M = f(X)$ ($M$ is deterministic given $X$) that is $l$ bits long, where $l<k$. This implies $H(X) = k$ and $...
- 223
1
vote
1
answer
165
views
Uniqueness of the distribution maximizing the channel capacity
Setting: We look at a discrete memoryless channel which takes an input probability distribution acting over symbols in $\mathcal{X}$ to an output probability distribution over symbols in $\mathcal{Y}$....
- 113
6
votes
1
answer
340
views
Is a binary sequence computable iff the Kolmogorov complexity of its initial segments is bounded?
Disclaimer: I am mostly unfamiliar with theoretical computer science, making it hard for me to navigate literature in the field. I ask the following out of curiosity.
Background/Motivation: Coming ...
- 163
5
votes
1
answer
188
views
Minimal information needed for determine some function
From calculus, we know that if someone has a continuous function $f$, it is enough to know $f$'s values on the rationals in order to know $f$ on the entire line. In some sense, a "countable amount of ...
- 51
11
votes
1
answer
359
views
Is algorithmic information theory still evolving?
I am currently looking for a subject for a thesis and encountered the field of algorithmic information theory.
The field seems very interesting for me, but it seems everything is the field was done ...
- 111
3
votes
2
answers
269
views
How can AIC converge in the limit when even 2 parameter models can have infinite VC dimension?
AIC-based model-selection converges to zero error in the limit, and also has finite-sample convergence that is rate-optimal with respect to worst case minimax error [1]. (Note that AIC refers to ...
- 105
1
vote
0
answers
65
views
Is there a theoretical guarantee that an autoencoder $g$ has $I(x;g(x)) \approx H(x)$?
I know that in general, a function $g$ can be a good auto-encoder (i.e., $g(x) \approx x$ for $x \sim D$) and on the same time $I(g(x);x)$ is small. This is the case when $g$ forms a good correlation ...
- 181
-1
votes
1
answer
199
views
Reducing disjoint or indexing or inner-product problem to s-t connectivity problem in directed graph
I am asked to prove that an O(1)-pass randomized streaming algorithm that solves s-t connectivity problem in a simple directed graph $G=(V,E)$ with $|V|=n$ vertices, with sucess possibility $>\frac{...
- 13
6
votes
1
answer
271
views
Algorithmic mutual information between random string and minimal Kolmogorov sufficient statistic
Regarding notation in the following, the function $\ell(B)$ returns the length of bitstring $B$, and the cardinality of set $S$ is denoted by $|S|$.
A bitstring $B$ is generated by drawing 0s and 1s ...
- 203
-1
votes
1
answer
74
views
Relationship between worst case length of transcript and entropy of transcript
Consider the two party model of communication complexity where Alice and Bob are given inputs $X$ and $Y$ sampled from some distribution $\mu$, and their goal is to solve some problem $P$ (the details ...
- 11
6
votes
2
answers
2k
views
Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?
While we usually use large e.g. 64 bit hashes, there are many techniques to reduce this size, e.g. for savings in storage and transmission.
Popular Bloom filter instead of marking just 1 hash ...
- 317
13
votes
1
answer
2k
views
Entropy and computational complexity
There are researcher showing that erasing bit has to consume energy, now is there any research done on the average consumption of energy of algorithm with computational complexity $F(n)$? I guess, ...
- 1,009
4
votes
1
answer
135
views
Can entropicly secure encryption algorithms be used on low-entropy messages by adding noise
There exist information-theoretic notions of security like Shannon's "perfect security" that one-time pads exhibit. All methods which achieve perfect security will require long keys, however. If we ...
- 1,131