View PDF HTML (experimental)

Abstract:A pair of probability distributions over $\{0,1\}^n$ is said to be $(k,\delta)$-wise indistinguishable if all of the size $k$ marginals are within statistical distance at most $\delta$. Previous works introduce this concept and study how far apart $t$-wise marginals can be under an assumption of $(k,\delta)$-wise indistinguishability. We consider symmetric distributions and obtain a new upper bound that unifies and improves previous bounds and applies across a wider range of parameters. In particular, prior works failed to rule out the existence of constants $0<c<c'<1$ so that there is a pair of $(cn,0)$-wise indistinguishable distributions where the $c'n$-wise marginals have statistical distance $\Omega(1)$. Our upper bound shows that the $c'n$-wise marginals must be exponentially close for all $c$ and $c'$. Our upper bound is accompanied with a nearly matching lower bound when $\delta=0$ and also yields new results in the case $\delta>0$ or when $t/n$ tends to 1. Our approach is to exploit the behaviour of the orthogonal Hahn polynomials under hypergeometric sampling and marginalisation operations. As a secondary contribution, we provide nearly matching upper and lower bounds on the maximum possible distance between a pair of $(k,\delta)$-wise indistinguishable distributions and the nearest pair of $(k,0)$-wise indistinguishable distributions.

Submission history

From: Christopher Williamson [view email]
[v1] Wed, 13 May 2026 16:48:41 UTC (13 KB)
[v2] Mon, 10 Aug 2026 10:48:49 UTC (21 KB)