Difference between revisions of "Majority"
m |
m (→Properties) |
||
| Line 12: | Line 12: | ||
* TODO: a description of Majority's Fourier Transform. See http://www.contrib.andrew.cmu.edu/~ryanod/?p=877 for details. | * TODO: a description of Majority's Fourier Transform. See http://www.contrib.andrew.cmu.edu/~ryanod/?p=877 for details. | ||
* Majority is the [[Stability|stablest]] Boolean function. <ref>Ryan O'Donnell, Analysis of Boolean functions, [http://www.contrib.andrew.cmu.edu/~ryanod/?p=2245]</ref> | * Majority is the [[Stability|stablest]] Boolean function. <ref>Ryan O'Donnell, Analysis of Boolean functions, [http://www.contrib.andrew.cmu.edu/~ryanod/?p=2245]</ref> | ||
| − | * Majority is the unique [[:Category:symmetric function|symmetric]], [[:Category:monotone function|monotone]] and [[:Category:odd function|odd]] function. TODO May's theorem, credit. | + | * Majority is the unique function that is [[:Category:symmetric function|symmetric]], [[:Category:monotone function|monotone]] and [[:Category:odd function|odd]] function. TODO May's theorem, credit. |
== References == | == References == | ||
Revision as of 14:17, 5 September 2018
Definition
A function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] is called a majority function if [math]f(x)[/math] returns the most common bit in the input:
[math] f(x) = \begin{cases} 1, & if ~ \sum_i x_i \geq 0 \\ -1 & otherwise \end{cases}[/math]
For even [math]n[/math], 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. [1]
- Majority is the unique function that is symmetric, monotone and odd function. TODO May's theorem, credit.
