# Expected Kolmogorov complexity under Kolmogorov complexity distribution

If $K(w)$ is the Kolmogorov complexity of a string $w$, where programs are prefix-encoded so $\sum_{w} 2^{-K(w)} \leq 1$, what is

$$\lim_{n\to\infty} \frac{\sum_{|w|=n}2^{-K(w)} K(w)}{\sum_{|w|=n} 2^{-K(w)}}?$$

Also, what is

$$\lim_{n\to\infty} \frac{\sum_{|w|=n}2^{-K(w)} \frac{K(w)}{n}}{\sum_{|w|=n} 2^{-K(w)}}?$$

The distribution here is closely related to the "universal distribution". The second limit would say whether $\Theta(|w|)$ is an approximation for $K(w)$.

• Possibly related: cstheory.stackexchange.com/questions/7993/… Oct 25, 2016 at 23:31
• I could just ask many similar questions and don't see at all why you have asked these. Why prefix-free? Why is the denominator summed for only $|w|=n$? Don't we know that this denominator is practically the slowest convergent series, i.e., $1/\sum_{|w|=n} 2^{-K(w)}=O(n\log n \log^2\log n)$? I think that instead of $n$, you can divide by practically anything that tends to $\infty$ to get a convergent sequence. Oct 27, 2016 at 7:37
• @domotorp The denominator is there to make it an expectation over all strings of length $n$ Oct 28, 2016 at 19:10
• @B I know, but why not take all strings? Anyhow, I agree that this is not as far-fetched as the other parameters. Oct 28, 2016 at 19:31
• @domotorp, perhaps Andrew means proportional for fixed $n$. E.g., if you take $n$ into account, proportional to $f(n)2^{j}$ for some $f$ (e.g. $f(n)=2^{-n}$). If my calculations are right, any such $f$ also gives the limit of the ratio value 1/2. Nov 2, 2016 at 20:22

If $\alpha$ is the answer to the 1st question then $\alpha=\infty$. Namely, for any $c$ there is an $n$ such that all strings $w$ of length at least $n$ have $K (w) \ge c$. In particular the expectation of $K (w)$ with respect to any distribution on strings of length $n$ is $\ge c$.
Similarly if $\beta$ is the answer to the 2nd question then $0\le\beta\le 1$, since $$(\exists c)(\forall w)(K(w)\le |w|+2\log |w| + c),$$ but I don't know exactly what $\beta$ is.
• OK the first one is easy; in other words, minimum $K$ goes to infinity so $E(K)$ goes to infinity. Nov 1, 2016 at 16:06