Skip to main content
5 of 5
added 6 characters in body

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.