# What's the distribution of the Kolmogorov complexity of the elements in the set of bitstrings of length n?

take e.g. all possible bitstrings of length n=10,000. there are 2^10,000 of them. imagine that for each of those strings we knew the length of the shortest program that could produce the string. what would the distribution of the lengths of those programs look like?

• How precise of an answer do you want? By a counting argument, only a $2^{-c}$ fraction of strings can possibly have a KC of less than $2^{10000-c}$, or in other words, all but $o(n)$ strings have complexity $n-o(n)$.
– usul
Sep 24, 2017 at 9:40
• PS. That should say all but $2^{o(n)}$ strings have complexity $n - o(n)$, or equivalently all but an $o(1)$ fraction of strings.
– usul
Sep 29, 2017 at 19:29
• Thank you, that is interesting. I suppose I'm interested in as precise an answer as is currently possible, but would take anything more than I know right now which is near zero :) The counting argument is probably obvious to most, but I would be interested in hearing it described. Sep 30, 2017 at 20:28