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

biased_measure_mass(p, n, subset_mask)	Compute μ_p(x : x has 1s exactly at positions in subset_mask).
p_biased_average_sensitivity(f[, p])	Compute the average sensitivity under p-biased distribution μ_p.
p_biased_expectation(f[, p])	Compute E_{μ_p}[f] - the expectation of f under p-biased measure.
p_biased_fourier_coefficient(f, p, S)	Compute single p-biased Fourier coefficient using Tal's formula.
p_biased_fourier_coefficients(f[, p])	Compute the p-biased Fourier coefficients of f.
p_biased_influence(f, i[, p])	Compute the p-biased influence of variable i on f.
p_biased_noise_stability(f, rho[, p])	Compute the p-biased noise stability at correlation rho.
p_biased_sensitivity(f, x[, p])	Compute the sensitivity of f at input x.
p_biased_total_influence(f[, p])	Compute the total p-biased influence.
p_biased_total_influence_fourier(f[, p])	Compute total p-biased influence via Fourier coefficients.
p_biased_variance(f[, p])	Compute Var_{μ_p}[f] - the variance under p-biased measure.
parity_biased_coefficient(n, k, i)	Compute the p-biased Fourier coefficient of the parity function.

Classes

PBiasedAnalyzer(f[, p])

Comprehensive p-biased analysis for Boolean functions.

boofun.analysis.p_biased.p_biased_fourier_coefficients(f: BooleanFunction, p: float = 0.5) → Dict[int, float]

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_fourier_coefficient(f: BooleanFunction, p: float, S: int) → float

Compute single p-biased Fourier coefficient using Tal’s formula.

This is an alternative (and often faster) formula for computing individual p-biased Fourier coefficients. Uses the explicit basis:

φ_S^(p)(x) = ∏_{i∈S} φ^(p)(x_i)

where φ^(p)(x_i) = -√(q/p) if x_i = -1, else √(p/q) (with q = 1-p)

This formula is from Tal’s FourierCoefMuP function.

Parameters:

• f – BooleanFunction to analyze

• p – Bias parameter in (0, 1)

• S – Subset mask (integer with bits indicating which variables)

Returns:

The p-biased Fourier coefficient f̂(S)_p

References

• Tal’s BooleanFunc.py: FourierCoefMuP

• O’Donnell Chapter 8

boofun.analysis.p_biased.p_biased_influence(f: BooleanFunction, i: int, p: float = 0.5) → float

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

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

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

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

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

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

boofun.analysis.p_biased.p_biased_sensitivity(f: BooleanFunction, x: int, p: float = 0.5) → int

Compute the sensitivity of f at input x.

This is the same as standard sensitivity (number of sensitive coordinates), independent of p. Included for API consistency with p_biased_average_sensitivity.

Parameters:

• f – BooleanFunction to analyze

• x – Input point (integer)

• p – Bias parameter (not used, for API consistency)

Returns:

Number of coordinates i where f(x) ≠ f(x^i)

boofun.analysis.p_biased.p_biased_average_sensitivity(f: BooleanFunction, p: float = 0.5) → float

Compute the average sensitivity under p-biased distribution μ_p.

This computes:

as_p(f) = E_{x ~ μ_p}[s(f, x)]

where s(f, x) is the sensitivity at input x.

This is Tal’s asMuP function. Note that by Poincaré’s inequality, this equals the p-biased total influence for Boolean functions.

Parameters:

• f – BooleanFunction to analyze

• p – Bias parameter

Returns:

Average sensitivity under μ_p

References

• Tal’s BooleanFunc.py: asMuP

• O’Donnell Proposition 8.28

boofun.analysis.p_biased.p_biased_total_influence_fourier(f: BooleanFunction, p: float = 0.5) → float

Compute total p-biased influence via Fourier coefficients.

The p-biased total influence via Fourier is:

I^(p)[f] = (1 / (4p(1-p))) × Σ_S |S| · f̂(S)_p²

The normalization factor 4p(1-p) is the variance of a single ±1 coordinate under the p-biased distribution. At p=0.5, this factor equals 1.

This should equal the average sensitivity under μ_p (Poincaré inequality).

Note: Tal’s original asFourierMuP function computes Σ_S |S| f̂(S)_p² WITHOUT the normalization, which only equals the total influence at p=0.5.

Parameters:

• f – BooleanFunction to analyze

• p – Bias parameter

Returns:

Total p-biased influence (via Fourier)

References

• O’Donnell Theorem 8.32 (p-biased Poincaré inequality)

• O’Donnell Proposition 8.28

boofun.analysis.p_biased.parity_biased_coefficient(n: int, k: int, i: int) → float

Compute the p-biased Fourier coefficient of the parity function.

For the parity function PAR_n(x) = x_1 ⊕ x_2 ⊕ … ⊕ x_n (XOR of all bits), this computes a specific coefficient related to the bias.

The formula uses Krawchouk-like recurrence:

S = Σ_{j=0}^{i} (-1)^j * C(n-k, j) * C(k, i-j) result = S / C(n, i)

where k relates to the bias via k = p*n (expected number of 1s).

This is Tal’s parity_biased function.

Parameters:

• n – Number of variables

• k – Bias-related parameter (typically floor(p*n) or similar)

• i – Coefficient index

Returns:

The biased parity coefficient

References

• Tal’s BooleanFunc.py: parity_biased

• Krawchouk polynomials in coding theory

class boofun.analysis.p_biased.PBiasedAnalyzer(f: BooleanFunction, p: float = 0.5)

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)

Initialize p-biased analyzer.

Parameters:

• f – BooleanFunction to analyze

• p – Bias parameter

property coefficients: Dict[int, float]

Get cached p-biased Fourier coefficients.

expectation() → float

Get E[f] under p-biased measure.

variance() → float

Get Var[f] under p-biased measure.

influence(i: int) → float

Get p-biased influence of variable i.

influences() → List[float]

Get p-biased influences of all variables.

total_influence() → float

Get total p-biased influence.

noise_stability(rho: float) → float

Get p-biased noise stability at correlation rho.

spectral_norm(level: int) → float

Get L2 norm of degree-level Fourier coefficients.

max_influence() → Tuple[int, float]

Find variable with maximum p-biased influence.

average_sensitivity() → float

Compute average sensitivity under μ_p distribution.

By Poincaré’s inequality, this equals total_influence() for Boolean functions.

total_influence_fourier() → float

Compute total influence via Fourier formula.

This should equal average_sensitivity() and total_influence(), providing a cross-validation check.

fourier_coefficient(S: int) → float

Compute single Fourier coefficient using Tal’s efficient formula.

Parameters:

S – Subset mask

Returns:

The p-biased Fourier coefficient f̂(S)_p

validate(tol: float = 1e-06) → Dict[str, bool]

Cross-validate p-biased computations.

Checks that mathematically equivalent quantities match: - total_influence() ≈ average_sensitivity() ≈ total_influence_fourier()

Parameters:

tol – Tolerance for floating point comparison

Returns:

Dictionary of validation checks and their results

summary() → str

Get human-readable summary of p-biased analysis.