Algorithmic mutual information between random string and minimal Kolmogorov sufficient statistic

Question

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.

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