Difference between revisions of "Iterated majority"
m (→Definition: Minor editing.) |
m |
||
| (9 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
== Definition == | == 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]]: | + | 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 | majority function]]: |
| − | <math> f(x) = \begin{cases} \textrm{maj}(x), & \textrm{if}~ n = 3 \\ | + | :::{| class="wikitable" |
| − | \textrm{maj}(f(x^{(1)}),f(x^{(2)}),f(x^{(3)}) & \textrm{otherwise}, \end{cases}</math> | + | |- |
| + | |<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> | + | 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 == | ||
| − | * | + | * 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 sensitivity|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 > \log(3/2)/\log(2)</math> then <math>f</math> is [[volatility|lame]] wrt <math>p_n</math>, and if <math>\alpha < \log(3/2)/\log(2)</math> then <math>f</math> is [[volatility|volatile]]. <ref>Johan Jonasson, Jeffrey E. Steif, [https://www.sciencedirect.com/science/article/pii/S0304414916000648 Volatility of Boolean functions], Stochastic Processes and their Applications, Theorem 1.25</ref> | ||
== References == | == References == | ||
| − | [[Category:monotone function]] [[Category:balanced function]] | + | [[Category:transitive-symmetric function]] [[Category:monotone function]] [[Category:balanced function]] [[Category:Noise sensitive function]] |
Latest revision as of 14:49, 7 April 2021
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. [1]
References
- ↑ Johan Jonasson, Jeffrey E. Steif, Volatility of Boolean functions, Stochastic Processes and their Applications, Theorem 1.25
