2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – D.W. Feb 20 '17 at 22:54
3
$\begingroup$

I've found an answer which uses certain facts I was not aware of, but it's nevertheless really good.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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