Total variation distance measures how well any test can tell two distributions apart. For product distributions, meaning $n$ independent coins with biases $p_1,\dots,p_n$ versus $q_1,\dots,q_n$, it is surprisingly hard to pin down. The standard route passes through Kullback–Leibler divergence using Pinsker's inequality. Kullback–Leibler divergence (a log-likelihood-ratio measure of mismatch) adds up cleanly over coordinates, but the conversion back to total variation loses a factor that can grow with $n$. Kontorovich showed that working directly in total variation reduces the gap to $\sqrt n$, and that this gap is unavoidable for his $\ell_2$ functional (On the tensorization of the variational distance). He left open a question: is there a simple formula that matches total variation up to an absolute constant, whatever the values of $n$, $p$ and $q$? Partial answers exist only piecewise. Near $p_i = 1/2$ the distance behaves like an $\ell_2$ norm. Near $p_i = 0$ it behaves like an $\ell_1$ norm (TV over Bernoulli products: the small parameter regime).
This note proposes to close that question with one continuous functional indexed by the per-coin variances $\sigma_i^2 = p_i(1-p_i)$, and to prove it matches total variation using moment bounds written in variance form. The observation that motivates the approach is that variance already appears exactly where Pinsker fails. The minimum Kullback–Leibler divergence needed to move a distance $v$ away from an atom of mass $\beta$ is $v^2/(8\beta(1-\beta))$ (A Reverse Pinsker Inequality). The Poisson-binomial proxy in TV homogenization inequalities is likewise normalized by total variance. The proof tool comes from a separate line of work. Skorski showed that writing binomial central moments in terms of $\sigma^2$ rather than $p$ removes the sign cancellations. Truncating the resulting series then gives valid bounds (Handy formulas for binomial moments). That property is what a Paley–Zygmund-style lower bound on total variation needs, since such a bound requires a certified upper bound on a fourth moment.
Core Claim
We conjecture a constant-factor result. For the likelihood ratio between the two products, the per-coin contributions can be grouped into two kinds. "Gaussian-like" coins have small relative discrepancy $|p_i-q_i|$ compared to $\sigma_i$. "Poisson-like" coins have discrepancy comparable to or larger than the variance. The first kind adds in $\ell_2$ and the second in $\ell_1$. Let $\Psi(p,q)$ be the functional that does this with a smooth, variance-indexed crossover, capped at 1. The conjecture is that $a\,\Psi \le \mathrm{TV} \le b\,\Psi$ for absolute constants $a$ and $b$.
Concretely, let $h_i$ denote the per-coordinate Hellinger distance, which behaves like $|p_i-q_i|/\sigma_i$ when the discrepancy is small relative to $\sigma_i$. The candidate family is
$$ \Psi_\tau(p,q)=\min\Big\{1,\;\Big(\sum_{i\in G_\tau} h_i^2\Big)^{1/2}+\sum_{i\notin G_\tau} h_i^2\Big\}, $$
where $G_\tau=\{i: h_i\le \tau\}$ is the set of coins whose discrepancy is at most $\tau$ times their standard deviation. We will also test smooth versions of the hard split.
What is new is not the use of Hellinger distance. It is two things. First, the claim that a single variance-indexed rule for switching between $\ell_2$ and $\ell_1$ aggregation removes both Kontorovich's $\sqrt n$ gap and the piecewise regime split of Avital et al. Second, a proof route in which every moment bound is a positive series in $\sigma_i^2$, so truncations are certified rather than approximate.
We state the scope honestly. The functional may need a third ingredient, such as a slice-discrepancy term in the style of $\Delta_1$ from Avital et al., for non-dominating pairs where discrepancies cancel. The numerical program below is designed to discover this before any proof effort is committed.
Research Program
The work has three stages.
Stage 1: numerical atlas. We compute exact total variation for Bernoulli products in two ways. For $n\le 22$ we enumerate the full cube. For larger $n$ we use parameter vectors with $m$ distinct values, where the total variation reduces to a sum over count vectors of a product of $m$ binomials and dynamic programming handles $n$ in the thousands with $m\le 4$. We then run adversarial search to maximize and minimize $\mathrm{TV}/\Psi_\tau$ over $(p,q)$. The search uses random restarts plus coordinate ascent in logit space, and it covers dominating and non-dominating pairs. The output is the empirical worst-case ratio as a function of $n$. The decisive signal is whether this ratio plateaus or keeps growing.
Stage 2: proofs, organized around variance-form moments.
- Lower bound. We restrict attention to the Gaussian-like block. There we lower-bound total variation by the probability that the centered log-likelihood-ratio statistic exceeds a fraction of its standard deviation, using Paley–Zygmund. This needs an upper bound on the fourth central moment of a heterogeneous sum. We will derive Poisson-binomial central moments as polynomials in the power sums $\sum_i\sigma_i^{2k}$, using Skorski's SymPy approach (symmetric polynomials and Gröbner elimination). We will then check whether positivity survives heterogeneity in a suitable basis. Skorski establishes positivity only for the homogeneous binomial, so this extension is itself a testable claim.
- Poisson-like block. Here we adapt the slice argument of Avital et al.
- Upper bound. This follows from Hellinger subadditivity on the Gaussian-like block and a union bound on the Poisson-like block.
- Constant loss. The symmetrization map of Kontorovich (randomizing to $p_i+q_i=1$) is available whenever a reduction to the symmetric case costs only a constant.
Stage 3: warm-up and by-product on the reverse Pinsker side. In the binary case, $D^*(v,Q)$ equals $\mathrm{KL}_2(\beta - v/2,\beta)$ up to higher-order terms (Minimum KL-Divergence on Complements of $L_{1}$ Balls.). We will expand this exactly in $v^2/\sigma^2(\beta)$, using $(1-2\beta)^2 = 1-4\sigma^2$ to eliminate the odd asymmetric terms. We will then test whether the coefficients have a fixed sign. If they do, truncation yields the global, non-asymptotic reverse Pinsker bounds that the asymptotic $v\to 0$ results lack. If they do not, that is a clean negative finding: it would show variance reparameterization does not remove oscillation in this setting, and it would limit how far the method transfers.
Baselines
Pinsker route (naive reference). This bounds total variation above by $\sqrt{\tfrac12\sum_i \mathrm{KL}(p_i\|q_i)}$ and pairs it with the trivial lower bound $\max_i|p_i-q_i|$. It is what practitioners use by default. We include it to show the size of the problem: the worst-case ratio grows with $n$, and it becomes infinite when some $q_i=0<p_i$.
Kontorovich's $\ell_2$ sandwich. The lower bound is $\mathrm{TV}\ge c\min\{1,\|\delta\|_2\}$ with $c>0.1798$, and the upper bound is $\|\delta\|_1$ (On the tensorization of the variational distance). It is the strongest general-purpose method, and its reported ratio is $\Theta(\sqrt n)$, which is provably optimal for that pair of functionals.
Regime-specific bounds of Avital et al. These have ratio 4 in the tiny regime ($\tfrac14\|p-q\|_1\le\mathrm{TV}\le\|p-q\|_1$) and ratio $4-2/n$ in the small regime via $\Delta_1$. They are the strongest constant-factor results, but only inside their regimes.
Kontorovich's $\Phi$ functional. This is two-sided up to constants for dominating Poisson-binomial pairs. It is not defined as a guarantee for full products.
Plain Hellinger sandwich. Total variation lies between $H^2$ and $\sqrt2 H$. This is the sharpest simple competitor, and it is discussed below.
Fair comparison. Every functional is evaluated on the same atlas instances with the same adversarial search budget. The budget is a fixed number of restarts and steps per $n$, and each baseline gets its own adversarial search. The comparison metric is the worst-case ratio found, as a function of $n$. $\Psi$ beats the field if its ratio stays below a fixed constant, say 10, for $n$ up to $10^3$ across all regimes, while the $\ell_2$ sandwich and the Hellinger sandwich are seen to grow.
Ablations.
- Functional ablation. Removing the variance-indexed split, using all-$\ell_2$ or all-$\ell_1$ aggregation, isolates the key ingredient of $\Psi$.
- Proof-tool ablation. We derive the same Paley–Zygmund lower bound using raw-$p$ moment expansions truncated at the same order. This shows whether the variance form actually improves the certified constant $a$.
Why not just…?
Why not just use the Hellinger sandwich? Hellinger distance tensorizes, and $H^2\le \mathrm{TV}\le\sqrt2H$. However, the ratio $\sqrt2/H$ blows up exactly when total variation is small. This is the $\ell_2$-versus-$\ell_1$ ambiguity in disguise: sparse coins make total variation track $H^2$, while balanced coins make it track $H$. $\Psi$ is essentially Hellinger distance with this ambiguity resolved coordinate by coordinate. This is the most serious threat. If the atlas shows that a simple global rule, such as $\min(H, H^2\cdot\text{something})$, already achieves constant ratio, we will report that result and drop the per-coordinate split.
Why not just estimate total variation by Monte Carlo? Sampling the likelihood ratio gives a point estimate with a confidence interval, not a certificate. Its relative error explodes when total variation is small, which is precisely the regime where the $\ell_1$ behavior matters. Nielsen and Sun make the analogous point for mixtures: they found deterministic bounds preferable to Monte Carlo intervals (Guaranteed Deterministic Bounds on the Total Variation Distance between Univariate Mixtures). A formula also supports analysis, for example of testing lower bounds, in a way that a numerical estimate cannot.
Why not just symmetrize and use the $\ell_2$ result? Kontorovich's Theorem 3 removes the gap for symmetric pairs. But his general reduction plus Theorem 2 shows that the $\ell_2$ functional necessarily loses $\sqrt n$ on asymmetric inputs. The lost information is exactly the variance heterogeneity that $\Psi$ encodes. We still reuse symmetrization inside the proofs where it costs only a constant.
Why not wait for the announced $O(\sqrt{\log n})$ approximation? Avital et al. describe such an approximation as forthcoming, and it would still carry an $n$-dependence. Our atlas provides a concrete test of whether any $\log n$ factor is actually necessary. If the adversarial search finds ratios for $\Psi$ growing like $\sqrt{\log n}$, that would suggest their rate may be the true answer, and we would say so.
Proposed Experiments and Decisive Checks
The first decisive check is the atlas plateau test. We plot the worst-case $\mathrm{TV}/\Psi_\tau$ against $n\in\{10,22,100,500,1000\}$ for three kinds of pairs: dominating pairs, non-dominating pairs with deliberate cancellation, and mixed-regime pairs combining balanced and near-zero coins. The same plot is made for all baselines. A plateau for $\Psi$ supports the conjecture. Growth confined to non-dominating pairs means a cancellation term is needed.
The second check tests whether variance-form moments stay positive for heterogeneous sums. We compute symbolic fourth and sixth central moments of Poisson-binomial sums in power sums of $\sigma_i^2$, and search for a basis in which all coefficients are nonnegative. If no such basis exists, the Paley–Zygmund route must rely on bounding terms rather than on positivity.
The third check is the reverse Pinsker series sign test. We examine the sign pattern of the exact series for $\mathrm{KL}_2(\beta-v/2,\beta)$ in $v^2/\sigma^2$ up to order 20, and compare truncated bounds against exact values on a grid of $(\beta,v)$.
As an application check, we apply $\Psi$ to Kontorovich's homogenization question. We compare $\Psi(p,q)$ with $\Psi(\bar p\mathbf 1,\bar q\mathbf 1)$ on the atlas to estimate the empirical homogenization constant. For comparison, the proven constant is $c\approx0.0115$ and the conjectured constant is $8/9$ (TV homogenization inequalities).
No reported worst-case ratio for the Hellinger sandwich on Bernoulli products was found on Lacuna. Our atlas will supply it.
References
- On the tensorization of the variational distance
- TV over Bernoulli products: the small parameter regime
- Minimum KL-Divergence on Complements of $L_{1}$ Balls.
- TV homogenization inequalities
- Handy formulas for binomial moments
- Guaranteed Deterministic Bounds on the total variation Distance between univariate mixtures