= Tribes threshold window
{title2=$p_{1-\varepsilon}-p_\varepsilon=\Theta_\varepsilon(1/\log n)$}
For $m$ tribes of size $w$ with $m\sim(\log2)2^w$ and $n=mw$, the success probability under the <p-biased product measure> is $1-(1-p^w)^m$. Its $x$-quantile is $p_x=[1-(1-x)^{1/m}]^{1/w}$. For fixed $0<x<1$,
$$
p_x=\frac12+\frac1{2w}\log\frac{-\log(1-x)}{\log2}+O_x(w^{-2}).
$$
Thus the fixed-error window has order $1/\log n$. For small fixed error the leading coefficient grows with $\log(1/\varepsilon)$, so the general <Friedgut-Kalai sharp threshold theorem> also has the correct error dependence up to absolute constants.
Back to article page
