= Friedgut-Kalai sharp threshold theorem
{c}
{title2=$q-p\geq C\log((1-\varepsilon)/\varepsilon)/\log n$}
= Friedgut-Kalai theorem
{c}
{synonym}
There is an absolute $C>0$ such that any nontrivial <transitive increasing event> on $n\geq2$ independent bits satisfies $\mu_q(A)>1-\varepsilon$ if $\mu_p(A)>\varepsilon$, $0<\varepsilon<1/2$, and the displayed bound holds with $p<q<1$. A uniform weighted <Kahn-Kalai-Linial theorem> gives one pivotal probability at least $c\mu_r(A)(1-\mu_r(A))\log(n)/n$. Transitivity makes the <total influence> at least $c\mu_r(A)(1-\mu_r(A))\log n$. The <Margulis–Russo formula> identifies this with the derivative of $\mu_r(A)$. Integration of the derivative of its log odds proves the threshold bound.
Back to article page
