The average sensitivity of a Boolean function is the expectation value of its Boolean
function sensitivity at a uniformly chosen input. It is also called total influence.
For 
and a random variable 
with the discrete
uniform distribution on 
, let 
reverse coordinate 
. Then
![I(f)=E[s(f,X)]=sum_(i=1)^nPr(f(X)!=f(X^({i}))).](/images/equations/AverageSensitivity/NumberedEquation1.svg) |
A coordinate function has average sensitivity 1, and the function 
has average sensitivity 
(O'Donnell 2021, pp. 49-50).
For the biased product measure on 
, each coordinate is independently 1 with probability 
, where 
. For a Boolean function 
, write 
for 
with coordinate 
set to 
. The corresponding total influence is
 |
Each summand is the probability over the other coordinates that coordinate 
is pivotal, without a factor of 
. At 
, this agrees with average sensitivity after recoding the
input and output values.
