Consider the following scenario: Fixed () suppose that a generic assignment is corrupted to , where with probability independently for . The noise can induce errors on with probability . In particular, we show that for the majority functions the following result holds, independently from .
Fact: .
Proof: Let a random assignment in ; the random variable is approximately normal distributed with average and variance , so that is concentrated with high probability in the range s.t. . Let be a random assignment s.t. for each ; the random variable is approximately normal distributed with average and variance so that, for small , for which holds, and for in the interval , is concentrated in the interval s.t. .
Since the error condition is and or and , the values of with high probability of error are concentrated in the interval s.t. . It follows that the probability of error is .
As observed in [6], Boolean functions represented as simple majority (i.e. ES) are quite stable in presence of noise, while two-level majority (like the functions represented by EP) are less stable and, finally, the functions represented through a large number of levels are quite sensitive to noise.
We conclude that the representation through EP is a good compromise between stability in presence of noise and ability of representing in a compact way a large class of functions.