Optimal predictor schemes pass a Benford test

[Vanessa Kosoy]

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 {\Delta }_2$. Consider $(f,\mu )$ a distributional estimation problem, $\alpha \in [0,1]$ and $\hat{P}$ a ${\Delta }_1(poly,log)$-optimal predictor scheme for $(f,\mu )$. Suppose $(f,\mu )$ is ${\Delta }_2(poly,log)$-irreducible with expectation $\alpha$. Then, $\hat{P}\underset{{\Delta }_2}{\stackrel{\mu }{\simeq }}\alpha$.

---

The following definition is adapted from Garrabrant with relatively minor modifications

Definition 2

Denote $U^{\le k}$ the uniform probability measure on $\{0,1{\}}^{\le k}$. Given $r:N\to N$ and $A:{\{0,1{\}}^{\ast }}^2\stackrel{alg}{\to }\{0,1\}$, denote $m_{A,r}\left(k\right):={\sum }_{x\in \{0,1{\}}^{\le k}}P{r}_{U^{r\left(|x|\right)}}\left[A\right(x,y)=1]$. Fix $t:N\to N$. $f:\{0,1{\}}^{\ast }\to [0,1]$ is called a $t\left(poly\right)$-irreducible pattern with expectation $\alpha \in [0,1]$ when for any polynomial $p:N\to N$ there is $c_p>0$ s.t. for any $W:{\{0,1{\}}^{\ast }}^2\stackrel{alg}{\to }\{0,1\}$ if $W$ runs within time $p\left(t\right(|x|\left)\right)$ on any input $(x,y)$ s.t.$|y|=p\left(t\right(|x|\left)\right)$ then

$$\forall k\in N:m_{W,p\left(t\right)}\left(k\right)\ge 3⟹|E_{U^{\le k}\times U^{p\left(t\right(k\left)\right)}}\left[f\right(x)\mid W(x,y_{\le p\left(t\right(|x|\left)\right)})=1]-\alpha |\le \frac{c_p|W|\sqrt{\log \log m_{W,p\left(t\right)}\left(k\right)}}{\sqrt{m_{W,p\left(t\right)}\left(k\right)}}$$

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 $W$ to be a random algorithm rather than requiring it to be deterministic.

Definition 3

Fix $t:N\to N$. ${\Delta }_{G,t}^2$ is the set of bounded functions $\delta :N^2\to R^{\ge 0}$ for which there are $c,d>0$ s.t.

$$\forall k:\forall j\le t\left(k\right):\delta (k,j{)}^d\le c{2}^{-k}\log (k+2\left)\right(\log (j+2){)}^2$$

Proposition 1

${\Delta }_{G,t}^2$ is an error space of rank 2.

Theorem 2

Assume $t:N\to N$ is s.t. for some polynomial $p:N\to N$ we have $p\left(t\right(k\left)\right)\ge k$. Consider $f:\{0,1{\}}^{\ast }\to [0,1]$, $\alpha \in [0,1]$. Assume $f$ is a $t\left(poly\right)$-irreducible pattern with expectation $\alpha$. Then, $(f,U)$ is ${\Delta }_{G,t}^2(poly,log)$-irreducible with expectation $\alpha$.

Definition 4

Denote $\Phi$ the set of functions $\varphi :N\to R^{\ge 0}$ s.t. ${lim}_{k\to \infty }\varphi \left(k\right)=\infty$. Given $\varphi \in \Phi$, define $t_{\varphi }\left(k\right):=\lfloor 2^{(\log k{)}^{\varphi \left(k\right)}}\rfloor$. Fix $\varphi \in \Phi$. ${\Delta }_{avg,\varphi }^2$ is the set of bounded functions $\delta :N^2\to R^{\ge 0}$ s.t. for any ${\varphi }^{\prime }\in \Phi$, if ${\varphi }^{\prime }\le \varphi$ then

$$\underset{k\to \infty }{lim}\frac{\sum _{j=2}^{t_{{\varphi }^{\prime }}\left(k\right)-1}\left(\log \log \right(j+1)-\log \log j)\delta (k,j)}{\log \log t_{{\varphi }^{\prime }}\left(k\right)}=0$$

Proposition 2

${\Delta }_{avg,\varphi }^2$ is an error space of rank 2.

---

Note that ${\Delta }_{avg}^2={\bigcap }_{\varphi \in \Phi }{\Delta }_{avg,\varphi }^2$.

Proposition 3

