# Entropy Equivalence Testing

arXiv: https://arxiv.org/abs/2605.23225 · HTML: https://mlsanity.com/paper/2605.23225/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 39 references that are in the map.
- First posted on arXiv 22 May 2026.

## Builds on (most cited first, 16 of 16)

- [Optimal Algorithms for Testing Closeness of Discrete Distributions](https://mlsanity.com/paper/1308.3946/) (2013)
- [Optimal Testing for Properties of Distributions](https://mlsanity.com/paper/1507.05952/) (2015)
- [Testing Ising Models](https://mlsanity.com/paper/1612.03147/) (2016)
- [Testing Bayesian Networks](https://mlsanity.com/paper/1612.03156/) (2016)
- [Testing Conditional Independence of Discrete Distributions](https://mlsanity.com/paper/1711.11560/) (2017)
- [Optimal Identity Testing with High Probability](https://mlsanity.com/paper/1708.02728/) (2017)
- [Optimal Testing of Discrete Distributions with High Probability](https://mlsanity.com/paper/2009.06540/) (2020)
- [Learning Polytrees](https://mlsanity.com/paper/1301.6688/) (2013)
- [Which Distribution Distances are Sublinearly Testable?](https://mlsanity.com/paper/1708.00002/) (2017)
- [Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing](https://mlsanity.com/paper/1612.03164/) (2016)
- [Independence Testing for Bounded Degree Bayesian Network](https://mlsanity.com/paper/2204.08690/) (2022)
- [Learning bounded-degree polytrees with known skeleton](https://mlsanity.com/paper/2310.06333/) (2023)
- [Estimating Renyi Entropy of Discrete Distributions](https://mlsanity.com/paper/1408.1000/) (2014)
- [Distribution Learning Meets Graph Structure Sampling](https://mlsanity.com/paper/2405.07914/) (2024)
- [Learnability of Parameter-Bounded Bayes Nets](https://mlsanity.com/paper/2407.00927/) (2024)
- [Testing (Conditional) Mutual Information](https://mlsanity.com/paper/2506.03894/) (2025)

## Abstract (arXiv)

We introduce the problem of entropy equivalence testing for probability distributions, a relaxation of the well-studied closeness testing problem, where the distribution testing algorithm is now only required to distinguish, given samples from two unknown distributions p,q and a parameter varepsilon ∈(0,1/2], between p=q and |H(p)-H(q)| ≥ varepsilon (where H denotes the Shannon entropy). We provide a time- and sample-efficient algorithm for this task, showing that the optimal sample complexity for this task can be significantly lower than that of closeness testing. As an application, we leverage this result to provide the first non-trivial testing algorithm for (standard) closeness of low-degree Bayesian networks, which significantly improves on either the sample or time complexity of a baseline based on full learning.