Instance-Optimal Identity Testing at the Original Total-Variation Radius: Resolving Canonne's 2024 Open Question 1
Description
Instance-optimal identity testing seeks the number of samples needed to distinguish an unknown distribution from a specified discrete reference at a given total-variation radius. Existing characterizations evaluate their functionals at different constant multiples of the radius, which can leave an arbitrarily large gap in sample complexity. We give an explicit functional that characterizes the fixed-sample complexity up to universal constants at the original radius, for every finite or countable reference distribution. The functional combines a strictly concave allocation problem with a truncated 3/2-moment and a count-fluctuation term for a heavy largest atom. Matching tests and normalized lower-bound priors establish the characterization throughout the radius interval, including transitions at the mass outside a largest atom and the regime of almost disjoint alternatives. For explicit rational input, a deterministic algorithm computes a factor-two bracket for the functional in polynomial bit complexity. This answers Open Question 1 posed by Canonne at COLT 2024 in the model of distributions on a countable alphabet.