= Balanced tribes construction with unused coordinates
{title2=$m=\lfloor(\log2)2^w\rfloor$}
Choose $w\geq1$ maximal such that $wm\leq n$ for the displayed $m$, and take the OR of $m$ AND blocks of size $w$, ignoring unused coordinates. Its failure probability is $(1-2^{-w})^m$, between one quarter and three quarters. Active coordinates have <influence> $2^{1-w}(1-2^{-w})^{m-1}$ and unused ones have zero influence. Maximality gives $2^{1-w}<4(\log2)(w+1)/n$; for $n\geq2$, $w\leq\log_2n$, so every influence is below $8\log n/n$. The construction is therefore a <quite fair Boolean function> with small influences for every $n\geq2$. The logarithmic bound cannot hold at $n=1$, where every quite fair function has influence one.
Back to article page
