Deterministic completions require unresolved information

Status: Proved.

Let $S,T$ be standard Borel spaces, let $\Prb$ be a probability law on $S$, let $T_0=p(S_0)$ for a measurable $p$, and let a future finite-valued record be a measurable deterministic function $R=R(S_0)$.

1. If $R$ is binary, write $q(T_0)=\Prb(R=1\mid T_0)$. The minimum probability of error of a measurable deterministic predictor of $R$ from $T_0$ is

   $$\inf_h\Prb\{R\ne h(T_0)\} =\E\min\{q(T_0),1-q(T_0)\}.$$

   If this is positive, $R$ does not descend almost surely through $p$; on a positive-measure set of readout fibers there are source states with different records.

2. If a finite-valued completion variable $Z$ makes $R=f(T_0,Z)$ almost surely, then, with entropy in bits,

   $$H(Z\mid T_0)\ge H(R\mid T_0).$$

   In particular, a conditionally uniform $n$-bit record requires at least $n$ bits of conditional completion entropy and $|\mathcal Z|\ge2^n$.

3. At a fixed readout $t$, suppose a deterministic simulator uses at most $M$ values of $Z$. If its record law is within $\varepsilon$ in total variation of the uniform law on $\{0,1\}^n$, then

   $$M\ge(1-\varepsilon)2^n.$$

   The bound is sharp when $M\le2^n$: a uniform distribution on any $M$ record strings has distance $1-M/2^n$ from the uniform target.