Discrete derivative of a Boolean function ($D_{i}f$)

On the unbiased cube, the discrete derivative isFor the p-biased product measure, the normalization factor is $\sigma /2$.

For the $\{-1,1\}$-valued convention on the unbiased Boolean hypercube, the influence of coordinate $i$ is ${\mathrm{Inf}}_i(f)=\Vert D_{i}f{\Vert }_2^2$, where $D_{i}f$ is the discrete derivative of a Boolean function. It equals the probability that flipping coordinate $i$ changes $f$. For the $\{0,1\}$-valued convention, the same flip probability is instead $4\Vert D_{i}f{\Vert }_2^2$, since a nonzero discrete derivative has magnitude $1/2$.

For a zero-one Boolean function, the flip-probability influence is ${\beta }_i=4{\sum }_{S\ni i}\hat{f}(S{)}^2$. Apply Beckner's inequality with noise parameter $\sqrt{\delta }$ to the discrete derivative of a Boolean function, whose nonzero magnitude is $1/2$. Its $L^{1+\delta }$ norm squared is ${\beta }_i^{2/(1+\delta )}/4$. Summing over coordinates gives the displayed weighted Fourier weight bound, a useful intermediate step in influence lower bounds.

The total influence isThis Fourier-Walsh transform identity uses $\{-1,1\}$-valued $f$ and the flip-probability convention for influence of a variable. For $\{0,1\}$-valued $f$, the right-hand side is multiplied by four. Indeed Parseval's identity applied to the discrete derivative of a Boolean function gives $\Vert D_{i}f{\Vert }_2^2={\sum }_{S\ni i}\hat{f}(S{)}^2$; sum over coordinates and apply the chosen normalization.

For an increasing Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ and independent Bernoulli distribution input bits of probability $p$, define $I_i^{(p)}(f)$ as the probability that coordinate $i$ is pivotal for an increasing event. Then, for $0<p<1$,To prove it, first give each coordinate its own parameter $p_i$. Conditioning on all other coordinates makes the expectation affine in $p_i$, with partial derivative equal to the expected difference between the values with bit $i$ fixed to one and zero. Monotonicity makes that difference the pivotal indicator. The chain rule along $p_1=\cdots =p_n=p$ yields the formula.^[ref]

For example, an AND of $n$ input bits has expectation $p^n$ and each pivotal probability is $p^{n-1}$. In the sign-coordinate p-biased product measure, $p$ instead denotes the mass at minus one: identify the increasing bit as $(1-x_i)/2$. Keeping an increasing function of the ordered signs themselves reverses the derivative's sign. Biased squared-derivative definitions of total influence also require their stated normalization.

A coordinate is pivotal for an increasing event in a configuration when changing only that coordinate changes whether the event occurs. Its pivotal probability is the coordinate's influence.