compressed information = randomness?

Question

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 comprehensible and not compressible, I don't understand why ths file is, at the same time, information that my computer and I can understand.

This file could be a book that my computer can show to me and read, and I can read and sum it ...so, it is really randomness?

Note: I understand that if I can make a summary of a text or define it with less words, that not means that it could be possible to get all the information of this book again, of course but this book is not random for me.

Note II: I undesrtand ramdoness as something that is not possible to reproduce with an smaller algorithm. I mean a string is random when I can't find an other smaller string that is an algorithm that can reproduce the first one.

Note III: I want to thank you all for your help.

Answer 1

okay, what you are talking about can be explained using the concept of Kolmogorov Complexity.

Let's understand the Kolomogorov complexity and randomness.

Suppose you have a string $A = HHHHH$ and $B = TTHTH$, now intuitively it seems $B$ has more randomness than $A$, however, statistically, both strings have an equal probability of being chosen. This troubled researchers for sometime untill Kolmogorov and Chaitin (independently) came up with a notion of randomness.

A string is said to be random if it cannot be compressed, that is it has no 'structure' in it. Formally, for any word $x \in (\Sigma_{bool})^*$, the Kolmogorov Complexity $K(x)$ of the word is the binary length of the shortest program generating it.

A word is said to be random if it is not compressible. i.e. $K(w_n) \geq |w_n| + c$

If you want to look up more on this, you can start with this wonderful survey note by Lance Fortnow

---

Now, as I understand your question, you are asking how is an a word that is incompressible be 'information' while we use the same notion for randomness.

So, this is a bit philosophical... well, randomness is always philosophical! anyway, What we call/define to random is actually information without a structure. The outcome of an unbiased coin toss is also random, i.e. it should not have any structure to it, and one should never be able to find any patterns or periodic repetitions in the string.

Information is basically a numerical measure of the uncertainty of an experimental outcome.

Now, let's use the K-Complexity... suppose we start writing down the outcomes of a coin toss. Now without the information you basically do not have an metric to evaluate randomness of the string. The randomness is more of a property associated with information. You can probably associate a certain degree of randomness to anything that's based on experiments.

The K-complexity is just a measure of randomness in information. For an completely 'random' string, the $K(w_n) = |w_n| + c$ and for a completely 'non-random' string, the $K(w_n) = \delta + c$ where $\delta$ is some small quantity.

Answer 2

This question starts from faulty premises. Just because a particular file is not compressible does not mean it was necessarily generated randomly or pseudorandomly. Randomness is a property of the source where the data came from, not a property of the data itself (not a property of a single value emitted by that source). See, for instance, https://xkcd.com/221/ and http://dilbert.com/strips/comic/2001-10-25/ :

It doesn't make sense to say "a file is random"; sometimes if we're sloppy, we might say something like that, but everyone understands that what we really mean is "the file was generated by a source that is random". Randomness is a property of the source.

In comparison, compressibility is a property of the data, not the source. We can test whether a particular file is compressible by gzip by, well, running gzip and seeing if the compressed result is smaller than the original file.

Therefore, a statement like "if a file is not compressible, then it is random" represents a confusion. It confuses the difference between the source and an observation of a value from that source.

We could try to correct the statement to remove this confusion, to get something like "if a file is not compressible, then it was not produced by a random source" -- but that corrected version is simply false. It is not accurate. It is possible for a random source to produce an output that can be compressed by gzip (as illustrated by the Dilbert comic above). There is a result in information theory which guarantees that, on average, this doesn't happen -- but that's a very different statement. And if you make a correct statement of the true result, you'll find that your reasoning falls apart in the first or second sentence of your question.

Given a question that starts from faulty premises, the best answer is "mu", i.e., "un-ask the question" and ask a different one. My advice would be to start by studying the definition of randomness, the known links between randomness and compressibility, and then that might help you formulate your question a little more precisely (or might help you understand the relationship between these concepts).

Answer 3

The relationship between randomness and compressibility only exists when we talk about the source, or the hypothetically infinite string of outputs from the source. For instance, we know that a source that outputs either 0 or 1 with equal probability is random and that the stream it produces is "incompressible" (in the sense that, for any fixed compression algorithm, in the limit as the length of the stream goes to infinity, the stream cannot be compressed by that compression algorithm: the average compression ratio is $\le 1$).

Any finite string can be compressed down to nothing, if you let me pick a suitable compression algorithm; i.e., for any finite string $y$, there is a pair of algorithms $c$ and $d$ which compress the string to nothing, and decompress nothing to the string. These algorithms are easy: $c(y) = \epsilon$ and $c(x) = 0x$ for all $x \neq y$, whereas $d(\epsilon) = y$ and $d(0x) = x$. The compression ratio is bad for most strings, but you've just compressed any finite string -- including one generated by a random source -- down to nothing.

You can talk about compressibility for specific compression and decompression algorithms in the context of random finite strings, but not about limits of compressibility in general terms.

Another way to understand this is that there's no such thing as a random finite string.

As for how this addresses the question:

Suppose I have a compressed file and it is not possible to compress it more without loss of information.

I demonstrate that this cannot hold for a finite string.

We say that this file is random or pseudorandom.

Then we conclude that such a thing does not exist.

So, if the randomness means not comprehensible and not compressible,

For producers and the potentially infinite streams they produce, I'd grant that this is a reasonable interpretation

I don't understand why this file is, at the same time, information that my computer and I can understand.

Because the file isn't a potentially infinite random stream, and represents a discreet entity which still contains plenty of information.

This file could be a book that my computer can show to me and read, and I can read and sum it ...so, it is really randomness?

It is not, as outline above.

Note: I understand that if I can make a summary of a text or define it with less words, that not means that it could be possible to get all the information of this book again, of course but this book is not random for me.

Neither is any string, since what (I think) you are describing is a valid way to interpret the result of applying a compression algorithm to any finite string: it's a digest, or summary, for which there is indeed some algorithm that will losslessly convert it back to its original form.

Answer 4

Part of the problem with this question is that it gets two different groups talking past each other. The core issue is: There are TWO distinct intuitive interpretations of 'random bit string':

STATISTICS: A bit-string is 'random' if it is generated by an independent sequence of fair coin flips (or similar such process).

INFORMATION: A bit-string is 'random' if it is non-redundant, i.e contains essentially no internal sub-structure.

It happens to be the case that most bit-strings which are 'statistics-random' are also 'information-random' [of course, one cannot even consider the converse unless one knows how the bit-string came to be]. The conflict of intuition occurs when trying to apply both intuitions simultaneously to certain bit-strings. Consider, for example, a sequence of one hundred consecutive ones - is this 'random'? You get two answers:

STATISTICS: If each one in the sequence was generated by a separate, independent flip of a fair coin - then yes, it is just as random as any other string of one hundred bits.

INFORMATION: Obviously a string of one hundred ones is almost entirely redundant, so no, it is not at all random.

It is simply the case that the usual human 'gut reaction' is that real coin flipping should never generate one hundred ones in a row. More generally, people have a tendency to conflate 'sufficiently improbable' with 'impossible'. This is an underlying reason why 'information random' theory exists.

To resolve the confusion in this case, I argue thus: The phrasing of the submitter's question indicates that it is based on 'information random'. Any responder who presumes 'random' only means 'statistics random' in order to explain why the submitter is confused, is misguided in this case. Please stop.