TOPICS
Search

Total Influence


The total influence of a real-valued function f:{-1,1}^n->R is the sum of its coordinate influences under the discrete uniform distribution, where n is a positive integer. If X is a random vector uniformly distributed on {-1,1}^n and X^({i}) reverses coordinate i, then

 I(f)=1/4sum_(i=1)^nE[(f(X)-f(X^({i})))^2],

where E denotes the expectation value (O'Donnell 2021, pp. 47-50).

For a Boolean function with values in {-1,1}, each coordinate contributes the probability that reversing coordinate i changes the output, so total influence equals average sensitivity. Under this quadratic normalization, a function with values in {0,1} instead has total influence one quarter of its average sensitivity. The pivotal-probability convention for a Boolean function with values in {0,1} uses average sensitivity without this factor.


See also

Average Sensitivity, Boolean Fourier Expansion, Boolean Function

Explore with Wolfram|Alpha

References

O'Donnell, R. Analysis of Boolean Functions. Cambridge, England: Cambridge University Press, 2014. https://doi.org/10.1017/CBO9781139814782. Revised version, 21 May 2021. https://arxiv.org/abs/2105.10386.

Cite this as:

Weisstein, Eric W. "Total Influence." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TotalInfluence.html

Subject classifications