Consider $\varphi \in \Phi$ s.t. ${lim}_{k\to \infty }{2}^{-k}(\log k{)}^{2\varphi \left(k\right)+1}=0$. Then ${\Delta }_{G,t_{\varphi }}^2\subseteq {\Delta }_{avg,\varphi }^2$.

Corollary 2

Fix $\varphi \in \Phi$ s.t. ${lim}_{k\to \infty }{2}^{-k}(\log k{)}^{2\varphi \left(k\right)+1}=0$. Cosnider $f:\{0,1{\}}^{\ast }\to [0,1]$, $\alpha \in [0,1]$ and $\hat{P}$ a ${\Delta }_{avg}^2$-optimal predictor scheme for $(f,U)$. Suppose $f$ is a $t_{\varphi }\left(poly\right)$-irreducible pattern with expectation $\alpha$. Then $\hat{P}\underset{{\Delta }_{avg,\varphi }^2}{\stackrel{U}{\simeq }}\alpha$.

Note 2

It is possible to repeat this theory without random and thus relate the deterministic version of irreducible patterns to $\Delta \left(log\right)$-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 $\Delta (poly,log)$-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 $\Delta$ an error space of rank 2. Consider $(f,\mu )$ a distributional estimation problem, $\alpha \in [0,1]$. Suppose $(f,\mu )$ is $\Delta (poly,log)$-irreducible with expectation $\alpha$. Then, there is a $\Delta$-moderate function $\delta :N^4\to [0,1]$ s.t. for any $k,j,s\in N$ and $A:{\{0,1{\}}^{\ast }}^2\stackrel{alg}{\to }\{0,1\}$

$$|E_{{\mu }^k\times U^s}\left[\right(f\left(x\right)-\alpha \left)A\right(x,y\left)\right]|\le \delta (k,j,T_A^{\mu }(k,s),2^{|A|})$$

Proof of Proposition 4

Take $\delta$ to be

$$\delta (k,j,t,u):=\underset{\begin{array}{c}{T}_A^{\mu }(k,s)\le t\\ |A|\le \log u\end{array}}{max}|E_{{\mu }^k\times U^s}\left[\right(f\left(x\right)-\alpha \left)A\right(x,y\left)\right]|$$

If $\delta$ is not $\Delta$-moderate then there is a polynomial $s:N^2\to N$ and a family of programs $\{A^{kj}:{\{0,1{\}}^{\ast }}^2\stackrel{alg}{\to }\{0,1\}{\}}_{k,j\in N}$ s.t.$T_{A^{kj}}^{\mu }(k,s(k,j\left)\right)$ is bounded by a polynomial in $k,j$ and $|A^{kj}|$ is logarithmically bounded in $k,j$ but

$$|E_{{\mu }^k\times U^{s(k,j)}}\left[\right(f\left(x\right)-\alpha \left)A^{kj}\right(x,y\left)\right]|\notin \Delta$$

We can unite the $A^{kj}$ into a single $(poly,log)$-predictor scheme $\hat{A}$ by providing them as advice for a universal program. This contradicts the assumption on $(f,\mu )$.

Proof of Theorem 1

If ${\hat{P}}_{\alpha ,h}$ is a $\Delta (poly,log)$-optimal predictor scheme for $(f,\mu )$ then $(f,\mu )$ is $\Delta (poly,log)$-irreducible with expectation $\alpha$ by Lemma L.B.3.

Assume $(f,\mu )$ is $\Delta (poly,log)$-irreducible with expectation $\alpha$. Consider $\hat{Q}=(Q,r_Q,a_Q)$ any $Q\cap [-1,+1]$-valued $(poly,log)$-bischeme. By Lemma L.B.3, it is sufficient to prove that

$$|E_{{\mu }^k\times U^{r_Q(k,j)}}\left[\right({\hat{P}}_{\alpha ,h}-f\left)\hat{Q}\right]|\in \Delta$$

We have

$$|E_{{\mu }^k\times U^{r_Q(k,j)}}\left[\right({\hat{P}}_{\alpha ,h}-f\left)\hat{Q}\right]|=|E_{{\mu }^k\times U^{r_Q(k,j)}}\left[\right({\pi }^{kj}\left(\alpha \right)-f\left)\hat{Q}\right]|$$

$$|E_{{\mu }^k\times U^{r_Q(k,j)}}\left[\right({\hat{P}}_{\alpha ,h}-f\left)\hat{Q}\right]|\le |E_{{\mu }^k\times U^{r_Q(k,j)}}\left[\right(\alpha -f\left)\hat{Q}\right]|+h(k,j{)}^{-1}$$

