Abstract
We develop a general technique for bounding the tail of the total variation distance between the empirical and the true distributions over countable sets. Our methods sharpen a deviation bound of Devroye (1983) for distributions over finite sets, and also hold for the broader class of distributions with countable support. We also provide some lower bounds of possible independent interest.
Introduction
A fundamental task in statistical inference is estimating an underlying probability distribution from a finite sample of $n$ observations. As the sample size grows, we expect the empirical distribution—the frequencies observed in our data—to converge to the true distribution. While classical tools like the Chernoff-Hoeffding inequality or the Dvoretzky-Kiefer-Wolfowitz (DKW) inequality provide guarantees for point estimates or cumulative distribution functions, bounding the Total Variation (TV) distance (or $L_1$ distance) presents a more significant challenge.
The TV distance measures the sum of absolute differences across all possible outcomes. For distributions with large or countably infinite support (e.g., Poisson or Geometric distributions), existing bounds have historically been either mathematically loose or restricted to finite sets. This paper improves upon the classic 1983 results by Luc Devroye, tightening the constants for finite support and extending the framework to countably infinite sets.
Methodology
The authors utilize McDiarmid’s inequality (the method of bounded differences) as the primary engine for their proofs. The approach follows a three-step logical progression:
1. Establishing Lipschitz Continuity
The authors demonstrate that the $L_1$ deviation function is "2-Lipschitz" with respect to the Hamming metric. In practical terms, this means that if a single observation in a sample of size $n$ is changed, the total $L_1$ error between the empirical and true distributions cannot shift by more than a small, fixed constant.
2. Concentration of Measure
Because the $L_1$ error function satisfies this Lipschitz property, McDiarmid’s inequality guarantees that the error will be tightly concentrated around its expected value. This allows the authors to move from discussing average-case behavior to providing high-probability tail bounds.
3. Bounding the Expectation
The core challenge lies in finding a tight upper bound for the expected $L_1$ error.
- For finite sets: The authors leverage properties of the binomial distribution to show that for a distribution with $k$ outcomes, the expected error is bounded by $\sqrt{k/n}$.
- For infinite sets: The authors employ a "splitting" strategy, categorizing outcomes into "heavy" (probabilities $\geq 1/n$) and "light" (probabilities $< 1/n$). This allows them to manage the infinite sum of errors without the values diverging.
Key Theoretical Insights
Sharper Constants
Previous bounds, such as those by Devroye, were often conservative due to the methods used to bound the exponent. By applying the Lipschitz property directly, this research improves the constant in the exponent of the deviation bound by an order of magnitude, significantly outperforming the previous constant of 1/25.
The "Square Root of Support" Rule
For a distribution with $k$ possible outcomes, the expected $L_1$ error follows a $\sqrt{k/n}$ relationship. This provides a clear "complexity budget": to maintain a specific level of accuracy, the sample size $n$ must scale linearly with the number of possible outcomes $k$.
Universal Convergence on Countable Sets
A major contribution of this work is the proof that the empirical distribution always converges to the true distribution for any countable set. However, the rate of this convergence depends on the "tail" of the distribution. If the sum of the square roots of the probabilities ($\sum \sqrt{p_j}$) is finite, convergence is rapid. If the distribution is extremely heavy-tailed, convergence is guaranteed but may be arbitrarily slow.
Results
Finite Support Bound
For a distribution with $k$ outcomes, the probability that the $L_1$ distance $J_n$ exceeds a threshold $\epsilon$ is bounded by: $$P(J_n > \epsilon) \leq \exp\left(-\frac{n}{2}(\epsilon - \sqrt{k/n})^2\right)$$ This result is significantly tighter than previous state-of-the-art bounds.
Countable Support Bound
The authors provide a general bound for infinite sets: $$P(J_n > \alpha_n + \beta_n + \epsilon) \leq \exp(-n\epsilon^2/2)$$ where $\alpha_n$ and $\beta_n$ are terms determined by the tail behavior of the true distribution.
Lower Bounds
To demonstrate the optimality of their work, the authors provide lower bounds on the expected error, proving that their upper bounds are nearly tight and cannot be significantly improved without further assumptions on the distribution.
Conclusion and Limitations
While this paper provides the sharpest known bounds for $L_1$ convergence on countable sets, it highlights a fundamental limitation: for general distributions on infinite sets, the rate of convergence can be arbitrarily slow if the distribution has a sufficiently "fat tail." Furthermore, these techniques are specific to discrete (countable) supports. Extending these sharp $L_1$ guarantees to uncountable sets (such as continuous distributions on the real line) remains a separate challenge, typically requiring different metrics like Wasserstein distance or kernel-based density estimation.
Summary updated