# Questions tagged [information-theory]

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

329 questions
Filter by
Sorted by
Tagged with
1 vote
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
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
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
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
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 ...
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 ...
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
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 ...
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 ...
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 vote
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
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 ...
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. ...
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 ...
1 vote
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
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
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?
38 views

1 vote
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 ...
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
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 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
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 ...