TCSLib

243 Boolean Analysis — Normalized Sums

243.1 Overview

The multilinear polynomial for a normalized sum has degree one, equal coordinate influences, and unit variance in positive dimension. Moment-matched independent inputs admit quantitative Gaussian comparison against Lipschitz tests.

243.2 Declarations

Definition 243.1 Normalized-sum multilinear polynomial
✓

For \(n\ge 0\), define a multilinear coefficient family \(P_n\) on subsets of \(\{ 1,\ldots ,n\} \) by \(P_n(S)=1/\sqrt n\) when \(|S|=1\) and \(P_n(S)=0\) otherwise; division by zero is zero. Its evaluation is \(n^{-1/2}\sum _i z_i\).

Lemma 243.2 Degree of the normalized-sum polynomial
✓

For every \(n\ge 0\), the multilinear polynomial with singleton coefficients \(1/\sqrt n\) and all other coefficients zero has degree at most one.

Lemma 243.3 Influence of a normalized-sum coordinate
✓

For \(n\ge 0\) and a coordinate \(i\in \{ 1,\ldots ,n\} \), let \(f(x)=n^{-1/2}\sum _j(-1)^{x_j}\) on the uniform Boolean cube. Its influence \(\mathbb E(D_i f)^2\), with \(D_i\) the coordinate half-difference, equals \(1/n\).

Lemma 243.4 Variance of the normalized-sum polynomial
✓

If \(n\gt 0\) and \(f(x)=n^{-1/2}\sum _{i=1}^n(-1)^{x_i}\) on the uniform Boolean cube, then \(\operatorname {Var}(f)=1\).

Lemma 243.5 Evaluation at arbitrary random inputs
✓

Let \(n\ge 0\), let \(\Omega \) be a measurable space, and let \(X_i:\Omega \to \mathbb R\) be arbitrary functions. The multilinear polynomial with singleton coefficients \(1/\sqrt n\) and all other coefficients zero evaluates at \((X_i(\omega ))_i\) to \(\sum _iX_i(\omega )/\sqrt n\) for every \(\omega \in \Omega \), with division by zero equal to zero.

Lemma 243.6 Gaussian comparison for independent normalized sums
✓

There is a universal \(K\gt 0\) such that, for every \(n\gt 0\), probability space \((\Omega ,\mu )\), and independent real random variables \(X_1,\ldots ,X_n\) with finite fourth moments, \(\mathbb E X_i=\mathbb E X_i^3=0\), \(\mathbb E X_i^2=1\), and \(\mathbb E X_i^4\le 9\), every \(c\)-Lipschitz \(\psi :\mathbb R\to \mathbb R\) with \(c\ge 0\) satisfies \(|\mathbb E\psi (n^{-1/2}\sum _iX_i)-\mathbb E\psi (Z)|\le Kc\, n^{-1/4}\), where \(Z\) is standard Gaussian.

Lemma 243.7 Product integration equals cube expectation
✓

For every \(n\ge 0\) and \(f:\{ 0,1\} ^n\to \mathbb R\), integration against the product of \(n\) uniform bit measures equals the uniform cube expectation \(2^{-n}\sum _xf(x)\).

Lemma 243.8 Gaussian comparison for normalized Boolean sums
✓

There is a universal \(K\gt 0\) such that, for \(n\gt 0\), independent uniform signs \(\epsilon _1,\ldots ,\epsilon _n\), a standard Gaussian \(Z\), and any \(c\)-Lipschitz \(\psi :\mathbb R\to \mathbb R\) with \(c\ge 0\), \(|\mathbb E\psi (n^{-1/2}\sum _i\epsilon _i)-\mathbb E\psi (Z)|\le Kc\, n^{-1/4}\).

Lemma 243.9 Gaussian limit for normalized Boolean sums
✓

For every \(c\ge 0\) and \(c\)-Lipschitz \(\psi :\mathbb R\to \mathbb R\), if \(\epsilon _1,\ldots ,\epsilon _{m+1}\) are independent uniform signs and \(Z\) is standard Gaussian, then \(\mathbb E\psi ((m+1)^{-1/2}\sum _i\epsilon _i)\to \mathbb E\psi (Z)\) as \(m\to \infty \), where the first expectation is integration under the product sign law.

Lemma 243.10 Cube-expectation limit for normalized sums
✓

For every \(c\ge 0\) and \(c\)-Lipschitz \(\psi :\mathbb R\to \mathbb R\), \(2^{-(m+1)}\sum _{x\in \{ 0,1\} ^{m+1}}\psi ((m+1)^{-1/2}\sum _i(-1)^{x_i})\to \mathbb E\psi (Z)\) as \(m\to \infty \), where \(Z\) is standard Gaussian.