Optimal Thresholds for Monotone Non-Boolean Functions

Abstract

Let $[q]=\{0,1,\dots ,q-1\}$, let $\hat{I}”[q]$ denote the simplex of probability measures on $[q]$, and let ${\hat{I}}^3$ denote the Lebesgue measure normalized on $\hat{I}”[q]$. We prove that for any symmetric monotone function $f:[q{]}^n\to [q]$ and any $a\in [q]$ we have \begin{equation*} γ(\{μ\in Δ[q]\;\vert\;\mathbb{P}_{x\simμ^{\otimes n}}[f(x)=a] \in (\varepsilon,1-\varepsilon)\}) = O(1/\log n)\text{.} \end{equation*} We also show that this bound is tight. This improves Kalai and Mossel's previous bound of $O(\log \log n/\log n)$ and answers their question completely.

13 pages, 1 figure