Questions tagged [information-theory]

Questions about Information theory, entropy, and information content of various sources

Filter by
Sorted by
Tagged with
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 ...
Sanjay  Biswas's user avatar
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. ...
clayton groth's user avatar
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 ...
ocksumoron's user avatar
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 ...
Zaz's user avatar
  • 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 ...
terepy's user avatar
  • 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?
PatrickBateman's user avatar
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(...
accounted4's user avatar
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 ...
Julius H.'s user avatar
  • 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 ...
Syamantak Kumar's user avatar
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$...
G S's user avatar
  • 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 ...
user1936752's user avatar
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 ...
JRT's user avatar
  • 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 ...
user avatar
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$-...
chausies's user avatar
  • 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 $...
unique's user avatar
  • 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} \...
Nodreh's user avatar
  • 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 ...
BipedalJoe's user avatar
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 ...
PTSONIC's user avatar
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 ...
Riemann's user avatar
  • 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-...
Samyon Ristov's user avatar
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-...
coderodde's user avatar
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 ...
Chris's user avatar
  • 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 ...
Gerrit Begher's user avatar
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 ...
new_student's user avatar
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 ...
Sam's user avatar
  • 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, ...
prime_mover's user avatar
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 ...
Martin Berger's user avatar
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 ...
Noel Jacob's user avatar
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)).
Sam's user avatar
  • 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 ...
Sam's user avatar
  • 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?
A45's user avatar
  • 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 ...
Shriram's user avatar
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 ...
Oleg Dats's user avatar
  • 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 ...
Gianni Spear's user avatar
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?
Z XH's user avatar
  • 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 ...
Froskoy2022's user avatar
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$$...
Water Lily's user avatar
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 ...
Water Lily's user avatar
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 ...
Dominic Peng's user avatar
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 ...
user141710's user avatar
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 ...
sayanc2011's user avatar
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 ...
Paradigm's user avatar
  • 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 ...
sadolit's user avatar
  • 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 ...
user1936752's user avatar
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 ...
TheEnvironmentalist's user avatar
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/...
jdods's user avatar
  • 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 ...
DarioP's user avatar
  • 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 ...
New_In_CS's user avatar
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://...
LambdaBeta's user avatar
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 &...
guipa's user avatar
  • 149

1
2 3 4 5
7