9 ms·

I'm going to keep reading (because I love the KC topic), but I'd appreciate anyone confirming if the following are errors in this article: 1.) Conflating usage

I'm going to keep reading (because I love the KC topic), but I'd appreciate anyone confirming if the following are errors in this article: 1.) Conflating usage of the term "random" and "complexity". After all, a set of "randomly" drawn sample permutations from an alphabet are all equally likely. However, their "complexity" may differ, which is basically the point of the article, but the term more or less "random" keeps being used to refer to permutations with more or less "complexity", which I think is probably going to perpetuate confusion on this topic. 2.) From the article: "Moreover, a string cannot be compressed if its KC(x)≥|x|". Shouldn't the expression accompanying this statement be KC(x)=|x| ?

deleted 3y ago
[deleted]
tromp 3y ago
Regarding point 1), one can easily show that with probability >= 1 - 2^{-k}, a randomly chosen bitstring x of length n must satisfy KC(x) >= n-k. After all, there are only 1+2+... 2^{n-k-1} = 2^{n-k}-1 shorter descriptions. So highly compressible strings are highly unlikely. Regarding 2), No, most strings x do not satisfy KC(x) = |x|, since you need to use some bits to specify that you're giving x literally. See the first theorem of [1]. [1] https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d861#theorems-concretely https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d8...
rhelz 3y ago
re #1: the conflation is justified, but you couldn't guess that just from what was presented in the OP. There are some cool theorems which justify it tho---if you like Kolmogorov complexity you are in for a fun ride. re #2: No. Basically the > part of it handles the case when the smallest program which prints out the string is actually LARGER than the length of the string. In that case, the string is still incompressible. Compression means mapping from larger strings to smaller strings.

deleted 3y ago

[deleted]

tromp 3y ago

Regarding point 1), one can easily show that with probability >= 1 - 2^{-k}, a randomly chosen bitstring x of length n must satisfy KC(x) >= n-k. After all, there are only 1+2+... 2^{n-k-1} = 2^{n-k}-1 shorter descriptions. So highly compressible strings are highly unlikely. Regarding 2), No, most strings x do not satisfy KC(x) = |x|, since you need to use some bits to specify that you're giving x literally. See the first theorem of [1]. [1] https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d861#theorems-concretely https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d8...

rhelz 3y ago

re #1: the conflation is justified, but you couldn't guess that just from what was presented in the OP. There are some cool theorems which justify it tho---if you like Kolmogorov complexity you are in for a fun ride. re #2: No. Basically the > part of it handles the case when the smallest program which prints out the string is actually LARGER than the length of the string. In that case, the string is still incompressible. Compression means mapping from larger strings to smaller strings.