# What are the moments of Kolmogorov Complexity for a Random Variable?

Given a random variable $$X$$ distributed under some computable distribution $$P$$ we have,

$$0 \le E[K(X)] - H(P) \le K(P)$$

Where $$H(P)$$ is the entropy of $$P$$. I tried using Hoeffding concentration bounds, but they aren't very helpful here. Are there similar bounds for $$E[(K(X)-H(P))^2]$$? In general, is there any way to get information about the distribution shape of $$K(X)$$ or is that uncomputable?

• How do you define $K(X)$ for a random variable $X$? – Aryeh Kontorovich Nov 7 '18 at 19:34
• @AryehKontorovich I linked a reference in the question, the expectation is supposed to be taken with a finite sum. You sum over the sample space of X multiplying by probability. It's mostly suggestive. – Zachary W. Robertson Nov 7 '18 at 20:46