Abstract
In a recent paper, we presented a new definition of influences in product spaces of continuous distributions, and showed that analogues of the most fundamental results on discrete influences, such as the KKL theorem, hold for the new definition in Gaussian space. In this paper we prove Gaussian analogues of two of the central applications of influences: Talagrand's lower bound on the correlation of increasing subsets of the discrete cube, and the Benjamini-Kalai-Schramm (BKS) noise sensitivity theorem. We then use the Gaussian results to obtain analogues of Talagrand's bound for all discrete probability spaces and to reestablish analogues of the BKS theorem for biased two-point product spaces.
Introduction
In the study of Boolean functions—the mathematical foundation of computer science and social choice theory—the concept of influence is central. It quantifies how much changing a single input coordinate (such as an individual voter's choice) affects the final output of a function. Historically, classic results like the Kahn-Kalai-Linial (KKL) theorem or Talagrand’s correlation bounds were developed for the "discrete cube" $\{-1, 1\}^n$ under uniform measure.
However, many real-world applications involve continuous variables (e.g., physical measurements) or "biased" discrete variables where outcomes are not equally likely. The challenge has been finding a natural definition of influence for these non-uniform spaces that preserves the elegance of the discrete theory. This paper demonstrates that geometric influence—a recently proposed definition—is the correct framework to generalize these fundamental theorems to Gaussian and biased discrete settings.
Methodology
The research employs three primary strategies to bridge the gap between discrete and continuous probability spaces:
- Discretization and Limit Arguments: To establish the Gaussian version of Talagrand’s bound (Theorem 1.6), the authors approximate continuous Gaussian functions using a sequence of functions on increasingly high-dimensional discrete cubes. By applying known discrete theorems and taking the limit as the dimension approaches infinity, they successfully transfer these properties into Gaussian space.
- Ornstein-Uhlenbeck Semigroup: For a direct approach, the authors utilize the Ornstein-Uhlenbeck operator, which describes noise evolution in Gaussian systems. This allows the application of reverse hypercontractivity—a deep functional inequality—to derive a second, distinct correlation bound (Theorem 1.7) that does not rely on discrete limits.
- Shifting Operators: To handle complex sets that are not "monotone" (functions that do not necessarily increase as their inputs increase), the authors use shifting techniques. These transform sets into simpler, monotone versions while ensuring that core properties like noise sensitivity are either preserved or enhanced.
Key Insights and Ideas
The Gaussian Bridge for Biased Spaces
A major finding is that proving theorems in the Gaussian world first, then translating them back to the discrete world, yields cleaner results for biased product spaces. The authors' "h-influence" (the discrete counterpart to geometric influence) appears in these formulas without the cumbersome scaling factors required by previous definitions. This suggests that the Gaussian setting is, in many ways, the more fundamental environment for these inequalities.
Dual Paths to Correlation
The paper provides two distinct lower bounds for the correlation of increasing sets, each optimized for different structures:
- Theorem 1.6 is tight for "threshold sets," where the output depends on the weighted sum of all inputs.
- Theorem 1.7 is tight for sets that depend primarily on a single coordinate.
This duality suggests that the optimal bound depends on the specific geometry of the set, hinting at a potential future "unified bound" that could combine the strengths of both approaches.
Geometric Interpretation
Geometric influence links abstract probability to high-dimensional geometry. It essentially measures the expected "size" of the boundary of a set along a specific coordinate direction. This physical interpretation provides a more intuitive understanding of how sensitivity and correlation behave in high dimensions.
Key Results
- Gaussian Talagrand Bounds: The authors established two quantitative versions of the Gaussian FKG inequality. These provide a lower bound on the overlap of two increasing sets based on the geometric influences of their coordinates.
- Quantitative Gaussian BKS Theorem: The research proves that a sequence of sets in Gaussian space is "noise sensitive"—meaning a minor perturbation in the input completely decorrelates the output—if the sum of the squares of their geometric influences vanishes.
- Refined Biased Cube Results: By using Gaussian results as a bridge, the authors re-established and improved the BKS theorem for biased discrete cubes, demonstrating that the geometric framework is more robust than traditional combinatorial methods.
Limitations and Future Directions
While the paper successfully reduces Gaussian results to biased cubes, the authors noted that extending this to more general discrete product spaces (e.g., spaces with more than two possible outcomes per coordinate) currently requires more cumbersome direct proofs rather than simple reduction.
Furthermore, the current work assumes "product measures," where every input variable is independent. Extending these geometric influence concepts to spaces with correlated variables remains a significant open frontier in probability theory. Finally, the search for a single, universally optimal correlation bound that merges hypercontractivity and reverse hypercontractivity techniques remains an ongoing challenge.
Summary updated