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.



What is the precise relation between Kolmogorov complexity and Shannon's entropy?
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](https://en.wikipedia.org/wiki/Shannon%27s_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$.


