Questions tagged [it.information-theory]
Questions in Information Theory
211 questions
18
votes
7
answers
25k
views
Which is the limit of lossless compression data? (if there exists such a limit)
Lately I've been dealing with compression-related algorithms, and I was wondering which is the best compression ratio that can be achievable by lossless data compression.
So far, the only source I ...
1
vote
2
answers
170
views
Encoding of nodes in Binary Decision Diagrams
A straightforward implementation of Binary Decision Diagrams (BDDs) typically requires 12 bytes per node, with an additional 4 bytes commonly used for auxiliary data. Each node is encoded as a 4-tuple ...
- 1
4
votes
1
answer
171
views
A potentially novel complexity measure for sets of strings
Inspired partly by Scott Aaronson's post about the first law of complexodynamics, I've been thinking lately about how to quantify the "interesting" or "structured" complexity of a ...
- 12.4k
0
votes
0
answers
38
views
Dependence of lossless compression (e.g. Lempel-Ziv) on string length and alphabet size
Suppose we have a lossless compression algorithm A, which compresses a string of length $n$.The symbols in the string are chosen uniformly at random from an alphabet with cardinality $p$. Different ...
0
votes
0
answers
59
views
Why LOUDS is considered succinct coding?
LOUDS encoding is widely cited as succinct, e.g., in the papers, in Github repos, etc.
It is straightforward that LOUDS takes 2n bits for encoding an ordered tree ...
- 113
1
vote
1
answer
91
views
Is it possible to encode the structure of a binary cardinal tree with n nodes using only n bits?
By binary cardinal tree, I mean a tree with degree 2.
The question confuses me because I know LOUDS/DFUDS can encode binary trees with 2n bits; however, this paper claims that it is possible to encode ...
- 18.7k
0
votes
0
answers
83
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 ...
- 101
0
votes
1
answer
48
views
Feature selection problem under promise
Are there well used examples of feature selection problem where the problem is defined under certain promise? Let's say the task is to select the minimum number of features such that the mutual ...
- 181
1
vote
0
answers
46
views
Practical Applications of Information Algebras
I've started reading Information Algebras, Kohlas (the Wikipedia may give you the gist) and I am curious as to whether any ideas from this theory/book could be practically implemented, perhaps as some ...
- 111
1
vote
1
answer
83
views
Detecting Erroneous Corrections
A block code $C$, with minimum distance $d$ can be used to:
Detect $d - 1$ errors
Correct $\lfloor\frac{d - 1}{2}\rfloor$ errors
However, the above usually assumes that the number of errors that are ...
CommunityBot
- 1
0
votes
0
answers
29
views
Is it accurate to describe a computer as a dynamic memory state?
is this an accurate statement? And where can I find out more about these topics?
At any point in time a computer is holding a memory state. Because
the computer is moving in various ways we can call ...
- 9
1
vote
1
answer
132
views
Relation Between Different Definitions of Information Distance
I'm reading the fourth edition of An Introduction to Kolmogorov Complexity and Its Applications by Li and Vitanyi. In Section 8.3 of the book, it introduces the concept of "information distance.&...
- 236
0
votes
1
answer
124
views
Maximum theoretical compression ratio for real-valued data
Given a sequence of $N$ real-valued vectors $\mathbf{v_1}, \mathbf{v_2}, ..., \mathbf{v_N}$, each of dimension $d$, do any of the below bounds exist?
The minimum number of real-valued vectors of ...
- 25.1k
1
vote
0
answers
46
views
Why the measure of information complexities for passive and active learning are increasing in research communities?
I am a PhD student working on the theory of active learning.
Over the years, accepted papers in COLT and ALT for active learning are focused on approaches that almost all of them define new ...
- 122
1
vote
1
answer
142
views
Information Bottleneck - Calculating the Mutual information between the Labels and the Features [closed]
I am trying to understand the Nonlinear Information Bottlecneck paper along with their implementation, but I am confused as to what is actually being calculated in the Mutual information $(I(Y, M))$ ...
- 41
62
votes
14
answers
5k
views
Information Theory used to prove neat combinatorial statements?
What's your favorite examples where information theory is used to prove a neat combinatorial statement in a simple way ?
Some examples I can think of are related to lower bounds for locally decodable ...
- 5,823
2
votes
1
answer
1k
views
Can the mutual information of a "cell" be negative?
Please forgive me if this is not the right Stack Exchange (I also posted it at Cross Validated). Please also forgive me for inventing terms.
For discrete random variables X and Y, the mutual ...
- 3
0
votes
0
answers
53
views
Can information, eg. Shannon Entropy, be considered an absolute value?
This question is a distillation of my question here: How do I calculate the information content of a mass spectrum?
Using a theoretical instrument that makes perfect measurements of fundamental ...
- 101
1
vote
2
answers
220
views
How much information does it take to specify, not each member of a group, but any one member?
It takes exactly $\log_2 n := \lg n$ bits of information to specify a number from $\{1,2,\ldots,n\}.$ Likewise, it takes $\lg{n\choose s}$ bits of information to specify a subset of $s$ out of the $n$ ...
- 11k
0
votes
0
answers
76
views
How do I calculate the information content of a mass spectrum?
Ions in a mass spectrum are represented using two independent values for the mass-to-charge ratio [m/z] of the ion and it's relative abundance. Here's an example for caffeine from HMDB: https://hmdb....
- 101
0
votes
1
answer
51
views
Looking for information on Information Theory applied to image pixelation
I'm in seventh grade and am doing a science project about how age and gender affects people's ability to recognize pixelated images. For background research I have been reading about information ...
- 12.4k
3
votes
0
answers
25
views
Modelling channels without specifying input alphabets
The standard mathematical model of a communication channel is that of a stochastic matrix $(C(x|a))_{a \in A, x \in X}$, where $A$ is the input alphabet and $X$ the output alphabet.
This definition ...
- 131
1
vote
1
answer
220
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}$....
- 25.1k
1
vote
0
answers
101
views
Generalizing Fano's inequality
Fano's inequality says the following:
Theorem: Let $X$ be a random variable with range $M$. Let $\hat{X} = g(Y)$ be the predicted value of $X$ given some transmitted value $Y$, where $g$ is a ...
- 11
2
votes
0
answers
198
views
On the number of optimal prefix-free binary codes [closed]
Let $T$ be a text of length $L$ containing the symbols $$\mathcal{A}=\{a_1, a_2, \ldots, a_n\},$$ where each symbol appears at least once and no other symbol appears in $T$.
Define the weights $$\...
- 21
0
votes
1
answer
213
views
Information theoretic arguments for complexity
This Wikipedia article,Decision tree model, states that decision tree complexity lower bound $O(n \log_2 n)$ for sorting problem is information theoretic since any algorithm ( modeled as decision ...
- 12.4k
0
votes
0
answers
61
views
Is there a name/terminology for binary codes with evenly spaced number of ones?
I am generating a random binary matrix $A \in \{0, 1\}^{m \times n}$ with the number of ones in each row set to evenly spaced numbers from an interval. For example, if $n=50$, the number of ones for $...
- 109
2
votes
0
answers
72
views
Origin of Berge's (Weak) Perfect Graph Conjecture
In an account of his thought process (refer p. 3) leading up to the perfect graph conjecture (which I'm preparing a seminar talk on), C. Berge states what seems to be a crucial step:
(1) a graph $G$ ...
- 2,826
0
votes
0
answers
64
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
180
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=...
- 25.1k
0
votes
1
answer
70
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 ...
CommunityBot
- 1
1
vote
1
answer
189
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. ...
- 25.1k
5
votes
0
answers
282
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 ...
- 109
2
votes
0
answers
91
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 ...
- 630
9
votes
6
answers
3k
views
Where does the information in a fractal come from?
When I view a fractal such as the Mandelbrot, my first thought is, where did this interesting picture come from. For a picture of this complexity, the information that generated this picture must be ...
9
votes
0
answers
161
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 ...
- 2,343
1
vote
0
answers
118
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
250
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 ...
- 321
3
votes
2
answers
510
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 ...
- 2,070
4
votes
1
answer
209
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 ...
CommunityBot
- 1
33
votes
5
answers
3k
views
Efficiently computable variants of Kolmogorov complexity
Kolmogorov prefix complexity (i.e. $K(x)$ is the size of minimal self-delimiting program that outputs $x$) has several nice features:
It corresponds to an intuition of giving strings with patters or ...
- 479
1
vote
0
answers
57
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 ...
- 31
1
vote
0
answers
130
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
180
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
457
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,...
- 376
4
votes
3
answers
5k
views
Difference between self-information and entropy
I get a bit confused about different definitions of entropy and/or self-information.
Entropy?
$$ H(X) = - \sum_{x \in X} P_X(x) \cdot \log{\left(P_X(x)\right)} $$
Self-information?
$$ I(x) = - \...
- 141
0
votes
1
answer
158
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 $\...
CommunityBot
- 1
0
votes
1
answer
123
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 ...
- 103
3
votes
1
answer
272
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,491
0
votes
0
answers
16
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