When did Majority become the stablest?

The fireworks happening over at Ryan O’Donnell’s blog reminded me of something that always puzzles me: Is Majority the Stablest? Or the Unstablest?

Consider the class of all monotone, balanced Boolean functions . We define the noise sensitivity of a function as , where is chosen uniformly whereas the noise is sampled from a noise distribution of our choice. Think of as telling us which bits of to flip. Two natural choices are:

1. The -noise distribution where each bit is flipped independently with probability .
2. The “bit-flip” distribution where we flip a single random bit. This behaves a lot like  where .

Say we’d like to find the monotone, balanced, Boolean function which is least sensitive to noise. A bit of thought shows that the answer is any co-ordinate/dictator function . So to rule out trivial answers, let us only allow functions where all variables are equally important. More precisely, functions should be invariant under a transitive group of  permutations on the variables. This is a bit of overkill, the right way to do this is to insist that no variable has too much influence.

The Majority function is pretty insensitive/stable under -noise, one can show that .  In contrast, for constant , many other functions will have sensitivity approaching .The Majority is Stablest Theorem due Mossel, O’Donnell and Oleskeiwicz shows Majority is indeed about as good as it gets, functions which are more stable need to have a distinguished variable (which we disallow).

Now consider the “bit-flip” distribution . Using the rule of thumb, one would expect the noise-stability of Majority to be around . This is indeed the case, no surprises there. What is surprising is that this is as unstable as it gets for monotone functions! The proof of this is simple: we start with the observation that since is monotone, captures the probability that flipping changes for a random . To see why this is so, fix all the other bits except . Now flipping from to can result in two possible outcomes:

1. It leaves unchanged, in which case the contribution to is 0.
2. It causes to change from to , in which case the contribution to is 2. By monotonicity, the reverse flip from to is not possible.

So now we have

Since , we have

with equality iff

So  among balanced, transitive, monotone functions, Majority is maximally unstable under and maximally stable under . And in an intriguing twist, one way to prove the stability under is to reduce it to bounding the stability under as is done in the proof of Peres’ Theorem, which tells us that the bound is true for all LTFs.

Coming soon:

1. If not Majority, then who?
2. What lies behind Majority’s rapid descent into instability?