$$|E_{{\mu }^k\times U^{r_Q(k,j)}}\left[\right({\hat{P}}_{\alpha ,h}-f\left)\hat{Q}\right]|\le |E_{{\mu }^k\times U^{r_Q(k,j)}}\left[\right(\alpha -f\left){\pi }^{kj}\right(\hat{Q}\left)\right]|+2h(k,j{)}^{-1}$$

$$|E_{{\mu }^k\times U^{r_Q(k,j)}}\left[\right({\hat{P}}_{\alpha ,h}-f\left)\hat{Q}\right]|\le |E_{{\mu }^k\times U^{r_Q(k,j)}}\left[\right(\alpha -f\left){\int }_0^1\theta \right(\hat{Q}-{\pi }^{kj}\left(t\right)\left)dt\right]|+2h(k,j{)}^{-1}$$

$$|E_{{\mu }^k\times U^{r_Q(k,j)}}\left[\right({\hat{P}}_{\alpha ,h}-f\left)\hat{Q}\right]|\le {\int }_0^1|E_{{\mu }^k\times U^{r_Q(k,j)}}\left[\right(\alpha -f\left)\theta \right(\hat{Q}-{\pi }^{kj}\left(t\right)\left)\right]|dt+2h(k,j{)}^{-1}$$

Applying Proposition 4 to $\theta (\hat{Q}-{\pi }^{kj}(t\left)\right)$, we conclude that there is $\delta \in \Delta$ s.t.

$$\forall t\in [0,1]:|E_{{\mu }^k\times U^{r_Q(k,j)}}\left[\right(\alpha -f\left)\theta \right(\hat{Q}-{\pi }^{kj}\left(t\right)\left)\right]|\le \delta (k,j)$$

Summing up

$$|E_{{\mu }^k\times U^{r_Q(k,j)}}\left[\right({\hat{P}}_{\alpha ,h}-f\left)\hat{Q}\right]|\le \delta (k,j)+2h(k,j{)}^{-1}$$

Proof of Corollary 1

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

Proposition 5

Fix $t:N\to N$. Assume $\delta :N^2\to R^{\ge 0}$ is bounded and $c,d>0$ are s.t.

$$\forall k:\forall j\le t\left(k\right):\delta (k,j{)}^d\le c{2}^{-k}\log (k+2\left)\right(\log (j+2){)}^2$$

Consider $d^{\prime }\ge d$. Then, there is $c^{\prime }>0$ s.t.

$$\forall k:\forall j\le t\left(k\right):\delta (k,j{)}^{d^{\prime }}\le c^{\prime }{2}^{-k}\log (k+2\left)\right(\log (j+2){)}^2$$

Proof of Proposition 5

$${\delta }^{d^{\prime }}\le (sup\delta {)}^{d^{\prime }-d}{\delta }^d$$

Proof of Proposition 1

The only not entirely obvious part is additivity. Consider ${\delta }_1,{\delta }_2\in {\Delta }_{G,t}^2$. Suppose $d_1,c_1,d_2,c_2\in R^{>0}$ are s.t.

$$\forall k:\forall j\le t\left(k\right):{\delta }_1(k,j{)}^{d_1}\le c_1{2}^{-k}\log (k+2\left)\right(\log (j+2){)}^2$$

$$\forall k:\forall j\le t\left(k\right):{\delta }_2(k,j{)}^{d_2}\le c_2{2}^{-k}\log (k+2\left)\right(\log (j+2){)}^2$$

For sufficiently large $d\in N$, $({\delta }_1+{\delta }_2{)}^d$ can be written as a sum of terms of the form ${\delta }_1^{d_1^{\prime }}{\delta }_2^{d_2^{\prime }}$ for $d_1^{\prime }\ge d_1$, $d_2^{\prime }\ge d_2$. Applying Proposition 5, we conclude that there is $c>0$ s.t.

$$\forall k:\forall j\le t\left(k\right):({\delta }_1+{\delta }_2{)}^d\le c{4}^{-k}(\log (k+2){)}^2\left(\log \right(j+2){)}^4$$

$$\forall k:\forall j\le t\left(k\right):({\delta }_1+{\delta }_2{)}^{\frac{d}{2}}\le c{2}^{-k}\log (k+2\left)\right(\log (j+2){)}^2$$

Proposition 6

For any $t:N\to N$, $n\in N$, $ϵ\in (0,2]$, $M>0$

