TCSLib

312 Boolean Analysis — Contraction

312.1 Overview

Coordinate noise admits a negative contraction rate depending only on its exponent. Positive and negative coordinate contractions combine into contraction for anisotropic noise with independent signs.

312.2 Declarations

Theorem 312.1 Negative coordinate noise contraction
✓

For every \(q\ge 2\) there exists \(0\lt c\le 1\), with \(c=2/5\) if \(q=4\), such that for every product \(P\) of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), every coordinate \(i\), and every real function \(f\) on its outcome space, \(\| N_{i,-c}f\| _{q,P}\le \| f\| _{q,P}\). For a real function \(h\) on \(\Omega \), use \(E_Uh(x)=\mathbb E_P[h(X)\mid X_U=x_U]\) for \(X\sim P\) and \(U\subseteq [n]\); \(\| h\| _{p,P}=(\mathbb E_P|h|^p)^{1/p}\) for \(p\gt 0\); \(N_{i,a}h=E_{[n]\setminus \{ i\} }h+a(h-E_{[n]\setminus \{ i\} }h)\).

Theorem 312.2 Self-adjoint coordinate noise
✓

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\), \(\rho \in \mathbb R\), and \(f,g:\Omega \to \mathbb R\). Then \(\mathbb E_P[(N_{i,\rho }f)g]=\mathbb E_P[fN_{i,\rho }g]\). For a real function \(h\) on \(\Omega \), use \(E_Uh(x)=\mathbb E_P[h(X)\mid X_U=x_U]\) for \(X\sim P\) and \(U\subseteq [n]\); \(N_{i,a}h=E_{[n]\setminus \{ i\} }h+a(h-E_{[n]\setminus \{ i\} }h)\).

Theorem 312.3 Positive coordinate noise contraction
✓

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\), \(0\le \rho \le 1\), \(q\ge 1\), and \(f:\Omega \to \mathbb R\). Then \(\| N_{i,\rho }f\| _{q,P}\le \| f\| _{q,P}\). For a real function \(h\) on \(\Omega \), use \(E_Uh(x)=\mathbb E_P[h(X)\mid X_U=x_U]\) for \(X\sim P\) and \(U\subseteq [n]\); \(\| h\| _{p,P}=(\mathbb E_P|h|^p)^{1/p}\) for \(p\gt 0\); \(N_{i,a}h=E_{[n]\setminus \{ i\} }h+a(h-E_{[n]\setminus \{ i\} }h)\).

Theorem 312.4 Negative contraction for all exponents
✓

For every \(q\gt 1\) there exists \(0\lt c\le 1\), with \(c=2/5\) when \(q\in \{ 4,4/3\} \), such that every product \(P\) of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\) satisfies \(\| N_{i,-c}f\| _{q,P}\le \| f\| _{q,P}\) for every coordinate \(i\) and real function \(f\). For a real function \(h\) on \(\Omega \), use \(E_Uh(x)=\mathbb E_P[h(X)\mid X_U=x_U]\) for \(X\sim P\) and \(U\subseteq [n]\); \(\| h\| _{p,P}=(\mathbb E_P|h|^p)^{1/p}\) for \(p\gt 0\); \(N_{i,a}h=E_{[n]\setminus \{ i\} }h+a(h-E_{[n]\setminus \{ i\} }h)\).

Definition 312.5 Partial anisotropic noise
✓

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]\), rates \(r_i\in \mathbb R\), and \(f:\Omega \to \mathbb R\). Define \(T_{J,\boldsymbol r}f(x)=\sum _S(\prod _{j\in S\cap J}r_j)f_S(x)\). For a real function \(h\) on \(\Omega \), use \(E_Uh(x)=\mathbb E_P[h(X)\mid X_U=x_U]\) for \(X\sim P\) and \(U\subseteq [n]\); \(h_S=\sum _{U\subseteq S}(-1)^{|S|-|U|}E_Uh\) for \(S\subseteq [n]\) (the Hoeffding–Efron–Stein components).

Theorem 312.6 Inserting a partial-noise coordinate
✓

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]\), rates \(r_i\in \mathbb R\), \(i\notin J\), and \(f:\Omega \to \mathbb R\). For \(T_{J,\boldsymbol r}f=\sum _S(\prod _{j\in S\cap J}r_j)f_S\), \(T_{J\cup \{ i\} ,\boldsymbol r}f=N_{i,r_i}(T_{J,\boldsymbol r}f)\). For a real function \(h\) on \(\Omega \), use \(E_Uh(x)=\mathbb E_P[h(X)\mid X_U=x_U]\) for \(X\sim P\) and \(U\subseteq [n]\); \(h_S=\sum _{U\subseteq S}(-1)^{|S|-|U|}E_Uh\) for \(S\subseteq [n]\) (the Hoeffding–Efron–Stein components); \(N_{i,a}h=E_{[n]\setminus \{ i\} }h+a(h-E_{[n]\setminus \{ i\} }h)\).

Theorem 312.7 Anisotropic contraction from coordinate bounds
✓

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 rates \(r_i\in \mathbb R\). If \(\| N_{i,r_i}g\| _{q,P}\le \| g\| _{q,P}\) for every coordinate \(i\) and every real \(g:\Omega \to \mathbb R\), then \(\| T_{\boldsymbol r}f\| _{q,P}\le \| f\| _{q,P}\) for every real \(f\). For a real function \(h\) on \(\Omega \), use \(E_Uh(x)=\mathbb E_P[h(X)\mid X_U=x_U]\) for \(X\sim P\) and \(U\subseteq [n]\); \(h_S=\sum _{U\subseteq S}(-1)^{|S|-|U|}E_Uh\) for \(S\subseteq [n]\) (the Hoeffding–Efron–Stein components); \(T_{\boldsymbol s}h=\sum _{S\subseteq [n]}(\prod _{i\in S}s_i)h_S\) for real coordinate rates \(s_i\); \(N_{i,a}h=E_{[n]\setminus \{ i\} }h+a(h-E_{[n]\setminus \{ i\} }h)\); \(\| h\| _{q,P}:=(\mathbb E_P|h|^q)^{1/q}\) as a totalized moment expression for every real \(q\), with \(1/0=0\), \(0^0=1\), and \(0^b=0\) for \(b\ne 0\).

Theorem 312.8 Independent signed rates decrease norms
✓

For every \(q\gt 1\) there exists \(0\lt c\le 1\), with \(c=2/5\) when \(q\in \{ 4,4/3\} \), such that for every product \(P\) of \(n\) finite probability spaces with strictly positive atom masses and outcome space \(\Omega =\prod _i\Omega _i\), every sign vector \(s\in \{ -1,1\} ^n\), and every real \(f\) on its outcome space, \(\| T_{c\boldsymbol s}f\| _{q,P}\le \| f\| _{q,P}\). For a real function \(h\) on \(\Omega \), use \(E_Uh(x)=\mathbb E_P[h(X)\mid X_U=x_U]\) for \(X\sim P\) and \(U\subseteq [n]\); \(h_S=\sum _{U\subseteq S}(-1)^{|S|-|U|}E_Uh\) for \(S\subseteq [n]\) (the Hoeffding–Efron–Stein components); \(\| h\| _{p,P}=(\mathbb E_P|h|^p)^{1/p}\) for \(p\gt 0\); \(T_{\boldsymbol s}h=\sum _{S\subseteq [n]}(\prod _{i\in S}s_i)h_S\) for real coordinate rates \(s_i\).