Iterated majority

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

• The [math]p[/math]-biased influence of every bit is bounded by [math]O_p(2^{-n})[/math].
• By the above, the iterated majority function is noise sensitive for every constant noise-level [math]p[/math], since [math]\sum_i \mathrm{Inf}_i^p(f)^2 \to 0[/math].
• Let [math]p_n = 1/2 - n^\alpha (2/3)^n[/math]. If [math]\alpha \gt \log(3/2)/\log(2)[/math] then [math]f[/math] is lame wrt [math]p_n[/math], and if [math]\alpha \lt \log(3/2)/\log(2)[/math] then [math]f[/math] is volatile.