About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Israel Journal of Mathematics
Paper
The influence of variables in product spaces
Abstract
Let X be a probability space and let f: X n → {0, 1} be a measurable map. Define the influence of the k-th variable on f, denoted by I f (k), as follows: For u=(u 1, u 2,..., u n-1) ∈X n-1 consider the set l k (u)={(u 1, u 2,..., u k-1, t, u k,..., u n-1):t ∈X}. {Mathematical expression} More generally, for S a subset of [n]={1,..., n} let the influence of S on f, denoted by I f (S), be the probability that assigning values to the variables not in S at random, the value of f 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 {Mathematical expression} 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/log n so that I f (S)≥1-ε. These extend previous results by Kahn, Kalai and Linial for Boolean functions, i.e., the case X={0, 1}. © 1992 Hebrew University.