I am working on the following problem:

Prove that, for all $k\in\mathbb N$, there exists $n\in\mathbb N$ so that every binary string $x\in\{0,1\}^{kn}$ with Kolmogorov complexity $K(x)$ at least $kn$ satisfies the following property:

By interpreting $x$ as $x_1\cdots x_n$, with $|x_i|=k$, for any $z\in\{0,1\}^k$ there is an index $i$ for which $x_i=z$.

To show this, I want to suppose that if there exists a string $x$ of length $kn$ so that, after writing $x=x_1\cdots x_n$, not all $k$-bit binary strings appear in $x_1\cdots x_n$. Then ideally I want to show that $x$ can be described in less than $kn$ bits, which means $x$ have Kolmogorov complexity less than $kn$, which establishes the contradiction I want.

Any hints on how to do this?

For completeness, the Kolmogorov complexity of a string $x$ is defined as the length of the shortest description of $x$. And by the description of a string $x$, I refer to a pair $(M,w)$, where $M$ is a Turing Machine and $w$ is some string, so that $M$ halts on $w$ as input, leaving behind $x$ on the tape. I encode the pair $(M,w)$ as $0^{|M|}1Mw$. Then, for any string $x$, if $M$ is a Turing Machine that halts immediately upon execution, then $(M,x)$ is a description for $x$, of length $2|M|+|x|+1$. Hence the Kolmogorov complexity of $x$ does not exceed $2|M|+|x|+1$.


Suppose that $x = x_1 \cdots x_n$, where $|x_i| = k$, and there exists some $z \in \{0,1\}^k$ such that $x_i \neq z$ for all $i$. We can encode $x$ by first listing $z$, and then encoding each $x_i$ using $\log_2 (2^k-1)$ fractional bits. The program also needs to know $n$. This shows that $$ K(x) \leq \log_2 (2^k-1) \cdot n + C_k + O(\log n), $$ where $C_k$ is a constant that depends only on $k$. In particular, if $n$ is large enough that the upper bound will be less than $nk$.


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.