The information-theory tag has no wiki summary.
0
votes
1answer
47 views
Notions of information content and randomness of binary square matrix
We have well established theory for measuring the information content and randomness of binary strings. Notions such as Shanon entropy and Kolmogorov-complexity were developed for binary strings.
For ...
14
votes
2answers
227 views
What's harder: Shuffling a sorted deck or sorting a shuffled one?
You have an array of $n$ distinct elements. You have access to a comparator (a black box function taking two elements $a$ and $b$ and returning true iff $a < b$) and a truly random source of bits ...
6
votes
1answer
83 views
How are data types related to information theory?
I was just reading from wikipedia the following about information:
From the stance of information theory, information is taken as a
sequence of symbols from an alphabet, say an input alphabet χ, ...
2
votes
1answer
45 views
Mutual information and moment generating functions
I went to listen to a workshop and someone from the audience asked the presenter how the moments can improve the mutual information. I am learning about MI (Mutual Information) so didn't have enough ...
3
votes
1answer
36 views
Pointwise mutual information vs. Mutual information?
I am learning about information theory and mutual information. However, I am quite confused with MI(Mutual information) vs. PMI(Pointwise mutual information) especially signs of MI and PMI values. ...
4
votes
1answer
93 views
Information theory from a (very pure) mathematician's perspective
I'm a pure mathematician interested in learning about information theory. Unfortunately, I'm about as pure as they come - my specialty is mathematical logic, and I have absolutely no experience with ...
3
votes
1answer
60 views
$\ell_1$ Minimization of Probability Distribution and KL-Divergence
Suppose through $\ell_1$ minimization I obtained two sparse probability distributions $P, Q$ which may contain many zero terms. Then I would like to compute the KL-Divergence of them $D(P || Q) = ...
2
votes
2answers
112 views
Generalized data structure
Data structures are seen as important, equal to algorithms. This view is especially encouraged in situations, where appropriate data structure is the main factor that allows an algorithm to exist and ...
6
votes
1answer
133 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 ...
6
votes
1answer
69 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
110 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 ...
2
votes
4answers
326 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
55 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 ...
5
votes
3answers
302 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 ...
5
votes
1answer
125 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
132 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
124 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
119 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 ...
6
votes
1answer
108 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 ...
2
votes
1answer
234 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
92 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 ...
12
votes
3answers
224 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 ...
8
votes
1answer
129 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 ...
11
votes
4answers
1k 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 ...
12
votes
1answer
228 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 ...
