TV homogenization inequalities

Aryeh KontorovicharXiv 2026 · DOI · arXiv

Abstract: We study the total variation distance under two information-erasing maps on inhomogeneous Bernoulli product measures: summation and homogenization. While summation is a Markov kernel and hence satisfies the usual data processing inequality, homogenization—which maps each Bernoulli parameter to the cumulative mean—is not. Nevertheless, we prove that the homogenization map also reduces the TV distance, up to a universal constant. The argument is based on an explicit two-sided control of the TV distance between Poisson binomials, obtained via a parameter interpolation and a second-moment extraction lemma.

1. Introduction: Information-Erasing Maps

In probability and information theory, "information-erasing" maps are operations that reduce the distinguishability between two distributions. A fundamental principle in this domain is the Data Processing Inequality (DPI). The DPI states that if a common randomized process (a Markov kernel) is applied to two different inputs, the resulting outputs can only become harder to tell apart.

This paper investigates two specific information-erasing maps applied to Bernoulli product measures—sequences of independent coin flips where each flip $i$ has a distinct success probability $p_i$:

  1. Summation: Mapping the sequence of Bernoulli trials to their sum. This is a standard Markov kernel, and thus the DPI applies naturally.
  2. Homogenization: Replacing each individual bias $p_i$ with the global arithmetic mean $\bar{p} = \frac{1}{n} \sum p_i$.

Intuitively, homogenization erases the specific information contained in the individual biases, suggesting it should decrease the Total Variation (TV) distance between two distributions. However, a significant technical hurdle exists: homogenization is not a Markov kernel. Consequently, the standard DPI toolbox cannot be used to prove that homogenization reduces TV distance. This paper establishes that a homogenization inequality holds regardless, necessitating a new analytical approach.

2. The Challenge of Non-Markovianity

The core difficulty lies in the fact that the homogenization map cannot be represented as a stochastic matrix or a Markov process. While summation is a "coarsening" of the sigma-algebra (which is always Markovian), homogenization changes the underlying parameters of the product measure itself. To bridge this gap, the research focuses on the geometry of the Poisson-binomial distribution—the law governing the sum of independent, non-identical Bernoulli trials.

3. Theoretical Framework: The $\Phi$ Functional

To analyze the TV distance without the DPI, the author introduces a proxy analytic quantity, the $\Phi$ functional:

$$\Phi(p, q) = \min\left(1, \frac{\Delta}{\sqrt{\sigma_p^2 + 1}}\right)$$

In this expression, $\Delta$ represents the $L_1$ distance between parameter vectors, and $\sigma_p^2$ is the variance. This functional serves as a highly effective estimator for the TV distance between Poisson-binomial sums. A key discovery in the paper is that for "dominating pairs" (where $p_i \ge q_i$ for all $i$), the TV distance is essentially equivalent to this $\Phi$ functional up to universal constants.

4. Proof Strategy: Interpolation and Extraction

Since standard information-theoretic tools are unavailable, the proof relies on several fine-grained analytical techniques:

  • Parameter Interpolation: The author constructs a continuous path in the parameter space between two distributions. By analyzing the derivatives of the TV distance along this path, the author can track how distinguishability evolves.
  • Anti-concentration Bounds: The proof utilizes sharp bounds on the maximum probability any single value can take in a Poisson-binomial distribution, ensuring the distribution is sufficiently "spread out" to allow for TV estimation.
  • Second-Moment Extraction: Using a lemma attributed to Paul Lévy, the author bounds the TV distance from below by examining the first two moments of a specific "wedge" event.
  • Coupling and Majorization: For the specific case of "complementary" parameters (where $q = 1-p$), the author demonstrates that homogenization can be realized via a Markov kernel using majorization theory, though this does not generalize to all cases.

5. Main Results

The flagship result of the paper is the formal establishment of the Homogenization Inequality:

$$TV(\text{Ber}(p), \text{Ber}(q)) \gtrsim TV(\text{Bin}(n, \bar{p}), \text{Bin}(n, \bar{q}))$$

This confirms that averaging parameters reduces distinguishability, mirroring the behavior of Markovian processes. The author establishes this inequality with a universal constant $c \approx 0.0115$. Furthermore, for dominating pairs, the author proves a two-sided control $TV(S_p, S_q) \asymp \Phi(p, q)$, providing a simplified method for estimating the TV distance of sums without requiring complex convolutions.

6. Conclusion and Future Directions

While the paper successfully proves the existence of the homogenization inequality, several open questions remain. Numerical experiments suggest that the established constant $c \approx 0.0115$ is quite conservative; the author conjectures the optimal constant is actually $8/9$.

Additionally, while the upper bound for $TV(S_p, S_q)$ is general, the matching lower bound currently requires the "dominating pair" assumption ($p \ge q$). Extending this to arbitrary parameter vectors remains a challenge due to potential "convolutional smoothing" and cancellations. Finally, the author notes that while the $\Phi$ functional is a strong proxy, it is not yet "topologically equivalent" to the TV distance in all edge cases, suggesting a path for future refinement of the functional's definition.

Summary updated

Abstract

We study the total variation distance under two information-erasing maps on inhomogeneous Bernoulli product measures: summation and homogenization. While summation is a Markov kernel and hence satisfies the usual data processing inequality, homogenization -- which maps each Bernoulli parameter to the cumulative mean -- is not. Nevertheless, we prove that the homogenization map also reduces the TV distance, up to a universal constant. The argument is based on an explicit two-sided control of the TV distance between Poisson binomials, obtained via a parameter interpolation and a second-moment extraction lemma.
BibTeX
@misc{kontorovich2026tv,
  author = {Aryeh Kontorovich},
  title = {{TV homogenization inequalities}},
  year = {2026},
  eprint = {2601.04079},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2601.04079},
}
Figure