This post continues my series on favorite theorems of the twenty-first century. For an overview of the categories and earlier selections, see my introductory post.
My choice for 2005 in Probability and Statistics is the “Majority Is Stablest” theorem of Elchanan Mossel, Ryan O’Donnell and Krzysztof Oleszkiewicz. Their preprint was posted in March 2005, a shorter version appeared at FOCS later that year, and the full paper was eventually published in the Annals of Mathematics in 2010 (Mossel et al. 2010).
The theorem can be interpreted as a statement about voting.
Suppose that an election has two candidates and voters. Encode a vote for the first candidate by and a vote for the second candidate by . The result of the voting is therefore a vector A voting rule which always chooses one of the two candidates is a function Such functions are called Boolean functions.
Assume that every voter chooses independently between the two candidates, each with probability . A natural requirement is that the voting rule should be fair: before the votes are cast, both candidates should have the same probability of winning. In formulas, this means
The most familiar fair voting rule, when is odd, is the majority function
What other properties should a good voting rule have?
One desirable property is that no individual voter should have too much power. For , let be the voting result obtained from by reversing the -th vote. The influence of voter on is where is chosen uniformly at random from .
Thus is exactly the probability that changing only voter ’s vote changes the winner.
For the majority rule, all voters have the same influence, and Indeed, changing voter affects the result precisely when the other voters are split equally between the two candidates. Hence as . In particular, the influence of every individual voter tends to zero.
Another desirable property is stability. Suppose that, after the votes have been cast, some of them are accidentally reversed during counting. We would like the winner to remain unchanged with high probability.
To describe this precisely, fix a number . Choose uniformly at random, and independently for each define by Thus each vote is misrecorded independently with probability The two votes and have correlation
The noise stability of at correlation is Since , Thus maximizing noise stability is exactly the same as maximizing the probability that errors in recording the votes do not change the winner.
The majority rule is very stable. In fact, This formula follows from the central limit theorem. The normalized sums converge to two correlated normal random variables with correlation , and the probability that they have the same sign can be computed explicitly.
Is majority the most stable fair voting rule?
Without any further assumptions, the answer is no. Consider the dictatorship It is fair, and which is larger than for . But in a dictatorship the first voter has influence .
Thus it is natural to ask for the most stable voting rule among those in which every individual voter has very small influence.
This question also arose independently in theoretical computer science. In work eventually published in 2007, Khot, Kindler, Mossel and O’Donnell formulated the “Majority Is Stablest” conjecture (Khot et al. 2007). Mossel, O’Donnell and Oleszkiewicz proved it in 2005.
Since the influences of tend to zero and the theorem is sharp.
For me, Majority Is Stablest is an especially appealing probability theorem because both the problem and its answer have such a simple interpretation. If every voter has little individual power, and if we want the result of an election to be as insensitive as possible to random errors, then asymptotically there is no better rule than the most obvious one: