If a bitstring is incompressible, then its minimal Kolmogorov sufficient statistic (MKSS) is zero, since the bitstring is best represented by a structure function that enumerates bitstrings, and thus the size of the index in the set is the bitstring's length.

However, if a bitstring is compressible, this is no longer true, and its MKSS is greater than zero.

My question is, given that a bitstring $b$ is compressible, $K(b) < \ell(b)$, is its MKSS more likely to be closer to zero or closer to $K(b)$?

My intuition is that it is more likely to be closer to zero for a reason similar to why most bitstrings have $MKSS(b) = 0$.

Also, can a probability be related to the length of the MKSS given that $b$ is compressible?

\begin{align*} P\{MKSS(b) > a | K(b) < \ell(b)\} = ?. \end{align*}

  • 1
    $\begingroup$ Have you seen Algorithmic Statistics by Péter Gács, John T. Tromp, and Paul M.B. Vitányi? $\endgroup$ – Evil Aug 31 '17 at 0:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.