Algorithmic mutual information between random string and minimal Kolmogorov sufficient statistic
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&gt;0$, for all $n&gt;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&gt;0$.  


Fix any string $B'$ such that $K(P^*_{B'}) \ge 2n$.  (We discuss below our assumption that $B'$ exists.)
Let $B$ be the shortest program that generates $P^*_{B'}$, so that $K(P^*_{B'}) = \ell(B)$.
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 &gt; 0$, there are $\epsilon&gt;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&gt; 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$.)


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.)
Let $\epsilon=2^{-\ell(B_0)}$.  Consider any $n\ge \ell(B_0)$ and let $B$ be a random $n$-bit string.  
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$.
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$.
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.)
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).