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.