$$min\left(2^{-k}\right(\log (k+2){)}^n\left(\log \right(j+2){)}^{2-ϵ},M)\in {\Delta }_{G,t}^2$$

Proof of Proposition 6

$$\left(2^{-k}\right(\log (k+2){)}^n\left(\log \right(j+2){)}^{2-ϵ}{)}^{\frac{2}{2-ϵ}}=(2^{-k}\left(\log \right(k+2\left){)}^n{)}^{\frac{2}{2-ϵ}}\right(\log (j+2){)}^2$$

Since $\frac{2}{2-ϵ}>1$ we can choose $c>0$ s.t. $\left(2^{-k}\right(\log (k+2){)}^n{)}^{\frac{2}{2-ϵ}}\le c{2}^{-k}$. We get

$$\left(2^{-k}\right(\log (k+2){)}^n\left(\log \right(j+2){)}^{2-ϵ}{)}^{\frac{2}{2-ϵ}}\le c{2}^{-k}(\log (j+2){)}^2$$

Proof of Theorem 2

Consider $\hat{A}=(A,r_A,a_A)$ a $\{0,1\}$-valued $(poly,log)$-bischeme. Define $\{W^{kj}:{\{0,1{\}}^{\ast }}^2\stackrel{alg}{\to }\{0,1\}{\}}_{k,j\in N}$ by

