Gaussian Bounds for Noise Correlation of Functions

Elchanan Mossel

Abstract

This paper establishes tight mathematical bounds on the expected value of products of low-influence functions defined on correlated probability spaces. By extending the Invariance Principle to multi-dimensional Gaussian spaces, the research demonstrates that functions where no single input dominates—"low-influence" functions—behave predictably like Gaussian random variables. These results provide foundational tools for social choice theory, specifically regarding the optimality of the Majority function, and offer critical insights into the hardness of approximation for constraint satisfaction problems in computer science.

Introduction

In many complex systems, from democratic elections to distributed computing, we analyze functions $f(x_1, \dots, x_n)$ where the inputs are subject to noise or correlation. A fundamental question in these fields is: if the inputs are correlated in a specific manner, how correlated are the resulting outputs?

While previous research, such as the "Majority is Stablest" theorem, provided answers for two correlated spaces, many real-world applications involve more complex interactions. These include voting scenarios with three or more candidates or "non-reversible" noise where relationships between variables are asymmetric. This paper generalizes these findings, providing tight bounds for the expected product of $k$ functions across correlated probability spaces, provided the functions have low influence—meaning no single coordinate $i$ significantly impacts the total variance.

The Invariance Principle and Gaussian Spaces

The core methodology of this work rests on a powerful "Invariance Principle." This principle suggests that for multilinear polynomials with low influences and bounded degrees, the specific nature of the underlying probability space (whether discrete bits or complex voting preferences) becomes secondary to the first few moments of the distribution.

By leveraging this principle, the author maps discrete, often intractable probability spaces onto smooth, multi-dimensional Gaussian distributions. This transition allows for the application of sophisticated geometric tools, such as:

  • Extended Fourier Theory: A generalized Fourier analysis applicable across an arbitrary number of correlated spaces.
  • Efron-Stein Decomposition: A technique to decompose functions into components based on variable subsets, enabling the truncation of functions to their low-degree parts without significant loss of information.
  • Borell’s Isoperimetric Inequality: The extension of classical results regarding the volume and surface area of sets in Gaussian space to handle multiple collections of Gaussians simultaneously.

Key Insights: The Optimality of Majority

A central theme of the paper is that functions lacking a "dictator" (a single influential variable) naturally converge toward Gaussian behavior. This leads to several significant insights:

1. Majority as an Extremal Function

The paper proves that the Majority function is mathematically extremal. In the context of social choice, it is the "most predictable" function and the most effective at minimizing Condorcet paradoxes (where collective preferences become cyclic) among all low-influence voting schemes.

2. Pairwise Independence

A surprising finding in the study of hyper-graphs is that if a distribution is pairwise independent, low-influence functions acting on that distribution behave as if they were entirely independent.

3. Stability through Smoothing

The research demonstrates that "noise stability" metrics are robust; slightly "smoothing" a function does not drastically change these quantities, justifying the use of low-degree approximations in complex proofs.

Results and Applications

The theoretical bounds derived in this paper have immediate practical implications:

  • Predictability in Elections (Theorem 1.1): For a random sample of voters, the optimal method to predict an election's outcome is the majority rule. The probability of a correct prediction is bounded by $\frac{2}{\pi} \arcsin \sqrt{\rho}$.
  • Condorcet Winners (Theorem 1.5): In elections with $k$ candidates, the probability that a low-influence voting scheme yields a unique Condorcet winner is approximately $k^{-1}$, matching the performance of the Majority function.
  • Hardness of Approximation: These mathematical bounds are instrumental in proving that certain Constraint Satisfaction Problems (CSPs) are "approximation resilient." This implies that, assuming the Unique Games Conjecture holds, no polynomial-time algorithm can outperform random guessing for these problems.

Limitations and Future Directions

While the paper provides tight bounds for many scenarios, some gaps remain. The author notes that deriving similarly tight results for the probability of a completely linear (acyclic) ranking in Condorcet voting remains an open challenge. Additionally, the theorems are strictly applicable to "low-influence" functions; the presence of a "dictator" variable significantly alters the bounds, particularly under high correlation. Finally, many of the implications for computer science remain tied to the unproven Unique Games Conjecture, representing a continuing area of research in computational complexity.

Summary updated

Abstract

In this paper we derive tight bounds on the expected value of products of {\em low influence} functions defined on correlated probability spaces. The proofs are based on extending Fourier theory to an arbitrary number of correlated probability spaces, on a generalization of an invariance principle recently obtained with O'Donnell and Oleszkiewicz for multilinear polynomials with low influences and bounded degree and on properties of multi-dimensional Gaussian distributions. The results derived here have a number of applications to the theory of social choice in economics, to hardness of approximation in computer science and to additive combinatorics problems.
BibTeX
@inproceedings{mossel2010gaussian,
  author = {Elchanan Mossel},
  title = {{Gaussian Bounds for Noise Correlation of Functions}},
  booktitle = {Geometric},
  year = {2010},
  doi = {10.1007/s00039-010-0047-x},
}
Figure