



























Let $[q] = \{0,1,\ldots,q-1\}$, let $Δ[q]$ denote the simplex of probability measures on $[q]$, and let $γ$ denote the Lebesgue measure normalized on $Δ[q]$. We prove that for any symmetric monotone function $f \colon[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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。