Optimal thresholds for monotone non-Boolean functions

Source abstract

Abstract Let left bracket q right bracket equals StartSet 0 comma 1 comma ellipsis comma q minus 1 EndSet [ q ] = { 0 , 1 , … , q − 1 } $[q] = \{0,1,\ldots ,q-1\}$ , let normal upper Delta left bracket q right bracket Δ [ q ] $\Delta [q]$ denote the simplex of probability measures on left bracket q right bracket [ q ] $[q]$ , and let gamma γ $\gamma$ denote the Lebesgue measure normalized on normal upper Delta left bracket q right bracket Δ [ q ] $\Delta [q]$ . We prove that for any symmetric monotone function f colon left bracket q right bracket Superscript n Baseline right arrow left bracket q right bracket f : [ q ] n → [ q ] ${\kern1pt}f \colon{\kern-1pt} [q]^n \to [q]$ and any a element of left bracket q right bracket a ∈ [ q ] $a \in [q]$ , we have γ ( { μ ∈ Δ [ q ] | P x ∼ μ ⊗ n [ f ( x ) = a ] ∈ ( ε , 1 − ε ) } ) = O ( 1 / log ⁡ n ) . $$\begin{equation*} \gamma (\{\mu \in \Delta [q]\;\vert \;\mathbb{P}_{x\sim \mu ^{\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 upper O left parenthesis log log n slash log n right parenthesis O ( log ⁡ log ⁡ n / log ⁡ n ) $O(\!\log \log n/\log n)$ and answers their question completely.