Sharp Normalized Covariance Bounds and Constant-Stretch Correlated Sampling on the Hypersimplex
Abstract
We establish the normalized covariance bound conjectured by Anari et al. (2026, Conjecture 3) for fixed-rank external-field measures. Let d≥2 and m∈[d−1]. For w∈(0,+∞)d, let S be an m-subset of [d] with rank-m external-field law ℙ(S=S)=(∏i∈ Swi)/em(w),S⊆[d],|S|=m, where em(w):=∑T⊆[d], |T|=m∏ℓ∈ Twℓ is the mth elementary symmetric polynomial in w1,…,wd. Let X:=(X1,…,Xd)⊤ be its indicator vector, i.e., Xi=𝕀{i∈S},i∈{1,…,d}. Let Σ:=Cov(X), put vi:=Σii for each i∈[d], and define v:=(v1,…,vd)⊤,D:=diag(v),V:=∑i=1dvi. We prove Σ⪰ D−vv⊤/V. This improves the coefficient 1/2 in the first version of our work (Cesari and Colomboni, 2026, Corollary 1.3) to the optimal universal value $1$. As a first corollary, we improve the coefficient in the pseudoinverse bound of Bacchiocchi et al. (2026, Lemma 2) from $2$ to the optimal value $1$. Specializing this bound to coordinate differences gives an alternative proof of our effective-resistance theorem from the first version of our work (Cesari and Colomboni, 2026, Theorem 1.1). The framework of Anari et al. (2026, Theorem 1 and Corollary 2) also yields unconditional correlated-sampling guarantees with stretch $6$ on the hypersimplex and $12$ on its at-most variant. Unconditional constant-stretch guarantees were first established in the first version of our work (Cesari and Colomboni, 2026, Corollaries 1.4 and 1.5), with constants $16$ and $32$, which we improve here to $6$ and $12$. These improved constants strengthen the positive resolution, established in the first version of our work, of the constant-stretch question posed by Naor et al. (2026, Theorem 2 and Section 5).
Related
- Structure, Not Belief: Correlated Thompson Sampling from LLM-Derived Covariance in Combinatorial Semi-Bandits
- Independently Verified Causal Spatio-Temporal Covariance Under Correlated Amplitude and Pointing Noise in Fractional Nonlocal Photo-Thermoelastic Semiconductors
- Poincaré's Inequality on Sliding-Window Occupation Count Kernels and the Optimal Normalized Spectral-Gap Constant
- The Normalized Maximum Likelihood for Regular Non-Smooth Models: Measure-Theoretic Foundations and Geometric Sampling
- Sampling Line-Graph Colorings with Constant Extra Colors
BibTeX
@misc{cesari2026sharp,
title = {{Sharp Normalized Covariance Bounds and Constant-Stretch Correlated Sampling on the Hypersimplex}},
author = {Tommaso Cesari and Roberto Colomboni},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.13990},
eprint = {2607.13990},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.13990},
}
RIS
TY - UNPB
TI - Sharp Normalized Covariance Bounds and Constant-Stretch Correlated Sampling on the Hypersimplex
AU - Tommaso Cesari
AU - Roberto Colomboni
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2607.13990
UR - https://arxiv.org/abs/2607.13990
AB - We establish the normalized covariance bound conjectured by Anari et al. (2026, Conjecture 3) for fixed-rank external-field measures. Let d≥2 and m∈[d−1]. For w∈(0,+∞)^d, let S be an m-subset of [d] with rank-m external-field law ℙ(S=S)=(∏_i∈ Sw_i)/e_m(w),S⊆[d],|S|=m, where e_m(w):=∑_T⊆[d], |T|=m∏_ℓ∈ Tw_ℓ is the mth elementary symmetric polynomial in w_1,…,w_d. Let X:=(X_1,…,X_d)^⊤ be its indicator vector, i.e., X_i=𝕀{i∈S},i∈{1,…,d}. Let Σ:=Cov(X), put v_i:=Σ_ii for each i∈[d], and define v:=(v_1,…,v_d)^⊤,D:=diag(v),V:=∑_i=1^dv_i. We prove Σ⪰ D−vv^⊤/V. This improves the coefficient 1/2 in the first version of our work (Cesari and Colomboni, 2026, Corollary 1.3) to the optimal universal value $1$. As a first corollary, we improve the coefficient in the pseudoinverse bound of Bacchiocchi et al. (2026, Lemma 2) from $2$ to the optimal value $1$. Specializing this bound to coordinate differences gives an alternative proof of our effective-resistance theorem from the first version of our work (Cesari and Colomboni, 2026, Theorem 1.1). The framework of Anari et al. (2026, Theorem 1 and Corollary 2) also yields unconditional correlated-sampling guarantees with stretch $6$ on the hypersimplex and $12$ on its at-most variant. Unconditional constant-stretch guarantees were first established in the first version of our work (Cesari and Colomboni, 2026, Corollaries 1.4 and 1.5), with constants $16$ and $32$, which we improve here to $6$ and $12$. These improved constants strengthen the positive resolution, established in the first version of our work, of the constant-stretch question posed by Naor et al. (2026, Theorem 2 and Section 5).
ER -