4 ms·

I think your comments on encoding a sequence of bits/pi is a little misleading. For example, in the case of the first 10 billion digits of pi, you do not even n

I think your comments on encoding a sequence of bits/pi is a little misleading. For example, in the case of the first 10 billion digits of pi, you do not even need a program to calculate it. One can just use a lookup table which maps the digits 0 through 9 to the frequency they appear in 10 billion digits of pi, which is <40 bytes of data. You are confusing the entropy of the digits of pi, for which the order does not matter, and the entropy of the sequence of pi, for which the order does matter. In the latter, you would want compare the probability of observing the exact sequence of pi compared to other sequences of numbers. This is an entirely different question. Because the sequence of digits of pi is deterministic, its entropy is 0, i.e., if one had a machine from which you could sample "10-billion digit sequences of pi" you would get the same sequence every time. >strictly speaking the shortest possible encoding of a sequence of bits could be smaller than this would suggest, since it's possible a pattern exists that has escaped notice. If it is a deterministic pattern, then the entropy of the sequence is actually 0. Otherwise the existence of patterns is something that the entropy computation already takes into account, and is in fact the entire point. In practice, finite sample sizes introduces noise and means that we can only ever estimate the true entropy, and Jensen's inequality implies that all such estimates are higher than the true entropy of a system, so that we observe even deterministic sequences with noisy filters. This is perhaps the clearer version of your point.

ttctciyf 4y ago
Contrariwise, to me you seem to be the confused party. I am contrasting the compression given by lzw or zip as discussed in the article, which would be unable to significantly compress the bit sequence of pi, with the "compression technique" of simply calculating the same sequence (in order!) with a short program. A lookup table is irrelevant, since we're talking about printing out the first 10 billion pi digits in order by a simple algorithm for computing them, not about anything involving calculating their frequency or probability. (In any case, since those digits pass statistical randomness tests, the frequency distribution wouldn't tell you much, which is why zip-style compression fails on pi.) The point I'm making is that running a very short program can print a 10 billion digit sequence which stats-based compression methods would fail to significantly compress. The digits of pi happen to be a good example of this, but there are likely plenty of others. Regards the second part of your comment, the notion of a "deterministic pattern" is intriguing, but what does it mean? If you mean "not random" then in the algorithmic information world that equates to "can be printed by a program shorter than itself". Obviously any (including random) sequence can be printed by some program, but the presence of regularity (or "patterns" if you like) in a sequence allows shorter encodings, either by creating a dictionary of recurring subsequences, as in lzw or zip style compression, or by some other means as in the calculation of pi's digits. I suggest you read up on AIT or Kolmogorov complexity at the wikipedia links I posted to get an idea of what my comment was actually about :)

ttctciyf 4y ago

Contrariwise, to me you seem to be the confused party. I am contrasting the compression given by lzw or zip as discussed in the article, which would be unable to significantly compress the bit sequence of pi, with the "compression technique" of simply calculating the same sequence (in order!) with a short program. A lookup table is irrelevant, since we're talking about printing out the first 10 billion pi digits in order by a simple algorithm for computing them, not about anything involving calculating their frequency or probability. (In any case, since those digits pass statistical randomness tests, the frequency distribution wouldn't tell you much, which is why zip-style compression fails on pi.) The point I'm making is that running a very short program can print a 10 billion digit sequence which stats-based compression methods would fail to significantly compress. The digits of pi happen to be a good example of this, but there are likely plenty of others. Regards the second part of your comment, the notion of a "deterministic pattern" is intriguing, but what does it mean? If you mean "not random" then in the algorithmic information world that equates to "can be printed by a program shorter than itself". Obviously any (including random) sequence can be printed by some program, but the presence of regularity (or "patterns" if you like) in a sequence allows shorter encodings, either by creating a dictionary of recurring subsequences, as in lzw or zip style compression, or by some other means as in the calculation of pi's digits. I suggest you read up on AIT or Kolmogorov complexity at the wikipedia links I posted to get an idea of what my comment was actually about :)