Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 13 / 4 / ii

Partition $N=mw$ bits into $m$ tribes of size $w$, and let the tribes function be one when some tribe consists entirely of ones. Permuting tribes and permuting bits within a tribe acts transitively on the $N$ coordinates, so this is a transitive increasing event. Under independent bits of density $p$, its exact success probability isChoose $m=\lfloor (\log 2)2^w\rfloor$. Then $u(1/2)\to 1/2$, while $\log N=w\log 2+O(\log w)$. For fixed $0<x<1$, its unique $x$-quantile isPut $a_x=-\log (1-x)$. Expanding $1-e^{-a_x/m}=a_x/m+O_x(m^{-2})$ givesThus, for fixed $0<\epsilon <1/2$,This positive window prevents an improvement to $o(1/\log N)$ in the Friedgut-Kalai sharp threshold theorem. Moreover, as the fixed error parameter tends to zero, the displayed logarithmic coefficient is $\log (1/\epsilon )+\log \log (1/\epsilon )+o(1)$, so the theorem's logarithmic error dependence is also optimal up to constants. This last comparison takes $w\to \infty$ for each fixed $\epsilon$; the expansion is not being claimed uniformly for arbitrarily tiny $w$-dependent errors.