6
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ Possibly related: cstheory.stackexchange.com/questions/7993/… $\endgroup$ – Andrew Oct 25 '16 at 23:31
  • $\begingroup$ 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. $\endgroup$ – domotorp Oct 27 '16 at 7:37
  • $\begingroup$ @domotorp The denominator is there to make it an expectation over all strings of length $n$ $\endgroup$ – Bjørn Kjos-Hanssen Oct 28 '16 at 19:10
  • $\begingroup$ @B I know, but why not take all strings? Anyhow, I agree that this is not as far-fetched as the other parameters. $\endgroup$ – domotorp Oct 28 '16 at 19:31
  • 2
    $\begingroup$ @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. $\endgroup$ – Neal Young Nov 2 '16 at 20:22
7
+100
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ OK the first one is easy; in other words, minimum $K$ goes to infinity so $E(K)$ goes to infinity. $\endgroup$ – Andrew Nov 1 '16 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.