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