We formulate a concept analogous to Garrabrant's irreducible pattern in the complexity theoretic language underlying optimal predictor schemes and prove a formal relation to Garrabant's original definition. We prove that optimal predictor schemes pass the corresponding version of the Benford test (namely, on irreducible patterns they are $\Delta$-similar to a constant).

Results

All the proofs are given in the appendix.

Definition 1

Fix $\Delta$ an error space of rank 2. Consider $(f,\mu )$ a distributional estimation problem, $\alpha \in [0,1]$. $(f,\mu )$ is called $\Delta (poly,log)$-irreducible with expectation $\alpha$ when for any $\{0,1\}$-valued $(poly,log)$-bischeme $\hat{A}=(A,r_A,a_A)$ we have

$$|E_{{\mu }^k\times U^{r_A(k,j)}}\left[\right(f-\alpha \left){\hat{A}}^{kj}\right]|\in \Delta$$

Theorem 1

Fix $\Delta$ an error space of rank 2. Assume $h:N^2\to N$ is a polynomial s.t. $h^{-1}\in \Delta$. Given $t\in [0,1]$, define ${\pi }_h^{kj}\left(t\right)$ to be $t$ rounded within error $h(k,j{)}^{-1}$. Consider $(f,\mu )$ a distributional estimation problem, $\alpha \in [0,1]$. Define the $(poly,log)$-predictor scheme ${\hat{P}}_{\alpha ,h}$ by ${\hat{P}}_{\alpha ,h}^{kj}\left(x\right):={\pi }_h^{kj}\left(\alpha \right)$. Then, $(f,\mu )$ is $\Delta (poly,log)$-irreducible with expectation $\alpha$ if and only if ${\hat{P}}_{\alpha ,h}$ is a $\Delta (poly,log)$-optimal predictor scheme for $(f,\mu )$.

Corollary 1

Consider ${\Delta }_1$, ${\Delta }_2$ error spaces of rank 2 s.t. ${\Delta }_1\subseteq {\Delta }_2$. Assume there is a polynomial $h:N^2\to N$ s.t. $h^{-1}\in {}^{}$