boofun.analysis.p_biased
P-biased Fourier analysis for Boolean functions.
This module implements Fourier analysis over p-biased product distributions, as described in O’Donnell’s “Analysis of Boolean Functions” Chapter 8.
In the standard (uniform) setting, inputs are drawn from {-1,+1}^n uniformly. In the p-biased setting, each coordinate is independently:
x_i = -1 with probability p x_i = +1 with probability 1-p
- The p-biased Fourier basis uses orthogonal polynomials called the:
φ_S^(p)(x) = ∏_{i∈S} φ^(p)(x_i)
- where φ^(p)(x) = (x - μ)/σ is the normalized basis function, with:
μ = E[x] = 1 - 2p σ = √Var(x) = 2√(p(1-p))
Key concepts: - p-biased measure μ_p: Pr[x_i = -1] = p, Pr[x_i = +1] = 1-p - p-biased inner product: ⟨f,g⟩_p = E_{x~μ_p}[f(x)g(x)] - p-biased Fourier coefficients: f̂(S)_p = ⟨f, φ_S^(p)⟩_p - p-noise operator T_{1-2ε}: smoothing towards the p-biased mean
Applications: - Analysis of Boolean functions under non-uniform input distributions - Sharp threshold phenomena (p → 0) - Monotone function analysis - Influence under biased distributions
Functions
|
Compute μ_p(x : x has 1s exactly at positions in subset_mask). |
|
Compute E_{μ_p}[f] - the expectation of f under p-biased measure. |
|
Compute the p-biased Fourier coefficients of f. |
|
Compute the p-biased influence of variable i on f. |
|
Compute the p-biased noise stability at correlation rho. |
|
Compute the total p-biased influence. |
|
Compute Var_{μ_p}[f] - the variance under p-biased measure. |
Classes
|
Comprehensive p-biased analysis for Boolean functions. |
- boofun.analysis.p_biased.p_biased_fourier_coefficients(f: BooleanFunction, p: float = 0.5) Dict[int, float][source]
Compute the p-biased Fourier coefficients of f.
- The p-biased Fourier expansion is:
f(x) = Σ_S f̂(S)_p φ_S^(p)(x)
where φ_S^(p)(x) = ∏_{i∈S} φ^(p)(x_i) and φ^(p)(x_i) = (x_i - μ)/σ.
- Parameters:
f – BooleanFunction to analyze
p – Bias parameter (default 0.5 = uniform)
- Returns:
Dictionary mapping subset masks to p-biased Fourier coefficients
- boofun.analysis.p_biased.p_biased_influence(f: BooleanFunction, i: int, p: float = 0.5) float[source]
Compute the p-biased influence of variable i on f.
- The p-biased influence is:
Inf_i^(p)[f] = E_{μ_p}[(D_i f)^2] = Σ_{S∋i} f̂(S)_p^2 / (p(1-p))
where D_i f(x) = (f(x^{(i→+1)}) - f(x^{(i→-1)})) / 2.
- Parameters:
f – BooleanFunction to analyze
i – Variable index
p – Bias parameter
- Returns:
p-biased influence of variable i
- boofun.analysis.p_biased.p_biased_total_influence(f: BooleanFunction, p: float = 0.5) float[source]
Compute the total p-biased influence.
I^(p)[f] = Σ_i Inf_i^(p)[f]
- Parameters:
f – BooleanFunction to analyze
p – Bias parameter
- Returns:
Total p-biased influence
- boofun.analysis.p_biased.p_biased_noise_stability(f: BooleanFunction, rho: float, p: float = 0.5) float[source]
Compute the p-biased noise stability at correlation rho.
Stab_ρ^(p)[f] = E[f(x)f(y)] where (x,y) are ρ-correlated under μ_p
- Parameters:
f – BooleanFunction to analyze
rho – Noise correlation parameter in [-1, 1]
p – Bias parameter
- Returns:
p-biased noise stability
- boofun.analysis.p_biased.p_biased_expectation(f: BooleanFunction, p: float = 0.5) float[source]
Compute E_{μ_p}[f] - the expectation of f under p-biased measure.
- Parameters:
f – BooleanFunction (in ±1 convention, or converted)
p – Bias parameter
- Returns:
Expected value of f under p-biased distribution
- boofun.analysis.p_biased.p_biased_variance(f: BooleanFunction, p: float = 0.5) float[source]
Compute Var_{μ_p}[f] - the variance under p-biased measure.
- Parameters:
f – BooleanFunction
p – Bias parameter
- Returns:
Variance of f under p-biased distribution
- boofun.analysis.p_biased.biased_measure_mass(p: float, n: int, subset_mask: int) float[source]
Compute μ_p(x : x has 1s exactly at positions in subset_mask).
- Parameters:
p – Bias parameter (Pr[x_i = -1] = p)
n – Number of variables
subset_mask – Bitmask of positions that should be -1
- Returns:
Probability mass under the p-biased measure
- class boofun.analysis.p_biased.PBiasedAnalyzer(f: BooleanFunction, p: float = 0.5)[source]
Comprehensive p-biased analysis for Boolean functions.
This class provides caching and convenient methods for analyzing Boolean functions under p-biased distributions.
- __init__(f: BooleanFunction, p: float = 0.5)[source]
Initialize p-biased analyzer.
- Parameters:
f – BooleanFunction to analyze
p – Bias parameter