# Number of $1$'s in a Kolmogorov-random number

The problem I'm trying to tackle is to show that for a Kolmogorov-random number of length $n$, the amount of $1$'s in its binary representation is greater than $n/4$.

My only idea so far, is to use a Turing machine that takes indices of $1$'s as an argument and produces a binary sequence accordingly. Then, for instance, we could say the amount of ones is at least $\sqrt n$ as (roughly) $C_U(n)\leq \sqrt n\log n < n$ for $n$ large enough (each index is at most of length $\log n$). But this doesn't allow us to infer there are more than $n/4$ ones.

Is there any other way to generate some given number that would prove the statement in question?

• Suppose the number of 1's is less than $n/4$. Can you think of a "small" Turing machine to output that number? How small will it be? How many possible numbers of length are there where the number of 1's is less than $n/4$? – D.W. Feb 20 '17 at 22:54

Our machine $M$ takes the length of a number, $n$, and an index $j$ as an input (we encode the first argument in such a way so that there was no doubt where it ends, i.e. putting $0$ in between every digit and ending with $1$). $j$ denotes the $j$-th number with less than $n/4$ ones in a lexicographic order. The only problem we have now, is to evaluate how big $j$ can be.
We have $$j_{\max}=\sum\limits_{i\leq n/4}\binom{n}{i}$$
Often, when proving Second Shannon's Theorem, the above sum (even more general, with $\lambda n,\ \lambda\in (0,1/2]$) is evaluated to be less than $2^{nH(\lambda)}$ with $H(\lambda)$ being the entropy of a non-fair coin throw.
Thus, we get $j_{\max}\leq 2^{nH(1/4)}$. Since $H(\lambda)\leq 1$, a number with less than $n/4$ ones cannot be random besides finitely many cases.
More exactly, $$C_U(x)\leq 2\log(n) + nH(1/4) + c$$ and this, for $n$ large enough, is less than $n$.