Is there a practical limit to the size of a piece of data with 0 statistical redundancy? 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)
 A: 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".
A: 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.
