The influence of variables in product spaces |
| |
| Authors: | Jean Bourgain Jeff Kahn Gil Kalai Yitzhak Katznelson Nathan Linial |
| |
| Institution: | (1) Département de Mathématiques, IHES, 35 route de Chartres, Bures-sur-Yvette, France;(2) Department of Mathematics, Rutgers University, 08903 New Brunswick, NJ, USA;(3) Landau Center for Research in Mathematical Analysis Institute of Mathematics and Computer Science, The Hebrew University of Jerusalem, 91904 Jerusalem, Israel;(4) IBM Almaden Research Center, Israel;(5) Department of Mathematics, Stanford University, 94305 Stanford, CA, USA |
| |
| Abstract: | LetX be a probability space and letf: X
n
→ {0, 1} be a measurable map. Define the influence of thek-th variable onf, denoted byI
f
(k), as follows: Foru=(u
1,u
2,…,u
n−1) ∈X
n−1 consider the setl
k
(u)={(u
1,u
2,...,u
k−1,t,u
k
,…,u
n−1):t ∈X}.
More generally, forS a subset of n]={1,...,n} let the influence ofS onf, denoted byI
f
(S), be the probability that assigning values to the variables not inS at random, the value off is undetermined.
Theorem 1:There is an absolute constant c
1
so that for every function f: X
n
→ {0, 1},with Pr(f
−1(1))=p≤1/2,there is a variable k so that
Theorem 2:For every f: X
n
→ {0, 1},with Prob(f=1)=1/2, and every ε>0,there is S ⊂ n], |S|=c
2(ε)n/logn so that I
f
(S)≥1−ε.
These extend previous results by Kahn, Kalai and Linial for Boolean functions, i.e., the caseX={0, 1}.
Work supported in part by grants from the Binational Israel-US Science Foundation and the Israeli Academy of Science. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
