Tight bounds found for testing if two distributions match
Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
Data Structures and AlgorithmsInformation Theory
Summary
Checking if two unknown collections of things are the same or quite different is important for many applications. The authors studied how many questions you need to ask to decide this when you can only ask certain types of questions chosen in advance. They found the smallest number of questions needed and proved you cannot do better, showing this number grows roughly with the logarithm of the size involved. This clarifies how difficult these testing problems are under specific sampling restrictions.
What this means in practice
- •For data engineers: Design efficient tests for whether two large datasets follow the same distribution under limited query models.
- •For database system designers: Develop database query optimizers that incorporate tight limits on checking data equivalence with constrained sample access.
A theory result. No direct application yet.
Authors
Gautam Kamath
Abstract
We study distribution testing with access to non-adaptive conditional samples. Specifically, we give tight bounds for equivalence testing, determining whether two unknown distributions are equal to or $\varepsilon$-far from each other in total variation distance. Our algorithm and lower bound show that $\tilde Θ\left(\frac{\log n}{\varepsilon^2}\right)$ queries are necessary and sufficient for this problem. These results demonstrate that the complexity of uniformity, identity, and equivalence testing with non-adaptive conditional samples are all $\tilde Θ(\log n)$.