Influence of variables

Let f be a Boolean function---that is, a function from [math]\displaystyle{ \{0,1\}^n }[/math] to [math]\displaystyle{ \{0,1\}. }[/math] Let us write a typical point of [math]\displaystyle{ \{0,1\}^n }[/math] as [math]\displaystyle{ (x_1,\dots,x_n). }[/math] The influence of the variable [math]\displaystyle{ x_i }[/math] on the function f is defined to be the probability that the value of f changes if you change the value of [math]\displaystyle{ x_i }[/math] (keeping the values of the other [math]\displaystyle{ x_j }[/math] fixed).

Examples

The parity function

The parity function takes a sequence x to the parity of the number of 1s in that sequence. Clearly, if you change the value of any variable, the value of f changes. Therefore, the influence of every variable is 1.

The majority function

Let f(x) be 1 if there are more 1s than 0s and 0 otherwise. Then changing the value of [math]\displaystyle{ x_i }[/math] from 0 to 1 changes the value of f(x) if and only if the number of 1s in the remaining n-1 variables is exactly [math]\displaystyle{ \lfloor n/2\rfloor. }[/math] The probability of this is proportional to [math]\displaystyle{ n^{-1/2}, }[/math] so in this case (after doing a similar calculation concerning changing the value of [math]\displaystyle{ x_i }[/math] from 1 to 0) we find that every variable has an influence proportional to [math]\displaystyle{ n^{-1/2}. }[/math]

The value of the first coordinate

Let [math]\displaystyle{ f(x)=x_1. }[/math] Then the influence of [math]\displaystyle{ x_1 }[/math] is 1 and the influence of all the other variables is 0.

Relevance to density Hales-Jewett

Somebody else is going to have to write these two sections ...