Influence

Motivation

Different functions depend differently on different bits. For the majority for example, all bits are equally important, since the function is symmetric. For the dictator, on the other hand, all the power is in the hands of a single bit, and the value of all other bits is ignored. Other functions lie in between: For example, in an intuitive sense, the pointer bits of the address are more important than the value bits, since all the pointer bits are "used" when evaluating the address function, while only a single value bit is used.

Definition

Standard definition

The influence is one way of quantifying the above intuition, and assigning a number which represents how important a particular bit is to the function's output. For an index [math]i = 1,\ldots,n[/math], the influence of the i-th bit is defined as

[math] \mathrm{Inf}_i(f) = \mathbf{Pr}_{x \sim \{-1,1\}^n} [f(x) \neq f(x^{\oplus i})], [/math]

where [math]x^{\oplus i}[/math] is equal to [math]x[/math] but with the [math]i[/math]-th bit flipped. In words, it is the probability that flipping the [math]i[/math]-th bit also flips the value of $f$.

The total influence of a function is the sum of all individual bit influences:

[math] \mathrm{I}(f) = \sum_{i=1}^{n} \mathrm{Inf}_i(f) [/math]

Biased analysis

Influences can also be defined for biased measures, rather than the uniform measure on [math]\{-1,1\}^n[/math]. Let [math]\mu[/math] be a product measure on [math]\{-1,1\}^n[/math], so that the probability that the [math]i[/math]-th bit is 1 is equal to [math]p_i[/math]. The [math]p[/math]-biased influence of the [math]i[/math]-th bit is then

[math] \mathrm{Inf}_i^p(f) = 4p(1-p)\mathbf{Pr}_{x \sim \mu} [f(x) \neq f(x^{\oplus i})]. [/math]

TODO: derivatives TODO: monotone functions TODO: KKL and Tribes as minimizer TODO: Talagrand's inequality TODO: Influence as isoperimetry