Regarding notation in the following, the function $\ell(B)$ returns the length of bitstring $B$, and the cardinality of set $S$ is denoted by $|S|$.

A bitstring $B$ is generated by drawing 0s and 1s from a uniform distribution and is of length $n=\ell(B)$.

Kolmogorov complexity for a bitstring $B$ is the length of the shortest program $B^*$ that generates $B$, $K(B) = \ell(B^*)$.

A typical $B$ is difficult to define precisely. Intuitively, it is the sort of bitstring that will be generated most of the time by randomly drawing 0s and 1s. However, the concept can be clarified by examining properties. A property $p$ applies to typical $B$s if the proportion of $B$s having that property approaches 1 as $\ell(B)$ is increased, \begin{align*} \underset{n\rightarrow \infty}{\lim} \frac{|\{B: p(B) \wedge \ell(B) \leq n\}|}{|\{B: \ell(B) \leq n\}|} \rightarrow 1. \end{align*}

For instance, a typical $B$ has the property that $K(B) = \ell(B)$. In other words, a typical $B$ is not compressible. Note: this is not a sufficient condition for typicality. It is possible for a $B$ to be atypical and incompressible.

There are atypical $B$s that can be compressed, and for these $K(B) < \ell(B)$.

Conditional Kolmogorov complexity, $K(B_2|B_1)$, is the length of the shortest program that generates $B_2$ when given $B_1$ as input.

Algorithmic mutual information is $I(B_1:B_2) = K(B_2) - K(B_2|B_1^*) = K(B_1) - K(B_1| B_2^*)$. This expression is accurate to within a constant independent of $B_1$ and $B_2$.

A Kolmogorov structure function for a bitstring $B$ is the set generating program $P_B$ such that $B$ is in the set $S_B$ generated by $P_B$ when given $n$ as input. The shortest $P_B$, such that $\ell(P_B) + \log_2(|S_B|) \leq K(B)$, is called the minimal Kolmogorov structure function, denoted by $P^*_B$. $\log_2(|S_B|)$ is close to the "randomness" in $B$ that cannot be captured by $P^*_B$.

In the case of a typical $B$ the length of $P^*_B$ is minimal, since knowing $n$ we can enumerate all bitstrings of length $n$ with a constant size program $C$. On the other hand, in the case of atypical $B$s, the length of $P^*_B$ may be significantly larger than $C$.

