Exploit structure of the overlap matrix beyond trace/spectral gap

§ Problem Statement

Setup

Let $(\mathcal X,\mathcal F)$ be a measurable space, let $n\ge 2$ , and let $P_1,\dots,P_n$ be probability measures on $(\mathcal X,\mathcal F)$ . Define their average measure

\bar P:=\frac1n\sum_{i=1}^n P_i,

and assume $P_i\ll \bar P$ for every $i$ (so all Radon-Nikodym derivatives $f_i:=dP_i/d\bar P$ are well-defined). Define the exchangeable permutation-mixture law $\mathbb P_n$ on $(\mathcal X^n,\mathcal F^{\otimes n})$ by

\mathbb P_n:=\frac1{n!}\sum_{\pi\in S_n}\bigotimes_{k=1}^n P_{\pi(k)},

where $S_n$ is the symmetric group on $\{1,\dots,n\}$ . Define its i.i.d. counterpart

\mathbb Q_n:=\bar P^{\otimes n}.

Assume $\mathbb P_n\ll \mathbb Q_n$ and define

\chi^2(\mathbb P_n\|\mathbb Q_n):=\int\left(\frac{d\mathbb P_n}{d\mathbb Q_n}-1\right)^2\,d\mathbb Q_n.

Introduce the overlap matrix $A\in\mathbb R^{n\times n}$ by

A_{ij}:=\frac1n\int f_i f_j\,d\bar P=\frac1n\int \frac{dP_i\,dP_j}{d\bar P},\qquad 1\le i,j\le n.

Then $A$ is symmetric, positive semidefinite, and has row/column sums equal to $1$ .

This setup follows Han & Niles-Weed (2024).

Unsolved Problem

Find structural assumptions on $A$ that are strictly finer than global spectral summaries (for example, $\operatorname{tr}(A)$ or the second-largest eigenvalue $\lambda_2(A)$ ) and that imply sharper finite- $n$ upper bounds on $\chi^2(\mathbb P_n\|\mathbb Q_n)$ . In particular, characterize classes of matrices $A$ (equivalently, classes of families $\{P_i\}_{i=1}^n$ ) for which one can prove explicit nonasymptotic rates

\chi^2(\mathbb P_n\|\mathbb Q_n)\le \Psi_n(A),

with $\Psi_n(A)$ depending on refined structure and improving provably over bounds that depend only on $\operatorname{tr}(A)$ and/or $\lambda_2(A)$ . Proposed directions (illustrative, unless directly established in cited sources) include entrywise heterogeneity, sparsity, block structure, and other higher-order invariants.

§ Discussion

Loading discussion…

§ Significance & Implications

In Han & Niles-Weed (2024), the current general bounds are broad but may be conservative for structured families. Subsequent follow-up work in September 2025 indicates at least partial progress on structure-sensitive refinements, while a complete characterization remains open.

§ Known Partial Results

Follow-up on permutation-mixture overlap-structure bounds (2025): The 2025 arXiv v3 paper develops a general (\chi^2)-control framework via symmetric-polynomial and permanent inequalities and shows model-agnostic bounds. A September 2025 follow-up (arXiv:2509.12584) provides at least partial progress toward structure-sensitive improvements, but the full matrix-structural characterization remains open.

§ References

[1]

Approximate independence of permutation mixtures

Yanjun Han, Jonathan Niles-Weed (2025)

Annals of Statistics (to appear)

📍 Section 6.1 (Discussion: Tightness of upper bounds), paragraph immediately after Lemma 6.2 ("for specific $P$, further properties of the matrix $A$...") on p. 26 (arXiv v3; Section 5.1 in earlier numbering).

Primary source paper where this problem is articulated.

Link ↗arXiv ↗

[2]

Follow-up on permutation-mixture overlap-structure bounds

arXiv preprint

📍 Follow-up reference (arXiv:2509.12584), used for status qualification rather than a full closure claim.

Post-September 2025 follow-up reference added to document partial progress and avoid stale all-open interpretation.

Link ↗arXiv ↗

§ Tags

open-question nonasymptotic-bounds exchangeable-mixtures spectral-methods information-theory