TCSLib

235 Boolean Analysis — Invariance

235.1 Overview

Fourth-order invariance compares independent input laws through squared influences, with variance-normalized smooth and Lipschitz consequences.

235.2 Declarations

Theorem 235.1 Fourth-order invariance principle
✓

Let \(F(x)=\sum _{S\subseteq \{ 1,\ldots ,n\} }a_S\prod _{i\in S}x_i\) be a real multilinear polynomial of degree at most \(k\); let \(I_i(F)=\sum _{S\ni i}a_S^2\). Let \(X=(X_i)\) and \(Y=(Y_i)\) be families of independent real inputs on probability spaces \((\Omega ,\mu )\) and \((\Xi ,\nu )\), respectively. Each input is measurable up to a null set, has finite fourth absolute moment, and has first, second, and third moments \(0,1,0\) and fourth moment at most \(9\). If \(\psi \colon \mathbb R\to \mathbb R\) is \(C^4\) and \(C\ge 0\) satisfies \(|\psi ^{(4)}(t)|\le C\) for every \(t\), then \(|\mathbb E_\mu \psi (F(X))-\mathbb E_\nu \psi (F(Y))|\le (C/12)9^k\sum _i I_i(F)^2\).

Theorem 235.2 Smooth invariance under small influences
✓

Let \(F(x)=\sum _{S\subseteq \{ 1,\ldots ,n\} }a_S\prod _{i\in S}x_i\) be a real multilinear polynomial of degree at most \(k\); let \(I_i(F)=\sum _{S\ni i}a_S^2\). Let \(X=(X_i)\) and \(Y=(Y_i)\) be families of independent real inputs on probability spaces \((\Omega ,\mu )\) and \((\Xi ,\nu )\), respectively. Each input is measurable up to a null set, has finite fourth absolute moment, and has first, second, and third moments \(0,1,0\) and fourth moment at most \(9\). Suppose \(\sum _{S\ne \varnothing }a_S^2\le 1\), \(\varepsilon \ge 0\), and \(I_i(F)\le \varepsilon \) for every \(i\). If \(\psi \in C^4(\mathbb R)\) and \(C\ge 0\) bounds \(|\psi ^{(4)}|\) everywhere, then \(|\mathbb E_\mu \psi (F(X))-\mathbb E_\nu \psi (F(Y))|\le (C/12)k9^k\varepsilon \).

Theorem 235.3 Exponential bound on the degree factor
✓

For every integer \(k\ge 0\), the real-number inequality \(k9^k\le 16^k\) holds.

Theorem 235.4 Fourth root of the invariance scale
✓

For every integer \(k\ge 0\) and real \(\varepsilon \ge 0\), the inequality \((k9^k\varepsilon )^{1/4}\le 2^k\varepsilon ^{1/4}\) holds.

Theorem 235.5 Universal Lipschitz invariance estimate
✓

There exists a universal real constant \(K\gt 0\) with the following property. Let \(F(x)=\sum _{S\subseteq \{ 1,\ldots ,n\} }a_S\prod _{i\in S}x_i\) be a real multilinear polynomial of degree at most \(k\); let \(I_i(F)=\sum _{S\ni i}a_S^2\). Let \(X=(X_i)\) and \(Y=(Y_i)\) be families of independent real inputs on probability spaces \((\Omega ,\mu )\) and \((\Xi ,\nu )\), respectively. Each input is measurable up to a null set, has finite fourth absolute moment, and has first, second, and third moments \(0,1,0\) and fourth moment at most \(9\). If \(\sum _{S\ne \varnothing }a_S^2\le 1\), \(\varepsilon \ge 0\), \(I_i(F)\le \varepsilon \) for every \(i\), and \(\psi \colon \mathbb R\to \mathbb R\) is \(c\)-Lipschitz with \(c\ge 0\), then \(|\mathbb E_\mu \psi (F(X))-\mathbb E_\nu \psi (F(Y))|\le Kc2^k\varepsilon ^{1/4}\).