Questions tagged [information-theory]
Questions about Information theory, entropy, and information content of various sources
329
questions
1
vote
1
answer
24
views
Is always $KL[f(x|a) || g(x|a) ] \leq KL[f(x) || g(x) ]$ for fixed $a$?
Suppose we have two prior distributions over $X$, namely $f(x)$ and $g(x)$ (assume $X$ is finite if necessary). Define $f(x|a) = Z_f\cdot f(x)\cdot h(a|x)$ and $g(x|a) = Z_g \cdot g(x) \cdot h(a|x)$, ...
- 4,062
0
votes
0
answers
59
views
How many states does a 2-symbol turing machine need on average to compute a N bit number?
The busy beaver problem asks what is the largest number computable by a 2-symbol N-state Turing machine, however, most numbers however are not re-presentable by a smaller program.
For a sufficiently ...
- 166
7
votes
1
answer
2k
views
Any algorithm to do Huffman encoding without using graphs?
QUESTION
Is there any efficient way to encode words into bits, without having to draw the graphs, solely by only using a list of probabilities?
EXAMPLE
This list of words:
Pr('Apple') = 0.5.
Pr('...
- 195
4
votes
1
answer
105
views
Expected Entropy of the Empirical Distribution
Given a distribution on $n$ outcomes where outcome $i$ has probability $p_i$, the Shannon entropy of the distribution is defined as $- \sum_{i = 1}^n p_i \cdot \log_2 p_i$.
Let's suppose I sample from ...
- 141
1
vote
0
answers
47
views
Communication Complexity of "2-Bit"
[For context, I'm trying to work through the derivation of Lemma 2.1 (2-Bit) here, https://users.cs.utah.edu/~jeffp/papers/multiCC-soda12.pdf. ]
The '2-Bit' setup is that Alice draws a bit-string of ...
- 46
2
votes
2
answers
52
views
Information content of a real number
Suppose I have a sequence of 5 IID Bernoulli variables, with probability of having value 1 being 0.5. If we observe an instance of the sequence, the information content would be 5 bits, as each ...
0
votes
0
answers
29
views
Algorithmic Information Approximation As Software Surface Minimization
Can putting information systems through a "functional bottleneck" to approximate their Algorithmic Information reduce their attack and argument surfaces substantially?
Software surface may ...
- 404
0
votes
0
answers
45
views
Do these courses fall under theoretical computer ccience [duplicate]
I am planning to apply for master's degree at TU Berlin and have to take some courses on theoretical computer science since the university requires me to take some credits on theoretical computer ...
- 1
0
votes
0
answers
50
views
Do these courses fall under theoretical computer ccience
I am planning to apply for master's degree at TU Berlin and have to take some courses on theoretical computer science since the university requires me to take some credits on theoretical computer ...
- 1
0
votes
0
answers
22
views
Do these courses fall under theoretical computer ccience [duplicate]
I am planning to apply for master's degree at TU Berlin and have to take some courses on theoretical computer science since the university requires me to take some credits on theoretical computer ...
- 1
1
vote
1
answer
67
views
Kolmogorov complexity of tuples
Exercise 14.1 of Elements of Information Theory asks us to prove that there is a constant c such that
$$K(x,y)\leq K(x) +K(y)+c$$
for all binary strings $x,y$. Intuitively this seems true. Just write ...
- 11
0
votes
0
answers
35
views
What are the steps to create an intuitive and straightforward proof of the optimality of Huffman coding?
I am having great difficulty following the proof in class. I assume "optimal" means it minimizes the Average bit length to encode an alphabet with known frequencies. My understanding of how ...
0
votes
0
answers
44
views
Is computation of a given operation infinitely multiply realizable 'computationally-speaking'?
This is a somewhat philosophical question, but I would like to know if there is a hard answer. Also, please excuse my likely unconventional terminology here, this is not my field of expertise.
...
- 101
2
votes
0
answers
89
views
Data structure for prefix covering
I have a list $[1, 2, \ldots, T]$. I want to create a collection of subsets, such that:
each element belongs to a small number of subsets
each prefix is a union of small number of subsets (these ...
- 21
1
vote
0
answers
41
views
How to prove a minimum number of queries needed to determine a piece of information
You have 27 coins, 1 of which is a different weight. Using a balance scale with 2 pans, how can you determine which coin is different in only 4 weighings?
Generalize this to N coins.
Hint
Solution
...
- 145
1
vote
1
answer
43
views
Is it possible to avoid encoding the state in streaming ANS?
regular ANS collects all the data into one big integer and provides optimal compression. In cases where all the symbol probabilities are powers of two, it is just as good as huffman coding (because ...
- 13
0
votes
1
answer
21
views
NP-HARD optimization problem and instance correlation
If an optimization problem A is NP-hard and P≠NP, then does there exist an instance x of A such that no polynomial algorithm provides an optimal solution for x?
0
votes
1
answer
38
views
What algorithm constructs the optimal code $f$ of size $a$?
I'm looking at Shannon's source coding theorem for symbol codes. It provides a very nice bound on the expected code length $S=|f(X)|$ of an optimal code $f$ over the sequence variable $X$:
$$
\frac{H(...
- 235
2
votes
0
answers
34
views
Sample Complexity Lower bound for PCA
I am trying to find (without success) a sample complexity lower bound for PCA. The concrete problem I am considering is -
$X_{1}, X_{2}, \cdots X_{n} \sim D(0, \Sigma)$ are $d$-dimensional vectors ...
1
vote
1
answer
45
views
Why do simple Logical Gates have an Irrational amount of Bits?
Suppose $2$ bits are used to encode a message, A and B.
If you know $A$ is $1$, you have one bit of information.
If you know $A\land B$ is $1$, you have two bits of information.
If you know $A\land B$...
- 13
1
vote
0
answers
72
views
How can the mutual information be equal to minus conditional entropy? [closed]
I am reading the following paper:
https://arxiv.org/abs/2301.06941
The authors in Eq.(8) have obtained a relation which has the mutual information, $i$, in the exponent of the exponential on the RHS ...
user157955
0
votes
0
answers
28
views
Asymmetric communication between two symmetric parties?
(sci-fi-esque question inspired by Counterpart).
A portal between our world (called $A$) and a parallel world that's exactly the same (called $B$) opens up. Bob sees himself through this portal.
$A$-...
- 542
0
votes
0
answers
26
views
Best function to preserve information after decreasing color depth?
Let's assume, I have a grayscale image that every pixel represented with 8 bits. I want to quantize (decrease color depth) the image into 2 bits. Hence, I need a function as $f:A\rightarrow B$ where $...
- 101
1
vote
4
answers
222
views
Is the reason for a stack to decrease the size of a program (by adding the use of subroutines)?
The stack allows subroutines to be used. It can store return address for "return from subroutine" instruction (RTN) and also arguments for the function.
It is not possible to store return ...
- 233
0
votes
1
answer
79
views
Consider a ternary channel with the following channel matrix:
\begin{bmatrix}
1-\alpha & 3\alpha/4 & \alpha/4\\
\alpha/4 & 1-\alpha & 3\alpha/4\\
3\alpha/4 & \alpha/4 & 1-\alpha\\
\end{bmatrix}
I was told that the probability of error of ...
- 5
0
votes
1
answer
45
views
Which system has higher entropy?
Suppose that I have two random processes. Process $X$ has probability 0.5 to be in state A and probability 0.5 to be in state B. Process $Y$ has probability 0.4 to be in state A and probability 0.6 to ...
- 103
1
vote
1
answer
46
views
Can a static pre-shared database reduce communication size?
Is the problem of communication with a pre-shared database studied? If yes, what field studies it, or which researchers work on it?
Let there be two parties that want to share multiple yet-to-be-...
0
votes
1
answer
70
views
Number of bit string interpretations correct?
Suppose you are given a bit string $B[1 ... n]$. Now, suppose that some bits are just padding bits conveying no information, the rest of the bits may be permuted and some meaningful (that is, non-...
- 52
2
votes
1
answer
51
views
Storing game traces (e.g. Chess, Othello) in a minimal number of bits
I am thinking about the problem of storing traces of games like Chess and Othello in an information-theoretic minimal number of bits. My idea was to think of a game as an ordered tree of possible ...
- 131
0
votes
1
answer
30
views
Reference request: Time and proofs of a shared past
(Short discaimer: I'm a mathematician by education (category theory, algebraic geometry) and so mostly unaware of how different fields in CS relate to each other. I'd be very happy to just get some ...
- 103
2
votes
0
answers
49
views
Generalizing Fano's Inequality [closed]
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 ...
- 21
1
vote
0
answers
25
views
the principle behind asking the minimum amount of questions for determining information entropy
This certain Khan Academy videos introduces the intuition about information entropy: https://www.youtube.com/watch?v=2s3aJfRr9gE&t=102s . It relates information entropy to the expected number of ...
- 163
0
votes
1
answer
148
views
How many bits are required to encode information in probability set G = [0.001, 0.002, 0.003, 0.994]?
I am currently working on data compression and thought it would be a good time to read up on the basics of information theory to better understand data compression and its algorithms.
As I understand, ...
0
votes
0
answers
43
views
Algebra of error models and error correcting codes?
In coding theory we typically consider the situation where we have a
channel that connects a sender and receiver. The messages flowing from
the sender to the receiver are corrupted by an error source ...
- 8,358
0
votes
2
answers
226
views
Binary compression algorithm with decompress by index
I have a list of 256-bit binary data to store. Any algorithm for doing lossless compression on it in a way I can retrieve an entry by its index without decompressing the whole data (if possible). The ...
1
vote
1
answer
213
views
Chain rule for mutual information
I am a bit confused in the following definition:
what does comma mean. I know I(X;Y) is the mutual information between X and Y but I am not sure how to interpret the I(X_1,X_2;Y)).
- 163
1
vote
1
answer
254
views
Undecidability in optimal data compression
There is this certain slide in Coursera Computer Science: Algorithms, Theory, and Machines course:
I think it is saying finding the optimal size of given data is undecidable. However, I thought there ...
- 163
1
vote
0
answers
45
views
Is there a method for information transfer without copying the data?
What I mean is, if in real life I had an object and I gave it to you, I would not have it anymore. I did not give you a copy of the object.
Is there a way to do that with information?
- 111
0
votes
0
answers
56
views
How to compress highly correlated arrays?
I want to write a compression algorithm for a specific use case that I have.
I have many arrays which are for the most part, very similar. Each value in the array is an integer and is related to the ...
- 101
1
vote
4
answers
1k
views
What is the name of the following binary encoding?
S is a the set of binary strings in Shortlex order: [0,1,00,01,10,11,...]
I want to encode / decode natural numbers with the following scheme:
Encoding N: For ...
- 309
1
vote
0
answers
19
views
What does it mean for an algorithm to not resample points?
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 ...
- 251
0
votes
1
answer
259
views
If all words have the same frequency, is the generated Huffman tree a balanced binary tree?
If all words have the same frequency, is the generated Huffman tree a balanced binary tree? At the same time, is the generated Huffman tree a complete binary tree?
- 11
1
vote
0
answers
25
views
Noisy channel coding: how to design a code for a discrete channel
When determining the capacity of a discrete channel, we maximise mutual information, and in doing so find the optimal input distribution for that channel.
I know that the noisy-channel coding theorem ...
- 11
1
vote
1
answer
46
views
Entropy of $\{X_1,\ldots,X_T\}$ where $X_1,\ldots,X_T \in_R [Q]$
I have a noiseless T-user multiple access channel. Let $[Q] = \{1, \dots , Q \}$. The users send symbols $X_i ∈[Q], i = 1, \dots , T$ . The channel is defined as follows
$$(X_1, X_2, \dots , X_T) → Y$$...
- 13
0
votes
1
answer
164
views
Upper bound of sum of codewords lengths
I need to show that for any binary optimal code for $n$-letter source the following inequality
holds:
$$\sum_{i=1}^n l_i \leq 0.5(n + 2)(n −1).$$
By $l_i$ denoted the length of the sequence ...
- 13
1
vote
1
answer
56
views
Sorting lower bound is linear when only a constant number of distinct keys?
I saw this proposition on Sedgewick's lecture slides on QuickSort, and I've been wondering why the number of comparisons is linear in the case of a constant number of distinct keys. I tried to ...
- 13
0
votes
0
answers
17
views
What does it exactly mean by information management as a function of O/s
I have read that information management is a function of O/s by which it
A) Manages, stores, retrieves,modify data. It makes sure that right people have access to their information.
B) Some of the ...
- 101
1
vote
0
answers
172
views
How to decode shortened Reed-Solomon code?
I am working with a shortened version of $[n,k,d]$ Reed-Solomon code. I am encoding a message of size $k−l$ which gives a shortened code of size $n−l$ (this is equivalent to encoding the same message ...
- 11
0
votes
0
answers
11
views
Is there an entropy evaluation method with an unified length?
For entropy, the most common one is Shannon entropy, however, it ignores time series of data. For instance, data 0x00001111 and 0x01010101 are given the same entropy. It is obvious that the second ...
- 101
4
votes
2
answers
117
views
Proof in the "Reaching Agreement in the Presence of Faults"
I am reading the "Reaching Agreement in the Presence of Faults", M. Pease et al and trying to understand their proof for the $n \geq 3m+1$ case.
In the induction step $m \gt 0$ it says the ...
- 41