Majority

Definition

A function $f:\{-1,1\}^n \to \{-1,1\}$ is called a majority function if $f(x)$ returns the most common bit in the input:

$f(x) = \begin{cases} 1, & if ~ \sum_i x_i \geq 0 \\ -1 & otherwise \end{cases}$

For even $n$, the above definition breaks ties in favor of 1, although any arbitrary rule may be used instead.

Properties

• Majority only depends on the number of ones and is therefore a symmetric Boolean function.
• Majority is a monotone function.
• TODO: a description of Majority's Fourier Transform. See http://www.contrib.andrew.cmu.edu/~ryanod/?p=877 for details.
• Majority is the stablest Boolean function.