<p>Kolmogorov complexity is only determined up to some additive constant, so it is not possible to give an exact answer. The bound that I describe here is even weaker.</p>

<p>Of course the expected number can be computed easily once we know how many of the $2^n$ strings have complexity less than $n_0$, so let me answer this. It is usually the first statement about Kolmogorov complexity that this number is at most $2^{n_0}-1$ - since there are only these many strings of smaller length. On the other hand, if your program says "of length $n$, take the $x$th number", then you get $2^{n_0-K(n)-C}$ strings of complexity less than $n_0$, where $K(n)$ is the prefix-free version of Kolmogorov complexity of $n$ (so at most $\log n+\log^* n + O(1)$). In more detail, the string first contains the description of the Turing machine that taken input $px$, where p is the description of a prefix-free program that outputs $n$, outputs the $x$th number of length $n$, which is $O(1)$ bits, and then this is followed by $px$.</p>

<p>Probably it is possible to improve these bounds, but I doubt that you could get an exact answer.</p>

CC BY-SA 3.0
2011-08-29T21:24:46.030Z
Could you explain a little about the phrase 'if your program says "of length n, take the xth number"'?
v s
CC BY-SA 3.0
2011-08-31T06:51:32.193Z
You are right, it should be prefix-free there, I corrected it.
domotorp
CC BY-SA 3.0
2011-08-28T09:53:11.307Z
2011-08-31T06:50:56.267Z
2011-08-31T06:50:56.267Z
domotorp
<p>A precise answer can be given. The number of strings of length $n$ with (plain) complexity at most $n_0$ is $2^{n_0 - K(n_0|n)}$, up to a constant factor. Hence any process that randomly chooses a subset will have, with reasonable probability, a $2^{-K(n_0|n) + O(1)}$ fraction of strings of complexity less than $n_0$. To show our our claim, it suffices to show that the number of strings with complexity <strong>equal</strong> to $k$ is also given by $2^{k - K(k|n)}$. We can show the necessary result by determining the summation of this value over $k$ from 1 up to $n_0$. To show this, we use an additivity result for plain complexity (due to B. Bauwens and A. Shen. <em>An additivity theorem for plain Kolmogorov complexity</em>. Theory of Computing Systems, 52(2):297-302, Feb 2013),
$$
 C(a,b) = K(a|C(a,b)) + C(b|a,C(a,b)) + O(1).
$$
Here $K(\cdot)$ denotes prefix-free Kolmogorov complexity. Choosing $a = n$, we observe that for each $n$-bit string $b$ of complexity $k$ we have
$$
 k = C(b) = C(n,b) + O(1) = K(n|k) + C(b|n,k) + O(1).
