# What is the precise relation between Kolmogorov complexity and Shannon's entropy?

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.

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

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$.