7
$\begingroup$

I was just wondering, just because I tend to wonder about these sort of things in my spare time, if there are any data pieces that are 1Gig+ that have 0 Statistical Redundancy? (i.e., uncompressible with lossless compression.)
Is it even possible for a file larger than a few bytes to have such a trait? Is that property possible at all, or merely theoretical?

Anyway, please let me know if such a thing would be possible, and, if feasible, please link me to a place where I could view such a piece of data. Google gave me nothing.

Might as well include the Wikipedia page about statistical redundancy: en.wikipedia.org/wiki/Redundancy (information theory)

Improve this question
$\endgroup$
14
  • 1
    $\begingroup$ @gung Funny you should say that... meta.stackexchange.com/q/157525/202692 $\endgroup$ – JamesTheAwesomeDude Dec 4 '12 at 4:18
  • 1
    $\begingroup$ I would have thought that the frequency of such an occurrence would be quite likely to be related to the frequency of finding large prime numbers. Even multiples of two or three quite large primes would be hard for a normal compression program to factor. $\endgroup$ – Robert Jones Dec 4 '12 at 11:42
  • 2
    $\begingroup$ What about a sequence of bits generated by a Bernoulli process with p=0.5? The redundancy should be zero, right? $\endgroup$ – mogron Dec 4 '12 at 12:05
  • 1
    $\begingroup$ @JamesTheAwesomeDude I conjecture that for every fixed, finite sequence, there exists a "non-cheating" algorithm that can compress this sequence. Of course one would need a formal definition of "non-cheating" compression algorithms to prove this. $\endgroup$ – mogron Dec 5 '12 at 13:35
  • 1
    $\begingroup$ @mogron Basically, a "non-cheater" algorithm can define any piece of data that it wants to be equivalent to any other piece of data that it wants, or it can define something more complex than that, but the catch is that the definition would be stored in header-type data in the beginning of the compressed file, therefore contributing to the filesize. So you can define a relatively complex algorithm, as long as it saves you more then it would take to define it. $\endgroup$ – JamesTheAwesomeDude Dec 5 '12 at 18:57
1
$\begingroup$

I'll ty to answer the question in terms of Kolmogorov complexity, which is the length of the smallest description of a finite sequence, given a fixed description language. A sequence is called Kolmogorov random, if the Kolmogorov complexity is at least as big as the length of the sequence (i.e., the sequence is incompressible).

For your problem, we use the set of programs on a fixed universal Turing machine as description language. Without loss of generality, we may assume that the universal Turing machine uses a binary alphabet. For each natural number $n>0$, there exists a Kolmogorov random sequence. The proof is simple: There are $2^n$ sequences of length $n$, but only $2^{n-1}$ programs of length less than $n$. So by the pigeonhole principle, there must be some sequences -- in fact, at least $2^n - 2^{n-1} = 2^{n-1}$ sequences -- of length $n$ that are incompressible.

This proof is of course not constructive. Also, it is not computable if a given sequence is Kolmogorov random.

Update

To make a connection to statistical redundancy: If you generate a sequence by some random process, the Kolmogorov complexity divided by the length of the sequence converges to the entropy of the generating process (as the length of the sequence goes to infinity). Thus, a sequence generated by a Bernoulli process with p=0.5 will be "Kolmogorov random in the limit".

Improve this answer
$\endgroup$
1
$\begingroup$

I’ll improve shortly on my above comment: If a compression algorithm is fixed, an arbitrary large non-compressible (with this algorithm) piece of data can be obtained just by iterating the algorithm. If a cycle appear before hitting the desired size, pick some starting point out of this cycle, and try again.

$\def\N\{\mathbb N^*}$Details. Considering that data are strings of 0 and 1, a file is (after prefixing it with a 1) nothing more than a (non zero) integer. The length of a file $n\in \N*$ is $\log(n)$. A compression algorithm is an injective function from $\N$ to $\N$ (it has to be injective to ensure decompression is possible). We say that $n$ is non-compressible if $\log(n) < \log(f(n))$.

I will distinct two cases (not absolutely necessary bit the first case is nicer) First, assume $f$ is non surjective and you know some $n \notin f(\N)$ (this is quite reasonable for practical examples). As $f$ is injective, if the orbit $f^{(k)}(n)$ is ultimately cyclic, it has to go through $n$ again. As $n \notin f(\N)$, this is impossible: so the orbit is not ultimately cyclic, and it has to go through arbitrary big numbers. More precisely, the length of the successive numbers have two increase from time to time, so this sequence contains an infinite amount of non-compressible numbers. Some have to be larger than the prescribed size.

In the general case, well, pick up a number $n$, and iterate. If you meet a non-compressible number of the desired size before hitting $n$ again, you are done. In the other case, pick up a starting point out of the cycle, and try again. You iterate this, each time excluding all the cycles previously described. The sequence generated also contains an infinite amount of non-compressible numbers.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.