Questions tagged [information-theory]

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

Filter by
Sorted by
Tagged with
6
votes
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 ...
8
votes
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)$. ...
4
votes
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 ...
7
votes
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 ...
4
votes
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 ...
9
votes
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 ...
6
votes
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 ...
3
votes
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 ...
0
votes
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 ...
3
votes
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 ...
7
votes
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^{...
3
votes
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?
5
votes
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 ...
16
votes
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 ...
10
votes
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 ...
19
votes
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 ...
16
votes
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 =...