<p>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 <em>any</em> distribution on strings of length $n $ is  $\ge c $.</p>

<p>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.</p>

CC BY-SA 3.0
2016-11-01T16:06:18.223Z
OK the first one is easy; in other words, minimum $K$ goes to infinity so $E(K)$ goes to infinity.
Andrew
CC BY-SA 3.0
2016-10-27T05:56:21.147Z
2016-11-02T03:10:37.810Z
2016-11-02T03:10:37.810Z
Bjørn Kjos-Hanssen
<p>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</p>

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

<p>Also, what is</p>

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

<hr>

<p>The distribution here is closely related to the <a href="http://www.scholarpedia.org/article/Algorithmic_probability#Discrete_Universal_A_Priori_Probability" rel="nofollow noreferrer">"universal distribution"</a>.
The second limit would say whether $\Theta(|w|)$ is an approximation for $K(w)$.</p>

CC BY-SA 3.0
2016-10-25T23:31:26.277Z
Possibly related: http://cstheory.stackexchange.com/questions/7993/expected-values-of-kolmogorov-complexity-in-a-random-sample/7995
Andrew
CC BY-SA 3.0
2016-10-27T07:37:00.153Z
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.
domotorp
CC BY-SA 3.0
2016-10-28T19:10:43.303Z
@domotorp The denominator is there to make it an expectation over all strings of length $n$
Bjørn Kjos-Hanssen
CC BY-SA 3.0
2016-10-28T19:31:59.197Z
@B I know, but why not take all strings? Anyhow, I agree that this is not as far-fetched as the other parameters.
domotorp
CC BY-SA 3.0
2016-11-01T16:18:34.983Z
This is a vague and possibly flawed heuristic, but if we assume that the number of strings $w$ with $K(w)=j, |w|=n$ is proportional to $2^j$, then the second expression is something like $(\sum_{j=1}^{n+c} 2^j 2^{-j} j/n)/(\sum_{j=1}^{n+c} 2^j 2^{-j}) \to 1/2$.
Andrew
CC BY-SA 3.0
2016-11-01T20:37:33.307Z
@A But it isn't, I mean how could that be true for all $n$? I think a better heuristic would be $K(w)=n+\log n+\log\log n+\ldots$
domotorp
CC BY-SA 3.0
2016-11-02T20:22:23.217Z
@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.
Neal Young
<pr.probability><kolmogorov-complexity>
Expected Kolmogorov complexity under Kolmogorov complexity distribution
Saram Meti
# Expected Kolmogorov complexity under Kolmogorov complexity distribution

(Asked by: username_0 on 2016-10-24)

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"](http://www.scholarpedia.org/article/Algorithmic_probability#Discrete_Universal_A_Priori_Probability).
The second limit would say whether $\Theta(|w|)$ is an approximation for $K(w)$.

**Tags:** pr.probability, kolmogorov-complexity

> **Comments:**
> **username_1**: Possibly related: http://cstheory.stackexchange.com/questions/7993/expected-values-of-kolmogorov-complexity-in-a-random-sample/7995  
> **username_2**: 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.  
> **username_3**: @username_2 The denominator is there to make it an expectation over all strings of length $n$  
> **username_2**: @B I know, but why not take all strings? Anyhow, I agree that this is not as far-fetched as the other parameters.  
> **username_1**: This is a vague and possibly flawed heuristic, but if we assume that the number of strings $w$ with $K(w)=j, |w|=n$ is proportional to $2^j$, then the second expression is something like $(\sum_{j=1}^{n+c} 2^j 2^{-j} j/n)/(\sum_{j=1}^{n+c} 2^j 2^{-j}) \to 1/2$.  
> **username_2**: @A But it isn't, I mean how could that be true for all $n$? I think a better heuristic would be $K(w)=n+\log n+\log\log n+\ldots$  
> **username_4**: @username_2, perhaps username_1 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.  

---

## 1 answers

### Answer by username_3 on 2016-10-27. Score: 7

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.

> **Comments:**
> **username_1**: OK the first one is easy; in other words, minimum $K$ goes to infinity so $E(K)$ goes to infinity.  

---

