# Sharp Normalized Covariance Bounds and Constant-Stretch Correlated Sampling on the Hypersimplex

arXiv: https://arxiv.org/abs/2607.13990 · HTML: https://mlsanity.com/paper/2607.13990/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jul 2026.

## Built on by (most cited first, 1 of 1)

- [An Efficient Minimax-Optimal Algorithm for Adversarial m-Set Bandits](https://mlsanity.com/paper/2608.12231/) (2026)

## Abstract (arXiv)

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 mathsf S be an m-subset of [d] with rank-m external-field law mathbb P(mathsf S=S)=fracprodi∈ Swiem(w),Ssubseteq[d],|S|=m, where em(w):=sumTsubseteq[d], |T|=mprodℓ∈ Twℓ is the mth elementary symmetric polynomial in w1,dots,wd. Let X:=(X1,dots,Xd)^top be its indicator vector, i.e., Xi=mathbb Ii∈mathsf S,i∈1,dots,d. Let Sigma:=Cov(X), put vi:=Sigmaii for each i∈[d], and define v:=(v1,dots,vd)^top,D:=diag(v),V:=sumi=1dvi. We prove Sigmasucceq D-fracvv^topV. 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).