Questions tagged [information-theory]
Questions about Information theory, entropy, and information content of various sources
322
questions
0
votes
0
answers
28
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
84
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
34
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
...
- 143
1
vote
1
answer
33
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
20
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
33
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(...
- 215
0
votes
0
answers
14
views
Is there a mathematical classification of formal languages for denoting graphs as a sequence of finite symbols?
I believe a general or pure definition of a “graph” in mathematics can be from algebraic topology, where a graph can be more abstractly seen as a simplicial complex, or a cell complex, or with scheme ...
- 123
2
votes
0
answers
24
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
44
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
0
votes
0
answers
8
views
Does optimal input distribution for $W^{\otimes n}_{Y|X}$ tell us anything about the optimal input distribution for $W^{\otimes n-1}_{Y|X}$?
Suppose I have $n$ i.i.d. copies of some channel $W_{Y|X}$ for some finite $n$. I wish to send the maximum number of messages over these $n$ copies such that the error in decoding the message is at ...
- 262
0
votes
0
answers
13
views
One-shot capacity achieving input, permutation invariance and i.i.d. decomposition
Suppose I have $n$ iid copies of a channel $W_{Y|X}$ and denote this by $W_{Y|X}^{\otimes n}$. I found a one-shot capacity of $W_{Y|X}^{\otimes n}$ to be an entropic quantity (specifically, it is the ...
- 101
1
vote
0
answers
68
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
25
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$-...
- 532
0
votes
0
answers
25
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
0
votes
0
answers
40
views
Compare two communication channel capacities without calculating individual capacities
I have two communication channels:
$\Gamma_1 = \begin{pmatrix}
0 & 0 & 1\\
\frac{1}{6} & \frac{1}{6} & \frac{2}{3}\\
\frac{1}{3} & \frac{1}{3} & \frac{1}{3}
\end{pmatrix} \...
- 1
1
vote
4
answers
198
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 ...
- 133
0
votes
1
answer
56
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
39
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
42
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
67
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
50
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
29
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
42
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
16
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
66
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
41
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,308
0
votes
2
answers
140
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
141
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
234
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
42
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
38
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 ...
- 1
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 ...
- 299
1
vote
0
answers
17
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
199
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
23
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
118
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
52
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
14
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
136
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
101
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
2
votes
0
answers
27
views
Information theory - Expurgation step to go from average error to worst case error in the large error regime
Consider a discrete memoryless channel $N$. We use a code to send messages over this channel.
Shannon showed that if we have a code $C$ with a finite number of codewords $|C|$ such that the average ...
- 262
1
vote
2
answers
169
views
What is the entropy of an unordered list?
I'm trying to compress unordered lists of a few thousand integers for transmission over HTTP, and Claude Shannon is disappointing me with his mathematical ambiguity :)
Each integer is 6-digits, so ...
1
vote
3
answers
86
views
Is every binary sequence the output of some meaningful-text-input algorithm?
Here is the problem: Let's say we have a random binary sequence, just an arbitrary sequence of zeroes and ones (of some arbitrary length of digits). Can we find an algorithm that would decode/...
- 111
2
votes
1
answer
78
views
Is an AI upscaler incapable of reducing entropy?
I was reading the description of Anime4K (a video upscaler software) and I found a statement triggering my attention:
[upscaling is done] without any meaningful decrease in entropy (lost information
...
- 123
2
votes
1
answer
196
views
Deriving a lower bound on the conditional entropy, conditioned on an event
I came across Lemma 19 in Certifying Equality With Limited Interaction, which states the following for jointly distributed random variables $Z$, $W$, where $Z$ takes values in $\{0,1\}^n$, and some ...
- 23
2
votes
0
answers
26
views
Asymptotically Optimal Universal Code In Other Bases
Universal codes are fairly well studied, and many asymptotically optimal universal codes exist for binary data (see https://en.wikipedia.org/wiki/Universal_code_(data_compression) especially https://...
- 163
3
votes
1
answer
133
views
Capacity of Binary Erasure Channel
Consider the the binary erasure channel, with input and output alphabet $\{0,?,1\}$ and channel matrix
\begin{bmatrix}
1-\lambda-\mu & \mu & \lambda\\
0 & 1 & 0\\
\lambda & \mu &...
- 149