Difference between revisions of "Iterated majority"
(Added basic page.) |
m (→Definition: Minor editing.) |
||
| Line 1: | Line 1: | ||
== Definition == | == Definition == | ||
| − | Let <math>n = 3^k</math>. The '''iterated majority function''' f:\{-1,1\}^n \to \{-1,1\}</math> is a recursively-defined variation on the [[majority function]] | + | Let <math>n = 3^k</math>. The '''iterated majority function''' <math>f:\{-1,1\}^n \to \{-1,1\}</math> is a recursively-defined variation on the [[majority function]]: |
| − | <math> f(x) = \begin{cases} maj(x), & if ~ n = 3 \\ | + | <math> f(x) = \begin{cases} \textrm{maj}(x), & \textrm{if}~ n = 3 \\ |
| − | maj(f(x^{(1)}),f(x^{(2)}),f(x^{(3)}) & otherwise, \end{cases}</math> | + | \textrm{maj}(f(x^{(1)}),f(x^{(2)}),f(x^{(3)}) & \textrm{otherwise}, \end{cases}</math> |
where <math>x^{(1)} = (x_1,x_2\ldots x_{n/3})</math>, <math>x^{(2)} = (x_{n/3+1},\ldots x_{2n/3})</math> and <math>x^{(3)} = (x_{2n/3+1},\ldots x_{n})</math> | where <math>x^{(1)} = (x_1,x_2\ldots x_{n/3})</math>, <math>x^{(2)} = (x_{n/3+1},\ldots x_{2n/3})</math> and <math>x^{(3)} = (x_{2n/3+1},\ldots x_{n})</math> | ||
| − | |||
== Properties == | == Properties == | ||
Revision as of 13:37, 6 June 2019
Definition
Let [math]n = 3^k[/math]. The iterated majority function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] is a recursively-defined variation on the majority function:
[math] f(x) = \begin{cases} \textrm{maj}(x), & \textrm{if}~ n = 3 \\ \textrm{maj}(f(x^{(1)}),f(x^{(2)}),f(x^{(3)}) & \textrm{otherwise}, \end{cases}[/math]
where [math]x^{(1)} = (x_1,x_2\ldots x_{n/3})[/math], [math]x^{(2)} = (x_{n/3+1},\ldots x_{2n/3})[/math] and [math]x^{(3)} = (x_{2n/3+1},\ldots x_{n})[/math]
Properties
- TODO
