Skip to main content
2 of 5
edited title

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

Just study the discrete case:

Shannon's entropy is $H(x)=\sum_i^n p(x_i) x_i$

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

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