Difference between revisions of "Influence of variables"

From Polymath Wiki
Jump to: navigation, search
(Gave basic definition and three examples)
(No difference)

Revision as of 17:43, 16 February 2009

Let f be a Boolean function---that 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).

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 n-1 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 Hales-Jewett

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