287 Boolean Analysis — Basic
287.1 Overview
Finite probability products are equipped with coordinate conditional expectations, an orthogonal decomposition, noise operators, and influences. The probability weights may differ between coordinates and are strictly positive.
287.2 Declarations
For a finite set \(S\) and a real function \(g\) on finite subsets of an ambient set, define \(E_S(g)=\sum _{A,B\subseteq S}(-1)^{|S|-|A|}(-1)^{|S|-|B|}g(A\cap B)\).
For a finite set \(S\), an element \(i\notin S\), and a real function \(g\) on finite subsets, put \(E_T(g)=\sum _{A,B\subseteq T}(-1)^{|T|-|A|}(-1)^{|T|-|B|}g(A\cap B)\). Then \(E_{S\cup \{ i\} }(g)=E_S(T\mapsto g(T\cup \{ i\} ))-E_S(g)\).
For a finite set \(U\) and a real function \(g\) on finite subsets, put \(E_S(g)=\sum _{A,B\subseteq S}(-1)^{|S|-|A|}(-1)^{|S|-|B|}g(A\cap B)\). Then \(\sum _{S\subseteq U}E_S(g)=g(U)\).
For every \(n\in \mathbb N\), a finite probability product consists of finite sets \(\Omega _i\) for \(i\in \{ 0,\ldots ,n-1\} \) and real weights \(w_i(a)\gt 0\) satisfying \(\sum _{a\in \Omega _i}w_i(a)=1\). The coordinate sets and weights may depend on \(i\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\). Its outcome space is \(\Omega =\prod _{i=0}^{n-1}\Omega _i\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), with coordinate weights \(w_i\). The mass of \(x\in \prod _i\Omega _i\) is \(m(x)=\prod _iw_i(x_i)\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), with product masses \(m(x)\). For \(f:\prod _i\Omega _i\to \mathbb R\), define \(\mathbb E_Pf=\sum _xm(x)f(x)\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\) and let \(A\) be an event in its outcome space. Its indicator \(\mathbf1_A\) equals \(1\) on \(A\) and \(0\) elsewhere.
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\) and let \(A\) be an event in its outcome space. Define \(\Pr _P(A)=\mathbb E_P\mathbf1_A\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), \(q\in \mathbb R\), and \(f:\prod _i\Omega _i\to \mathbb R\). Define \(\| f\| _{q,P}=(\mathbb E_P|f|^q)^{1/q}\) using real powers and division; for \(q\gt 0\) this is the usual moment expression.
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\) and \(f:\prod _i\Omega _i\to \mathbb R\). Define \(\operatorname {Var}_P(f)=\mathbb E_P(f-\mathbb E_Pf)^2\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), \(S\subseteq \{ 0,\ldots ,n-1\} \), and \(f:\prod _i\Omega _i\to \mathbb R\). Say that \(f\) depends only on \(S\) if \(f(x)=f(y)\) whenever \(x_i=y_i\) for every \(i\in S\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), \(S\subseteq \{ 0,\ldots ,n-1\} \), and \(f:\prod _i\Omega _i\to \mathbb R\). Define \(E_Sf(x)=\mathbb E_{Y\sim P}f(z)\), where \(z_i=x_i\) for \(i\in S\) and \(z_i=Y_i\) otherwise.
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), \(S\subseteq \{ 0,\ldots ,n-1\} \), and \(f:\prod _i\Omega _i\to \mathbb R\). Its \(S\)-component is \(f_S=\sum _{T\subseteq S}(-1)^{|S|-|T|}E_Tf\), where \(E_T\) conditions on the coordinates in \(T\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), \(k\in \mathbb N\), and \(f:\prod _i\Omega _i\to \mathbb R\). The predicate that \(f\) has degree at most \(k\) means that every orthogonal component \(f_S\) with \(|S|\gt k\) vanishes identically.
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), \(k\in \mathbb N\), and \(f:\prod _i\Omega _i\to \mathbb R\). Define \(f^{\le k}(x)=\sum _{|S|\le k}f_S(x)\), where \(f_S\) is the orthogonal component indexed by \(S\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), \(\rho \in \mathbb R\), and \(f:\prod _i\Omega _i\to \mathbb R\). Define \(T_\rho f(x)=\sum _S\rho ^{|S|}f_S(x)\), where \(f_S\) are the orthogonal components and the powers have natural exponents.
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), a coordinate \(i\), and \(f:\prod _j\Omega _j\to \mathbb R\). Define \(L_if=f-E_{[n]\setminus \{ i\} }f\), where \(E_S\) conditions on the coordinates in \(S\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), a coordinate \(i\), and \(f:\prod _j\Omega _j\to \mathbb R\). Define \(I_i(f)=\mathbb E_P(L_if)^2\), where \(L_if\) subtracts the conditional expectation over coordinate \(i\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\) and \(f:\prod _i\Omega _i\to \mathbb R\). Define \(I(f)=\sum _{i=0}^{n-1}I_i(f)\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), \(\rho \in \mathbb R\), a coordinate \(i\), and \(f:\prod _j\Omega _j\to \mathbb R\). Define \(I_i^{(\rho )}(f)=\sum _{S\ni i}\rho ^{|S|-1}\mathbb E_Pf_S^2\), with natural exponents, including \(\rho =0\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), \(\rho \in \mathbb R\), and \(f:\prod _i\Omega _i\to \mathbb R\). Define \(\operatorname {Stab}_\rho (f)=\mathbb E_P[fT_\rho f]\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\) with coordinate weights \(w_i\) and let \(\lambda \in \mathbb R\). The atom lower bound \(\lambda \) means that \(\lambda \le w_i(a)\) for every coordinate \(i\) and outcome \(a\in \Omega _i\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\) and \(f:\prod _i\Omega _i\to \mathbb R\). The Boolean-valued predicate means \(f(x)\in \{ -1,1\} \) at every outcome \(x\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), with product masses \(m(x)\). Then \(\sum _xm(x)=1\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), \(S\subseteq [n]\), and \(F:\Omega \times \Omega \to \mathbb R\), where \(\Omega =\prod _i\Omega _i\). For independent \(X,Y\sim P\), let \(X\mathbin {\star _S}Y\) keep \(X_i\) on \(S\) and \(Y_i\) elsewhere; then \(\mathbb E F(X\mathbin {\star _S}Y,Y\mathbin {\star _S}X)=\mathbb EF(X,Y)\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\) and \(c\in \mathbb R\). Then \(\mathbb E_P[c]=c\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), let \(s\) be a finite index set, and let \(a_j\in \mathbb R\) and \(F_j:\Omega \to \mathbb R\). Then \(\mathbb E_P\sum _{j\in s}a_jF_j=\sum _{j\in s}a_j\mathbb E_PF_j\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), \(S,T\subseteq [n]\), \(f:\Omega \to \mathbb R\), and \(x\in \Omega \). For coordinate conditional expectations, \(E_S(E_Tf)(x)=E_{S\cap T}f(x)\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), \(S\subseteq [n]\), and \(f,g:\Omega \to \mathbb R\). For conditional expectation \(E_S\) onto \(S\), \(\mathbb E_P[fE_Sg]=\mathbb E_P[(E_Sf)g]\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), a finite index set \(s\), and functions \(F_j:\Omega \to \mathbb R\). Then \(\mathbb E_P\sum _{j\in s}F_j=\sum _{j\in s}\mathbb E_PF_j\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), \(a\in \mathbb R\), and \(f:\Omega \to \mathbb R\). Then \(\mathbb E_P[af]=a\mathbb E_Pf\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\) and \(f:\Omega \to \mathbb R\) with orthogonal components \(f_S\). Then \(\mathbb E_Pf^2=\sum _{S\subseteq [n]}\mathbb E_Pf_S^2\).
Let \(P\) be a product of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), \(J\subseteq [n]\), and functions \(f,h:\Omega \to \mathbb R\). If \(f\) takes values in \(\{ -1,1\} \) and \(h\) depends only on \(J\), there exists \(g:\Omega \to \{ -1,1\} \) depending only on \(J\) such that \(\Pr _P(f\ne g)\le \mathbb E_P(f-h)^2\).