no. 16 · Tuesday 17 November 2026
Distribution-free certificate of similarity between distributions with blurred total variation distance
Abstract
Classical two-sample tests aim to determine whether two distributions are equal or not based on samples from each one. Even in an distribution-free setting, well-known methods such as the permutation test can provide statistical evidence that the two distributions differ. However, failure to reject equality does not necessarily establish that they are similar. In this work, we study the complementary problem of certifying distributional similarity with finite-sample confidence, without imposing assumptions on the underlying distributions. We show, however, that for continuous distributions, any distribution-free upper confidence bound on the total variation (TV) distance must be trivial with high probability, even if the distributions are identical. Thus, certifying similarity in TV with a distribution-free guarantee is practically impossible. We therefore examine the blurred TV distance, a relaxation of TV distance that enables us to quantify similarity after applying a common blurring operation while retaining the interpretation of TV. We construct distribution-free upper and lower confidence bounds on blurred TV, establish their finite-sample validity, and examine its properties in high dimensions.
- comments
- 54 pages, 4 figures
- fields
- Statistics Theory