Gaussian bounds for noise correlation of functions (Q2379368): Difference between revisions

From the abstract: ``In this paper we derive tight bounds on the expected value of products of 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.'' ``We present two applications of the new bounds to the theory of social choice. We show that Majority is asymptotically the most predictable function among all low influence functions given a random sample of the voters. Moreover, we derive an almost tight bound in the context of Condorcet aggregation and low influence voting schemes on a large number of candidates. In particular, we show that for every low influence aggregation function, the probability that Condorcet voting on \(k\) candidates will result in a unique candidate that is preferable to all others is \(k^{-1+o(1)}\). This matches the asymptotic behavior of the majority function for which the probability is \(k^{-1-o(1)}\).''