Boolean Noise Operator

The Boolean noise operator averages a function over random coordinate reversals on ${-1,1}^n$ . For , let have the discrete uniform distribution on this set, and put , where the signs $Z_i in {-1,1}$ are independent of and one another, with . The linear operator is

where the right side is a conditional expectation (O'Donnell 2021, p. 55). Thus , , and . On a Boolean Fourier expansion, it acts diagonally,

$T_rhou(x)=sum_(S subset= {1,...,n})rho^(|S|)u^^(S)product_(i in S)x_i.$

Its crossover probability as a binary symmetric channel is .

See also

Binary Symmetric Channel, Boolean Fourier Expansion, Conditional Expectation, Courtade-Kumar Conjecture, Hellinger Conjecture, Linear Operator, Noise

Explore with Wolfram|Alpha

More things to try:

References

O'Donnell, R. Analysis of Boolean Functions. 21 May 2021. https://arxiv.org/abs/2105.10386.

Cite this as:

Weisstein, Eric W. "Boolean Noise Operator." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BooleanNoiseOperator.html

Subject classifications