6
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Where did you hear such file called random? It merely lacks the patterns your compression algorithm is able to compress. $\endgroup$ – Karolis Juodelė Oct 3 '13 at 9:31
  • $\begingroup$ I can't remember where I read it. But if this compressed file's bytes are not random, then there is an algorithm with which to get the file, and therefore it could be more compressed... Something is hear I'm not good understanding. $\endgroup$ – Pedro Oct 3 '13 at 10:36
  • 1
    $\begingroup$ The biggest problem here is a lack of definition of "random". $\endgroup$ – Karolis Juodelė Oct 3 '13 at 10:59
  • 1
    $\begingroup$ @Pedro, there is no such thing as randomness, as far as this is concerned at least. There is only statistical randomness. $\endgroup$ – Karolis Juodelė Oct 3 '13 at 15:30
  • 1
    $\begingroup$ Suppose you have the following encoding algorithm (that just applies to books in the Library of Congress). You number all the books. To encode a book, I just send you the number of the book. Suppose that I choose a random book, and encode it. Clearly, that's a random number between 1 and 22,765,967. But when you decode it, there's information that you can understand. Our real encoding and decoding algorithms don't actually work that efficiently, so the encoded bits always contain some non-randomness, but this should give you the general idea of how it works. $\endgroup$ – Peter Shor Oct 3 '13 at 20:22
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ glad i could be of some help :) $\endgroup$ – Subhayan Oct 4 '13 at 7:41
2
$\begingroup$

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/ :

Dilbert on randomness XKCD on randomness

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).

$\endgroup$
  • 1
    $\begingroup$ You're coming at randomness from a cryptographic point of view. Information theory does link randomness to compressibility. $\endgroup$ – Gilles Oct 3 '13 at 18:23
  • 2
    $\begingroup$ @Gilles, actually, no. My point of view is also the information theoretic view. In information theory, randomness is a property of the source (the distribution of the random variable), not of the data (a single observation of the r.v.). This is not limited to cryptography. There is a linkage between randomness and compressibility, but it is not what was claimed in the question. (For instance, a classic result is that a uniformly random source generates values that are on average not compressible. But that's very different from what the question claims!) Your criticism is off-base. $\endgroup$ – D.W. Oct 3 '13 at 18:29
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @PeterShor The OP asks how an incompressible string can still contain useful information. What I try to do in this answer is demonstrate that any finite string contains useful information, i.e., there's no such thing as an incompressible (or random) finite string, or that the relationship between the two for sources and streams doesn't hold true for the finite case. It's similar in some respects to what D.W. says in the answer below, just more condensed and with fewer cartoons. $\endgroup$ – Patrick87 Oct 3 '13 at 20:24
  • $\begingroup$ Now, I'm beginning to think the downvote (not mine) was justified. If I flip a coin 100 times and write down the results, why isn't this a random finite string? $\endgroup$ – Peter Shor Oct 3 '13 at 20:27
  • 1
    $\begingroup$ @PeterShor It depends on what you mean by "random string". If you mean "produced by a random source", then of course this is random. If you mean "incompressible", then it's clearly not random, since I provide a means to compress it. I use the definition of "random" that the OP seems to be using for the purposes of being understood: holding "random = incompressible", then finite strings are neither. $\endgroup$ – Patrick87 Oct 3 '13 at 20:32
  • $\begingroup$ Let me see if I get this straight. You're saying that any string I give you is compressible? So what happens if I give you some string, you compress it and give me the results, and we repeat. Can you compress any file down to one bit that way? $\endgroup$ – Peter Shor Oct 3 '13 at 20:34
  • $\begingroup$ @PeterShor Sure, with two caveats: I can use different compression and decompression algorithms each time; and the compression ratio doesn't have to be good in general, just for the specific strings you give me. Of course, that's unnecessary, since I could take the original file and compress it to one bit, if you wanted that. $\endgroup$ – Patrick87 Oct 3 '13 at 20:36
0
$\begingroup$

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.

$\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.