Abstract
We study the total variation distance (TV) between two $n$-fold Bernoulli product measures parametrized by $\vec p=(p_1,\ldots,p_n)$ and $\vec q=(q_1,\ldots,q_n)$, respectively, in the tiny and small regimes. In the tiny regime, we have $p_i,q_i\lesssim 1/n^2$, and in the small regime, $p_i,q_i\lesssim 1/n$. We discover that in the tiny regime, the TV distance behaves as $\|\vec p-\vec q\|_1$, while in the small regime, it behaves as [ \sum_{i=1}^n \Big| p_i\prod_{j\neq i}(1-p_j) - q_i\prod_{j\neq i}(1-q_j) \Big|, ] both up to absolute constants. Along the way we discover some identities of possible independent interest.
Introduction
In probability theory and statistics, measuring the distance between two distributions is a fundamental task. For product measures—distributions formed by independent random variables—measures like Kullback-Leibler (KL) divergence or Hellinger distance are computationally efficient because they "tensorize," allowing the total distance to be calculated as a simple sum of individual component differences.
However, the Total Variation (TV) distance does not share this property. The TV distance between two Bernoulli product measures $\text{Ber}(p)$ and $\text{Ber}(q)$ represents the maximum possible difference in probability that the two distributions can assign to any single event. Despite its importance, computing this distance exactly is known to be #P-hard. This computational barrier necessitates the development of sharp, simple-to-evaluate approximations, particularly in regimes where the success probabilities $p_i$ and $q_i$ are small.
Methodology: Slice Decomposition
The core analytical technique used in this research is slice decomposition. The authors analyze the probability space of the Hamming cube $\{0,1\}^n$ by partitioning it into "slices" based on the number of successes $k$:
- Slice 0: The event where no successes occur (all tails).
- Slice 1: The event where exactly one success occurs (singletons).
- Slice $k$: The event where exactly $k$ successes occur.
By examining the discrepancy (the difference in probability mass) on each slice, the authors identify which components of the distribution dominate the TV distance as the parameters $p_i$ and $q_i$ vary. The analysis utilizes classical tools such as Bernoulli’s inequality and the Mean Value Theorem, alongside a newly discovered summation identity regarding elementary symmetric polynomials.
Key Regimes and Results
The paper identifies two distinct regimes where the TV distance can be characterized by simple geometric or combinatorial formulas.
1. The Tiny Regime ($p_i, q_i \lesssim 1/n^2$)
In this regime, the probability of observing two or more successes is negligible. Consequently, the TV distance is almost entirely determined by the sum of the differences in individual success probabilities. The authors formalize this in Theorem 1.1, showing that the TV distance behaves like the $\ell_1$ norm:
$$\frac{1}{4} \|p - q\|_1 \le \text{TV}(\text{Ber}(p), \text{Ber}(q)) \le \|p - q\|_1$$
2. The Small Regime ($p_i, q_i \lesssim 1/n$)
As probabilities increase toward $1/n$, multiple successes become more likely, but the "singleton" events (exactly one success) remain the primary drivers of the statistical difference. In Theorem 1.2, the authors prove that the TV distance is within a factor of 2 of the singleton slice discrepancy $\Delta_1$:
$$\frac{1}{2} \Delta_1 \le \text{TV} \le (2 - \frac{1}{n}) \Delta_1$$
where $\Delta_1 = \sum_{i=1}^n | p_i\prod_{j\neq i}(1-p_j) - q_i\prod_{j\neq i}(1-q_j) |$. This result provides a computable proxy for a distance that is otherwise computationally intractable.
Discussion and Geometric Transition
This work clarifies the geometric transition of TV distance across the parameter space. Previous literature established that when probabilities are near $1/2$, the TV distance behaves like the $\ell_2$ norm ($\sqrt{\sum (p_i - q_i)^2}$). This paper completes the picture for the sparse end of the spectrum, showing a transition from $\ell_2$ behavior at the center to $\ell_1$-like behavior as parameters approach zero.
Furthermore, the authors provide a refined $\ell_2$ upper bound for "quasi-symmetric" pairs (where one parameter is $\le 1/2$ and the other is $\ge 1/2$), demonstrating the robustness of $\ell_2$ behavior in the balanced regime.
Conclusion and Future Work
While the current results provide sharp bounds up to absolute constants, future research may focus on tightening these constants for specific applications. The authors have indicated that these findings lay the groundwork for a forthcoming $O(\sqrt{\log n})$ approximation of the TV distance across a much broader range of parameters, potentially offering a general-purpose tool for approximating TV distance in high-dimensional Bernoulli products.
Summary updated