Questions tagged [information-theory]

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

Filter by
Sorted by
Tagged with
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 ...
john mangual's user avatar
  • 1,941
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 ...
user avatar
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 ...
robert's user avatar
  • 453
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 ...
Koray Tugay's user avatar
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 ...
nalzok's user avatar
  • 1,101
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 ...
DSblizzard's user avatar
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 ...
Ran G.'s user avatar
  • 20.7k
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 ...
Klangen's user avatar
  • 1,100
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 ...
Troy McClure's user avatar
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 ...
Hesham Hany's user avatar
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 (...
usul's user avatar
  • 4,129
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 ...
user1247's user avatar
  • 273
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 =...
Kevin's user avatar
  • 1,082
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 ...
Sean C's user avatar
  • 143
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 < ...
Koz Ross's user avatar
  • 813
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 ...
user3467349's user avatar
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 ...
Realz Slaw's user avatar
  • 6,191
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. ...
gennady's user avatar
  • 119
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 ...
Ran G.'s user avatar
  • 20.7k
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 ...
user avatar
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 ...
Miangu's user avatar
  • 185
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)$. ...
Mitchell Kaplan's user avatar
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 ...
AlexMayle's user avatar
  • 213
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 ...
Zeta.Investigator's user avatar
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 ...
Pedro's user avatar
  • 397
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 ...
Michael's user avatar
  • 291
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, ...
pentadecagon's user avatar
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 ...
Ned Ruggeri's user avatar
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^{...
user1374864's user avatar
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 ...
Lwins's user avatar
  • 370
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 ...
snerd's user avatar
  • 394
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 χ, ...
Aaron Anodide's user avatar
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 ...
Danny's user avatar
  • 994
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 ...
ShyPerson's user avatar
  • 925
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: ...
Realz Slaw's user avatar
  • 6,191
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 ...
Jake's user avatar
  • 3,800
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 ...
user6618's user avatar
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 ...
badroit's user avatar
  • 727
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{...
Ski Mask's user avatar
  • 463
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 ...
Bear's user avatar
  • 153
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. ...
KalEl's user avatar
  • 173
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 ...
Cassie's user avatar
  • 305
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 ...
bakester14's user avatar
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 ...
Light Yagmi's user avatar
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 ...
Ria George's user avatar
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 ...
D.W.'s user avatar
  • 159k
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. ...
Cassie's user avatar
  • 305
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, ...
Sebastian's user avatar
  • 4,536
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? ...
Raffael's user avatar
  • 337
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 ...
Nikos M.'s user avatar
  • 957

1
2 3 4 5
7