3 ms·

> Kolmogorov randomness. A string of data is Kolmogorov random if, for a given universal Turing machine, there is no program shorter than the string that produc

by kace91 7y ago

> Kolmogorov randomness. A string of data is Kolmogorov random if, for a given universal Turing machine, there is no program shorter than the string that produces the string I know nothing about this field, but it strikes me as wrong intuitively. Say that I have a certain amout of data. I can find specific patterns on it (for example, a chain of 10 ceros) that are compressible (0*10). For a large enough amount of data, that can save me enough space to include a program that can print the decompressed string in less space than the original string, thus implying my original string wasn't random - but we've then reached the absurd, because it is perfectly understandable that randomness could create locally compressible substrings. What am I missing?

willis936 7y ago
Entropy! If you are familiar with programming I suggest doing the following experiment: 1. make an image of one solid color 2. make another image of the same size that with each pixel being a random RGB value 3. losslessly compress both images any way you can 4. compare the compressed file sizes to the uncompressed bitmap file size Make sure to make a hypothesis before the experiment! To dig a little deeper on this: all subsequences are equally probable in a random sequence. The full implications of that requires a bit more playing around and reading. I think if you explore it you’ll find that there is an intuition that can be built up.
dTal 7y ago
>For a large enough amount of data, that can save me enough space to include a program that can print the decompressed string in less space than the original string It can't. You'll find that, in a truly random sequence, the "compressible substrings" will be infrequent enough that you will use up your data budget just specifying where they go. Let's take your run-length example. Let's work in bits to make it simple. Your chain of 10 zeros - 10 bits of information - happens on average every 2^10 bits. Let's say we magically compress this sequence down to 0 bits - we just assume that statistically it's in there somewhere, so we don't need to store it. All that's left is to specify where it goes! How many bits do we need for that? Well... the sequence occurs on average every 2^10 bits. We need all 10 of the saved bits just to say where the sequence goes! We haven't saved anything! The more compressible the substring, the less frequent it is, and the more information is required to specify its location. This is also why we can't compress files by specifying their offset in the digits of pi, incidentally.

by kace91 7y ago

willis936 7y ago

Entropy! If you are familiar with programming I suggest doing the following experiment: 1. make an image of one solid color 2. make another image of the same size that with each pixel being a random RGB value 3. losslessly compress both images any way you can 4. compare the compressed file sizes to the uncompressed bitmap file size Make sure to make a hypothesis before the experiment! To dig a little deeper on this: all subsequences are equally probable in a random sequence. The full implications of that requires a bit more playing around and reading. I think if you explore it you’ll find that there is an intuition that can be built up.

dTal 7y ago

>For a large enough amount of data, that can save me enough space to include a program that can print the decompressed string in less space than the original string It can't. You'll find that, in a truly random sequence, the "compressible substrings" will be infrequent enough that you will use up your data budget just specifying where they go. Let's take your run-length example. Let's work in bits to make it simple. Your chain of 10 zeros - 10 bits of information - happens on average every 2^10 bits. Let's say we magically compress this sequence down to 0 bits - we just assume that statistically it's in there somewhere, so we don't need to store it. All that's left is to specify where it goes! How many bits do we need for that? Well... the sequence occurs on average every 2^10 bits. We need all 10 of the saved bits just to say where the sequence goes! We haven't saved anything! The more compressible the substring, the less frequent it is, and the more information is required to specify its location. This is also why we can't compress files by specifying their offset in the digits of pi, incidentally.