Discrete derivative of a Boolean function Created 2026-09-24 Updated 2026-10-14
On the unbiased cube, the discrete derivative is
For the p-biased product measure, the normalization factor is .
Margulis–Russo formula Created 2026-09-24 Updated 2026-09-24
For the indicator of a monotone family under a p-biased product measure, the Margulis–Russo formula identifies the derivative of with the suitably normalized total influence of .
Write , , , and . The functions form the p-biased product measure orthonormal basis, so the Fourier expansion is . The normalized discrete derivative of a Boolean function satisfies
Applying Parseval identity and then exchanging two finite sums gives
The noise operator on the Boolean hypercube acts diagonally on the same basis: . Hence the noise stability is
Its derivative is
Taking the right-hand value at leaves exactly the linear Fourier weight , while taking the left-hand value at gives .
Tribes threshold window 2026-10-14
For tribes of size with and , the success probability under the p-biased product measure is . Its -quantile is . For fixed ,
Thus the fixed-error window has order . For small fixed error the leading coefficient grows with , so the general Friedgut-Kalai sharp threshold theorem also has the correct error dependence up to absolute constants.