Answers are grounded in this paper and cite their sources.
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. Let (X i j : 1 les i les k,1 les j les n) be a matrix of random variables whose columns X 1 ,..., X n are independent and identically distributed and such that any two rows X i , X j for 1 les inej les k are independent. Assume further that the values that row X i takes with non-zero probability are the same no matter how one conditions on the remaining rows X 1 ,..., X i-1 X i+1 ,..., X k . Our results show that given k functions f 1 ,... , f k taking values in [0,1] it holds that |E[Pi i=1 k f i (X i )] - Pi i=1 k E[ fi (X i )]| < epsi if all influences of the functions f i are smaller than tau(epsi, k) which is independent of n. In words: low influence functions of pairwise independent rows behave like independent random variables. The general statement of our result applies when the rows are not pairwise independent and when (some) of the variables do not have low influences for (some) functions. The results obtained here allow analyzing hyper-graph long-code tests. A number of applications in hardness of approximation assuming the Unique Games Conjecture were obtained using the results derived here in subsequent work by Raghavendra and jointly by Austrin and the author. Our results imply new results on voting schemes in social choice and in additive number theory. In particular we show that among all low influence functions, Majority is asymptotically the most predictable and is (almost) optimal in the context of Condorcet voting.
No takes yet. Share an insight, caveat, or question.
Elchanan Mossel (2008) studied this question.
Synapse has enriched 7 closely related papers on similar clinical questions. Consider them for comparative context: