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

Improve this question
$\endgroup$
7
  • $\begingroup$ Possibly related: cstheory.stackexchange.com/questions/7993/… $\endgroup$
    – Andrew
    Commented Oct 25, 2016 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
    Commented Oct 27, 2016 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
    Commented Oct 28, 2016 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
    Commented Oct 28, 2016 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
    Commented Nov 2, 2016 at 20:22

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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