Symmetric Bounded Indistinguishability: Hypergeometric Smoothing and Hahn Polynomials

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^{\prime }<1$ so that there is a pair of $(cn,0)$-wise indistinguishable distributions where the $c^{\prime }n$-wise marginals have statistical distance $\Omega (1)$. Our upper bound shows that the $c^{\prime }n$-wise marginals must be exponentially close for all $c$ and $c^{\prime }$. 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.

Expanded version with new results and presentation, extending v1