User:IssaRice/Logical inductor construction

Notes from the Logical Induction paper as I walk through the construction of LIA in section 5.

Lemma 5.1.1 (Fixed Point Lemma)

The following is used in the Fixed Point Lemma (5.1.1):

Writing the $n$-strategy as

$T_n=\sum _{j=1}^k{\xi }_j{\varphi }_j-\sum _{j=1}^k{\xi }_j\underset{j}{\overset{*n}{\varphi }}$

we have

$\mathbb{V}(T_n({\mathbb{P}}_{\le n-1},\mathbb{V}))=\sum _{j=1}^k{\xi }_j({\mathbb{P}}_{\le n-1},\mathbb{V})\cdot \mathbb{V}({\varphi }_j)-\sum _{j=1}^k{\xi }_j({\mathbb{P}}_{\le n-1},\mathbb{V})\cdot \underset{j}{\overset{*n}{\varphi }}({\mathbb{P}}_{\le n-1},\mathbb{V})$

But $\underset{j}{\overset{*n}{\varphi }}({\mathbb{P}}_{\le n-1},\mathbb{V})=\mathbb{V}({\varphi }_j)$ so the two sums cancel to obtain $0$.

See also

• https://machinelearning.subwiki.org/wiki/User:IssaRice/Logical_induction_notation