# Questions tagged [information-theory]

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

217 questions
Filter by
Sorted by
Tagged with
1answer
732 views

### Generalizing the Comparison Sorting Lower Bound Proof

Let's start with the comparison sorting lower bound proof, which I'll summarize as follows: For $n$ distinct numbers, there are $n!$ possible orderings. There is only one correct sorted sequence of ...
1answer
774 views

### Rényi entropy at infinity or min-entropy

I'm reading a paper that refers to the limit as n goes to infinity of Rényi entropy. It defines it as ${{H}_{n}}\left( X \right)=\dfrac{1}{1-n} \log_2 \left( \sum\limits_{i=1}^{N}{p_{i}^{n}} \right)$. ...
1answer
2k views

### What units should Shannon entropy be measured in?

The only examples I've seen use bits as a measurement of entropy, but all these examples happen to use binary code alphabets. If we wanted to see how well a coding with a code alphabet of length n ...
4answers
3k views

### Is there any theoretically proven optimal compression algorithm?

Is Huffman coding always optimal since it uses Shanon's ideas? What about text, image, video, ... compression? Is this subject still active in the field? What classical or modern references should I ...
1answer
135 views

### What are the rudimentary types of information connectivity i.e. model types?

I am looking at a modelling tool and are trying to determine all the types of ways that you can model (at a rudimentary level) I remember seeing a list of ways in which you can connect or categorise ...
3answers
7k views

### Is Huffman Encoding always optimal?

The requirement of the encoding to be prefix free results in large trees due to the tree having to be complete. Is there a threshold where fixed-length non-encoded storage of data would be more ...
1answer
881 views

### Measuring entropy for a table (e.g., SQL results)

We're running some benchmarks for an approximative query-answering system. It's sufficient to just think of it as running some SQL queries with joins. We are counting the results returned as part of ...
1answer
219 views

### Source entropy and other questions related to information theory

Kolmogorov-Sinai entropy (KS) explains the mathematical concept behind KS entropy. $$h ( T ) =\sup\limits_{\xi} \, h ( T , \xi )$$ defines the formula for KS where the left-hand side is nothing but ...
1answer
653 views

### Time series probability and mutual information

There is a time series of say $100$ data points. I wish to assign symbols of $0, 1, 2$ for each unique data point. The issue is I have tried but got stuck since no matter I specify the symbols, the ...
1answer
310 views

### Operations on OBDD: negation through Shannon's expansion

I have a problem with the application of the Shannon expansion for to obtain the negation of a formula boolean, than will need for implement the negation operator on OBDD (Order Binary Decision ...
1answer
169 views

### Prove fingerprinting

Let $a \neq b$ be two integers from the interval $[1, 2^n].$ Let $p$ be a random prime with $1 \le p \le n^c.$ Prove that \text{Pr}_{p \in \mathsf{Primes}}\{a \equiv b \pmod{p}\} \le c \ln(n)/(n^{...
2answers
2k views

### Can the Bell-LaPadula model emulate the Chinese Wall model?

I have been reading on security policies and the question wether Bell-LaPadula can be used to implement Chinese Wall. Does anyone know more about it?
1answer
127 views

### Why are blocking artifacts serious when there is fast motion in MPEG?

Why are blocking artifacts serious when there is fast motion in MPEG? Here is the guess I made: In MPEG, each block in an encoding frame is matched with a block in the reference frame. If the ...
3answers
403 views

### Difference between “information” and “useful information” in algorithmic information theory

According to Wikipedia: Informally, from the point of view of algorithmic information theory, the information content of a string is equivalent to the length of the shortest possible self-contained ...
1answer
205 views

### Error-correcting rate is misleading

In coding theory, 'how good a code is' means how many channel errors can be corrected, or better put, the maximal noise level that the code can deal with. In order to get better codes, the codes are ...
5answers
11k views

### Why is encrypting with the same one-time-pad not good?

To encrypt a message $m_1$ with a one-time-pad key $k$ you do $Enc(m_1,k) = m_1 \oplus k$. If you use the same $k$ to encrypt a different message $m_2$ you get $Enc(m_2,k) = m_2 \oplus k$, and if ...
1answer
850 views

### Efficient encoding of sudoku puzzles

Specifying any arbitrary 9x9 grid requires giving the position and value of each square. A naïve encoding for this might give 81 (x, y, value) triplets, requiring 4 bits for each x, y, and value (1-9 =...