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.

Results

The proofs of the results are given in Appendix A.

Motivation

We start with describing the analogous construction in classical probability theory.

Fix $n\in N$. Denote $A:=\{a\in N\mid a<n\}$. Suppose $\{q_a\in [0,1]{\}}_{a\in A}$ is a probability distribution on $A$, i.e. ${\sum }_{a\in A}{q}_a=1$. We want to construct a procedure that samples $A$ according to the probabilities $q$.

Suppose we are given $h$, a uniformly distributed $[0,1{]}^A$-valued random variable. Then we can select $s(q,h)\in A$ by

$$s(q,h):=min\{a\in A\mid \frac{q_a}{{\sum }_{b=a}^{n-1}{q}_b}\ge h_a\}$$

It is easy to see that $s(q,h)$ implements the desired sampling i.e. $\mathrm{Pr}\left[s\right(q,h)=a]=q_a$.

---

In order to translate the above into logical uncertainty, we need a source of pseudorandom that can be the counterpart of $h$. The following definition establishes the desiderata of this object.

Definition

Fix an error space $E$ and $d:N\to R^{\ge 0}$. Consider $n\in N$, $\nu$ a probability measure on $[0,1{]}^n$, $\mu$ a word ensemble and $h:\mathrm{supp}\mu \to [0,1{]}^n$. $(\mu ,h)$ is said to be $\nu$-distributed $E(poly,log)$-pseudorandom within precision $d$ when for any $\{0,1\}$-valued $(poly,log)$-bischeme $\hat{S}$, uniformly bounded family of functions $\{f^k:[0,1{]}^n\to R{\}}_{k\in N}$ and sequence $\{L^k\in R^{>0}{\}}_{k\in N}$ s.t. $f^k$ is Lipschitz continuous with constant $L^k$, there is $\delta \in E$ s.t.

$$\left|E_{\mu \times U^{r_S}}\right[\hat{S}(f\circ h-E_{\nu }[f\left]\right)|\le \delta +Ld$$

Note

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.

Construction

Consider $t:N\to N$ and $\alpha :N\to R^{\ge 0}$. $E_{2(t,\alpha )}$ is defined to be the set of bounded functions $\delta :N^2\to R^{\ge 0}$ s.t.

$$\exists ϵ>0\forall m\in N:\text{for almost all}k\in N:\forall j<(t^k{)}^m:ϵ{\delta }^{kj}\le {\alpha }^k$$

Proposition 1

Consider $t:N\to N$ and $\alpha :N\to R^{\ge 0}$. If exists $m\in N$ s.t. ${\alpha }^k=\Omega \left(2^{-k^m}\right)$ then $E_{2(t,\alpha )}$ is an error space. If exists $m\in N$ s.t. ${\alpha }^k=\Omega \left(k^{-m}\right)$ then $E_{2(t,\alpha )}$ is an ample error space.

Proposition 2

For any $\varphi \in \Phi$, $E_{2(t_{\varphi },\frac{1}{\varphi })}\subseteq E_{2(ll,\varphi )}$.

Theorem 1

For any $n\in N$ there is $M_n>0$ s.t. the following holds. Consider $\nu$ a probability measure on $[0,1{]}^n$ and $\mu$ a word ensemble. Let $h^{\ast }:\mathrm{supp}\mu \to [0,1{]}^n$ be generated by independently sampling $\nu$ for each $x\in \mathrm{supp}\mu$. Suppose $t:N\to N$, $\alpha :N\to R^{\ge 0}$ and $d:N\to R^{\ge 0}$ are s.t. $t^k\ge k$ and

$$\forall m\in N:\underset{k\to \infty }{lim}\left(t^k{)}^m\right(d^k{)}^{-n}\exp (-\frac{1}{2}\frac{\left(d^k{)}^{2n}\right({\alpha }^k{)}^2}{{\sum }_{x\in \{0,1{\}}^{\ast }}{\mu }^k(x{)}^2})=0$$

Then $(\mu ,h^{\ast })$ is $\nu$-distributed $E_{2(t,\alpha )}(poly,log)$-pseudorandom within precision $M_{n}d$ with probability 1.

---

Finally, we show pseudorandomization guarantees non-degeneracy.

Notation

Given measurable space $X$ and $Y$, $f:X\stackrel{mk}{\to }Y$ will denote a Markov kernel with source $X$ and target $Y$. For each $x\in X$, $f\left(x\right)$ will refer to the corresponding $Y$-valued random variable.

Theorem 2

Fix $n\in N$. Consider $E$ an error space, $d:N\to R^{\ge 0}$, $\mu$ a word ensemble, $q:\mathrm{supp}\mu \stackrel{mk}{\to }[0,1{]}^n$, $\zeta :N\to (0,\frac{1}{n}]$ and $h:\mathrm{supp}\mu \to [0,1{]}^n$. Suppose that for any $x\in \mathrm{supp}{\mu }^k$, ${\sum }_{a=0}^{n-1}{q}_a\left(x\right)=1$ and $\forall a<n:q_a\left(x\right)\ge {\zeta }^k$ with probability 1 and that $(\mu ,h)$ is uniform $E(poly,log)$-pseudorandom within precision $d$. Define $p:\mathrm{supp}\mu \to [0,1{]}^n$ by

$$p_a\left(x\right):$$