Abstract 1 Introduction 2 An 𝑶~⁢(𝒏𝟑/𝟒𝜺+𝐥𝐨𝐠𝟐⁡(𝒏/𝜺)𝜺𝟐) Upper Bound for EET 3 Bayesian Network Equivalence Testing 4 Lower Bound References Appendix A Deferred Proofs

Entropy Equivalence Testing

Clément L. Canonne ORCID University of Sydney, Australia    Yash Pote ORCID National University of Singapore, Singapore    Jonathan Scarlett ORCID National University of Singapore, Singapore    Joy Qiping Yang ORCID University of Sydney, Australia
Abstract

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 ε∈(0,1/2], between p=q and |H⁢(p)−H⁢(q)|⩾ε (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.

Keywords and phrases:
Entropy, distribution testing, sublinear algorithm, Bayesian network
Category:
RANDOM
Funding:
Jonathan Scarlett: Supported by the National University of Singapore under the Presidential Young Professorship scheme.
Joy Qiping Yang: Supported by a JD Technology Research Scholarship in Artificial intelligence.
Copyright and License:
[Uncaptioned image] © Clément L. Canonne, Yash Pote, Jonathan Scarlett, and Joy Qiping Yang; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation → Lower bounds and information complexity
; Mathematics of computing → Probabilistic algorithms
Related Version:
Full Version: https://arxiv.org/abs/2605.23225 [14]
Acknowledgements:
We would like to thank Sayantan Sen, Jan Seyfried and Marco Tomamichel for the discussion on their work of testing Conditional Mutual Information. JY would also like to thank Davin Choo for the early discussions predating this project. This work is conducted while JY was interning at National Institute of Informatics, hosted by Yuichi Yoshida.
Editors:
Mohit Singh and Tom Gur

1 Introduction

Distribution testing, a subfield of property testing [35, 30] concerned with efficient algorithms for deciding statistical properties of data, has witnessed a significant interest since its systematic introduction by Batu, Fortnow, Rubinfeld, Smith, and White [5], with a flurry of works over the past two decades addressing a range of hypothesis testing tasks, under various models of distribution testing (see, e.g., [34, 10, 11] and [29, Chapter 11] for surveys and expositions).

Two of the flagship and most fundamental tasks in distribution testing are identity testing (and its special case, uniformity testing), and closeness testing (also known as equivalence testing): in the first, an algorithm is given independent samples from an (unknown) discrete probability distribution, and must decide whether the distribution is equal to some known reference distribution, or significantly deviates from it in a meaningful notion of distance (typically total variation distance). In the second, the algorithm has access to samples from two unknown distributions, and similarly must decide whether they are equal, or significantly far from each other. Here, “significantly far” is quantified by an input parameter ε>0, and the algorithm is required to be correct with high probability 1−δ,111One typically sets δ to be a small constant, e.g., δ=1/10: this is without much loss of generality, as one can amplify this by repetition to any target 1−δ, at the cost of an O⁢(log⁡(1/δ)) factor in sample and time complexity. while minimizing the sample complexity, that is, the total number of samples taken from the distribution(s) in the worst case as a function of the domain size n, distance parameter ε, and error probability δ.

The sample complexity of these two flagship tasks is by now well understood, with several time-efficient algorithms known to achieve the optimal sample complexity, as a function of all parameters: namely,

Θ⁢(n⁢log⁡(1/δ)+log⁡(1/δ)ε2)

for identity testing [32, 1, 28, 27], and

Θ⁢(n2/3⁢log1/3⁡(1/δ)+log⁡(1/δ)ε4/3+n⁢log⁡(1/δ)+log⁡(1/δ)ε2)

for closeness testing [5, 17, 28, 26]. However, in spite of these impressive advances, these sample complexities can remain prohibitively large for many combinations of (n,ε), notably for small ε corresponding to distributions that may be very close to one another. Given that their sample complexities are constant-factor optimal, there would seem to be little room for improvement, yet two possible avenues remain. The first is to relax the guarantees: total variation is known to be a very stringent measure of distance, and testing with respect to a more permissive distance measure may enable significant sample complexity savings, while still being “good enough” for the application at hand. This direction was partially explored in, for instance, [24]. The second avenue, particularly well suited to high-dimensional data, is to make additional structural assumptions on the distribution: high-dimensional data is seldom fully unstructured, and one can usually leverage domain knowledge to make modelling assumptions, for instance that the probability distributions exhibit a low-degree Bayesian network structure, or are consistent with an Ising model. This line of work, in the context of distribution testing, was initiated in [12, 23].

Our work makes progress on both of these fronts. We first define a relaxation of closeness testing, which we term entropy equivalence testing, where one is asked to detect if the two unknown distributions have significantly different (Shannon) entropy:222Recall that the (Shannon) entropy of a probability distribution p over a discrete domain 𝒳 is defined as H⁢(p)=∑x∈𝒳p⁢(x)⁢log⁡1p⁢(x).

Entropy Equivalence Testing (EET): Given sample access to distributions p,q over a known domain of size n and parameters ε∈(0,1/2] and δ∈(0,1], distinguish, with probability at least 1−δ, between the following two cases: (1) p=q, and (2) |H⁢(p)−H⁢(q)|≥ε.

We note that the “single-distribution” version of this task, when q is fully known to the algorithm, was recently introduced [15], under the name Entropy Identity Testing (𝖤𝖨𝖳). [15] then leveraged their algorithm for 𝖤𝖨𝖳 to obtain an improved identity testing algorithm for “standard” identity testing (i.e., in total variation distance) of bounded-in-degree Bayes nets, establishing a connection between the two aforementioned avenues of research. We build upon and deepen this connection to obtain, from our algorithm for 𝖤𝖤𝖳, the first non-trivial closeness testing algorithm for Bayes nets.

1.1 Our results

We now describe our results in more detail. Our first contribution is an efficient algorithm for the 𝖤𝖤𝖳 task defined above (where we implicitly set the probability of failure δ to be a small constant):

Theorem 1.

There exists an algorithm for the Entropy Equivalence Testing problem with sample complexity

O~⁢(n3/4ε)+O⁢(log2⁡(n/ε)ε2)

and running time near-linear in the number of samples.

Combining Theorem 1 and the “baseline tester” discussed below (see Section 1.2) which follows from a reduction from entropy difference to total variation distance and has sample complexity O~⁢(max⁡(n2/3ε4/3,nε2)), one gets, after simplifying the resulting sample complexity, our main result:

Corollary 2 (Main testing result).

There exists an algorithm for the Entropy Equivalence Testing problem with sample complexity

O~⁢(min⁡{n3/4ε,n2/3ε4/3})+O⁢(log2⁡(n/ε)ε2)

and running time near-linear in the number of samples.

We complement this positive result with an information-theoretic lower bound, showing that our algorithm has nearly optimal sample complexity:

Theorem 3 (Lower bound).

Any algorithm for the Entropy Equivalence Testing problem must draw

Ω~⁢(min⁡{n3/4ε,n2/3ε4/3})+Ω⁢(log2⁡nε2)

total samples from p and q.

Finally, we show how to leverage our algorithm for 𝖤𝖤𝖳 to obtain a closeness testing algorithm for bounded in-degree Bayes nets: we emphasize that, to the best of our knowledge, this is the first testing algorithm for this problem, besides the “naïve” (and computationally inefficient) testing-by-learning approach that fully learns the two unknown distributions with O~⁢(2d⁢n/ε2) samples, in time 2Ω⁢(n):

Theorem 4.

There exists an algorithm for closeness testing (in total variation distance) of in-degree d Bayesian networks with sample complexity

s=O~⁢(min⁡{23⁢d/4⁢nε2,22⁢d/3⁢n4/3ε8/3}+n2ε4),

and running time O~⁢(nd+1⁢s).

Interestingly, the techniques underlying Theorem 4 can also be easily adapted to obtain an algorithm for identity testing of Bayes nets, improving upon the work of [15]: see Corollary 18.

1.2 Technical overview

We now provide an overview of the techniques and main ideas underlying our results.

1.2.1 Upper bound for EET

A bound of O~⁢(max⁡{n2/3ε4/3,nε2}) readily follows from a standard inequality, allowing one to reduce the entropy difference problem to closeness testing in TV: namely, when dTV⁢(p,q)⩽12, then |H⁢(p)−H⁢(q)|⩽dTV⁢(p,q)⁢log⁡ndTV⁢(p,q) [21, Lemma 2.7]. Another straightforward upper bound is obtained by estimating the entropy, a harder task, which takes Θ⁢(nε⋅log⁡n+log2⁡nε2) samples [42]. This hints at the possibility of getting a better bound of O⁢(nc/ε+log2⁡n/ε2) for some absolute constant c<1. Surprisingly, the final upper bound of O~⁢(min⁡{n2/3ε4/3,n3/4ε}+1ε2) is related to the squared Hellinger distance (and not the total variation). This is a result of considering two testers that can solve 𝖤𝖤𝖳 independently, and choosing the one with lower sample complexity. The main contribution of our work is providing an alternative tester to the TV reduction tester above.

An 𝑶~⁢(𝒏𝟑/𝟒𝜺+𝟏𝜺𝟐) tester.

Our analysis starts with a reduction to testing both farness (vs. equality) in Hellinger distance and a cross-entropy difference term (with respect to the uniform mixture) via some algebraic manipulations (see Lemma 9). The problem thus becomes testing whether Hellinger distance is large (which we know costs O⁢(min⁡{n3/4ε,n2/3ε4/3})⩽O⁢(n3/4ε)) and testing whether the cross-entropy term is large (since one of them will be large if the entropy difference is large). A natural idea is of course to employ a plug-in estimator for the cross entropy difference (see (1)). Unfortunately, this empirical estimator has an inherent333In the works of [42], their plug-in estimator also exhibits similar bias in the analysis, and they resort to machinery from polynomial approximation to reduce the bias (which will increase the variance the higher the degree of the polynomial). bias of the form ∑i∈[n]|pi−qi|m⁢(pi+qi), where m is the (equal) number of samples we take from p and q to compute the estimate. Our argument to deal with the bias is as follows: If the expectation of the plug-in estimator has low bias (at most O⁢(ε)), then we can rely on its estimate alone. On the other hand, if it has high bias (at least Ω⁢(ε)), we hope to catch it and reject (i.e., declare that |H⁢(p)−H⁢(q)|>ϵ) early.

Low mass regime: Reduction to TV.

One main challenge to designing this test is that the bias is impossible to test without a lower bound on pi+qi (the variance of estimating the bias could be huge). The key to passing this hurdle is an idea inspired by a different algorithm from [28], whose analysis implies that for the elements i∈[n] where qi (or pi) is small, we can perform tests more efficiently (in TV) via access to its conditional distribution (as efficiently as O~⁢(n3/4/ε)), with the intuition being: The TV distance between the conditional distributions is actually larger (inverse of its mass size Ω~⁢(ε/q⁢(T)), where T is the set of small-mass elements). Via a reduction to TV from cross-entropy difference, we can also test farness on these elements with O~⁢(n3/4/ε) samples.

Detecting bias in the high mass regime.

Capitalizing on this, we will consider exclusively elements with large mass: pi⩾Ω~⁢(ε/n3/4). With a bound on m⁢(pi+qi)⩾Ω⁢(1) (since we take m=O~⁢(n3/4ε)), this reduces to testing farness in TV distance, which can be performed with O⁢(n/ε2) samples (to bound the bias term by O⁢(ε)), rather than the O⁢(nc/ε) for some c<1 that we set out for. Luckily our problem can be easier (depending on relation between n⁢ and ⁢ε) than testing in TV (see Lemma 13). Intuitively, this is related to testing in the instance-optimal setting [40, 28] – one can test with sample complexity as a function of p,q (for our case p,q has exclusively large probability masses), rather than as a function of the domain size (the worst case over all possible p,q). Interestingly, to detect the bias, we are using the same test statistic (with different threshold) first used in [17] to test in TV distance and subsequently in [24] to test in Hellinger distance.

Had we not made a “reject” decision after the bias check in the high mass regime (nor rejected due to its low mass cross-entropy difference), it would suggest that the bias on the high mass regime is at most O⁢(ε) and therefore, the estimator for ∑i(pi−qi)⁢log⁡((pi+qi)/2) is reliable: A standard analysis of expectation and variance followed by an application of Chebyshev’s inequality then yields Theorem 1.

1.2.2 Lower bound for EET

The lower bound is a combination of Ω~⁢(min⁡{n2/3ε4/3,n3/4ε}) and Ω⁢(log2⁡nε2). The former is derived via a reduction from testing mutual information to entropy difference. The task of testing mutual information (𝖬𝖨) is as follows: if I(X:Y)=0, then accept with probability 0.99; If I(X:Y)⩾ε, then reject with probability 0.99. Given the close relation between mutual information and entropy: I(X:Y)=H(X)+H(Y)−H(X,Y), one can reduce the problem of 𝖬𝖨 testing to 𝖤𝖤𝖳 by treating p as the joint distribution of X,Y and q as the product of X and Y (we can simulate sample access to the product of X and Y with two samples from the joint distribution). Therefore, the existing lower bound from [37, Corollary 6.2] holds for our problem. The latter lower bound of Ω⁢(log2⁡nε2) comes from [15, Lemma 2.7], given the reduction from identity testing to equivalence testing.

1.2.3 Application to equivalence testing of Bayes nets

As laid out by [15], one can utilize testing entropy difference as a subroutine to testing Bayes nets. The key of the analysis is derived via the celebrated Chow-Liu decomposition [20]: If two Bayes nets p and q have similar local entropies, then they must share approximately similar structures (their corresponding DAGs are close in some sense; see [15, Lemma 3.4]). Once we confirm that they share a similar structure, the problem boils down to checking local (every subset of random variables of size at most d+1) KL-divergences. While KL-divergences are known to be untestable [24, Theorem 7] in the extreme cases when q⁢(x)=0, there is hope if one can obtain a lower bound on q⁢(x). In fact, we can reduce testing in KL to testing in Hellinger distance with an O⁢(max𝑥⁢log⁡p⁢(x)q⁢(x)) factor overhead using [37, Lemma 3.1]. To get a lower bound on q⁢(x), we use a standard technique of testing the mixture of q and the uniform distribution.

1.3 Related works

Estimating entropy.

Entropy estimation is a well-studied problem in both the information theory [41, 42, 31] and property testing [39, 3] communities, with the near-optimal sample complexity Θ⁢(nε⁢log⁡n+log2⁡nε2) being eventually established by [42, 31] (for discrete distributions). As we are considering the testing problem, our upper bound is less costly compared to its learning (estimation) variant. Moreover, other variants of entropy have been studied, such as Rényi entropy [2]. The more general problem of estimating functionals of distributions was also considered by [31].

Identity testing and closeness testing.

The standard formulation of identity testing asks the following problem: Given a full description of a hypothesis q, how many i.i.d. samples are needed from p to distinguish between p=q and dTV⁢(p,q)⩾ε, where p and q are both distributions over support of size [n]? This problem is well-known to have a sample complexity of Θ⁢(n/ε2), a much lower cost compared to fully learning every parameter of p, which takes Θ⁢(n/ε2) samples. A similar problem can be asked if one is instead only provided sample access to p and q, both unknown. This is the closeness testing problem (in TV) and it is known that a Θ⁢(max⁡{nε2,n2/3ε4/3}) sample complexity is necessary and sufficient, making this a slightly harder problem than identity testing while still saving on samples compared to fully learning p and q. Our problem differs from the standard formulation by testing in the entropy difference rather than in TV distance. Most relevant to our work is the work of [15], which solves the problem of entropy identity testing (up to polylogarithmic factors) with a sample complexity of Θ~⁢(nε+1ε2). Another relevant work is that of [24], which asks the question of testing in different distances, e.g., distinguishing between dKL⁢(p∥q)⩽ε2/100 and dH⁢(p,q)⩾ε for identity testing (sample access to p and the full description of q). Interestingly, as shown in the same work, equivalence testing in squared Hellinger distance, i.e., distinguishing between p=q and dH2⁢(p,q)⩾ε has a similar cost of Θ⁢(min⁡{n2/3ε4/3,n3/4ε}) (though perhaps not so surprising, as we are reducing to testing in squared Hellinger square in one of the cases we handle). Our work adds to their results for equivalence testing in entropy difference.

Testing mutual information.

Testing mutual information (𝖬𝖨) asks the following question: Given sample access to a (discrete) distribution p over two random variables X,Y with a domain of size |ΣX| and |ΣY| respectively, how many samples do we need from p to distinguish between I(X:Y)=0 and I(X:Y)⩾ε? The study of this problem was initiated by [9] to solve the problem of learning a special variant of Bayes net (trees). While their 𝖬𝖨 tester is sufficient for learning trees-structured distributions near-optimally, their upper bound is loose in terms of dependence on |ΣX| and |ΣY|: O⁢(|ΣX|⋅|ΣY|ε). More recently, [37] gave a near-optimal bound of Θ~⁢(min⁡{|ΣX|3/4⁢|ΣY|1/4ε,|ΣX|2/3⁢|ΣY|1/3ε4/3}) (assuming |ΣX|⩾|ΣY|). We note that this bound bears similarity (e.g., setting |ΣY|=O⁢(1)) to ours due to the close relation between 𝖬𝖨 and entropy: I(X:Y)=H(X)+H(Y)−H(X,Y). Indeed, 𝖬𝖨 testing can be reduced to 𝖤𝖤𝖳 naturally (as outlined above). Before these works, [4, 13] studied the problem of (conditional) independence testing in the TV distance.

Testing Bayesian networks.

A Bayesian network (Bayes net) is a high-dimensional distribution over n random variables that factorizes into n conditional probabilities: p⁢(X1,…,Xn)=∏i=1np⁢(Xi∣Πi), where Πi∈[n] is called the parent set of Xi. This factorization is associated with a directed acyclic graph (DAG) G=(V,E) (V={X1,…,Xn}), and if Xj∈Πi, then the edge (Xj,Xi)∈E (with Xj being one of Xi’s parents). A distribution p is called a Bayes net if its joint probability density function factorizes according to G and p is called Markov with respect to G. Learning Bayesian networks from samples is a fundamental problem in learning theory, and there is a plethora of evidence that this problem is hard computationally [18, 22, 7]. On the other hand, time-efficient algorithms (polynomial in n, the number of random variables) do exist in some special cases [19, 8, 9].

Identity testing and closeness testing of Bayes nets were systematically studied by [12], though their stronger upper bounds only consider relaxed version of Bayes nets where both p and q are required be balanced and non-degenerate. While they also provide a more general upper bound (without assuming balancedness and non-degeneracy for Bayes nets), they still require that the node ordering be the same between p and q, a non-trivial assumption. Our upper bound does not make any assumption other than the bounded in-degree d, which is a natural and necessary parameter to consider, since testing unbounded degree Bayes nets is exponentially hard: Ω⁢(2n/2ε2) (e.g., see [6, Theorem B.1]). The strongest upper bound that we are aware of is by [25], which can solve the identity testing444Note that their setting of identity testing actually corresponds to equivalence testing in our setting. problem in O~⁢(2d/2⁢nε2) samples,555Implicitly, using the Hellinger testing result of [24, Theorem 1]. under the assumption that p and q have the same structure (Markov with respect to the same DAG). For equivalence testing, under the same assumption, they give a bound of O~⁢(min⁡{23⁢d/4⁢nε2,22⁢d/3⁢n4/3ε8/3}).666Implicitly, using the optimal Hellinger equivalence test [24]. Our results match their bounds if d≫log⁡(n/ε), and our algorithm will work without the extra assumption that p and q share the same structure. A lower bound of Ω⁢(2d/2⁢nε2) when d⩽log⁡n [6, Theorem 4.1] holds for identity testing of Bayes nets and thus also for its closeness testing variant (our setting).

1.4 Preliminaries

Define the factorial moment by (x)m:=x!(x−m)!, which gives an unbiased estimator for the monomials of the Poisson mean: namely, if X∼Poi⁡(λ), then 𝔼⁢[(X)m]=λm for all m⩾0. More generally, we have the following fact, whose proof we provide in Appendix A for completeness:

Fact 5.

Let X be a Poisson random variable with parameter λ, and f:ℝ→ℝ be any function, then, we have that 𝔼⁢[(X)m⋅f⁢(X)]=λm⋅𝔼⁢[f⁢(X+m)]. In particular, choosing f≡1, we have that 𝔼⁢[(X)m]=λm for all m⩾0.

Fact 6 (Folklore).

For any 0<α⩽1/2 and ε∈(0,1], testing whether the bias of a coin is at most α or at least α⁢(1+ε), with probability at least 1−δ, can be done with n=O⁢(1α⁢ε2⁢log⁡1δ) samples.

Distances and norms.

We will use a number of standard distance measures for two distributions p,q over [n], and various known inequalities between them, e.g., see [36]. The squared Hellinger distance is

dH2⁢(p,q):=12⁢∑i∈[n](pi−qi)2

The total variation distance is dTV⁢(p,q):=12⁢‖p−q‖1=12⁢∑i∈[n]|pi−qi|. The ℓ2 distance is ‖p−q‖2:=(∑i∈[n](pi−qi)2)1/2, and the χ2-divergence of p from q is dχ2⁢(p,q):=∑i∈[n](pi−qi)2/qi. These satisfy the chain of inequalities

dTV⁢(p,q)⩽2⁢dH⁢(p,q)anddH2⁢(p,q)⩽dTV⁢(p,q)⩽dχ2⁢(p,q),

and the equivalence 12⁢∑i(pi−qi)2/(pi+qi)=Θ⁢(dH2⁢(p,q)). The Kullback–Leibler (KL) divergence is dKL⁢(p∥q):=∑ipi⁢log⁡(pi/qi), which satisfies dKL⁢(p∥q)⩽dχ2⁢(p,q) and Pinsker’s inequality dTV⁢(p,q)⩽dKL⁢(p∥q)/2.

Notation.

In what follows, for a given integer n⩾1, we denote by [n] the set [n]={1,2,…,n}, and by Un the uniform distribution on [n]. When clear from context, we will omit the subscript, and write U instead of Un. Given a probability distribution p over [n] and a set S⊆[n] such that p⁢(S)>0 we write p(⋅∣S) for the conditional distribution of p on S. For the high dimensional (Bayes net) section, we use pT to denote the marginalization of p over T, where T is a subset of {X1,…,Xn}, e.g., pX1,X2 denotes the marginal distribution of (X1,X2). We also use Πi to denote the parent set of the random variable Xi in a Bayes net.

Throughout the paper, we use log for the natural logarithm, and adopt the standard asymptotic notation O⁢(⋅),Ω⁢(⋅),Θ⁢(⋅), as well as the closely related O~⁢(⋅),Ω~⁢(⋅),Θ~⁢(⋅), which hide polylogarithmic factors in their argument.

2 An 𝑶~⁢(𝒏𝟑/𝟒𝜺+𝐥𝐨𝐠𝟐⁡(𝒏/𝜺)𝜺𝟐) Upper Bound for EET

In this section, we establish our main theorem, Theorem 1. We begin with a simple algorithmic “trick” that allows us to reduce the task to one where both p,q put at least some minimum probability η>0 on every element of the domain:

Lemma 7.

Let p,q be distributions over [n], and set η:=ε/(4⁢log⁡(n/ε)). Let p~:=(1−η)⁢p+η⁢U and likewise for q~. Then p~i,q~i⩾ε/(4⁢n⁢log⁡(n/ε)) for every i∈[n], and

||H⁢(p~)−H⁢(q~)|−|H⁢(p)−H⁢(q)||⩽ε/2.

Moreover, one sample from p~ (resp. q~) can be simulated from one sample from p (resp. q).

Proof.

Since dTV⁢(p,p~)⩽η2=ε8⁢log⁡(n/ε), by invoking the bound on entropy difference with respect to TV distance in [21, Lemma 2.7], we get

|H⁢(p)−H⁢(p~)|⩽ε8⁢log⁡(n/ε)⁢log⁡(n⋅8⁢log⁡(n/ε)ε)=ε⋅log⁡(n/ε)+log⁡(8⁢log⁡(n/ε))8⁢log⁡(n/ε)⩽ε/4.

Similarly, we have |H⁢(q)−H⁢(q~)|⩽ε/4. By the triangle inequality, we then have

|H⁢(p~)−H⁢(q~)|⩽|H⁢(p)−H⁢(p~)|+|H⁢(q)−H⁢(q~)|+|H⁢(p)−H⁢(q)|⩽ε/2+|H⁢(p)−H⁢(q)|,

and

|H⁢(p)−H⁢(q)|⩽|H⁢(p~)−H⁢(q~)|+|H⁢(p)−H⁢(p~)|+|H⁢(q)−H⁢(q~)|⩽ε/2+|H⁢(p~)−H⁢(q~)|,

establishing the lemma. ◀ Of course, if p=q, then p~=q~; Lemma 7 guarantees that if |H⁢(p)−H⁢(q)|⩾ε, then |H⁢(p~)−H⁢(q~)|⩾Ω⁢(ε). That is, p~,q~ satisfy the promise with the same ε (up to constants) whenever p,q do, so we can henceforth assume that mini∈[n]⁡pi,mini∈[n]⁡qi⩾ε4⁢n⁢log⁡(n/ε). With this in hand, we are ready to establish our main theorem, restated, as follows:

Theorem 8 (Theorem 1, restated).

There exists an algorithm (Algorithm 1) which, given sample access to two unknown probability distributions p,q over a known domain [n], as well as parameter ε∈(0,1/2], takes

O⁢(n3/4⁢log⁡(n/ε)⋅log⁡nε+log2⁡(n/ε)ε2)

samples from both p and q, and has the following guarantees:

  • ■

    If p=q, then the algorithm outputs accept with probability at least 9/10;

  • ■

    If |H⁢(p)−H⁢(q)|⩾ε, then the algorithm outputs reject with probability at least 9/10.

Further, the algorithm runs in time O⁢(N⁢log⁡N), where N is the total number of samples.

Algorithm 1 Entropy equivalence testing (𝖤𝖤𝖳).

The remainder of this section is dedicated to proving this theorem, which we do via a series of lemmas.

The first lemma relates a difference in entropy to a difference in (squared) Hellinger distance and a cross entropy term with respect to a mixture:

Lemma 9.

For any two distributions p,q over [n], we have

|H⁢(p)−H⁢(q)|⩽Θ⁢(dH2⁢(p,q))+|∑i=1n(pi−qi)⁢log⁡1(pi+qi)/2|.
Proof.

Letting r≔p+q2, we can write

H⁢(p)−H⁢(q)
=∑i(pi⁢log⁡1pi−qi⁢log⁡1qi)
=∑i(−pi⁢log⁡pi(pi+qi)/2+pi⁢log⁡1(pi+qi)/2+qi⁢log⁡qi(pi+qi)/2−qi⁢log⁡1(pi+qi)/2)
=dKL⁢(q∥r)−dKL⁢(p∥r)+∑i(pi⁢log⁡1(pi+qi)/2−qi⁢log⁡1(pi+qi)/2)
=dKL⁢(q∥r)−dKL⁢(p∥r)+∑i(pi−qi)⁢log⁡1(pi+qi)/2.

We then observe that

dKL⁢(q∥r)⩽dχ2⁢(q,r)=∑i(qi−pi+qi2)2pi+qi2=∑i12⁢(pi−qi)2pi+qi=Θ⁢(dH2⁢(p,q)),

where the last equality comes from the equivalence of between Hellinger distance and Triangle distance (e.g., see [24, Proposition 3]).777Note that the induced KL terms have been studied in information theory (called Jensen-Shannon divergence; see e.g., [33, Chapter 7] and more systematically in [38], where they actually show that the Jensen-Shannon divergence and the Triangle distance are equivalent up to constant factors). Similarly, we have that dKL⁢(p∥r)⩽dχ2⁢(p,r)=Θ⁢(dH2⁢(p,q)), and we conclude that

|H⁢(p)−H⁢(q)| ⩽|dKL(q∥r)|+|dKL(p∥r)|+|∑i(pi−qi)log1(pi+qi)/2|
⩽Θ⁢(dH2⁢(p,q))+|∑i(pi−qi)⁢log⁡1(pi+qi)/2|,

as claimed. ◀ Lemma 9 allows us to split the entropy difference |H⁢(p)−H⁢(q)| into a Hellinger part and a term |∑i(pi−qi)⁢log⁡(1/((pi+qi)/2))|, so that an entropy difference ε implies at least one of these two terms must be ε/2: thus, it suffices to test both, and reject if, and only if, at least one of them is detected to be Ω⁢(ε). (Clearly, if p=q, both the Hellinger and KL-like terms are zero.)

The Hellinger term can be tested with O~⁢(n3/4/ε) samples using a Hellinger closeness tester (e.g., [28, Proposition 2.15]): if dH2⁢(p,q)⩾Ω⁢(ε), this tester will allow us to reject with high probability. For the rest of the subsection we therefore can assume dH2⁢(p,q)⩽O⁢(ε), and the task reduces to testing the second, “KL-like” term,

Λ⁢(p,q)≔|∑i(pi−qi)⁢log⁡1(pi+qi)/2|, (1)

and specifically to distinguish Λ⁢(p,q)=0 from Λ⁢(p,q)⩾ε2.

To do so, the idea is to handle separately the set S∗ of “heavy” elements, on which either p or q puts relatively high probability (specifically, at least some threshold τ≔Ω~⁢(ε/n3/4)), and the remaining set S∗¯=[n]∖S∗ of “light” elements (which have low probability under both p and q). Of course, we do not know this set S∗, as both p,q are unknown; however, by taking O~⁢(1/τ)=O~⁢(n3/4/ε) samples (which is inconsequential, as we will pay this sample complexity for the Hellinger test anyway), we can obtain a set S which is a good proxy for S∗. To make this formal, define the following two sets:

S1 :={i∈[n]∣pi+qi⩾C1⋅εn3/4⁢log⁡(n/ε)}.
S2 :={i∈[n]∣pi+qi⩾C2⋅εn3/4⁢log⁡(n/ε)},

where C2⩾C1>0 are two absolute constants. Our focus is to identify a set S⊆[n] such that S2⊆S⊆S1.

Lemma 10.

Using O⁢(n3/4⁢log⁡(n/ε)⁢log⁡nε) samples from p and q, one can efficiently return a set S satisfying S2⊆S⊆S1 with probability at least 99100.

Proof.

By Fact 6, choosing 2⁢C1⩽C2, as we have sample access to the uniform mixture p+q2, we can distinguish pi+qi2⩾C2⋅ε2⁢n3/4⁢log⁡(n/ε) and pi+qi2⩽C1⋅ε2⁢n3/4⁢log⁡(n/ε) with probability 1−1100⁢n costing O⁢(n3/4⁢log⁡(n/ε)⋅log⁡nε) samples from p and q. Therefore, running the test over the support [n] (using the same set of samples to run this test for all i’s) and adding each i∈[n] to the set S if we detect pi+qi⩾C2⋅εn3/4⁢log⁡(n/ε), by a union bound, the algorithm will be simultaneously correct on all i∈[n] with probability at least 99100. ◀ To summarize, once we have identified such a set S, given that

Λ⁢(p,q)⏟0⁢ or ⩾ε2⩽|∑i∈S¯(pi−qi)⋅log⁡1pi+qi|⏟≕ΛS¯⁢(p,q)+|∑i∈S(pi−qi)⋅log⁡1pi+qi|⏟≕ΛS⁢(p,q)

it suffices to separately test (1) ΛS¯⁢(p,q)=0 vs. ΛS¯⁢(p,q)⩾ε/4, and (2) ΛS⁢(p,q)=0 vs. ΛS⁢(p,q)⩾ε/4; we do so below, assuming that our set S satisfies S2⊆S.888For simplicity of exposition, we henceforth ignore the factor 4, and consider ε instead of ε/4; a simple rescaling argument gives the original guarantees.

Test 1: 𝚲𝑺¯⁢(𝒑,𝒒)=𝟎 vs. 𝚲𝑺¯⁢(𝒑,𝒒)⩾𝜺

Inspired by the ideas of [28], we can then check if the distributions are far in TV distance in the low-probability regime (i.e., elements in S¯), which will suffice by a simple reduction from entropy difference to TV (using the lower bound mini⁡pi,mini⁡qi⩾Ω~⁢(ε/n)). In more detail, we have

|∑i∈S¯(pi−qi)⋅log⁡1pi+qi|⩽∑i∈S¯|pi−qi|⋅log⁡1pi+qi⩽O⁢(log⁡(n/ε))⋅∑i∈S¯|pi−qi|.

While this is a task that would in general require a large number of samples, here we can leverage the additional fact that S¯ does not contain any heavy elements.

Lemma 11.

Let T⊆[n] be a set such that maxi∈T⁡(pi+qi)⩽C2⋅εn3/4⁢log⁡(n/ε). Then, testing pT=qT versus ∑i∈T|pi−qi|⩾εlog⁡(n/ε) (with probability of success 9/10) can be done with O⁢(n3/4⋅log⁡(n/ε)/ε) samples from p,q.

Proof.

By [28], we know that O~⁢(n3/4ε) samples suffice to distinguish pT=qT from dTV⁢(pT,qT)⩾ε with high constant probability. For the sake of completeness, we briefly explain how to adapt their argument to our setting. First, it takes O⁢(log⁡(n/ε)ε) samples to check whether the mass of p on T is larger than Ω⁢(ε/log⁡(n/ε)), and similarly for q: if both have mass smaller that this, we accept, as ∑i∈S¯|pi−qi|⩽p⁢(T)+q⁢(T)<εlog⁡(n/ε). If only one of the two puts large enough mass on T, we reject, as this shows that ∑i∈T|pi−qi|≠0. Otherwise, both p,q put enough mass on T, and we continue.

With O⁢(log2⁡(n/ε)ε2) samples, we then confirm that their probability masses on T approximately match, i.e., that |p⁢(T)−q⁢(T)|⩽O⁢(εlog⁡(n/ε)). If they do not, we can output reject. Otherwise, we have

∑i∈T|pi−qi| =∑i∈T|p(i|i∈T)p(T)−q(i|i∈T)q(T)|
⩽∑i∈T(|p(i|i∈T)p(T)−p(i|i∈T)q(T)|+|p(i|i∈T)q(T)−q(i|i∈T)q(T)|)
=|p(T)−q(T)|+q(T)⋅∥p(⋅|T)−q(⋅|T)∥1.

Thus, if ‖pT−qT‖⩾Ω⁢(εlog⁡(n/ε)) and |p⁢(T)−q⁢(T)|⩽O⁢(εlog⁡(n/ε)) (for suitable choice of constants in the O⁢(⋅), Ω⁢(⋅)), then we have that

dTV(pT,qT)=12∥p(⋅|T)−q(⋅|T)∥1⩾Ω(εq⁢(T)⋅log⁡(n/ε)).

Recalling that q⁢(T),p⁢(T)⩾εlog⁡(n/ε) and q⁢(T)=Θ⁢(p⁢(T)), we can sample from pT,qT via rejection sampling at the cost of an expected O⁢(1/q⁢(T)), O⁢(1/p⁢(T)) factor in the sample complexity. Thus, we can use an off-the-shelf TV equivalence tester (e.g., from [17, Theorem 1]) to test dTV(p(⋅|T),q(⋅|T))⩾Ω(εq⁢(T)⋅log⁡(n/ε)) vs. p(⋅|T)=q(⋅|T) at the cost of

max⁡{n2/3⁢q4/3⁢(T)⁢log4/3⁡(n/ε)ε4/3,n1/2⁢q2⁢(T)⁢log2⁡(n/ε)ε2}

samples from p(⋅|T),q(⋅|T); which, by the above discussion, requires an expected

max⁡{n2/3⁢q1/3⁢(T)⁢log4/3⁡(n/ε)ε4/3,n1/2⁢q⁢(T)⁢log2⁡(n/ε)ε2}

samples from p,q (which can be made high-probability via Markov’s inequality, paying a constant factor in the sample complexity and a small additional probability of failure). Since q⁢(T)⩽εn3/4⁢log⁡(n/ε)⋅n=ε⋅n1/4log⁡(n/ε), we finally conclude that taking O⁢(n3/4⋅log⁡(n/ε)ε) samples suffices. ◀

Test 2: 𝚲𝑺⁢(𝒑,𝒒)=𝟎 vs. 𝚲𝑺⁢(𝒑,𝒒)⩾𝜺

We now look at the second – and more involved – case, namely, detecting when the entropy difference is far in the high mass regime. That is, we are testing ΛS⁢(p,q)=0 vs. ΛS⁢(p,q)⩾ε.

We will define a suitable test statistic, Z, and analyze its expectation (with the goal of bounding its bias and relate it to ΛS⁢(p,q)), before bounding its variance to conclude with an application of Chebyshev’s inequality. At a high level, our strategy is as follows: either the empirical entropy difference Z has low bias, which means we can simply rely on its output for the test, or it has high bias, in which case this can be detected by performing additional checks to detect this bias.

Let m=O~⁢(n3/4ε+log⁡(n/ε)ε2) be the number of samples taken from p,q, and assume the Poissonized setting: that is, instead of exactly m samples, we take a random Poi⁡(m) number of samples.999This standard technique is valid as it only affects the sample complexity by constant terms and an arbitrarily small error probability adjustment, since a Poisson random variable tightly concentrates around its mean. Its advantage is to provide additional independence between the empirical counts of each element, which is useful in the analysis. Recall that by construction of the set S⊆S1, we can assume pi+qi⩾Ω~⁢(εn3/4) for all i∈S. Focusing on S, we run two further checks, each at cost O⁢(log2⁡m/ε2):

  1. 1.

    |p⁢(S)−q⁢(S)|⩽O⁢(ε/log⁡m), which implies |∑i∈S(pi−qi)|⁢log⁡m⩽O⁢(ε).

  2. 2.

    ‖p−q‖22⩽O⁢(ε2/log2⁡m), which is checked via testing at distance ε/log⁡m using an ℓ2-closeness tester (e.g., via learning p,q in ℓ2 distance, see for instance [16]).

If either check rejects, we reject; otherwise we proceed assuming both guarantees hold.

Letting Xi (resp. Yi) be the number of occurrences of element i∈S among the samples from p (resp. from q), we define our entropy difference estimator to be

Z:=∑i∈SXi−Yim⁢log⁡1Xi+Yi,

and we write Zi:=Xi−Yim⁢log⁡1Xi+Yi for the i-th summand and let Zi=0 when Xi+Yi=0. By the above Poissonization procedure, we have Xi∼Poi⁡(m⋅pi) and Yi∼Poi⁡(m⋅qi) for all i, and the (Xi)i (resp. (Yi)i) are independent. We first bound the bias of this estimator Z:

Lemma 12.

For any set S⊆[n],

|∑i∈S(pi−qi)⁢log⁡1m⁢(pi+qi)−𝔼⁢[Z]|⩽∑i∈S|pi−qi|m⁢(pi+qi).
Proof.

Let Ji:=Xi+Yi∼Poi⁢(λi) with λi:=m⁢(pi+qi). Conditional on Ji=j, the count Xi is Bin⁢(j,pi/(pi+qi))-distributed, so 𝔼⁢[Xi−Yi∣Ji]=Ji⋅(pi−qi)/(pi+qi). By the law of total expectation, pulling the factor log⁡(1/Ji) outside the inner expectation,
𝔼⁢[Zi]=1m⁢𝔼⁢[(Xi−Yi)⁢log⁡1Ji]=1m⁢𝔼⁢[log⁡1Ji⋅𝔼⁢[Xi−Yi∣Ji]]=pi−qim⁢(pi+qi)⁢𝔼⁢[Ji⁢log⁡(1/Ji)].

We then apply the Poisson identity (Fact 5) 𝔼⁢[Ji⁢f⁢(Ji)]=λi⁢𝔼⁢[f⁢(Ji+1)], taking f⁢(j)=log⁡(1/j):

𝔼⁢[Zi]=pi−qim⁢(pi+qi)⋅λi⁢𝔼⁢[log⁡(1/(Ji+1))]=−(pi−qi)⁢𝔼⁢[log⁡(Ji+1)].

Subtracting the target (pi−qi)⁢log⁡(1/λi),

(pi−qi)⁢log⁡1λi−𝔼⁢[Zi]=(pi−qi)⁢𝔼⁢[log⁡Ji+1λi].

We proceed to bound 𝔼⁢[log⁡((Ji+1)/λi)] from above and below. By Jensen’s inequality applied to the concave function log,

𝔼⁢[log⁡Ji+1λi]⩽log⁡(1+1λi)⩽1λi.

For the lower bound, the inequality log⁡x⩾1−1/x applied to x=(Ji+1)/λi, together with 𝔼⁢[1/(Ji+1)]=(1−e−λi)/λi for Ji∼Poi⁢(λi), gives

𝔼⁢[log⁡Ji+1λi]⩾1−λi⁢𝔼⁢[1Ji+1]=e−λi⩾0.

Combining these findings gives |𝔼⁢[log⁡((Ji+1)/λi)]|⩽1/λi (using e−λi⩽1/λi for all λi>0), so

|(pi−qi)⁢log⁡1λi−𝔼⁢[Zi]|⩽|pi−qi|λi.

Summing over i∈S yields the claim. ◀

The bias of our estimator is determined by the RHS of Lemma 12; note that if p=q, the RHS simplifies to 0. As a result, a natural idea would be to use this RHS as a proxy, and to check if the RHS is noticeably large using another test: if it is larger than ⩾Ω⁢(ε), we can immediately reject, as this is clear evidence that p≠q. We do so in the following lemma:

Lemma 13.

Suppose that dH2⁢(p,q)⩽O⁢(ε). Then, with s=O⁢(n3/4⁢log⁡(n/ε)/ε) samples from p,q, one can distinguish between the following two cases with high constant probability:

  1. 1.

    p=q (which implies ∑i∈S|pi−qi|m⁢(pi+qi)=0).

  2. 2.

    ∑i∈S|pi−qi|(pi+qi)⩾Ω⁢(m⁢ε).

Proof.

We use the test statistic

T≔∑i∈S(Xi−Yi)2−(Xi+Yi)Xi+Yi,

where Xi∼Poi⁡(s⋅pi) and Yi∼Poi⁡(s⋅qi). We show:

  • ■

    In the first case, 𝔼⁢[T]=0, while in the second case 𝔼⁢[T]⩾Ω⁢(n).

  • ■

    Var⁢[T]⩽O⁢(n) in both cases.

Chebyshev’s inequality then will enable us to separate the two cases by thresholding T at a value scaling as Θ⁢(n).

Analyzing 𝔼⁢[𝑻].

The first part is similar to the analysis from [17, Lemma 4], which relies on the same statistic T (for a different purpose): write δi:=(pi−qi)/(pi+qi) and Ji:=Xi+Yi. Conditional on Ji=j, we have Yi=j−Xi so Xi−Yi=2⁢Xi−j, and Xi∼Bin⁢(j,pi/(pi+qi)). Hence,

𝔼⁢[Xi−Yi∣Ji=j]=j⁢δi,

and the binomial variance Var⁢[Xi∣Ji=j]=j⋅pi⁢qi(pi+qi)2 gives

Var⁢[Xi−Yi∣Ji=j]=4⁢j⋅pi⁢qi(pi+qi)2=j⁢(1−δi2).

Combining, 𝔼⁢[(Xi−Yi)2∣Ji=j]=Var⁢[Xi−Yi∣Ji=j]+𝔼⁢[Xi−Yi∣Ji=j]2=j⁢(1−δi2)+j2⁢δi2. The i-th summand of T is (Xi−Yi)2−JiJi, which we set to 0 when Ji=0 (the 0/0 case). For Ji=j⩾1,

𝔼⁢[(Xi−Yi)2−JiJi|Ji=j]=(j2−j)⁢δi2j=(j−1)⁢δi2.

Taking the outer expectation, with the indicator 𝟏⁢{Ji⩾1} enforcing the 0/0 convention,

𝔼⁢[T]=∑i∈Sδi2⋅𝔼⁢[(Ji−1)⁢𝟏⁢{Ji⩾1}]=∑i∈Sδi2⁢(λi−1+e−λi),

where 𝔼⁢[(Ji−1)⁢𝟏⁢{Ji⩾1}]=𝔼⁢[Ji]−Pr⁡[Ji⩾1]=λi−(1−e−λi).

In particular, in the first case (when p=q), δi=0 for every i∈S, and so 𝔼⁢[T]=0. We therefore now focus on the second case, for which we depart from [17]. By the construction of S (Lemma 10), pi+qi⩾Ω⁢(εn3/4⁢log⁡(n/ε)) for every i∈S, so choosing s=Ω⁢(n3/4⋅log⁡(n/ε)/ε) with a sufficiently large constant gives λi=s⁢(pi+qi)⩾2 for all i∈S. The bound λ−1+e−λ⩾λ−1⩾λ/2 for λ⩾2 then yields

𝔼⁢[T]⩾12⁢∑i∈Sλi⁢δi2=s2⁢∑i∈S(pi−qi)2pi+qi.

By Cauchy–Schwarz,

∑i∈S(pi−qi)2pi+qi⩾1n⁢(∑i∈S|pi−qi|pi+qi)2.

Since m⁢(pi+qi)⩾1 (in view of i∈S and m=Ω~⁢(n3/4ε)), we have 1pi+qi⩾1m⁢(pi+qi). Applying this termwise and using the definition of the second case,

∑i∈S|pi−qi|pi+qi⩾1m⁢∑i∈S|pi−qi|pi+qi⩾Ω⁢(m⁢ε).

Combining,

𝔼⁢[T]⩾s2⁢n⋅Ω⁢(m⁢ε2)=Ω⁢(s⁢m⁢ε2n),

which is Ω⁢(n+log2⁡(n/ε)n1/4⁢ε)⩾Ω⁢(n) given the settings of s=Θ~⁢(n3/4/ε) and m=Θ~⁢(n3/4/ε+log2⁡(n/ε)ε2).

Upper bound on 𝐕𝐚𝐫⁢[𝑻].

The variance bound from [17, Lemma 5] gives

Var⁢[T]⩽2⁢min⁡{n,s}+5⁢s⁢∑i∈S(pi−qi)2pi+qi.

Under the lemma’s assumption on the Hellinger distance, ∑i∈S(pi−qi)2/(pi+qi)=Θ⁢(dH2⁢(p,q))⩽O⁢(ε), so the second term is O~⁢(s⋅ε), and Var⁢[T]⩽O⁢(n+s⋅ε), where s=O~⁢(n3/4/ε). This scaling of s leads to the simplified bound Var⁢[T]⩽O⁢(n).

Concluding via Chebyshev.

In the first case, 𝔼⁢[T]=0 and Var⁢[T]⩽O⁢(n), so |T|⩽O⁢(n) with probability ⩾9/10. In the second case, 𝔼⁢[T]⩾C⁢n and Var⁢[T]⩽O⁢(n)⩽𝔼⁢[T]2/C′, so T⩾C′′⁢n with probability ⩾9/10. Thresholding at Θ⁢(n) thus distinguishes the two cases. ◀

Having used the RHS of Lemma 12 as a proxy for the bias, and checked that it is small (and rejected otherwise), we are not yet done: we could still have both small bias for Z (so that 𝔼⁢[Z]≈∑i∈S(pi−qi)⁢log⁡1m⁢(pi+qi)) and large ΛS⁢(p,q)=|∑i∈S(pi−qi)⁢log⁡1m⁢(pi+qi)|. However, now, since we know that |𝔼⁢[Z]|≈ΛS⁢(p,q), to conclude it suffices to run one last check: namely, that Z is small enough.

Indeed, we know now that Z has small bias: if we can also show, via a variance argument, that Z concentrates around its expectation, then we will have |Z|≈w.h.p.|𝔼⁢[Z]|≈ΛS⁢(p,q), and checking that |Z| is small will ensure (with high probability) that we can guarantee that ΛS⁢(p,q) is small. Thus, our last missing piece is an upper bound on Var⁡[Z], which will let us show that Z concentrates around its expectation.

Lemma 14.

The variance of the entropy difference estimator Z satisfies

Var⁡[Z]⩽O⁢(log2⁡m)⁢‖p−q‖22+log2⁡mm⩽O⁢(ε2).
Proof.

Under Poissonization, the counts {Xi}i∈S and {Yi}i∈S are mutually independent across coordinates. As a result, the Zi’s are also independent, and

Var⁢[Z]=∑i∈SVar⁢[Zi]⩽∑i∈S𝔼⁢[Zi2].

Fix any i∈S, letting Ji:=Xi+Yi∼Poi⁢(m⁢(pi+qi)), and defining the event ℰi:={Ji⩽3⁢m}. Since m⁢(pi+qi)⩽m, the Chernoff bound for Poisson random variables gives Pr⁡[ℰic]⩽e−Ω⁢(m). Then:

  • ■

    On ℰi: |log⁡(1/Ji)|⩽log⁡(3⁢m) for Ji≠0, and noting from before that Zi=0 when Ji=0, we have |Zi|⁢ 1ℰi⩽log⁡(3⁢m)m⁢|Xi−Yi|. Squaring and taking expectations,

    𝔼⁢[Zi2⁢ 1ℰi]⩽log2⁡(3⁢m)m2⁢𝔼⁢[(Xi−Yi)2]=log2⁡(3⁢m)m2⁢(m⁢(pi+qi)+m2⁢(pi−qi)2),

    using Var⁢[Xi−Yi]=m⁢(pi+qi) and 𝔼⁢[Xi−Yi]=m⁢(pi−qi) (moments of Poisson r.v.’s).

  • ■

    On ℰic: from |Xi−Yi|⩽Ji and |log⁡(1/Ji)|=log⁡Ji⩽Ji (valid since Ji>3⁢m⩾1), we get |Zi|⁢ 1ℰic⩽Ji2/m. Combining Cauchy–Schwarz with the moment bound 𝔼⁢[Ji8]=O⁢(m8) (since Poisson moments are polynomials in the mean, by Fact 5) and the tail bound Pr⁡[ℰic]⩽e−Ω⁢(m),

    𝔼⁢[Zi2⁢ 1ℰic]⩽1m2⁢𝔼⁢[Ji4⁢ 1ℰic]⩽1m2⁢𝔼⁢[Ji8]⁢Pr⁡[ℰic]⩽e−Ω⁢(m).

Summing over i∈S, using log2⁡(3⁢m)⩽4⁢log2⁡m (for m⩾3) and ∑i(pi+qi)⩽2,

Var⁢[Z]⩽O⁢(log2⁡m)⁢‖p−q‖22+O⁢(log2⁡m)m+n⋅e−Ω⁢(m).

The last term is absorbed into O⁢(log2⁡mm) since m⩾log⁡n makes n⋅e−Ω⁢(m)⩽1/m. ◀ Combining Lemma 12 and Lemma 13, and conditioning on all tests passing, the expectation of Z has small bias:

|𝔼⁢[Z]−∑i(pi−qi)⁢log⁡1(pi+qi)|⩽O⁢(ε).

By Lemma 14, Var⁢[Z]⩽O⁢(ε2), so Chebyshev gives |Z−𝔼⁢[Z]|⩽O⁢(ε) with probability at least 9/10. Combining via the triangle inequality,

Pr⁡[|Z−∑i(pi−qi)⁢log⁡1(pi+qi)|⩽O⁢(ε)]⩾910.
To conclude this subcase.

We choose a threshold for |Z| at a suitable constant multiple of ε that distinguishes the two cases. If Λ⁢(p,q)=|∑i∈S(pi−qi)⁢log⁡1(pi+qi)|=0, then with probability at least 9/10 the test on T from Lemma 13 will not reject and |Z|⩽O⁢(ε), and so this overall test accepts. If dH2⁢(p,q)⩽O⁢(ε) and |∑i∈S(pi−qi)⁢log⁡1(pi+qi)|⩾Ω⁢(ε), then with probability at least 9/10 either the test on T from Lemma 13 rejects, or it does not and then |Z|⩾Ω⁢(ε), and this overall test rejects.

Wrapping up

Putting the above ingredients together:

  • ■

    If p=q, then with high constant probability, (1) the Hellinger test on dH⁢(p,q) accepts, and (2) (a) the set S is correctly identified, (b) the test on ΛS¯⁢(p,q) accepts, (c) (i) the test on T (checking for low bias for Z) accepts, and (ii) the test on Z (test on ΛS⁢(p,q) assuming low bias for Z) accepts. Overall, the algorithm accepts with probability at least 9/10 by a union bound.

  • ■

    If |H⁢(p)−H⁢(q)|⩾ε, then with high constant probability (1) either the Hellinger test on dH⁢(p,q) rejects; or it accepts because dH⁢(p,q) is small, in which case Λ⁢(p,q) must be large; then, with high constant probability (2) (a) the set S is correctly identified, (b) the test on ΛS¯⁢(p,q) rejects, or it accepts because ΛS¯⁢(p,q) is small, which means ΛS⁢(p,q) must be large: in which case (c) (i) the test on T (checking for low bias for Z assuming dH⁢(p,q) is small) rejects, or it accepts because the bias is small, in which case (ii) the test on Z (test on ΛS⁢(p,q) assuming low bias for Z) rejects. Overall, the algorithm rejects with probability at least 9/10 by a union bound.

Overall, each subtest in Algorithm 1 uses no more than O⁢(n3/4⁢log⁡(n/ε)⁢log⁡nε) or O⁢(log2⁡(n/ε)ε2) samples, and hence the total sample complexity of our algorithm is

O⁢(n3/4⁢log⁡(n/ε)⁢log⁡nε+log2⁡(n/ε)ε2).

All our test statistics can be computed in O⁢(n) time once all Xi,Yi are collected.101010The statistics for testing Hellinger square is the same as T (albeit with different threshold; see [24, Theorem 5]). T can be computed in O⁢(n) time once all Xi, Yi are known. Computing S←{i∈[n]:Xi+Yi⩾Ω⁢(m1⋅ε/(n3/4⁢log⁡(n/ε)))} can be done in O⁢(n) time and calculating the empirical of S can be implemented in O⁢(m2) time. As for the conditional TV tester, the rejection sampling will cost as many samples as we take in total, and for TV closeness testing we use the same statistic T (see, e.g., [24, Theorem 4]). For ℓ2 tester, the statistic is also computable in O⁢(n) time [17, Section 3]. Assuming that we can compute log⁡(x) in constant time, one can compute the statistic Z in O⁢(n) time. To compute Xi,Yi, one can first sort over all samples which takes O⁢(s⁢log⁡s) time, where s is the number of samples in one of the subtests, and then sum them up. Thus, the time complexity of our algorithm is O⁢(N⁢log⁡N), where N is the total number of samples. This concludes the proof of Theorem 8.

3 Bayesian Network Equivalence Testing

In this section, we show how to leverage our Entropy Equivalence Testing (𝖤𝖤𝖳) algorithm (Algorithm 2) to obtain an equivalence testing (closeness testing) algorithm for bounded-degree Bayesian networks (Bayes nets). Specifically, the problem we consider is the following:

Bayes-Net Equivalence Testing: Given sample access to distributions p,q over {0,1}n, each Markov with respect to a DAG of in-degree at most d (the DAG is unknown, and possibly distinct between p and q), and parameters ε∈(0,1/2] and δ∈(0,1], distinguish, with probability at least 1−δ, between the following two cases: (1) p=q, and (2) dTV⁢(p,q)≥ε.

Definition 15.

A projection of a Bayes net p on {0,1}n onto a DAG G is denoted by pG, and is defined by its probability mass function (PMF) as follows:

pG⁢(X1,…,Xn)=∏i=1np⁢(Xi∣ΠiG),

where ΠiG is the set of parents of Xi in G. Moreover, with a slight abuse of notation, we write pXi,Πi or pXi,Πi⁢(xi,πi) for the marginal distribution of p on the subset {Xi,Πi}.

The baseline here is the testing-by-learning approach, whereby one learns the two unknown in-degree d Bayes nets to TV distance ε3 and checks the distance between the two learned hypotheses. It is known that learning an in-degree d Bayes net in total variation distance can be done in O~⁢(2d⁢n/ε2) samples (see [12, Appendix A]): to the best of our knowledge, the time complexity of any learning algorithm achieving this bound is exponential, namely, 2Ω~⁢(n). In contrast, we obtain a testing algorithm with drastically better running time (for all d=o⁢(n)), and significantly better sample complexity whenever d≫log⁡(n/ε2).

Theorem 16 (Theorem 4, restated).

There exists an algorithm (Algorithm 2) that, given sample access to two Bayesian networks p and q over {0,1}n with in-degree at most d, as well as a parameter ε∈(0,1], takes

s=O~⁢(min⁡{23⁢d/4⁢nε2,22⁢d/3⁢n4/3ε8/3}+n2ε4),

samples from p,q, and distinguishes with probability at least 2/3 between (1) p=q and (2) dTV⁢(p,q)⩾ε. Moreover, the algorithm runs in time O~⁢(nd+1⁢s).

Algorithm 2 Closeness testing for Bayesian networks.
Proof.

The pseudocode is provided in Algorithm 2. Due to space constraints, we defer the proof of correctness to the full version [14]. ◀

▶ Remark 17.

We have an interesting dichotomy: our algorithm is efficient (polynomial in n) only if d is constant. However, it is worse than its learning counterpart when d is constant: n2 (our test) vs. n (learning). On the other hand, if d=Ω⁢(log⁡n), then our tester will be more efficient than learning sample-wise, but its runtime becomes nΩ⁢(log⁡n), and is thus quasi-polynomial.

As identity testing is a special case of closeness testing, our above analysis can straightforwardly be ported to yield an identity testing algorithm (using an algorithm for identity testing in Hellinger instead of a closeness one as the first building block). An immediate consequence of this is to yield an improved identity tester for Bayes net with sample complexity O~⁢(2d/2⁢nε2+n2ε4), thus improving on the prior bound O~⁢(2d/2⁢n3/2ε2+n2ε4) [15, Theorem 1.2].

Corollary 18.

Given sample access to a Bayesian networks p and a full description of Bayesian network q over {0,1}n with in-degree at most d, as well as a parameter ε∈(0,1], there is an algorithm that takes

s=O~⁢(2d/2⁢nε2+n2ε4),

samples from p, and distinguishes with probability at least 2/3 between (1) p=q and (2) dTV⁢(p,q)⩾ε. Moreover, the algorithm runs in time O~⁢(nd+1⁢s).

4 Lower Bound

In this section, we establish our sample complexity lower bound for 𝖤𝖤𝖳 (Theorem 3). The Ω~⁢(min⁡{n3/4/ε,n2/3/ε4/3}) term follows from a reduction to mutual information (𝖬𝖨) testing combined with [37, Corollary 6.2], and the Ω⁢(log2⁡n/ε2) term follows directly from [15, Lemma 2.7], whose two-point construction is also a hard instance for 𝖤𝖤𝖳.

For a joint distribution PA⁢C over [kA]×[kC] with marginals PA,PC, the mutual information between coordinates is

I(A:C):=H(A)+H(C)−H(A,C),

and equals zero if and only if PA⁢C=PA⊗PC. The 𝖬𝖨 testing problem asks, given sample access to PA⁢C, to distinguish I(A:C)=0 from I(A:C)⩾ε with probability at least 2/3. [37, Corollary 6.2] established the lower bound

Ω~⁢(min⁡{kA3/4⁢kC1/4ε,kA2/3⁢kC1/3ε4/3})

for this task.

Reduction from MI testing to EET
Lemma 19.

Let kA,kC⩾2 and n=kA⁢kC. Any 𝖤𝖤𝖳 algorithm 𝒜 over [n] with sample complexity T yields an 𝖬𝖨 testing algorithm over [kA]×[kC] with sample complexity 3⁢T and the same success probability.

Proof.

Map [kA]×[kC] with [n] via some fixed bijection. Using 𝒜, we construct a 𝖬𝖨 tester for PA⁢C over [kA]×[kC] as follows:

  1. 1.

    Draw 3⁢T i.i.d. samples (a1,c1),…,(a3⁢T,c3⁢T) from PA⁢C.

  2. 2.

    Form T samples of P:=PA⁢C, denoted by (ai,ci) for i=1,…,T.

  3. 3.

    Form T samples of Q:=PA⊗PC, denoted by (aT+2⁢i−1,cT+2⁢i) for i=1,…,T. Since the samples are i.i.d., the a- and c-coordinates of each pair are independent draws from PA and PC respectively.

  4. 4.

    Run 𝒜 on the T samples of P and the T samples of Q.

Observe that |H(P)−H(Q)|=|H(A,C)−H(A)−H(C)|=I(A:C). Then:

  • ■

    If I(A:C)=0, then PA⁢C=PA⊗PC, so P=Q and 𝒜 returns accept.

  • ■

    If I(A:C)⩾ε, then |H⁢(P)−H⁢(Q)|⩾ε and 𝒜 returns reject.

◀

Theorem 20 (𝖤𝖤𝖳 lower bound: Theorem 3, restated).

Any algorithm that, given sample access to two unknown distributions p,q over [n] and parameter ε∈(0,1], distinguishes p=q from |H⁢(p)−H⁢(q)|⩾ε with probability at least 2/3 requires

Ω~⁢(min⁡{n3/4ε,n2/3ε4/3})+Ω⁢(log2⁡nε2)

samples from each of p and q.

Proof.

Apply Lemma 19 with kA=n/2 and kC=2. Combining with [37, Corollary 6.2] gives the first term:

Ω~⁢(min⁡{(n/2)3/4⋅21/4ε,(n/2)2/3⋅21/3ε4/3})=Ω~⁢(min⁡{n3/4ε,n2/3ε4/3}).

For the second term, [15, Lemma 2.7] exhibits distributions p,q over [n] with |H⁢(p)−H⁢(q)|⩾ε that no algorithm can distinguish from p=q using fewer than Ω⁢(log2⁡n/ε2) samples from p when q is given. Any 𝖤𝖤𝖳 algorithm using T samples from each of p,q yields such a tester by simulating T samples from the known q, so 𝖤𝖤𝖳 also requires Ω⁢(log2⁡n/ε2) samples. ◀

References

  • [1] Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath. Optimal testing for properties of distributions. In NeurIPS, pages 3591–3599, 2015. URL: https://proceedings.neurips.cc/paper/2015/hash/1f36c15d6a3d18d52e8d493bc8187cb9-Abstract.html.
  • [2] Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, and Himanshu Tyagi. The complexity of estimating rényi entropy. In SODA, pages 1855–1869. SIAM, 2015. doi:10.1137/1.9781611973730.124.
  • [3] Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, and Ronitt Rubinfeld. The complexity of approximating the entropy. SIAM J. Comput., 35(1):132–150, 2005. doi:10.1137/S0097539702403645.
  • [4] Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, and Patrick White. Testing random variables for independence and identity. In FOCS, pages 442–451. IEEE Computer Society, 2001. doi:10.1109/SFCS.2001.959920.
  • [5] Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White. Testing that distributions are close. In FOCS, pages 259–269. IEEE Computer Society, 2000. doi:10.1109/SFCS.2000.892113.
  • [6] Arnab Bhattacharyya, Clément L. Canonne, and Joy Qiping Yang. Independence testing for bounded degree bayesian networks. In NeurIPS, 2022.
  • [7] Arnab Bhattacharyya, Davin Choo, Sutanu Gayen, and Dimitrios Myrisiotis. Learnability of parameter-bounded bayes nets. In AAAI, pages 15559–15566. AAAI Press, 2025. doi:10.1609/AAAI.V39I15.33708.
  • [8] Arnab Bhattacharyya, Sutanu Gayen, Philips George John, Sayantan Sen, and N. V. Vinodchandran. Distribution learning meets graph structure sampling. In Advances in Neural Information Processing Systems, volume 38, pages 21411–21432, 2025.
  • [9] Arnab Bhattacharyya, Sutanu Gayen, Eric Price, Vincent Y. F. Tan, and N. V. Vinodchandran. Near-optimal learning of tree-structured distributions by chow and liu. SIAM J. Comput., 52(3):761–793, 2023. doi:10.1137/22M1489678.
  • [10] Clément L. Canonne. A Survey on Distribution Testing: Your Data is Big. But is it Blue? Number 9 in Graduate Surveys. Theory of Computing Library, 2020. doi:10.4086/toc.gs.2020.009.
  • [11] Clément L. Canonne. Topics and techniques in distribution testing: A biased but representative sample. Found. Trends Commun. Inf. Theory, 19(6):1032–1198, 2022. doi:10.1561/0100000114.
  • [12] Clément L Canonne, Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Testing Bayesian networks. In Conference on Learning Theory, pages 370–448. PMLR, 2017. URL: http://proceedings.mlr.press/v65/canonne17a.html.
  • [13] Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Testing conditional independence of discrete distributions. In STOC, pages 735–748. ACM, 2018. doi:10.1145/3188745.3188756.
  • [14] Clément L. Canonne, Yash Pote, Jonathan Scarlett, and Joy Qiping Yang. Entropy equivalence testing. CoRR, abs/2605.23225, 2026. doi:10.48550/arXiv.2605.23225.
  • [15] Clément L Canonne and Joy Q Yang. Entropy testing and its application to testing Bayesian networks. Advances in Neural Information Processing Systems, 2024.
  • [16] Clément L. Canonne. A short note on learning discrete distributions, 2020. arXiv:2002.11457.
  • [17] Siu On Chan, Ilias Diakonikolas, Paul Valiant, and Gregory Valiant. Optimal algorithms for testing closeness of discrete distributions. In SODA, pages 1193–1203. SIAM, 2014. doi:10.1137/1.9781611973402.88.
  • [18] David Maxwell Chickering, David Heckerman, and Christopher Meek. Large-sample learning of bayesian networks is np-hard. J. Mach. Learn. Res., 5:1287–1330, 2004. URL: https://jmlr.org/papers/volume5/chickering04a/chickering04a.pdf.
  • [19] Davin Choo, Joy Qiping Yang, Arnab Bhattacharyya, and Clément L. Canonne. Learning bounded-degree polytrees with known skeleton. In ALT, Proceedings of Machine Learning Research, pages 402–443. PMLR, 2024. URL: https://proceedings.mlr.press/v237/choo24a.html.
  • [20] C. K. Chow and C. N. Liu. Approximating discrete probability distributions with dependence trees. IEEE Trans. Inf. Theory, 14(3):462–467, 1968. doi:10.1109/TIT.1968.1054142.
  • [21] Imre Csiszár and János Körner. Information Theory: Coding Theorems for Discrete Memoryless Systems. Cambridge University Press, 2011.
  • [22] Sanjoy Dasgupta. Learning polytrees. In UAI, pages 134–141. Morgan Kaufmann, 1999. URL: https://dslpitt.org/uai/displayArticleDetails.jsp?mmnu=1&smnu=2&article_id=162&proceeding_id=15.
  • [23] Constantinos Daskalakis, Nishanth Dikkala, and Gautam Kamath. Testing ising models. In SODA, pages 1989–2007. SIAM, 2018. doi:10.1137/1.9781611975031.130.
  • [24] Constantinos Daskalakis, Gautam Kamath, and John Wright. Which distribution distances are sublinearly testable? In SODA, pages 2747–2764. SIAM, 2018. doi:10.1137/1.9781611975031.175.
  • [25] Constantinos Daskalakis and Qinxuan Pan. Square hellinger subadditivity for bayesian networks and its applications to identity testing. In COLT, volume 65 of Proceedings of Machine Learning Research, pages 697–703. PMLR, 2017. URL: http://proceedings.mlr.press/v65/daskalakis17a.html.
  • [26] Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, John Peebles, and Eric Price. Optimal testing of discrete distributions with high probability. In STOC, pages 542–555. ACM, 2021. doi:10.1145/3406325.3450997.
  • [27] Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price. Sample-optimal identity testing with high probability. In ICALP, LIPIcs, pages 41:1–41:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.ICALP.2018.41.
  • [28] Ilias Diakonikolas and Daniel M. Kane. A new approach for testing properties of discrete distributions. In FOCS, pages 685–694. IEEE Computer Society, 2016. doi:10.1109/FOCS.2016.78.
  • [29] Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. doi:10.1017/9781108135252.
  • [30] Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653–750, 1998. doi:10.1145/285055.285060.
  • [31] Jiantao Jiao, Kartik Venkat, Yanjun Han, and Tsachy Weissman. Minimax estimation of functionals of discrete distributions. IEEE Trans. Inf. Theory, 61(5):2835–2885, 2015. doi:10.1109/TIT.2015.2412945.
  • [32] Liam Paninski. A coincidence-based test for uniformity given very sparsely sampled discrete data. IEEE Trans. Inf. Theory, 54(10):4750–4755, 2008. doi:10.1109/TIT.2008.928987.
  • [33] Yury Polyanskiy and Yihong Wu. Information Theory: From Coding to Learning. Cambridge University Press, 2025.
  • [34] Ronitt Rubinfeld. Taming big probability distributions. XRDS, 19(1):24–28, 2012. doi:10.1145/2331042.2331052.
  • [35] Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252–271, 1996. doi:10.1137/S0097539793255151.
  • [36] Igal Sason and Sergio Verdú. f-divergence inequalities. IEEE Trans. Inf. Theory, 62(11):5973–6006, 2016. doi:10.1109/TIT.2016.2603151.
  • [37] Jan Seyfried, Sayantan Sen, and Marco Tomamichel. Testing (conditional) mutual information. Electron. Colloquium Comput. Complex., TR25, 2025. URL: https://eccc.weizmann.ac.il/report/2025/076.
  • [38] Flemming Topsøe. Some inequalities for information divergence and related measures of discrimination. IEEE Trans. Inf. Theory, 46(4):1602–1609, 2000. doi:10.1109/18.850703.
  • [39] Gregory Valiant and Paul Valiant. Estimating the unseen: An n/log(n)-sample estimator for entropy and support size, shown optimal via new clts. In STOC, pages 685–694. ACM, 2011. doi:10.1145/1993636.1993727.
  • [40] Gregory Valiant and Paul Valiant. An automatic inequality prover and instance optimal identity testing. In FOCS, pages 51–60. IEEE Computer Society, 2014. doi:10.1109/FOCS.2014.14.
  • [41] Yihong Wu and Pengkun Yang. Optimal entropy estimation on large alphabets via best polynomial approximation. In ISIT, pages 824–828. IEEE, 2015. doi:10.1109/ISIT.2015.7282570.
  • [42] Yihong Wu and Pengkun Yang. Minimax rates of entropy estimation on large alphabets via best polynomial approximation. IEEE Trans. Inf. Theory, 2016. doi:10.1109/TIT.2016.2548468.

Appendix A Deferred Proofs

Fact 5. [Restated, see original statement.]

Let X be a Poisson random variable with parameter λ, and f:ℝ→ℝ be any function, then, we have that 𝔼⁢[(X)m⋅f⁢(X)]=λm⋅𝔼⁢[f⁢(X+m)]. In particular, choosing f≡1, we have that 𝔼⁢[(X)m]=λm for all m⩾0.

Proof.

We first show that 𝔼⁢[X⋅f⁢(X)]=λ⋅𝔼⁢[f⁢(X+1)] by standard Poisson calculations:

𝔼⁢[X⋅f⁢(X)]=∑k=0λk⁢e−λk!⋅k⋅f⁢(k)=λ⋅∑k=1λk−1⁢e−λ(k−1)!⋅f⁢(k)=λ⋅∑k=0λk⁢e−λk!⁢f⁢(k+1)
= λ⋅𝔼⁢[f⁢(X+1)]

The proof is then completed by induction, by noting that

𝔼⁢[(X)m⋅f⁢(X)] =𝔼⁢[X⋅(X−1)m−1⋅f⁢(X)]
=λ⋅𝔼⁢[(X−1+1)m−1⋅f⁢(X+1)]
=λ2⋅𝔼⁢[(X)m−2⋅f⁢(X+2)]
=…
=λm⋅𝔼⁢[f⁢(X+m)].

◀