boofun.analysis.gaussian
Gaussian analysis of Boolean functions (O’Donnell Chapter 10).
This module implements the connection between Boolean functions and Gaussian space, which is fundamental for understanding the behavior of Boolean functions under noise and for proving central limit-type theorems.
Key concepts: - Hermite polynomials: The Gaussian analog of Fourier characters - Gaussian noise stability: Stability under correlated Gaussian noise - Ornstein-Uhlenbeck operator: The Gaussian analog of the noise operator - Central Limit Theorem for Boolean functions
The connection to Gaussians allows us to: 1. Understand the “typical” behavior of low-degree Boolean functions 2. Prove hypercontractivity results 3. Apply invariance principles (connecting discrete and continuous)
Mathematical background: - Standard Gaussian space: (ℝ^n, γ_n) where γ_n is the n-dimensional Gaussian - Hermite polynomials H_k(x) form an orthonormal basis for L^2(ℝ, γ) - The Hermite expansion generalizes Fourier expansion to Gaussians
References: - O’Donnell, “Analysis of Boolean Functions”, Chapter 10 - Mossel, O’Donnell, Oleszkiewicz, “Noise stability of functions with low influences”
Functions
Compute the Berry-Esseen bound for the CLT approximation of f. |
|
|
Estimate how well f's distribution is approximated by a Gaussian. |
|
Compute the Gaussian inner product ⟨f, g⟩_γ. |
|
Compute the Gaussian noise sensitivity: 1 - Stab_ρ[f]. |
|
Compute the Gaussian noise stability of f at correlation rho. |
Compute the Hermite expansion of the multilinear extension of f. |
|
|
Return the nth Hermite polynomial. |
Return the multilinear extension of f. |
|
|
Apply the Ornstein-Uhlenbeck (noise) operator T_ρ to f. |
|
Evaluate the nth physicist's Hermite polynomial at x. |
|
Evaluate the nth probabilist's Hermite polynomial at x. |
Classes
Comprehensive Gaussian analysis for Boolean functions. |
- boofun.analysis.gaussian.hermite_polynomial(n: int, variant: str = 'probabilist') Callable[[float], float][source]
Return the nth Hermite polynomial.
There are two common normalizations: - Probabilist’s: He_n(x) where E[He_n(X) He_m(X)] = δ_{nm} for X ~ N(0,1) - Physicist’s: H_n(x) with different normalization
- The probabilist’s Hermite polynomials satisfy:
He_0(x) = 1 He_1(x) = x He_n(x) = x * He_{n-1}(x) - (n-1) * He_{n-2}(x)
- Parameters:
n – Degree of the polynomial
variant – “probabilist” or “physicist”
- Returns:
Function computing He_n(x) or H_n(x)
- boofun.analysis.gaussian.hermite_coefficients(f: BooleanFunction) Dict[Tuple[int, ...], float][source]
Compute the Hermite expansion of the multilinear extension of f.
For a Boolean function f: {-1,1}^n → ℝ, the multilinear extension p(x) has a Hermite expansion:
p(x) = Σ_α ĥ_α H_α(x)
where H_α(x) = ∏_i H_{α_i}(x_i).
- For multilinear polynomials (degree 1 in each variable):
ĥ_S = f̂(S) for |S| = k (Fourier = Hermite for multilinear)
- Parameters:
f – BooleanFunction to analyze
- Returns:
Dictionary mapping multi-indices to Hermite coefficients
- boofun.analysis.gaussian.probabilists_hermite(n: int, x: float) float[source]
Evaluate the nth probabilist’s Hermite polynomial at x.
The probabilist’s Hermite polynomials are orthonormal under the standard Gaussian measure: E[He_n(X) He_m(X)] = δ_{nm} for X ~ N(0,1).
Uses the recurrence: He_n(x) = x * He_{n-1}(x) - (n-1) * He_{n-2}(x)
- Parameters:
n – Degree
x – Point to evaluate
- Returns:
He_n(x)
- boofun.analysis.gaussian.physicists_hermite(n: int, x: float) float[source]
Evaluate the nth physicist’s Hermite polynomial at x.
- The physicist’s normalization satisfies:
H_n(x) = (-1)^n e^{x^2} d^n/dx^n e^{-x^2}
Recurrence: H_n(x) = 2x * H_{n-1}(x) - 2(n-1) * H_{n-2}(x)
- Parameters:
n – Degree
x – Point to evaluate
- Returns:
H_n(x)
- boofun.analysis.gaussian.gaussian_noise_stability(f: BooleanFunction, rho: float) float[source]
Compute the Gaussian noise stability of f at correlation rho.
- The Gaussian noise stability is:
Stab_ρ[f] = E_{(x,y) ρ-correlated Gaussians}[f̃(x) f̃(y)]
where f̃ is the multilinear extension of f.
- For the discrete case, this equals the standard noise stability:
Stab_ρ[f] = Σ_S ρ^|S| f̂(S)²
- Parameters:
f – BooleanFunction to analyze
rho – Correlation parameter in [-1, 1]
- Returns:
Gaussian noise stability
- boofun.analysis.gaussian.ornstein_uhlenbeck_operator(f: BooleanFunction, rho: float) np.ndarray[source]
Apply the Ornstein-Uhlenbeck (noise) operator T_ρ to f.
- The O-U operator is defined as:
(T_ρ f)(x) = E_y[f(y)] where y_i = ρ x_i + sqrt(1-ρ²) z_i
and z_i are independent standard Gaussians.
In Fourier domain: (T_ρ f)^(S) = ρ^|S| f̂(S)
- Parameters:
f – BooleanFunction to apply operator to
rho – Noise parameter
- Returns:
Truth table of T_ρ f (as real values, not Boolean)
- boofun.analysis.gaussian.gaussian_noise_sensitivity(f: BooleanFunction, rho: float) float[source]
Compute the Gaussian noise sensitivity: 1 - Stab_ρ[f].
This measures how much the function changes under Gaussian noise.
- Parameters:
f – BooleanFunction to analyze
rho – Correlation parameter
- Returns:
Gaussian noise sensitivity
- boofun.analysis.gaussian.berry_esseen_bound(f: BooleanFunction) float[source]
Compute the Berry-Esseen bound for the CLT approximation of f.
For a Boolean function f with low influences, the distribution of f(x) for random x approaches Gaussian. The Berry-Esseen theorem quantifies this:
sup_t |Pr[f(x) <= t] - Φ(t)| <= C * Σ_i Inf_i[f]^3 / Var[f]^{3/2}
where Φ is the standard normal CDF.
- Parameters:
f – BooleanFunction to analyze
- Returns:
Berry-Esseen bound (smaller = better Gaussian approximation)
- boofun.analysis.gaussian.clt_approximation(f: BooleanFunction, num_samples: int = 10000) Tuple[float, float][source]
Estimate how well f’s distribution is approximated by a Gaussian.
Uses Monte Carlo sampling to estimate the mean and variance of f, then computes the Kolmogorov-Smirnov distance to a Gaussian.
- Parameters:
f – BooleanFunction to analyze
num_samples – Number of random samples
- Returns:
Tuple of (mean, variance) of f’s distribution
- boofun.analysis.gaussian.gaussian_inner_product(f: BooleanFunction, g: BooleanFunction) float[source]
Compute the Gaussian inner product ⟨f, g⟩_γ.
- For the discrete case with ±1 values, this equals:
⟨f, g⟩_γ = E[f(x)g(x)] = Σ_S f̂(S) ĝ(S)
(Plancherel’s theorem)
- Parameters:
f – BooleanFunctions to compute inner product of
g – BooleanFunctions to compute inner product of
- Returns:
Gaussian inner product
- boofun.analysis.gaussian.multilinear_extension(f: BooleanFunction) Callable[[np.ndarray], float][source]
Return the multilinear extension of f.
The multilinear extension p: ℝ^n → ℝ is the unique multilinear polynomial that agrees with f on {-1, 1}^n:
p(x) = Σ_S f̂(S) ∏_{i∈S} x_i
This extends f from the Boolean hypercube to all of ℝ^n.
- Parameters:
f – BooleanFunction to extend
- Returns:
Function computing p(x) for any x ∈ ℝ^n
- class boofun.analysis.gaussian.GaussianAnalyzer(f: BooleanFunction)[source]
Comprehensive Gaussian analysis for Boolean functions.
Provides methods for analyzing Boolean functions in the context of Gaussian space and central limit theorems.
- __init__(f: BooleanFunction)[source]
Initialize Gaussian analyzer.
- Parameters:
f – BooleanFunction to analyze
- is_approximately_gaussian(threshold: float = 0.1) bool[source]
Check if f’s distribution is approximately Gaussian.
Uses the Berry-Esseen bound to check if the function has low enough influences to be well-approximated by a Gaussian.
- Parameters:
threshold – Maximum Berry-Esseen bound for “Gaussian”
- Returns:
True if distribution is approximately Gaussian