My question: is the algorithmic mutual information between a typical $B$ and a $P^*_{B'}$ for any bitstring $B'$ ever larger than $C$? Although $\ell(B')$ is not constrained by $\ell(B)$, the $P^*_{B'}$ is provided with $n=\ell(B)$ in this case, since the goal is to generate $B$. However, this does not mean that $B\in S_{B'}$, since $\ell(B)$ does not necessarily cause $P^*_{B'}$ to generate a set that contains $B$.

Note in the case of a typical $B$ that trivially $I(P^*_B:B)=\ell(C)$ since $\ell(P^*_B)=\ell(C)$. However, this does not mean that there is not another $P^*_{B'}$ from an atypical $B'$ such that $K(B|P^*_{B'}) < K(B)-\ell(C)$, and thus $I(P^*_{B'}:B) > \ell(C)$.

I think the answer is always $I(B:P^*_{B'}) = \ell(C)$ for a typical $B$. If $K(P^*_{B'}|B) < K(P^*_{B'})-\ell(C)$, then part of the randomness of $B$ describes $P^*_{B'}$, so $P^*_{B'}$ is not a minimal structure function for $B'$. I don't know how to prove this formally.

To provide context for this question, I am trying to derive a law of minimal Kolmogorov sufficient statistic nongrowth, based on Leonid Levin's conservation independence in "Randomness Conservation Inequalities; Information and Independence in Mathematical Theories". Levin's law states $I(z:y) > I(x:y)$ where $x$ is the result of applying a Turing machine $U$ to $z$, so $x=U(z)$. I would like to similarly prove $\ell(P^*_z) > \ell(P^*_x)$, and am using $I(B:P^*_{B'})=\ell(C)$ for typical $B$ as one of the premises in my proof.

  • $\begingroup$ This question was transferred from cs.stackexchange.com, where it received no answer. I've deleted the question at that site. $\endgroup$
    – yters
    Commented Jul 2, 2018 at 11:21
  • 1
    $\begingroup$ So you wrote that for typical $R$, the length of $S$ is zero... which immediately implies the mutual information between $S$ and anything is zero. $\endgroup$ Commented Jul 3, 2018 at 18:02
  • $\begingroup$ @BjørnKjos-Hanssen Because a typical $R$ does not have its own $S$, doesn't mean there isn't some $S$ such that $K(R|S) < K(R)$. However, in that case, $K(R|S) + K(S) > K(R)$ because $S$ cannot be the minimal Kolmogorov sufficient statistic for $R$. $\endgroup$
    – yters
    Commented Jul 3, 2018 at 20:31
  • $\begingroup$ I'm confused by the statement "the $P^∗_{B′}$ is provided with $n=\ell(B)$, in this case, since the goal is to generate $B$." By definition $P^*_{B'}$ generates a set containing $B'$, given $\ell(B')$. Are you redefining $P^*_{B'}$ so that it must generate a set containing $B$, given $\ell(B)$? But then $P^*_{B'}$ would just be $P^*_{B}$. Please clarify? $\endgroup$
    – Neal Young
    Commented Jul 5, 2018 at 16:17
  • $\begingroup$ There's a technical issue in the def'n of typical and minimal here. Let $p_n$ be the probability that a random string $B$ of length $n$ or less has $\ell(B)=K(B)$. Your post says that $p_n\rightarrow 1$, but it's false. For any encoded TM $P$ let $P'$ be obtained by adding a useless state to $P$, so $P'$ does not have minimal description length and $\ell(P′)=\ell(P)+c$ for some constant $c$. So $1−p_{n+c} \ge p_n/c′$ for a constant $c′$. So it cannot be that $p_n\rightarrow 1$. $\endgroup$
    – Neal Young
    Commented Jul 11, 2018 at 15:00

1 Answer 1


EDIT 2: Updated the answer for the updated definition of typical.

I may be misunderstanding your definition of $P^*_{B'}$. With that caveat, though, I believe your conjecture does not hold. The proof is in two steps.

Lemma 1. For some $c_0>0$, for all $n>0$, there are strings $B$ and $B'$ such that $K(P^*_{B'} | B) \le c_0$ and $K(P^*_{B'}) = \ell(B) \ge n$.

Proof sketch. Let $c_0$ be the length of any universal TM. Fix any $n>0$.

  1. Fix any string $B'$ such that $K(P^*_{B'}) \ge 2n$. (We discuss below our assumption that $B'$ exists.)

  2. Let $B$ be the shortest program that generates $P^*_{B'}$, so that $K(P^*_{B'}) = \ell(B)$.

  3. And $K(P^*_{B'} | B) \le c_0$, because given input $B$, the universal TM outputs $P^*_{B'}$.

Here's the justification for Step 1. If $B'$ does not exist, then there are only finitely many minimal Kolmogorov structure functions. I assume this is known not to hold, because otherwise $I(B : P^*_{B'}) \le K(P^*_{B'}) = O(1)$ for all $B$ and $B'$, and the conjecture would be trivially true (for some constant, at least). Also, the post states "On the other hand, in the case of atypical $B$s, the length of $P^*_{B}$ may be significantly larger than $C$." Perhaps someone who knows more about this topic could confirm that there are infinitely many minimal Kolmogorov structure functions. $~~\Box$

This concludes the proof sketch for Lemma 1. Next we show that the conjecture does not hold.

Lemma 2. For any $c > 0$, there are $\epsilon>0$ and a string $B'$ such that, for all sufficiently large $n$, for a random $n$-bit string $B$, with probability at least $\epsilon$, $I(B : P^*_{B'}) \ge c$.

Proof. Fix any $c> 0$. Assume WLOG that $c\ge c_0$ from Lemma 1, and $c + \log(c) + c_1 + c_2 \le 2c$ for fixed constants $c_1, c_2$ defined in Steps 4 and 5 below. (Otherwise just increase $c$.)

  1. Fix strings $B_0$ and $B'$ such that $K(P^*_{B'} | B_0) \le c$ and $K(P^*_{B'}) = \ell(B_0) \ge 4c$. (These exist by Lemma 1.)

  2. Let $\epsilon=2^{-\ell(B_0)}$. Consider any $n\ge \ell(B_0)$ and let $B$ be a random $n$-bit string.

  3. The event that $B_0$ is a prefix of $B$ happens with probability at least $\epsilon$. Assume this event occurs. To complete the proof we show that $I(B:P^*_{B'}) \ge c$.

  4. First note that $$K(P^*_{B'} | B) \le K(P^*_{B'} | B_0) + K(B_0 | B) + c_1$$ (for some fixed $c_1$) because, given $B$, we can compute $B_0$ from $B$, then compute $P^*_{B'}$ from $B_0$.

  5. Using $K(P^*_{B'} | B_0) \le c$ (from Step 1), and $K(B_0|B)\le \log \ell(B_0) + c_2$ (for some fixed $c_2$, using a TM that truncates its input $B$ to its first $\ell(B_0)$ bytes), this implies $$K(P^*_{B'} | B) \le c + \log \ell(B_0) + c_1 + c_2 \le \ell(B_0)/2.$$ (Using above our assumptions on $c$ and $\ell(B_0) \ge 4c$ from Step 1.)

  6. Using this and $K(P^*_{B'}) = \ell(B_0) \ge 4c$ (from Step 1), we have $$I(B : P^*_{B'}) = K(P^*_{B'}) - K(P^*_{B'} | B) \ge \ell(B_0) - \ell(B_0)/2 \ge 2c.$$ $\Box$

I guess this completes the proof, but I'm unsure whether I've properly interpreted the post, because of the following statement in the post "the $P^∗_{B′}$ is provided with $n=\ell(B)$, in this case, since the goal is to generate $B$." I'm not sure what it this means, as it seems to contradict the earlier definition of $P^*_{B'}$ in the post (which is used in the proof above).

  • $\begingroup$ This is a pretty good answer. However, incompressibility does not entail typicality. Unless a large percentage of incompressible bitstrings encode a $P^*_{B'}$, then this answer does not show for typical bitstrings $I(B:P^*_{B'}) > c$. I apologize for not defining typicality better in my question. $\endgroup$
    – yters
    Commented Jul 5, 2018 at 20:13
  • $\begingroup$ I updated the answer to reflect your updated definition of "typical". Can you please clarify the caveat in your post about how $P^*_{B'}$ is defined for $B'$? (I commented on it above.) Thanks. $\endgroup$
    – Neal Young
    Commented Jul 6, 2018 at 2:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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