Previously, we discussed the construction of logical counterfactuals in the language of optimal predictors. These counterfactuals were found to be well-behaved when a certain non-degeneracy condition is met which can be understood as a bound on the agent's ability to predict itself. We also demonstrated that desired game-theoretic behavior seems to require randomization (thermalizing instead of maximizing) which has to be logical randomization to implement metathreat game theory by logical counterfactuals. Both of these considerations suggest that the agent has to pseudorandomize (randomize in the logical uncertainty sense) its own behavior. Here, we show how to implement this pseudorandomization and prove it indeed guarantees the non-degeneracy condition.
The proofs of the results are given in Appendix A.
We start with describing the analogous construction in classical probability theory.
Fix . Denote . Suppose is a probability distribution on , i.e. . We want to construct a procedure that samples according to the probabilities .
Suppose we are given , a uniformly distributed -valued random variable. Then we can select by
It is easy to see that implements the desired sampling i.e. .
In order to translate the above into logical uncertainty, we need a source of pseudorandom that can be the counterpart of . The following definition establishes the desiderata of this object.
Fix an error space and . Consider , a probability measure on , a word ensemble and . is said to be -distributed -pseudorandom within precision when for any -valued -bischeme , uniformly bounded family of functions and sequence s.t. is Lipschitz continuous with constant , there is s.t.
Compare the above to the previously given definition of an "irreducible" estimation problem.
We now give a basic existence result for pseudorandom functions by establishing that a random function is pseudorandom.
Consider and . is defined to be the set of bounded functions s.t.
Consider and . If exists s.t. then is an error space. If exists s.t. then is an ample error space.
For any , .
For any there is s.t. the following holds. Consider a probability measure on and a word ensemble. Let be generated by independently sampling for each . Suppose , and are s.t. and
Then is -distributed -pseudorandom within precision with probability 1.
Finally, we show pseudorandomization guarantees non-degeneracy.
Given measurable space and , will denote a Markov kernel with source and target . For each , will refer to the corresponding -valued random variable.
Fix . Consider an error space, , a word ensemble, , and . Suppose that for any , and with probability 1 and that is uniform -pseudorandom within precision . Define by
Assume is a symmetric -orthogonal predictor for . Let be the lowest eigenvalue of . Then there is s.t.
In the setting of Theorem 2, assume . Then there is a symmetric -optimal predictor for s.t. its lowest eigenvalue is at least .
Proposition 1 and 2 are obvious and we skip the proofs.
Given , let be the set of functions given by or for , .
Proof of Theorem 1
Consider any continuous function . For any and , we have
Denote the probability measure from which is sampled. That is, is the completion of . Denote .
By Hoeffding's inequality,
For some we have . Denote . For any we have
For any , we know that
It follows that with -probability 1
This implies that for any -valued -bischeme
Consider a uniformly bounded family of functions and sequence s.t. is Lipschitz continuous with constant . By Corollary B (see Appendix B) there are , and s.t. , and .
Fix an error space and . Consider , a probability measure on , a word ensemble and . Assume is -distributed -pseudorandom within precision . Then, for any -valued -bischeme , uniformly bounded family of functions and sequence s.t. is Lipschitz continuous with constant , there is s.t.
Proof of Proposition A.1
The definition of pseudorandom implies for any and as above there is an -moderate function s.t. for any ,
This easily implies the desired result.
Proof of Theorem 2
Since it is possible to find a lowest eigenvector of a symmetric matrix in time polynomial in the number of significant digits, there is a -valued -bischeme s.t. and for . For any bounded -valued -bischeme with we have
Denote . Let be an -valued -bischeme s.t. . We have and in particular if is s.t. then .
For any , , denote , . Define by
is Lipschitz continuous with constant .
only depends on the first variables. As a function of these variables, its graph is a pyramid of height 1 whose base is the box . It follows that .
For any -valued -bischeme we can apply Proposition A.1 to get s.t.
We have . Assuming , we get s.t.
It is easy to see that for any for any , if then . Hence . We conclude
Since can be approximated by a -bischeme up to an error in , there is s.t.
Fix an error space . Consider a distributional estimation problem and a corresponding -orthogonal predictor . Suppose is a bounded -valued -bischeme s.t. (denote ) and . Then is an -optimal predictor for .
Proof of Proposition A.2
Consider a bounded -valued -bischeme with . We have
Proof of Corollary
Given a field , let be the space of symmetric matrices over . Given , denote the following function. Given , let be an orthonormal basis of eigenvectors for and be the corresponding eigenvalues. Then, . As easy to see, the definition doesn't depend on the choice of .
Denote . Let be a -valued -bischeme with whose lowest eigenvalue is at least and which satisfies . Using Theorem 2 and we conclude that
Applying Proposition A.2 we get the desired result.
Cartwright and Kucharski give a generalization of Jackson's inequality for an arbitrary compact connected Lie group. We only need the uniform norm, rank 1 case for the standard torus, so we state here this special case.
Fix . Denote the standard n-dimensional torus. Then there is s.t. for any there is s.t. its Fourier transform satisfies and for any we have
Moreover, the are uniformly bounded.
The fact are uniformly bounded is not stated explicitly in Cartwright and Kucharski but it is evident from their construction of .
For any there are s.t. the following holds. Consider and , Lipschitz continuous with constant . Then there are and s.t. , and .
Proof of Corollary B
Using reflections, can be continued to a function on with periodic boundary conditions which is still Lipschitz continuous with constant . This new function can be reinterpreted as a function Lipschitz continuous with constant . Applying Theorem B, where . Using the properties of , we have , where for some because the are uniformly bounded and can be bounded by . Since is real, , yielding the desired result.