$$W^{kj}(x,y)=\{\begin{array}{cc}{\hat{A}}^{kj}(x,y_{\le r_A(k,j)})& \text{if}|x|=k\\ 0& \text{if}|x|\ne k\end{array}$$

Choose a polynomial $p:N\to N$ s.t.$W^{kj}(x,y)$ runs within time $p\left(t\right(|x|\left)\right)$ for $j\le t\left(k\right)$, $|x|\le k$ and $|y|=p\left(t\right(|x|\left)\right)$ and that $r_A(k,j)\le p\left(t\right(k\left)\right)$ for $j\le t\left(k\right)$. We have

$$\forall k:\forall j\le t\left(k\right):m_{W^{kj},p\left(t\right)}\left(k\right)\ge 3⟹|E_{U^{\le k}\times U^{p\left(t\right(k\left)\right)}}\left[f\right(x)\mid W^{kj}(x,y_{\le p\left(t\right(|x|\left)\right)})=1]-\alpha |\le \frac{c_p|W^{kj}|\sqrt{\log \log m_{W^{kj},p\left(t\right)}\left(k\right)}}{\sqrt{m_{W^{kj},p\left(t\right)}\left(k\right)}}$$

$$\forall k:\forall j\le t\left(k\right):m_{W^{kj},p\left(t\right)}\left(k\right)\ge 3⟹|E_{U^k\times U^{r_A(k,j)}}\left[f\right(x)\mid {\hat{A}}^{kj}(x,y)=1]-\alpha |\le \frac{\left(c_1\log \right(k+2)+c_2\log (j+2\left)\right)\sqrt{\log \log m_{W^{kj},p\left(t\right)}\left(k\right)}}{\sqrt{m_{W^{kj},p\left(t\right)}\left(k\right)}}$$

for some $c_1,c_2>0$. $m_{W^{kj},p\left(t\right)}\left(k\right)\le 2^{k+1}$ therefore

$$\forall k:\forall j\le t\left(k\right):m_{W^{kj},p\left(t\right)}\left(k\right)\ge 3⟹|E_{U^k\times U^{r_A(k,j)}}[f\mid {\hat{A}}^{kj}=1]-\alpha |\le \frac{\left(c_1\log \right(k+2)+c_2\log (j+2\left)\right)\sqrt{\log (k+1)}}{\sqrt{m_{W^{kj},p\left(t\right)}\left(k\right)}}$$

$$\forall k:\forall j\le t\left(k\right):m_{W^{kj},p\left(t\right)}\left(k\right)\ge 3⟹|E_{U^k\times U^{r_A(k,j)}}[f-\alpha \mid {\hat{A}}^{kj}=1]|\le \frac{\left(c_1\log \right(k+2)+c_2\log (j+2\left)\right)\sqrt{\log (k+1)}}{\sqrt{m_{W^{kj},p\left(t\right)}\left(k\right)}}$$

$$\forall k:\forall j\le t\left(k\right):m_{W^{kj},p\left(t\right)}\left(k\right)\ge 3⟹|E_{U^k\times U^{r_A(k,j)}}[f-\alpha \mid {\hat{A}}^{kj}=1]|\le \frac{\left(c_1\log \right(k+2)+c_2\log (j+2\left)\right)\sqrt{\log (k+1)}}{\sqrt{P{r}_{U^k\times U^{r_A(k,j)}}[{\hat{A}}^{kj}=1]2^k}}$$

$$\forall k:\forall j\le t\left(k\right):m_{W^{kj},p\left(t\right)}\left(k\right)\ge 3⟹\frac{|E_{U^k\times U^{r_A(k,j)}}\left[\right(f-\alpha \left){\hat{A}}^{kj}\right]|}{P{r}_{U^k\times U^{r_A(k,j)}}[{\hat{A}}^{kj}=1]}\le \frac{\left(c_1\log \right(k+2)+c_2\log (j+2\left)\right)\sqrt{\log (k+1)}}{\sqrt{P{r}_{U^k\times U^{r_A(k,j)}}[{\hat{A}}^{kj}=1]2^k}}$$

$$\forall k:\forall j\le t\left(k\right):m_{W^{kj},p\left(t\right)}\left(k\right)\ge 3⟹|E_{U^k\times U^{r_A(k,j)}}\left[\right(f-\alpha \left){\hat{A}}^{kj}\right]|\le \sqrt{P{r}_{U^k\times U^{r_A(k,j)}}[{\hat{A}}^{kj}=1]}\frac{\left(c_1\log \right(k+2)+c_2\log (j+2\left)\right)\sqrt{\log (k+1)}}{{\sqrt{2}}^k}$$

$$\forall k:\forall j\le t\left(k\right):m_{W^{kj},p\left(t\right)}\left(k\right)\ge 3⟹|E_{U^k\times U^{r_A(k,j)}}\left[\right(f-\alpha \left){\hat{A}}^{kj}\right]|\le \frac{\left(c_1\log \right(k+2)+c_2\log (j+2\left)\right)\sqrt{\log (k+1)}}{{\sqrt{2}}^k}$$

$$\forall k:\forall j\le t\left(k\right):m_{W^{kj},p\left(t\right)}\left(k\right)\ge 3⟹E_{U^k\times U^{r_A(k,j)}}\left[\right(f-\alpha ){\hat{A}}^{kj}{]}^2\le 2^{-k}(c_1\log (k+2)+c_2\log (j+2){)}^2\log (k+1)$$

On the other hand

$$\forall k:\forall j\le t\left(k\right):m_{W^{kj},p\left(t\right)}\left(k\right)<3⟹P{r}_{U^k\times U^{r_A(k,j)}}[{\hat{A}}^{kj}=1]2^k<3$$

$$\forall k:\forall j\le t\left(k\right):m_{W^{kj},p\left(t\right)}\left(k\right)<3⟹P{r}_{U^k\times U^{r_A(k,j)}}[{\hat{A}}^{kj}=1]<3\cdot 2^{-k}$$

$$\forall k:\forall j\le t\left(k\right):m_{W^{kj},p\left(t\right)}\left(k\right)<3⟹P{r}_{U^k\times U^{r_A(k,j)}}[{\hat{A}}^{kj}=1{]}^2<3\cdot 2^{-k}$$

$$\forall k:\forall j\le t\left(k\right):m_{W^{kj},p\left(t\right)}\left(k\right)<3⟹E_{U^k\times U^{r_A(k,j)}}\left[\right(f-\alpha ){\hat{A}}^{kj}{]}^2<3\cdot 2^{-k}$$

Combining the two cases

$$\forall k:\forall j\le t\left(k\right):E_{U^k\times U^{r_A(k,j)}}\left[\right(f-\alpha ){\hat{A}}^{kj}{]}^2\le 2^{-k}max(\left(c_1\log \right(k+2)+c_2\log (j+2\left){)}^2\log \right(k+1),3)$$

Using Proposition 6, we conclude that

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

Proof of Proposition 2

Proven exactly the same way as for ${\Delta }_{avg}^2$.

Proof of Proposition 3

Consider $\delta \in {\Delta }_{G,t_{\varphi }}^2$. Take $c,d>0$ s.t.

$$\forall k:\forall j\le t\left(k\right):\delta (k,j{)}^d\le c{2}^{-k}\log (k+2\left)\right(\log (j+2){)}^2$$

Given ${\varphi }^{\prime }\in \Phi$ s.t. ${\varphi }^{\prime }\le \varphi$, we have

$$\frac{\sum _{j=2}^{t_{{\varphi }^{\prime }}\left(k\right)-1}\left(\log \log \right(j+1)-\log \log j)\delta (k,j{)}^d}{\log \log t_{{\varphi }^{\prime }}\left(k\right)}\le \frac{\sum _{j=2}^{t_{{\varphi }^{\prime }}\left(k\right)-1}\left(\log \log \right(j+1)-\log \log j)c{2}^{-k}\log (k+2)\left(\log \right(j+2){)}^2}{\log \log t_{{\varphi }^{\prime }}\left(k\right)}$$

$$\frac{\sum _{j=2}^{t_{{\varphi }^{\prime }}\left(k\right)-1}\left(\log \log \right(j+1)-\log \log j)\delta (k,j{)}^d}{\log \log t_{{\varphi }^{\prime }}\left(k\right)}\le c{2}^{-k}\log (k+2)\frac{\sum _{j=2}^{t_{{\varphi }^{\prime }}\left(k\right)-1}\left(\log \log \right(j+1)-\log \log j)\left(\log \right(j+2){)}^2}{\log \log t_{{\varphi }^{\prime }}\left(k\right)}$$

$$\frac{\sum _{j=2}^{t_{{\varphi }^{\prime }}\left(k\right)-1}\left(\log \log \right(j+1)-\log \log j)\delta (k,j{)}^d}{\log \log t_{{\varphi }^{\prime }}\left(k\right)}\le c{2}^{-k}\log (k+2)\frac{\sum _{j=2}^{t_{{\varphi }^{\prime }}\left(k\right)-1}\left(\log \log \right(j+1)-\log \log j)\left(\log \right(t_{{\varphi }^{\prime }}\left(k\right)+1){)}^2}{\log \log t_{{\varphi }^{\prime }}\left(k\right)}$$

$$\frac{\sum _{j=2}^{t_{{\varphi }^{\prime }}\left(k\right)-1}\left(\log \log \right(j+1)-\log \log j)\delta (k,j{)}^d}{\log \log t_{{\varphi }^{\prime }}\left(k\right)}\le c{2}^{-k}\log (k+2)\left(\log \right(t_{{\varphi }^{\prime }}\left(k\right)+1){)}^2$$

$$\underset{k\to \infty }{lim}\frac{\sum _{j=2}^{t_{{\varphi }^{\prime }}\left(k\right)-1}\left(\log \log \right(j+1)-\log \log j)\delta (k,j{)}^d}{\log \log t_{{\varphi }^{\prime }}\left(k\right)}\le c\underset{k\to \infty }{lim}{2}^{-k}\log (k+2)\left(\log \right(t_{{\varphi }^{\prime }}\left(k\right)+1){)}^2$$

$$\underset{k\to \infty }{lim}\frac{\sum _{j=2}^{t_{{\varphi }^{\prime }}\left(k\right)-1}\left(\log \log \right(j+1)-\log \log j)\delta (k,j{)}^d}{\log \log t_{{\varphi }^{\prime }}\left(k\right)}\le c\underset{k\to \infty }{lim}{2}^{-k}\log (k+2)\left(\log t_{{\varphi }^{\prime }}\right(k){)}^2$$

$$\underset{k\to \infty }{lim}\frac{\sum _{j=2}^{t_{{\varphi }^{\prime }}\left(k\right)-1}\left(\log \log \right(j+1)-\log \log j)\delta (k,j{)}^d}{\log \log t_{{\varphi }^{\prime }}\left(k\right)}\le c\underset{k\to \infty }{lim}{2}^{-k}\log (k+2)(\log k{)}^{2{\varphi }^{\prime }\left(k\right)}$$

$$\underset{k\to \infty }{lim}\frac{\sum _{j=2}^{t_{{\varphi }^{\prime }}\left(k\right)-1}\left(\log \log \right(j+1)-\log \log j)\delta (k,j{)}^d}{\log \log t_{{\varphi }^{\prime }}\left(k\right)}\le c\underset{k\to \infty }{lim}{2}^{-k}(\log k{)}^{2{\varphi }^{\prime }\left(k\right)+1}$$

$$\underset{k\to \infty }{lim}\frac{\sum _{j=2}^{t_{{\varphi }^{\prime }}\left(k\right)-1}\left(\log \log \right(j+1)-\log \log j)\delta (k,j{)}^d}{\log \log t_{{\varphi }^{\prime }}\left(k\right)}=0$$

We conclude that ${\delta }^d\in {\Delta }_{avg,\varphi }^2$ and therefore $\delta \in {\Delta }_{avg,\varphi }^2$.

Proof of Corollary 2

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