# Difference between revisions of "Influence of variables"

Let f be a Boolean function---that is, a function from $\{0,1\}^n$ to $\{0,1\}.$ Let us write a typical point of $\{0,1\}^n$ as $(x_1,\dots,x_n).$ The influence of the variable $x_i$ on the function f is defined to be the probability that the value of f changes if you change the value of $x_i$ (keeping the values of the other $x_j$ 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 $x_i$ 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 $\lfloor n/2\rfloor.$ The probability of this is proportional to $n^{-1/2},$ so in this case (after doing a similar calculation concerning changing the value of $x_i$ from 1 to 0) we find that every variable has an influence proportional to $n^{-1/2}.$

#### The value of the first coordinate

Let $f(x)=x_1.$ Then the influence of $x_1$ 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 ...