# Questions tagged [information-theory]

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

248 questions
Filter by
Sorted by
Tagged with
40 views

44 views

### How to show that in noiseless coding theorem, the bound $\mathrm{MinACL}<H(P)+1$ is tight?

The theorem states that $$H(P)\leq\mathrm{MinACL}(P)<H(P)+1$$ where, $\mathrm{MinACL}$ means the minimum average code word length of a given information source, i.e. the average code word ...
266 views

### Huffman Coding vs Arithmetic Coding

Are there conditions under which given text $T$ that huffman code and arithmetic code will produce the exact encoding of $T$?
46 views

### What is the term for two file formats that describe the same amount of information?

I am working on file formats conversion. Some of them can be converted back and forth to others without losing any information (fields or precision of the numbers encoded), others file format do not ...
46 views

### What is the compressibility of this simple “book”?

Compressibility is defined as $$C=\frac{2^{HN}}{2^{H_{max}N}}$$ The book is made up of a simple alphabet of only {a,b,c,d} which occur with probabilities $$P(a)=0.2, P(b)=0.4, P(c)=0.1, P(d)=0.3$$ ...
148 views

### Why it is not a Huffman code

I have been given several examples I the aim is to explain why it is not a Huffman code. So, for instance, the first one was: $\{00,01,10,110\}$ This code is not Huffman becuase it has just one ...
7k views

### Do lossless compression algorithms reduce entropy?

According to Wikipedia: Shannon's entropy measures the information contained in a message as opposed to the portion of the message that is determined (or predictable). Examples of the latter ...
99 views

### Dependency on adjacent blocks decreases as block count increases

The following is an excerpt from Information Theory: A Tutorial Introduction, page 65. Now, supposing the identity of each letter in English does not depend on any letter that is more than 10 ...
270 views

### I think you can always compress compressed data, is it true?

In compressed data, repetition of same pattern is not a lot, so, you can expect it to be with space inside to contain always. I found a way to compress data without limitation. Is it right? Am I ...
44 views

### Computing/sketching essential bit content of a binary source

I'm given the Bernoulli distribution of a biased coin toss with probability distribution $P_X = \{0.2, 0.8\}$ over the alphabet $\mathcal{A}_X=\{0,1\}$. I want to sketch the normalized essential bit ...
2k views

### Shannon Entropy of 0.922, 3 Distinct Values

Given a string of values $AAAAAAAABC$, the Shannon Entropy in log base $2$ comes to $0.922$. From what I understand, in base $2$ the Shannon Entropy rounded up is the minimum number of bits ...
38 views

### How many prefix code we can find for a given distribution of probability?

A source emits 5 signals s1, s2, s3, s4 and s5 whose probabilities are as follows: 1/3, 1/3, 1/9, 1/9, 1/9, 1/9. How many prefix codes we can construct on A={a, b, c}? And how many are there with the ...
23 views

### What is the relation between the quantity of information of $A_i$ and $A$, where $A=\bigcup_iA_i$?

Let $A$ be an event divided into 4 events $A_i$ with the same probability. Why does the quantity of information of $A_i$ satisfy $$I(A_i) = I(A) + \log (4)?$$
49 views

### How to use HITS algorithm to rank pages

I am trying to implement a simple web search engine mechanism with using HITS algorithm. I understand how the algorithm work and produce hubs and authority values for each page. But how can I use this ...
93 views

### fully homomorphic encryption with information-theoretic security?

An encryption algorithm with information-theoretic security is one which even with infinite amount of computation cannot be broken. That is, given only the ciphertext, no amount of computation can ...
146 views

### what does the redundancy of a code means?

I was reading a paper about a transposition and single deletion error correcting code and they claim that the redundancy of the code was only $\log(6n-3)$ bits. But what does that means? I was ...
124 views

### Infinite Huffman Tree

We have to derive an optimal binary encoding for the infinite set of symbols $\{s_1, s_2, \dots \}$. They're distribution is given by $$p(s_i) = 9 \cdot 10^{-i}$$ My intuition was to use a Huffman ...
28 views

### Classify/Distinguish between 8008 binary grids, with 13 queries

I have $8008$ binary grids of size $6 \times 10$ (they are all grids with the property described below), which I want to distinguish between with at most $13$ queries. A query will determine if the ...
44 views

### Maximizing entropy under constraint

How do I prove that entropy is maximal for $P(A_2) = \cdots = P(A_n) = (1-a) /(n-1)$ while $P(A_1) = a$ (a fixed number) and $A_1,…, A_n$ is a partition of the sample space?
34 views

### How to know a certain grammar is parse-able

Is it possible to parse all kinds of structured data and give them a semantic meaning? For example, C++ is a really complicated language and I could never imagine a parser would be possible for it. ...
6k views

### Can data be compressed to size smaller than Shannon data compression limit?

I was reading about data compression algorithms and the theoretical limit for data compression. Recently I encountered a compression method called "Combinatorial Entropy Encoding", the main idea of ...
129 views

### Finding the total capacity of two communication channels

I have the transition matrices of two communication channels. I am able to find the capacity of each by performing an optimization calculation, however I need the total capacity of the two channels. ...
35 views

### How hexadecimal representation is more compact and intelligible for documentation?

My textbook says, "Instead, it is far better to use a hexadecimal representation for documentation purposes. Whether or not a code represents a binary number, it can be treated as ...
35 views

### Does data entropy depend on the arrangement of the characters in a file?

From what I understand data entropy controls the limit of data compression and it depends on the probability of the characters in the file. Assuming that we have a file of size 256 bytes containing ...
90 views

### A necessary [and sufficient?] condition for the number of comparisons required to sort $n$ elements

I am familiar with the decision tree based argument for the minimal number of comparisons required to sort $n$ distinct elements - Since there are $n!$ permutations on the $n$ elements, the decision ...
113 views

### Proof of Lower Bound for Deterministic Distinct Elements Algorithm

There is a proof in this document (page 8, Section 4, Lemma 3: https://inst.eecs.berkeley.edu/~cs170/fa16/lecture-11-29.pdf) that mirrors a proof my professor gave in my algorithms class. The lemma ...
169 views

### Applying Shannon Entropy to data storage

I know Shannon Entropy is defined for messages. When it's said the size of a file stored in a HDD is 1 MB, are we talking about the Shannon Entropy? If so, how do we extend the definition to static ...
27 views

### Is there a universal metric of “size of a program”?

There is a universal metric of information: amount of bits. It's universal in the sense that if we write a piece of information in DNA (4-ary digits), we can simply multiply by 2-log-4 to get the ...
232 views

### How realistic is the i.i.d assumption in the definition of Shannon's entropy?

Let me first say I come from a physics background and have about zero exposure to computer science, so the question may be very naive. Shannon's entropy looks perfectly natural and useful from a ...
172 views

### Kolmogorov Complexity proving there exists a constant for when if two strings are equal length

When talking about kolmogorov complexity, I understand that it describes true randomness of given (for now) a string $x$, if we can describe x in less than the $|x|$ then its complexity is said to be ...
1k views

88 views

### Calculating Frequency of Terms with Zipf's Law

I'm studying for an exam and came across this question. I feel like it's much simpler than I am making it out to be, but I'm not sure. Suppose we have a corpus in which Zipf’s Law holds. If the most ...