Consider the discrete case:

Shannon's entropy is $H(x)=-\sum\limits_i^n p(x_i) log\space p(x_i)$.

Probability based on prefix-free Kolmogorov complexity is $R(x_i)=2^{-K(x_i)}$ where $K(x_i)$ is the prefix-free Kolmogorov complexity of $x_i$.

What is the relation between $R(x_i)$ and $p(x_i)$? Are they equal?

I remember vaguely that a book has discuss on the relation without any precise result.

  • $\begingroup$ Actually the $K(x_i)$ is the length of an optimal code. $\endgroup$ – XL _At_Here_There Jul 21 '17 at 16:51

What follows, which is all standard stuff (and should be in, say, Li and Vitanyi's monograph, or Downey and Hirschfeldt perhaps), might be the sort of relationship you vaguely recall seeing.

Your $R(x):= 2^{-K(x)}$ is not itself a probability measure, but it is a lower semi-computable semi-measure; and it is optimal among such in the following sense: for any lower semi-computable semi-measure $p$ on strings, there is some constant $c_p >0$ such that $2^{c_p} \cdot R(x) \ge p(x)$ for all strings $x$. Moreover, then, $K(x)\leq c_p - \log_2 p(x)$ for all $x$. Also, it's known that $c_p = K(p)+O(1)$.

For a fixed such $p$, then, we have that the expected value (w.r.t. $p$) of the Kolmogorov complexity of a string is $$ \sum_x p(x) K(x) \leq K(p) + H(p) + O(1), $$ where I'm using the definition $H(p) := - \sum_x p(x) \log_2 p(x)$ for the Shannon entropy of $p$.

On the other hand, Shannon's source coding theorem yields $H(p)\leq \sum_x p(X) K(x)$, so in total we have $$ 0 \leq \left(\sum_x p(x)K(x)\right) - H(p) \leq K(p)+O(1). $$ Thus the Shannon entropy is close to the expected value of Kolmogorov complexity for low-complexity $p$.

  • $\begingroup$ Yes, maybe it is what I vaguely recall, it is an inequality. And the relation seems to show that KC depends on probability, or probability is determined by KC. $\endgroup$ – XL _At_Here_There Jul 21 '17 at 20:35

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.