Questions tagged [information-theory]
Questions about Information theory, entropy, and information content of various sources
326
questions
61
votes
8
answers
34k
views
Is Morse code without spaces uniquely decipherable?
Are all Morse code strings uniquely decipherable? Without the spaces,
......-...-..---.-----.-..-..-..
could be Hello World ...
40
votes
7
answers
5k
views
Can PRNGs be used to magically compress stuff?
This idea occurred to me as a kid learning to program and
on first encountering PRNG's. I still don't know how realistic
it is, but now there's stack exchange.
Here's a 14 year-old's scheme for an ...
35
votes
6
answers
8k
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 ...
32
votes
4
answers
30k
views
Is Morse Code binary, ternary or quinary?
I am reading the book: "Code: The Hidden Language of Computer Hardware and Software" and in Chapter 2 author says:
Morse code is said to be a binary (literally meaning two by two) code
...
31
votes
2
answers
2k
views
Simulating a probability of 1 of 2^N with less than N random bits
Say I need to simulate the following discrete distribution:
$$
P(X = k) =
\begin{cases}
\frac{1}{2^N}, & \text{if $k = 1$} \\
1 - \frac{1}{2^N}, & \text{if $k = 0$}
\end{cases}
$$
The most ...
29
votes
7
answers
30k
views
Efficient compression of simple binary data
I have a file containing ordered binary numbers from $0$ to $2^n - 1$:
0000000000
0000000001
0000000010
0000000011
0000000100
...
1111111111
7z did not compress ...
26
votes
6
answers
20k
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 ...
23
votes
5
answers
7k
views
Data compression using prime numbers
I have recently stumbled upon the following interesting article which claims to efficiently compress random data sets by always more than 50%, regardless of the type and format of the data.
Basically ...
20
votes
4
answers
2k
views
Compressing two integers disregarding order
Comparing an ordered pair (x,y) to an unordered pair {x, y} (set), then information theoretically, the difference is only one bit, as whether x comes first or y requires exactly a single bit to ...
19
votes
4
answers
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 ...
19
votes
2
answers
1k
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 (...
17
votes
3
answers
497
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 ...
17
votes
3
answers
2k
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 =...
14
votes
3
answers
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 ...
14
votes
5
answers
3k
views
PRNG for generating numbers with n set bits exactly
I'm currently writing some code to generate binary data. I specifically need to generate 64-bit numbers with a given number of set bits; more precisely, the procedure should take some $0 < n < ...
12
votes
4
answers
8k
views
Compression of Random Data is Impossible?
A few days ago this appeared on HN http://www.patrickcraig.co.uk/other/compression.htm. This refers to a challenge from 2001 - where someone was offering a prize of \$5000 for any kind of reduction to ...
12
votes
2
answers
2k
views
Is there a generalization of Huffman Coding to Arithmetic coding?
In trying to understand the relationships between Huffman Coding, Arithmetic Coding, and Range Coding, I began to think of the shortcomings of Huffman coding to be related to the problem of fractional ...
11
votes
6
answers
2k
views
Find the number using binary search against one possible lie
We all know this classic problem, "there is some hidden number and you have to interactively guess it.", which could be solved using binary search when we know that maximum number that we can guess.
...
10
votes
1
answer
246
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 ...
9
votes
3
answers
13k
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 ...
9
votes
2
answers
2k
views
Does a binary code with length 6, size 32 and distance 2 exist?
The problem is to prove or disprove the existence of $C$, s.t., $|c| = 6,\forall c\in C$; $|C| = 32$; $d(c_i,c_j)\geq2,1\leq i<j\leq32$. ($d$ stands for hamming distance)
I tried to construct a ...
9
votes
1
answer
1k
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)$. ...
8
votes
4
answers
765
views
Compression functions are only practical because "The bit strings which occur in practice are far from random"?
I would have made a comment, as this pertains to Andrej Bauer's answer in this thread; however, I believe it is worth a question.
Andrej explains that given the set of all bit strings of length 3 or ...
8
votes
4
answers
4k
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 ...
8
votes
4
answers
1k
views
compressed information = randomness?
Suppose I have a compressed file and it is not possible to compress it more without loss of information. We say that this file is random or pseudorandom.
So, if the randomness means not ...
7
votes
3
answers
616
views
Are there lossless data compression techniques that do not exploit repetitive patterns?
Lossless Data compression (source coding) algorithms heavily rely on repetitive pattern (redundancy).
Is there a Lossless Data compression method/algorithm that is independent of repetitive pattern ...
7
votes
2
answers
3k
views
Compressing normally distributed data
Given normally distributed integers with a mean of 0 and a standard deviation $\sigma$ around 1000, how do I compress those numbers (almost) perfectly? Given the entropy of the Gaussian distribution, ...
7
votes
3
answers
739
views
What Good Is Kolmogorov Complexity Since It Is Relative?
Kolmogorov complexity is relative to a choice of Universal Turing Machine. Because of the Invariance Theorem, the difference in complexity assigned by two Universal Turing Machines is bounded by a ...
7
votes
1
answer
200
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^{...
7
votes
2
answers
812
views
Impossibility for Byzantine Generals Problem where $n \leq 3m$
Wiki: https://en.wikipedia.org/wiki/Byzantine_fault_tolerance
In the paper "Reaching Agreement in the Presence of Faults", M. Pease et al. proved that there is no protocol (of some kind) to solve the ...
6
votes
3
answers
2k
views
Arithmetic coding and "the optimal compression ratio"
Trying to learn more about compression techniques and found something in the wikipedia article on arithmetic coding that I'm not sure I fully grok. In describing how Huffman Coding can sometimes be ...
6
votes
1
answer
187
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 χ, ...
6
votes
1
answer
2k
views
Showing that the entropy of i.i.d. random variables is the sum of entropies
The shannon entropy of a random variable $Y$ (with possible outcomes $\Sigma=\{\sigma_{1},...,\sigma_{k}\}$) is given by
$H(Y)=-\sum\limits_{i=1}^{k}P(Y=\sigma_{i})\;\log(P(Y=\sigma_{i}))$.
For a ...
6
votes
1
answer
967
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
1
answer
476
views
Reconstructing a screen of permuted pixels
Reconstructing a screen of permuted pixels
Summary
Given a video with the pixel locations randomly permuted (once, for the entire video), can we (efficiently) reconstruct the original picture?
Let:
...
6
votes
1
answer
148
views
Understanding simulated annealing information theoretically
So I recently rediscovered simulated annealing through a path that others seem to be well aware of. I was aware of Metropolis-Hastings as a sampling algorithm that creates a Markov-Chain whose ...
6
votes
1
answer
487
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 ...
6
votes
1
answer
1k
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 ...
5
votes
1
answer
1k
views
The Entropy of the phrase "Eile Mit Weile"
I want to calculate the Entropy of the phrase "Eile mit Weile". I found the probability of each letter as the following
$$P(e)=\frac{4}{12}$$
$$P(i)=\frac{3}{12}$$
$$P(l)=\frac{2}{12}$$
$$P(m)=\frac{...
5
votes
1
answer
158
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 ...
5
votes
1
answer
2k
views
Mutual information intuition
I was creating an example for a casual talk on mutual information. I considered a system of two coins, which with probability 1/2 are copies of each other, and with probability 1/2 are independent.
...
5
votes
1
answer
540
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 ...
5
votes
1
answer
743
views
How much data could I store on a Rubik's Cube?
Google tells me that a standard 3x3x3 Rubik's Cube has 43,252,003,274,489,856,000 permutations. If I wanted to store data on that Rubik's Cube, how much could I store?
The only way I see to store ...
5
votes
2
answers
587
views
Measuring the information of a document?
I'd like to measure how much information a document $D$ contains.
Clearly, the New York Times published yesterday contains more information than my diary wrote on the same day. But, I do not know ...
5
votes
1
answer
424
views
Conceptual question about entropy and information
Shannon's entropy measures the information content by means of probability. Is it the information content or the information that increases or decreases with entropy? Increase in entropy means that ...
5
votes
2
answers
964
views
Estimate entropy, based upon observed frequency counts
Suppose I have $n$ independent observations $x_1,\dots,x_n$ from some unknown distribution over a known alphabet $\Sigma$, and I want to estimate the entropy of the distribution. I can count the ...
5
votes
1
answer
2k
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. ...
5
votes
0
answers
268
views
Average redundancy in Huffman or Hu-Tucker codes on random symbol probabilities
Huffman and Hu-Tucker codes are well-known compression schemes, which both come close to the entropy lower bound. It is known that if $L_1$ and $L_2$ are the lengths of a Huffman resp. Hu-Tucker code, ...
4
votes
5
answers
714
views
Is there a correlation of zip compression ratio and density of information provided by a text?
I'll phrase my question using an intuitive and rather extreme example:
Is the expected compression ratio (using zip compression) of a children's book higher than that of a novel written for adults?
...
4
votes
3
answers
1k
views
Can a transcendental number like $e$ or $\pi$ be compressed as not algorithmically random?
The related and interesting fields of Information Theory, Turing Computability, Kolmogorov Complexity and Algorithmic Information Theory, give definitions of algorithmically random numbers.
An ...