Efron–Stein Variance Bound

Worked Example

Consider the OR function on n=4 IID Bernoulli(0.5) variables. The function is f(X) = max(X₁, X₂, X₃, X₄).

1. The expected value of f(X) is the probability that at least one coordinate is 1. This is 1 - P(all 0s) = 1 - (1 - 0.5)⁴ = 1 - 0.0625 = 0.9375.
2. Since f(X) is an indicator variable (it only takes values 0 or 1), its variance is E[f] - E[f]² = 0.9375 - 0.9375² = 0.05859375.
3. To compute the Efron-Stein bound, we resample coordinate i to get Xⁱ. The value f(X) ≠ f(Xⁱ) only if all other coordinates are 0, and the i-th coordinate changes.
4. The probability that all other coordinates are 0 is (1 - p)^n-1 = 0.5³ = 0.125.
5. If all other coordinates are 0, the difference squared is 1 when X_i ≠ Xⁱ_i, which happens with probability 2p(1-p) = 0.5. Thus, the expected squared difference for one coordinate is 0.125 × 0.5 = 0.0625.
6. The Efron-Stein bound is 0.5 × ∑_i=1⁴ E[(f(X) - f(Xⁱ))²] = 0.5 × 4 × 0.0625 = 0.125.
7. The exact variance (0.05859375) is strictly less than the bound (0.125), with a slack of 0.06640625.

Experiment

Follow these steps to observe the variance bound in action using the interactive module controls.

1. Open the Efron–Stein Variance Bound module.
2. Set Function to Sum. Observe that the exact variance and the bound are equal. The Efron-Stein bound is perfectly tight for linear functions like the sum.
3. Set Function to AND and Success probability to 0.25. Observe how the bound provides a safe upper estimate for the variance of the minimum function.
4. Observe the coordinate resampling visualization. It demonstrates one base sample and compares it to samples where exactly one coordinate is independently redrawn.

Limitations

The bound requires the input variables to be independent. It does not hold for arbitrary correlated variables. While it is always true that Var(f) ≤ 0.5 ∑ E[(f(X) - f(Xⁱ))²], the bound can be loose (have significant slack) for highly nonlinear functions like OR and AND, especially as n grows large or probabilities approach 0.5. The bound is perfectly tight only for functions that are a sum of independent univariate functions. Additionally, this module focuses on IID Bernoulli variables; the theory applies to any independent distributions, but the exact formulas implemented here assume the Bernoulli case.

References

The concepts demonstrated in this module are based on the following resources.

• The Jackknife Estimate of Variance (Efron and Stein, 1981) - Introduces the foundational inequality bounding variance through leave-one-out and resampling techniques.