Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.07246 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913142579134464 |
|---|---|
| author | Lepsveridze, Saba Lin, Allen |
| author_facet | Lepsveridze, Saba Lin, Allen |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_07246 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal Thresholds for Monotone Non-Boolean Functions Lepsveridze, Saba Lin, Allen Probability 60C05 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. |
| title | Optimal Thresholds for Monotone Non-Boolean Functions |
| topic | Probability 60C05 |
| url | https://arxiv.org/abs/2509.07246 |