Difference between revisions of "Influence of variables"
(Gave basic definition and three examples) 
(No difference)

Revision as of 17:43, 16 February 2009
Let f be a Boolean functionthat is, a function from [math]\{0,1\}^n[/math] to [math]\{0,1\}.[/math] Let us write a typical point of [math]\{0,1\}^n[/math] as [math](x_1,\dots,x_n).[/math] The influence of the variable [math]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]x_i[/math] (keeping the values of the other [math]x_j[/math] fixed).
Contents
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]x_i[/math] from 0 to 1 changes the value of f(x) if and only if the number of 1s in the remaining n1 variables is exactly [math]\lfloor n/2\rfloor.[/math] The probability of this is proportional to [math]n^{1/2},[/math] so in this case (after doing a similar calculation concerning changing the value of [math]x_i[/math] from 1 to 0) we find that every variable has an influence proportional to [math]n^{1/2}.[/math]
The value of the first coordinate
Let [math]f(x)=x_1.[/math] Then the influence of [math]x_1[/math] is 1 and the influence of all the other variables is 0.
Motivation
Relevance to density HalesJewett
Somebody else is going to have to write these two sections ...