Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [information-theory]

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

Filter by
Sorted by
Tagged with
1 vote
2 answers
43 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 ...
Ishan Kashyap Hazarika's user avatar
0 votes
0 answers
27 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 ...
James Bowery's user avatar
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 ...
Burak's user avatar
  • 1
0 votes
0 answers
45 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 ...
Burak's user avatar
  • 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 ...
Burak's user avatar
  • 1
1 vote
1 answer
62 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 ...
Caspar's user avatar
  • 11
0 votes
0 answers
33 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
87 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
36 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
  • 145
1 vote
1 answer
37 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
36 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 Hamilton's user avatar
2 votes
0 answers
32 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
1 vote
0 answers
70 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
27 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
1 vote
4 answers
217 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
72 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
43 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
43 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
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-...
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
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 ...
Gerrit Begher's user avatar
2 votes
0 answers
47 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
17 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
123 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
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 ...
Martin Berger's user avatar
0 votes
2 answers
191 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
195 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
248 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
43 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
49 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
  • 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 ...
Oleg Dats's user avatar
  • 299
1 vote
0 answers
18 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
245 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
160 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
54 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
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 ...
user141710's user avatar
1 vote
0 answers
157 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
112 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
30 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
198 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
90 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
86 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

1
2 3 4 5
7