Optimal predictor schemes pass a Benford test

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 -similar to a constant).

Results

All the proofs are given in the appendix.

Definition 1

Fix an error space of rank 2. Consider a distributional estimation problem, . is called -irreducible with expectation when for any -valued -bischeme we have

Theorem 1

Fix an error space of rank 2. Assume is a polynomial s.t. . Given , define to be rounded within error . Consider a distributional estimation problem, . Define the -predictor scheme by . Then, is -irreducible with expectation if and only if is a -optimal predictor scheme for .

Corollary 1

Consider , error spaces of rank 2 s.t. . Assume there is a polynomial s.t. . Consider a distributional estimation problem, and a -optimal predictor scheme for . Suppose is -irreducible with expectation . Then, .


The following definition is adapted from Garrabrant with relatively minor modifications

Definition 2

Denote the uniform probability measure on . Given and , denote . Fix . is called a -irreducible pattern with expectation when for any polynomial there is s.t. for any if runs within time on any input s.t. then

Note 1

Definition 2 differs from Garrabrant’s original definition in several respects:

  • We consider an arbitrary function rather than the characteristic function of the set of provable sentences.

  • Instead of a single time bound, we consider a family of time bounds differing by a polynomial.

  • We allow to be a random algorithm rather than requiring it to be deterministic.

Definition 3

Fix . is the set of bounded functions for which there are s.t.

Proposition 1

is an error space of rank 2.

Theorem 2

Assume is s.t. for some polynomial we have . Consider , . Assume is a -irreducible pattern with expectation . Then, is -irreducible with expectation .

Definition 4

Denote the set of functions s.t. . Given , define . Fix . is the set of bounded functions s.t. for any , if then

Proposition 2

is an error space of rank 2.


Note that .

Proposition 3

Consider s.t. . Then .

Corollary 2

Fix s.t. . Cosnider , and a -optimal predictor scheme for . Suppose is a -irreducible pattern with expectation . Then .

Note 2

It is possible to repeat this theory without random and thus relate the deterministic version of irreducible patterns to -optimal predictor schemes (which have logarithmic advice and no coin flips or equivalently logarithmic number of coin flips).

Appendix

We will refer to the previously established results about -optimal predictor schemes by L.N where N is the number in the linked post. Thus Theorem 1 there becomes Theorem L.1 here and so on.

Proposition 4

Fix an error space of rank 2. Consider a distributional estimation problem, . Suppose is -irreducible with expectation . Then, there is a -moderate function s.t. for any and

Proof of Proposition 4

Take to be

If is not -moderate then there is a polynomial and a family of programs s.t. is bounded by a polynomial in and is logarithmically bounded in but

We can unite the into a single -predictor scheme by providing them as advice for a universal program. This contradicts the assumption on .

Proof of Theorem 1

If is a -optimal predictor scheme for then is -irreducible with expectation by Lemma L.B.3.

Assume is -irreducible with expectation . Consider any -valued -bischeme. By Lemma L.B.3, it is sufficient to prove that

We have

Applying Proposition 4 to , we conclude that there is s.t.

Summing up

Proof of Corollary 1

Trivially follows from Theorem 1 and Theorem L.A.7.

Proposition 5

Fix . Assume is bounded and are s.t.

Consider . Then, there is s.t.

Proof of Proposition 5

Proof of Proposition 1

The only not entirely obvious part is additivity. Consider . Suppose are s.t.

For sufficiently large , can be written as a sum of terms of the form for , . Applying Proposition 5, we conclude that there is s.t.

Proposition 6

For any , , ,

Proof of Proposition 6

Since we can choose s.t. . We get

Proof of Theorem 2

Consider a -valued -bischeme. Define by

Choose a polynomial s.t. runs within time for , and and that for . We have

for some . therefore

On the other hand

Combining the two cases

Using Proposition 6, we conclude that

Proof of Proposition 2

Proven exactly the same way as for .

Proof of Proposition 3

Consider . Take s.t.

Given s.t. , we have

We conclude that and therefore .

Proof of Corollary 2

Follows trivially from Theorem 2, Proposition 3 and Corollary 1.

No comments.