$$
Hence, for each such $b$ we have $C(b|n,k) = k - K(n|k)+O(1)$. Let $k' = k - K(n|k)$. Now one can observe that there are at most $O(2^{k'})$ such strings $b$, and each of the lexicographically first $2^{k'}$ strings of length $n$ satisfy $C(b|n,k) \le k' + O(1)$. Thus $\Omega(2^{k'})$ of them satisfy $C(b|n,k) = k' + O(1)$.</p>

CC BY-SA 3.0
2013-02-16T13:13:42.760Z
2013-02-19T20:28:22.473Z
2013-02-19T20:28:22.473Z
Bruno Bauwens
<p>Kolmogorov complexity of a string is not computable. However, in a random subset of size $M$ of binary strings of length $n$, how many are expected to have complexity less than some integer $n_{0}$ less than $n$ (as a function of $M$, $n$ and $n_{0}$)?</p>

CC BY-SA 3.0
2011-08-29T19:05:13.053Z
Are you using "standard" Kolmogorov complexity here, or prefix complexity?
Aubrey da Cunha
CC BY-SA 3.0
2011-08-29T21:21:33.977Z
Actually I was thinking only of Kolmogorov complexity. I was guessing the $2^{n_{o}}$ bound that domotorp mentioned when we consider the universe of all strings. I was not clear if any 'consistent' result for an arbitrary random subset of size $M$ can be produced. However would prefix complexity bring us to a different view point?
v s
CC BY-SA 3.0
2011-08-31T06:53:06.060Z
It certainly would not change the order of magnitude, in fact I think now my answer is a bound for both versions.
domotorp
CC BY-SA 3.0
2011-08-31T10:50:16.237Z
For every $n$ and every $c$, the probability that a random $n$-bit string $x$ has Kolmogorov complexity $K(x) \geq n-c$ is greater than $1 - \frac{1}{2^c}$ (with $c = n-n_0$). So in a random distribution of $M$ strings, you should expect $\frac{M}{2^(n-n_0)}$ strings with $K(x) \lt n_0$ ... intuitively, there is a very high probability to pick a string with high Kolmogorov complexity.
Marzio De Biasi
<cc.complexity-theory><kolmogorov-complexity>
Expected values of Kolmogorov complexity in a random sample
v s
# Expected values of Kolmogorov complexity in a random sample

(Asked by: username_0 on 2011-08-28)

Kolmogorov complexity of a string is not computable. However, in a random subset of size $M$ of binary strings of length $n$, how many are expected to have complexity less than some integer $n\_{0}$ less than $n$ (as a function of $M$, $n$ and $n\_{0}$)?

**Tags:** cc.complexity-theory, kolmogorov-complexity

> **Comments:**
> **username_1**: Are you using "standard" Kolmogorov complexity here, or prefix complexity?  
> **username_0**: Actually I was thinking only of Kolmogorov complexity. I was guessing the $2^{n_{o}}$ bound that username_2 mentioned when we consider the universe of all strings. I was not clear if any 'consistent' result for an arbitrary random subset of size $M$ can be produced. However would prefix complexity bring us to a different view point?  
> **username_2**: It certainly would not change the order of magnitude, in fact I think now my answer is a bound for both versions.  
> **username_3**: For every $n$ and every $c$, the probability that a random $n$-bit string $x$ has Kolmogorov complexity $K(x) \geq n-c$ is greater than $1 - \frac{1}{2^c}$ (with $c = n-n_0$). So in a random distribution of $M$ strings, you should expect $\frac{M}{2^(n-n_0)}$ strings with $K(x) \lt n_0$ ... intuitively, there is a very high probability to pick a string with high Kolmogorov complexity.  

---

## 2 answers

### Answer by username_2 on 2011-08-28. Score: 10

Kolmogorov complexity is only determined up to some additive constant, so it is not possible to give an exact answer. The bound that I describe here is even weaker.

Of course the expected number can be computed easily once we know how many of the $2^n$ strings have complexity less than $n\_0$, so let me answer this. It is usually the first statement about Kolmogorov complexity that this number is at most $2^{n\_0}-1$ - since there are only these many strings of smaller length. On the other hand, if your program says "of length $n$, take the $x$th number", then you get $2^{n\_0-K(n)-C}$ strings of complexity less than $n\_0$, where $K(n)$ is the prefix-free version of Kolmogorov complexity of $n$ (so at most $\log n+\log^\* n + O(1)$). In more detail, the string first contains the description of the Turing machine that taken input $px$, where p is the description of a prefix-free program that outputs $n$, outputs the $x$th number of length $n$, which is $O(1)$ bits, and then this is followed by $px$.

Probably it is possible to improve these bounds, but I doubt that you could get an exact answer.

> **Comments:**
> **username_0**: Could you explain a little about the phrase 'if your program says "of length n, take the xth number"'?  
> **username_2**: You are right, it should be prefix-free there, I corrected it.  

---

### Answer by username_4 on 2013-02-16. Score: 3

A precise answer can be given. The number of strings of length $n$ with (plain) complexity at most $n\_0$ is $2^{n\_0 - K(n\_0|n)}$, up to a constant factor. Hence any process that randomly chooses a subset will have, with reasonable probability, a $2^{-K(n\_0|n) + O(1)}$ fraction of strings of complexity less than $n\_0$. To show our our claim, it suffices to show that the number of strings with complexity **equal** to $k$ is also given by $2^{k - K(k|n)}$. We can show the necessary result by determining the summation of this value over $k$ from 1 up to $n\_0$. To show this, we use an additivity result for plain complexity (due to B. Bauwens and A. Shen. *An additivity theorem for plain Kolmogorov complexity*. Theory of Computing Systems, 52(2):297-302, Feb 2013),
$$
C(a,b) = K(a|C(a,b)) + C(b|a,C(a,b)) + O(1).
$$
Here $K(\cdot)$ denotes prefix-free Kolmogorov complexity. Choosing $a = n$, we observe that for each $n$-bit string $b$ of complexity $k$ we have
$$
k = C(b) = C(n,b) + O(1) = K(n|k) + C(b|n,k) + O(1).
$$
Hence, for each such $b$ we have $C(b|n,k) = k - K(n|k)+O(1)$. Let $k' = k - K(n|k)$. Now one can observe that there are at most $O(2^{k'})$ such strings $b$, and each of the lexicographically first $2^{k'}$ strings of length $n$ satisfy $C(b|n,k) \le k' + O(1)$. Thus $\Omega(2^{k'})$ of them satisfy $C(b|n,k) = k' + O(1)$.


---

