A New Approach for Testing Properties of Discrete Distributions

arXiv:1601.05557v2 [] 9 May 2016

Ilias Diakonikolas∗
University of Southern California
diakonik@usc.edu.

Daniel M. Kane
University of California, San Diego
dakane@cs.ucsd.edu.

May 10, 2016

Abstract
We study problems in distribution property testing: Given sample access to one or more
unknown discrete distributions, we want to determine whether they have some global property
or are ǫ-far from having the property in ℓ1 distance (equivalently, total variation distance, or
“statistical distance”). In this work, we give a novel general approach for distribution testing.
We describe two techniques: our first technique gives sample–optimal testers, while our second technique gives matching sample lower bounds. As a consequence, we resolve the sample
complexity of a wide variety of testing problems.
Our upper bounds are obtained via a modular reduction-based approach. Our approach
yields optimal testers for numerous problems by using a standard ℓ2 -identity tester as a blackbox. Using this recipe, we obtain simple estimators for a wide range of problems, encompassing
most problems previously studied in the TCS literature, namely: (1) identity testing to a fixed
distribution, (2) closeness testing between two unknown distributions (with equal/unequal sample sizes), (3) independence testing (in any number of dimensions), (4) closeness testing for
collections of distributions, and (5) testing histograms. For all of these problems, our testers
are sample-optimal, up to constant factors. With the exception of (1), ours are the first sampleoptimal testers for the corresponding problems. Moreover, our estimators are significantly simpler to state and analyze compared to previous results.
As an important application of our reduction-based technique, we obtain the first nearly
instance-optimal algorithm for testing equivalence between two unknown distributions. The
sample complexity of our algorithm depends on the structure of the unknown distributions – as
opposed to merely their domain size – and is much better compared to the worst-case optimal
ℓ1 -tester in most natural instances. Moreover, our technique naturally generalizes to other
metrics beyond the ℓ1 -distance. As an illustration of its flexibility, we use it to obtain the first
near-optimal equivalence tester under the Hellinger distance.
Our lower bounds are obtained via a direct information-theoretic approach: Given a candidate hard instance, our proof proceeds by bounding the mutual information between appropriate
random variables. While this is a classical method in information theory, prior to our work, it
had not been used in distribution property testing. Previous lower bounds relied either on the
birthday paradox, or on moment-matching and were thus restricted to symmetric properties.
Our lower bound approach does not suffer from any such restrictions and gives tight sample
lower bounds for the aforementioned problems.

∗

Part of this work was performed while the author was at the University of Edinburgh. Research supported by
EPSRC grant EP/L021749/1, a Marie Curie Career Integration Grant, and a SICSA grant.

1

Introduction

1.1 Background The problem of determining whether an unknown object fits a model based
on observed data is of fundamental scientific importance. We study the following formalization
of this problem: Given samples from a collection of probability distributions, can we determine
whether the distributions in question satisfy a certain property? This is the prototypical question in
statistical hypothesis testing [NP33, LR05]. During the past two decades, this question has received
considerable attention by the TCS community in the framework of property testing [RS96, GGR98],
with a focus on discrete probability distributions.
The area of distribution property testing [BFR+ 00, BFR+ 13] has developed into a mature research field with connections to information theory, learning and statistics. The generic inference
problem in this field is the following: given sample access to one or more unknown distributions,
determine whether they have some global property or are “far” (in statistical distance or, equivalently, ℓ1 norm) from having the property. The goal is to obtain statistically and computationally
efficient testing algorithms, i.e., algorithms that use the information-theoretically minimum sample
size and run in polynomial time. See [GR00, BFR+ 00, BFF+ 01, Bat01, BDKR02, BKR04, Pan08,
Val11, DDS+ 13, ADJ+ 11, LRR11, ILR12, CDVV14, VV14, DKN15b, DKN15a, ADK15, CDGR16]
for a sample of works and [Rub12, Can15] for two recent surveys.
In this work, we give a new general approach for distribution testing. We describe two novel
techniques: our first technique yields sample–optimal testers, while our second technique gives
matching sample lower bounds. As a consequence, we resolve the sample complexity of a wide
variety of testing problems.
All our upper bounds are obtained via a collection of modular reductions. Our reduction-based
method provides a simple recipe to obtain optimal testers under the ℓ1 -norm (and other metrics),
by applying a randomized transformation to a basic ℓ2 -identity tester. While the ℓ2 -norm has been
used before as a tool in distribution testing [BFR+ 00], our reduction-based approach is conceptually
and technically different than previous approaches. We elaborate on this point in Section 1.4. We
use our reduction-based approach to resolve a number of open problems in the literature (see
Section 1.3). In addition to pinning–down the sample complexity of a wide range of problems, a
key contribution of our algorithmic approach is methodological. In particular, the main conceptual
message is that one does not need an inherently different statistic for each testing problem. In
contrast, all our testing algorithms follow the same pattern: They are obtained by applying a
simple transformation to a basic statistic – one that tests the identity between two distributions in
ℓ2 -norm – in a black-box manner. Following this scheme, we obtain the first sample-optimal testers
for many properties. Importantly, our testers are simple and, in most cases, their analysis fits in a
paragraph.
As our second main contribution, we provide a direct, elementary approach to prove sample
complexity lower bounds for distribution testing problems. Given a candidate hard instance, our
proof proceeds by bounding the mutual information between appropriate random variables. Our
analysis leads to new, optimal lower bounds for several problems, including testing closeness (under
various metrics), testing independence (in any dimension), and testing histograms. Notably, proving
sample complexity lower bounds by bounding the mutual information is a classical approach in
information theory. Perhaps surprisingly, prior to our work, this method had not been used in
distribution testing. Previous techniques were either based on the birthday paradox or on momentmatching [RRSS09, Val11], and were thus restricted to testing symmetric properties. Our technique
circumvents the moment-matching approach, and is not restricted to symmetric properties.

1

1.2 Notation We write [n] to denote the set {1,
Pn. . . , n}. We consider discrete distributions over
[n], which are functions p : [n] → [0, 1] such that i=1 pi = 1. We use the notation pi to denote the
probability of element i in distribution p.
A pseudo-distribution over a finite set S is any function p : S → [0, 1]. For a distribution
p : [n] → [0, 1] and a set S ⊆ [n], we will denote by (p|S) the conditional distribution on S and by
p[S] the pseudo-distribution obtained by restricting p on the set S.
The ℓ1 (resp. ℓ2 ) norm of a (pseudo-)distribution is identified
qP with the ℓ1 (resp. ℓ2 ) norm of
Pn
n
2
the corresponding vector, i.e., kpk1 = i=1 |pi | and kpk2 =
i=1 pi . The ℓ1 (resp. ℓ2 ) distance
between (pseudo-)distributions pPand q is defined as the the p
ℓ1 P
(resp. ℓ2 ) norm of the vector of
n
2
their difference, i.e., kp − qk1 = ni=1 |pi − qi | and kp − qk2 =
i=1 (pi − qi ) .
1.3 Our Contributions The main contribution of this paper is a reduction–based framework
to obtain testing algorithms, and a direct approach to prove lower bounds. We do not aim to
exhaustively cover all possible applications of our techniques, but rather to give some selected
results that are indicative of the generality and power of our methods. More specifically, we obtain
the following results:

1. We give an alternative optimal ℓ1 -identity tester against a fixed distribution, with sample com√
plexity O( n/ǫ2 ), matching the recently obtained tight bound [VV14, DKN15b]. The main advantage of our tester is its simplicity: Our reduction and its analysis are remarkably short and simple
in this case. Our tester straightforwardly implies the “χ2 versus ℓ1 ” guarantee recently used as the
main statistical test in [ADK15].
2. We design an optimal tester for ℓ1 -closeness between two unknown distributions in the standard
and the (more general) unequal-sized sample regimes. For the standard regime (i.e., when we draw
the same number of samples from each distribution), we recover the tight sample complexity of
O(max(n2/3 /ǫ4/3 , n1/2 /ǫ2 )), matching [CDVV14]. Importantly, our tester straightforwardly extends
to unequal-sized samples, giving the first optimal tester in this setting. Closeness testing with
unequal sized samples was considered in [AJOS14] that gives sample upper and lower bounds with
a polynomial gap between them. Our tester uses m1 = Ω(max(n2/3 /ǫ4/3 , n1/2 /ǫ2 )) samples from one
√
−1/2
distribution and m2 = O(max(nm1 /ǫ2 , n/ǫ2 )) from the other. This tradeoff is sample-optimal
(up to a constant factor) for all settings, and improves on the recent work [BV15] that obtains the
same tradeoff under the additional assumption that ǫ > n−1/12 . In sharp contrast to [BV15], our
algorithm is extremely simple and its analysis fits in a few lines.
3. We study the problem of ℓ1 -testing closeness between two unknown distributions in an instanceoptimal setting, where the goal is to design estimators whose sample complexity depends on the
(unknown) structure of the sampled distributions – as opposed to merely their domain size. We
obtain the first algorithm for this problem: Our tester uses
Õ(min(m + kq <1/m k0 · kq <1/m k2 /ǫ2 + kqk2/3 /ǫ2 ))
m>0

samples from each of the distributions p, q on [n]. Here, q <1/m denotes the pseudo-distribution
obtained from q by removing the domain elements with mass ≥ 1/m, and kq <1/m k0 is the number
√
of elements with mass < 1/m. (Observe that since kq <1/m k2 ≤ 1/ m, taking m = min(n, n2/3 /ǫ4/3 )
attains the complexity of the standard ℓ1 -closeness testing algorithm to within logarithmic factors.)
An important distinction between our algorithm and the instance-optimal identity testing algorithm
of [VV14] is that the sample complexity of the latter depends on the structure of the explicitly known
2

distribution, while ours depends on parameters of the unknown distributions. Roughly speaking,
the [VV14] algorithm knows a priori when to stop drawing samples, while ours “discovers” the
right sample complexity adaptively while obtaining samples. As an illustration of our technique,
we give an alternative algorithm for the identity testing problem in [VV14] whose analysis fits in
two short paragraphs. The sample complexity of our alternative algorithm is Õ(kqk2/3 /ǫ2 ), where
q is the explicit distribution, matching the bound of [VV14] up to logarithmic factors.
4. We show that our framework easily generalizes to give near-optimal algorithms and lower
bounds for other metrics as well, beyond the ℓ1 -norm. As an illustration of this fact, we describe
an algorithm and a nearly-matching lower bound for testing closeness under Hellinger distance,
√
√
H 2 (p, q) = (1/2)k p − qk22 , one of the most powerful f -divergences. This question has been
studied before: [GMV09] gave a tester for this problem with sample complexity Õ(n2/3 /ǫ4 ). The
sample complexity of our algorithm is Õ(min(n2/3 /ǫ4/3 , n3/4 /ǫ)), and we prove a lower bound of
Ω(min(n2/3 /ǫ4/3 , n3/4 /ǫ)). Note that the second term of n3/4 /ǫ in the sample complexity differs
from the corresponding ℓ1 term of n1/2 /ǫ2 .
5. We obtain the first sample-optimal algorithm and matching lower bound for testing independence over ×di=1 [ni ]. Prior to our work, the sample complexity of this problem remained open,
even for the two-dimensional case. We prove that the optimal sample complexity of indepenQ
1/3 Q
dence testing (upper and lower bound) is Θ(maxj (( di=1 ni )1/2 /ǫ2 , nj ( di=1 ni )1/3 /ǫ4/3 )). Previous testers for independence were suboptimal up to polynomial factors in n and 1/ǫ, even for
d = 2. Specifically, Batu et al. [BFF+ 01] gave an independence tester over [n] × [m] with same 2/3 m1/3 ) · poly(1/ǫ), for n ≥ m. On the lower bound side, Levi, Ron, and
ple complexity O(n
√
Rubinfeld [LRR11] showed a sample complexity lower bound of Ω( nm) (for all n ≥ m), and
1/3
Ω(n2/3 m
n =PΩ(m log m)). More recently, Acharya et al. [ADK15] gave an upper bound
Qd ) (for
of O((( i=1 ni )1/2 + di=1 ni )/ǫ2 ), which is optimal up to constant factors for the very special case
that all the ni ’s are the same. In summary, we resolve the sample complexity of this problem in
any dimension d, up to a constant factor, as a function of all relevant parameters.
6. We obtain the first sample-optimal algorithms for testing equivalence for collections of distributions [LRR11] in the sampling and the oracle model, improving on [LRR11] by polynomial factors.
In the sampling model, we observe that the problem is equivalent to (a variant of) two-dimensional
independence testing. In fact, in the unknown-weights case, the problem is identical. In the
known-weights case, the problem is equivalent to two-dimensional independence testing, where the
algorithm is given explicit access to one of the marginals (say, the marginal on [m]). For this
√
setting, we give a sample-optimal tester with sample size O(max( nm/ǫ2 , n2/3 m1/3 /ǫ4/3 ))1 . In the
query model, we give a sample-optimal closeness tester for m distributions over [n] with sample
√
complexity O(max( n/ǫ2 , n2/3 /ǫ4/3 )). This bound is independent of m and matches the worst-case
optimal bound for testing closeness between two unknown distributions.
7. As a final application of our techniques, we study the problem of testing whether a distribution
belongs in a given “structured family” [ADK15, CDGR16]. We focus on the property of being a
k-histogram over [n], i.e., that the probability mass function is piecewise constant with at most
k known interval pieces. This is a natural problem of particular interest in model selection. For
k = 1, the problem is tantamount to uniformity testing, while for k = Ω(n) it can be seen to be
equivalent to testing closeness between two unknown distributions over a domain of size Ω(n). We
1

It should be noted that, while this is the same form as the sample complexity for independence testing in two
dimensions, there is a crucial difference. In this setting, the parameter m represents the support size of the marginal
that is explicitly given to us, rather than the marginal with smaller support size.

3

design a tester for the property of being a k-histogram (with respect to a given set of intervals)
√
with sample complexity O(max( n/ǫ2 , n1/3 k1/3 /ǫ4/3 )) samples. We also prove that this bound is
information-theoretically optimal, up to constant factors.
1.4 Prior Techniques and Overview of our Approach In this section, we provide a detailed
intuitive explanation of our two techniques, in tandem with a comparison to previous approaches.
We start with our upper bound approach. It is reasonable to expect that the ℓ2 -norm is useful
as a tool in distribution property testing. Indeed, for elements with “small” probability mass,
estimating second moments is a natural choice in the sublinear regime. Alas, a direct ℓ2 -tester will
often not work for the following reason: The error coming from the “heavy” elements will force the
estimator to draw too many samples.
In their seminal paper, Batu et al. [BFR+ 00, BFR+ 13] gave an ℓ2 -closeness tester and used it
to obtain an ℓ1 -closeness tester. To circumvent the aforementioned issue, their ℓ1 -tester has two
stages: It first explicitly learns the pseudo-distribution supported on the heavy elements, and then it
applies the ℓ2 -tester on the pseudo-distribution over the light elements. This approach of combining
learning (for the heavy elements) and ℓ2 -closeness testing (for the light elements) is later refined by
Chan et al. [CDVV14], where it is shown that it inherently leads to a suboptimal sample complexity
for the testing closeness problem. Motivated by this shortcoming, it was suggested in [CDVV14]
that the use of the ℓ2 -norm may be insufficient, and that a more direct approach may be needed to
achieve sample-optimal ℓ1 -testers. This suggestion led researchers to consider different approaches
to ℓ1 -testing (e.g., appropriately rescaled versions of the chi-squared test [ADJ+ 12, CDVV14, VV14,
BV15, ADK15]) that, although shown optimal for a couple of cases, lead to somewhat ad-hoc
estimators that come with a highly-nontrivial analysis.
Our upper bound approach postulates that the inefficiency of [BFR+ 00, BFR+ 13] is due to the
explicit learning of the heavy elements and not to the use of the ℓ2 -norm. Our approach provides a
simple and general way to essentially remove this learning step. We achieve this via a collection of
simple reductions: Starting from a given instance of an ℓ1 -testing problem A, we construct a new
instance of an appropriate ℓ2 -testing problem B, so that the answers to the two problems for these
instances are identical. Here, problem A can be any of the testing problems discussed in Section 1.3,
while problem B is always the same. Namely, we define B to be the problem of ℓ2 -testing closeness
between two unknown distributions, under the promise that at least one of the distributions in
question has small ℓ2 -norm. Our reductions have the property that a sample-optimal algorithm for
problem B implies a sample-optimal algorithm for A. An important conceptual consequence of our
direct reduction-based approach is that problem B is of central importance in distribution testing,
since a wide range of problems can be reduced to it with optimal sample guarantees. We remark
that sample-optimal algorithms for problem B are known in the literature: a natural estimator
from [CDVV14], as well as a similar estimator from [BFR+ 00] achieve optimal bounds.
The precise form of our reductions naturally depends on the problem A that we start from.
While the details differ based on the problem, all our reductions rely on a common recipe: We
randomly transform the initial distributions in question (i.e., the distributions we are given sample
access to) to new distributions (over a potentially larger domain) such that at least one of the
new distributions has appropriately small ℓ2 -norm. Our transformation preserves the ℓ1 -norm, and
is such that we can easily simulate samples from the new distributions. More specifically, our
transformation is obtained by drawing random samples from one of the distributions in question
to discover its heavy bins. We then artificially subdivide each heavy bin into multiple bins, so that
the resulting distribution becomes approximately flat. This procedure decreases the ℓ2 -norm while
increasing the domain size. By balancing these two quantities, we obtain sample-optimal testers
for a wide variety of properties.
4

In summary, our upper bound approach provides reductions of numerous distribution testing
problems to a specific ℓ2 -testing problem B that yield sample-optimal algorithms. It is tempting to
conjecture that optimal reductions in the opposite direction exist, which would allow translating
lower bounds for problem B to tight lower bounds for other problems. We do not expect optimal
reductions in the opposite direction, roughly because the hard instances for many of our problems
are substantially different from the hard instances for problem B. This naturally brings us to our
lower bound approach, explained below.
Our lower bounds proceed by constructing explicit distributions D and D ′ over (sets of) distributions, so that a random distribution p drawn from D satisfies the property, a random distribution
p from D ′ is far from satisfying the property (with high probability), and it is hard to distinguish between the two cases given a small number of samples. Our analysis is based on classical
information-theoretic notions and is significantly different from previous approaches in this context.
Instead of using techniques involving matching moments [RRSS09, Val11], we are able to directly
prove that the mutual information between the set of samples drawn and the distribution that p
was drawn from is small. Appropriately bounding the mutual information is perhaps a technical
exercise, but remains quite manageable only requiring elementary approximation arguments. We
believe that this technique is more flexible than the techniques of [RRSS09, Val11] (e.g., it is not
restricted to symmetric properties), and may prove useful in future testing problems.
Remark 1.1. We believe that our reduction-based approach is a simple and appealing framework
to obtain tight upper bounds for distribution testing problems in a unifying manner. Since the
dissemination of an earlier version of our paper, Oded Goldreich gave an excellent exposition of our
approach in the corresponding chapter of his upcoming book [Gol16b].
1.5 Organization The structure of this paper is as follows: In Section 2, we describe our
reduction-based approach and exploit it to obtain our optimal testers for a variety of problems.
In Section 3, we describe our lower bound approach and apply it to prove tight lower bounds for
various problems.

2

Our Reduction and its Algorithmic Applications

In Section 2.1, we describe our basic reduction from ℓ1 to ℓ2 testing. In Section 2.2, we apply our
reduction to a variety of concrete distribution testing problems.
2.1 Reduction of ℓ1 -testing to ℓ2 -testing The starting point of our reduction-based approach
is a “basic tester” for the identity between two unknown distributions with respect to the ℓ2 norm. We emphasize that a simple and natural tester turns out to be optimal in this setting.
More specifically, we will use the following simple lemma (that follows, e.g., from Proposition 3.1
in [CDVV14]):
Lemma 2.1. Let p and q be two unknown distributions on [n]. There exists an algorithm that on
input n, ǫ > 0, and b ≥ max{kpk2 , kqk2 } draws O(bn/ǫ2 ) samples from each of p and q, and with
probability at least 2/3 distinguishes between the cases that p = q and kp − qk1 > ǫ.
Remark 2.2. We remark that Proposition 3.1 of [CDVV14] provides a somewhat stronger guarantee than the one of Lemma 2.1. Specifically, it yields a robust ℓ2 -closeness tester with the
following performance guarantee: Given O(bn/ǫ2 ) samples from distributions p, q over [n], where
b ≥ max{kpk2 , kqk2 }, the algorithm distinguishes (with probability at least 2/3) between the cases
√
√
that kp − qk2 ≤ ǫ/(2 n) and kp − qk2 ≥ ǫ/ n. The soundness guarantee of Lemma 2.1 follows
from the Cauchy-Schwarz inequality.
5

Observe that if kpk2 and kqk2 are both small, the algorithm of Lemma 2.1 is in fact sample√
√
efficient. For example, if both are O(1/ n), its sample complexity is an optimal O( n/ǫ2 ). On
the other hand, the performance of this algorithm degrades as kpk2 or kqk2 increases. Fortunately,
there are some convenient reductions that simplify matters. To begin with, we note that it suffices
that only one of kpk2 and kqk2 is small. This is essentially because if there is a large difference
between the two, this is easy to detect.
Lemma 2.3. Let p and q be two unknown distributions on [n]. There exists an algorithm that on
input n, ǫ > 0, and b ≥ min{kpk2 , kqk2 } draws O(bn/ǫ2 ) samples from each of p and q and, with
probability at least 2/3, distinguishes between the cases that p = q and kp − qk1 > ǫ.
Proof. The basic idea is to first test if kpk2 = Θ(kqk2 ), and if so to run the tester of Lemma 2.1.
To test whether kpk2 = Θ(kqk2 ), we estimate kpk2 and kqk2 up to a multiplicative constant factor.
√
It is known [GR00, BFF+ 01] that this can be done with O( n) = O(min(kpk2 , kqk2 )n) samples. If
kpk2 and kqk2 do not agree to within a constant factor, we can conclude that p 6= q. Otherwise, we
use the tester from Lemma 2.1, and note that the number of required samples is O(kpk2 n/ǫ2 ).
In our applications of Lemma 2.3, we take the parameter b to be equal to our upper bound on
min{kpk2 , kqk2 }. In all our algorithms in Section 2.2 this upper bound will be clear from the
context. If both our initial distributions have large ℓ2 -norm, we describe a new way to reduce them
by splitting the large weight bins (domain elements) into pieces. The following key definition is the
basis for our reduction:
Definition 2.4. Given a distribution p on [n] and a multiset S of elements of [n], define the split
distribution pS on [n + |S|] asPfollows: For 1 ≤ i ≤ n, let ai denote 1 plus the number of elements of
S that are equal to i. Thus, ni=1 ai = n + |S|. We can therefore associate the elements of [n + |S|]
to elements of the set B = {(i, j) : i ∈ [n], 1 ≤ j ≤ ai }. We now define a distribution pS with
support B, by letting a random sample from pS be given by (i, j), where i is drawn randomly from
p and j is drawn randomly from [ai ].
We now show two basic facts about split distributions:
Fact 2.5. Let p and q be probability distributions on [n], and S a given multiset of [n]. Then: (i)
We can simulate a sample from pS or qS by taking a single sample from p or q, respectively. (ii) It
holds kpS − qS k1 = kp − qk1 .
Fact 2.5 implies that it suffices to be able to test the closeness of pS and qS , for some S. In
particular, we want to find an S so that kpS k2 and kqS k2 are small. The following lemma shows
how to achieve this:
Lemma 2.6. Let p be a distribution on [n]. Then: (i) For any multisets S ⊆ S ′ of [n], kpS ′ k2 ≤
kpS k2 , and (ii) If S is obtained by taking Poi(m) samples from p, then E[kpS k22 ] ≤ 1/m.
Proof. Let ai equal one plus the number of copies of i in S, and a′i equal one plus the number of
copies of i in S ′ . We note that pS = (i, j) with probability pi /ai . Therefore, for (i) we have that
kpS k22

=

ai
n X
X
i=1 j=1

(pi /ai )2 =

n
X
i=1

p2i /ai ≥

n
X
i=1

p2i /a′i = kpS ′ k22 .

P
For claim (ii), we note that the expected squared ℓ2 -norm of pS is ni=1 p2i E[a−1
i ]. We note that
ai is distributed as 1 + X where X is a Poi(mpi ) random variable. Recall that if Y is a random
variable distributed as Poi(λ), then E[z Y ] = eλ(z−1) . Taking an integral we find that
6

E [1/(1 + X)] = E

Z

1

X



z dz =

0

Therefore, we have that E[kpS k22 ] ≤
proof.
2.2

Z

1

X

E[z ]dz =

Z

0

0

Pn

2
i=1 pi /(mpi )

1

eλ(z−1) dz = (1 − e−λ )/λ ≤ 1/λ.

= (1/m)

Pn

i=1 pi

= 1/m. This completes the

Algorithmic Applications

2.2.1 Testing Identity to a Known Distribution We start by applying our framework to
give a simple alternate optimal identity tester to a fixed distribution in the minimax sense. In this
case, our algorithm is extremely easy, and provides a much simpler proof of the known optimal
bound [VV14, DKN15b]:
Proposition 2.7. There exists an algorithm that given an explicit distribution q supported on [n]
√
and O( n/ǫ2 ) independent samples from a distribution p over [n] distinguishes with probability at
least 2/3 between the cases where p = q and kp − qk1 ≥ ǫ.
P
Proof. Let S be the multiset where S contains ⌊nqi ⌋ copies of i. Note that |S| ≤ ni=1 nqi = n.
Note also that qS assigns probability mass at most 1/n to each bin. Therefore, we have that
√
kqS k2 = O(1/ n). It now suffices to distinguish between the cases that pS = qS and the case that
√
kpS − qS k1 ≥ ǫ. Using the basic tester from Lemma 2.3 for b = O(1/ n), we can do this using
√
√
O(2nb/ǫ2 ) = O( n/ǫ2 ) samples from pS . This can be simulated using O( n/ǫ2 ) samples from p,
which completes the proof.
Remark 2.8. We observe that the identity tester of Proposition 2.7
Psatisfies a stronger guarantee:
More specifically, it distinguishes between the cases that χ2 (p, q) := ni=1 (pi −qi )2 /qi ≤ ǫ2 /10 versus
kp − qk1 ≥ ǫ. Hence, it implies Theorem 1 of [ADK15]. This can be seen as follows: As explained in
Remark 2.2, the basic tester of Lemma 2.1 from [CDVV14] is a robust tester with respect to the ℓ2 √
norm. Thus, the tester of Proposition 2.7 distinguishes between the cases that kpS −qS k2 ≤ ǫ/(2 n)
√
and kpS − qS k2 ≥ ǫ/ n. The desired soundness follows from the fact kp − qk1 = kpS − qS k1 and
the Cauchy-Schwarz inequality. The desired “chi-squared” completeness property follows from the
easily verifiable (in)equalities χ2 (p, q) = χ2 (pS , qS ) and χ2 (pS , qS ) ≥ n · kpS − qS k22 .
Remark 2.9. After the dissemination of an earlier version of this paper, inspired by our work,
Goldreich [Gol16a] reduced testing identity to a fixed distribution to its special case of uniformity
testing, via a refinement of the above idea. Unfortunately, this elegant idea does not seem to
generalize to other problems considered here.
2.2.2 Testing Closeness between two Unknown Distributions We now turn to the problem of testing closeness between two unknown distributions p, q. The difficulty of this case lies in
the fact that, not knowing q, we cannot subdivide into bins in such a way as to guarantee that
√
kqS k2 = O(1/ n). However, we can do nearly as well by first drawing an appropriate number of
samples from q, and then using them to provide our subdivisions.
Proposition 2.10. There exists an algorithm that given sample access to two distributions p and
q over [n] distinguishes with probability 2/3 between the cases p = q and kp − qk1 > ǫ using
√
O(max(n2/3 /ǫ4/3 , n/ǫ2 )) samples from each of p and q.
Proof. The algorithm is as follows:

7

Algorithm Test-Closeness
Input: Sample access to distributions p and q supported on [n] and ǫ > 0.
Output: “YES” with probability at least 2/3 if p = q, “NO” with probability at least 2/3
if kp − qk1 ≥ ǫ.
1. Let k = min(n, n2/3 ǫ−4/3 ).
2. Define a multiset S by taking Poi(k) samples from q.
3. Run the tester from Lemma 2.3 to distinguish between pS = qS and kpS − qS k1 ≥ ǫ.
To show correctness, we first note that with high probability we have |S| = O(n). Furthermore,
by Lemma 2.6 it follows that the expected squared ℓ2 norm of qS is √
at most 1/k. Therefore, with
probability at least 9/10, we have that |S| = O(n) and kqS k2 = O(1/ k).
The tester from Lemma 2.3 distinguishes between pS = qS and kpS −qS k1 ≥ ǫ with O(nk−1/2 /ǫ2 )
samples. By Fact 2.5, this is equivalent to distinguishing between p = q and kp − qk1 ≥ ǫ. Thus, the
√
total number of samples taken by the algorithm is O(k + nk−1/2 /ǫ2 ) = O(max(n2/3 ǫ−4/3 , n/ǫ2 )).
We consider a generalization of testing closeness where we have access to different size samples
from the two distributions, and use our technique to provide the first sample-optimal algorithm for
the entire range of parameters:
Proposition 2.11. There exists an algorithm that given sample access to two distributions, p and
q over [n] distinguishes with probability 2/3 between the cases p = q and kp − qk1 > ǫ given m1
√
−1/2
samples from q and an additional m2 = O(max(nm1 /ǫ2 , n/ǫ2 )) samples from each of p and q.
Proof. The algorithm is as follows:
Algorithm Test-Closeness-Unequal
Input: Sample access to distributions p and q supported on [n] and ǫ > 0.
Output: “YES” with probability at least 2/3 if p = q, “NO” with probability at least 2/3
if kp − qk1 ≥ ǫ.
1. Let k = min(n, m1 ).
2. Define a multiset S by taking Poi(k) samples from q.
3. Run the tester from Lemma 2.3 to distinguish between pS = qS and kpS − qS k1 ≥ ǫ.
To show correctness, we first note that with high probability we have |S| = O(n). Furthermore,
by Lemma 2.6 it follows that the expected squared ℓ2 -norm of qS is √
at most 1/k. Therefore, with
probability at least 9/10, we have that |S| = O(n) and kqS k2 = O(1/ k).
The tester from Lemma 2.3 distinguishes between pS = qS and kpS −qS k1 ≥ ǫ with O(nk−1/2 /ǫ2 )
samples. By Fact 2.5, this is equivalent to distinguishing between p = q and kp−qk1 ≥ ǫ. In addition
to the m1 samples from q, we had to take O(nk −1/2 /ǫ2 ) = O(m2 ) samples from each of p and q.

8

2.2.3 Nearly Instance–Optimal Testing In this subsection, we provide near-optimal testers
for identity and closeness in the instance-optimal setting. We start with the simpler case of testing
identity to a fixed distribution. This serves as a warm-up for the more challenging case of two
unknown distributions.
Note that the identity tester of Proposition 2.7 is sample-optimal only for a worst-case choice
of the explicit distribution q. (It turns out that the worst case corresponds to q being the uniform
distribution over [n].) Intuitively, for most choices of q, one can actually do substantially better.
This fact was first formalized and shown in [VV14].
In the following proposition, we give a very simple tester with a compact analysis whose sample
complexity is essentially optimal as a function of q. The basic idea of our tester is the following:
First, we partition the domain into categories based on the approximate mass of the elements of q,
and then we run an ℓ2 -tester independently on each category.
Proposition 2.12. There exists an algorithm that on input an explicit distribution q over [n],
a parameter ǫ > 0, and Õ(kqk2/3 /ǫ2 ) samples from a distribution p over [n] distinguishes with
probability at least 2/3 between the cases where p = q and kp − qk1 ≥ ǫ.
Proof. For j = 0, . . . , k with k = ⌈2 log 2 (10n/ǫ)⌉, let Sj ⊆ [n] be the set of coordinates i ∈ [n] so
that qi ∈ (2−j−1 , 2−j ]. Let S∞ be the set of coordinates i ∈ [n] so that qi < 2−k−1 ≤ ǫ/(10n). We
note that if kp − qk1 > ǫ, then kp[Sj ] − q[Sj ]k1 ≫ ǫ/ log(n/ǫ) for some j. We claim that it suffices
to design a tester that distinguishes between the cases that p[Sj ] = q[Sj ] and kp[Sj ] − q[Sj ]k1 ≫
ǫ/ log(n/ǫ) with probability at least 2/3. Repeating such a tester O(log log(n/ǫ)) times amplifies
its probability of success to 1 − 1/ log 2 (n/ǫ). By a union bound over j, all such testers are correct
with probability at least 2/3. To show completeness, note that if p = q, then p[Sj ] = q[Sj ] for all j,
and therefore all testers output “YES”. For soundness, if kp − q 1 ≥ ǫ, there exists a j such that
kp[Sj ] − q[Sj ]k1 ≫ ǫ/ log(n/ǫ), and therefore the corresponding tester returns “NO”.
To test whether kp[Sj ] − q[Sj ]k1 ≫ ǫ/ log(n/ǫ) versus p[Sj ] = q[Sj ], we proceed as follows: We
first use O(log2 (n/ǫ)/ǫ2 ) samples to approximate kp[Sj ]k1 to within additive error ǫ/(10 log(n/ǫ)).
If kq[Sj ]k1 is not within the range of possible values, we determine that p[Sj ] 6= q[Sj ]. Otherwise, we
consider the conditional distributions (p|Sj ), (q|Sj ) and describe a tester to distinguish between the
cases that (p|Sj ) = (q|Sj ) and k(p|Sj ) − (q|Sj )k1 ≫ ǫ/(log(n/ǫ)kq[Sj ]k1 ). Note that we can assume
that kq[Sj ]k1 ≫ ǫ/ log(n/ǫ), otherwise there is nothing to prove. We note that this necessarily fails
to happen if j = ∞.
−1/2
Let mj = |Sj |. We have that kq[Sj ]k1 = Θ(mj 2−j ) and k(q|Sj )k2 = Θ(mj ). Therefore, using
the tester from Lemma 2.3, we can distinguish between (p|Sj ) = (q|Sj ) and k(p|Sj ) − (q|Sj )k1 ≫
5/2
ǫ′ := ǫ/(log(n/ǫ)kq[Sj ]k1 ) using O(k(q|Sj )k2 · mj /ǫ′2 ) = O(mj 4−j log2 (n/ǫ)/ǫ2 ). samples from
(p|Sj ). The probability that a sample from p lies in Sj is kp[Sj ]k1 ≫ kq[Sj ]k1 ≫ mj 2−j . Using
rejection sampling, we can get a sample from (p|Sj ) using O(2j /mj ) samples from p. Therefore,
3/2
the number of samples from p needed to make the above determination is O(mj 2−j log2 (n/ǫ)/ǫ2 ).
In summary, we have described a tester that distinguishes between p = q and kp − qk1 > ǫ with
3/2
sample complexity polylog(n/ǫ) · O((1 + maxj (mj 2−j ))/ǫ2 ). We note that
kqk2/3 ≥ max
j

P

i∈Sj

2/3
qi

!3/2

3/2

≥ max(mj 2−2j/3 )3/2 = max(mj 2−j ).
j

j

Therefore, the overall sample complexity is O(kqk2/3 polylog(n/ǫ)/ǫ2 ) as desired.

9

We now show how to use our reduction-based approach to obtain the first nearly instanceoptimal algorithm for testing closeness between two unknown distributions. Note that the algorithm
of Proposition 2.12 crucially exploits the a priori knowledge of the explicit distribution. In the
setting where both distributions are unknown, this is no longer possible. At a high-level, our
adaptive closeness testing algorithm is similar to that of Proposition 2.12: We start by partitioning
[n] into categories based on the approximate mass of one of the two unknown distributions, say
q, and then we run an ℓ2 -tester independently on each category. A fundamental difficulty in our
setting is that q is unknown. Hence, to achieve this, we will need to take samples from q and create
categories based on the number of samples coming from each bin.
To state our result, we need the following notation:
Definition 2.13. Let q be a discrete distribution and x > 0. We denote by q <x the pseudodistribution obtained from q by setting the probabilities of all domain elements with probability at
least x to 0.
The main result of this subsection is the following:
Proposition 2.14. Given sample access to two unknown distributions, p, q over [n] and ǫ > 0,
there exists a computationally efficient algorithm that draws an expected
Õ(min(m + kq <1/m k0 kq <1/m k2 /ǫ2 + kqk2/3 /ǫ2 ))
m>0

samples from each of p and q, and distinguishes with probability 2/3 between p = q and kp−qk1 ≥ ǫ.
Before we proceed with the proof of Proposition 2.14 some comments are in order. First, note
√
that since kq <1/m k2 ≤ 1/ m, taking m = min(n, n2/3 /ǫ4/3 ) attains the complexity of the standard
ℓ1 -closeness testing algorithm to within logarithmic factors. (It should be noted that the logarithmic
factors in the above proposition can be removed by combining the required ℓ2 -testers into a single
tester, using as a test statistic a linear combination of the individual test statistics.)
We now illustrate with a number of examples that the algorithm of Proposition 2.14 performs
substantially better than the worst-case optimal ℓ1 -closeness tester in a number of interesting cases.
First, consider the case that the distribution q is essentially supported on relatively heavy bins. It
is easy to see that the sample complexity of our algorithm will then be roughly proportional to
kqk2/3 /ǫ2 . We remark that this bound is essentially optimal, even for the easier setting that q had
been given to us explicitly. As a second example, consider the case that q is roughly uniform. In this
√
case, we have that kqk2 will be small, and our algorithm will have sample complexity Õ( n/ǫ2 ).
Finally, consider the case that the bins of the distribution q can be partitioned into two classes:
they have mass either approximately 1/n or approximately x > 1/n. For this case, our above
algorithm will need
√
Õ(min(x−1 + n/ǫ2 , nx−1/2 /ǫ2 ))
samples. (This follows by taking m = 2/x in the first case, and m = 1 in the second case.)
We remark that this sample bound can be shown to be optimal for such distributions (up to the
logarithmic factor in the Õ). Also note that the aforementioned sample upper bound is strictly
better than the worst-case bound of n2/3 /ǫ4/3 , unless x equals n−2/3 ǫ4/3 .
We are now ready to give the proof of Proposition 2.14.
Proof. We begin by describing and analyzing a testing algorithm that attains the stated sample
complexity for a given value of m. We then show how to adapt this algorithm to complete the
proof.
10

For the case of fixed m, our algorithm is given in the following pseudo-code:
Algorithm Test-Closeness-Adaptive
Input: Sample access to distributions p and q supported on [n] and m, ǫ > 0.
Output: “YES” with probability at least 2/3 if p = q, “NO” with probability at least 2/3
if kp − qk1 ≥ ǫ.
1. Let C be a sufficiently large constant. Draw Cm log2 (n) independent samples from q.
def

2. Divide [n] into B = O(log(m log(n))) categories in the following way: A bin is in
category S−∞ if at most log(n) of the samples from the previous step landed in the
bin. Otherwise, if a samples landed in the bin, place it in category S⌊log2 (a)⌋ .
3. Let pS and qS be the distributions over categories for p and q. Use the standard
ℓ1 -tester to test whether pS = qS versus kpS − qS k1 ≥ ǫ/C with error probability at
most 1/10. If they are unequal, return “NO”.
4. Approximate the probability mass q(S−∞ ) up to additive accuracy ǫ/C. If it is less
than 2ǫ/C, ignore this category in the following.
5. For each category Sa that is non-empty (and not S−∞ thrown out by the last step):
(a) Approximate q(Sa ) to within a factor of 2 with error probability at most
1/(100B).
(b) Verify that p(Sa ) is within a factor of 2 of this approximation. Otherwise, return
“NO”.
(c) Approximate k(q|Sa )k2 to within a factor of 2 with error probability 1/(100B).

(d) Draw samples from p and q until they each have at least C|Sa |k(q|Sa )k2 B 3 /ǫ2
many samples from Sa .
(e) Use these samples along with the ℓ2 -tester of Lemma 2.3 to distinguish between
the cases (p|Sa ) = (q|Sa ) and k(p|Sa ) − (q|Sa )k1 ≥ ǫ/(CBq(Sa )) with error
probability at most 1/(100B).
6. In the latter case, return “NO”. Otherwise, return “YES”.
To analyze the above algorithm, we note that it suffices to assume that all of the intermediate
tests for which the hypotheses are satisfied, return the correct results. We also note that it suffices to
consider the case that m ≤ n/ǫ2 (as otherwise the empirical distribution is already an O(m)-sample
algorithm).
We start by noting that with high probability over the samples taken in Step 1, for any bin i
with q(i) = x the number of samples drawn from this bin is at most xCm log3 (n), and if x > 1/m
the number of samples is at least xCm log(n). Furthermore, if x < 1/(Cm), i lies in category S−∞
with high probability. We assume throughout the rest of this analysis that this event holds for all
bins.
We now prove correctness. Assuming that all intermediate tests are correct, it is easy to see
that if the algorithm returns “NO”, then p and q must be unequal. We need to argue the converse.
If our algorithm returns “YES”, it must be the case that
11

• kpS − qS k1 < ǫ/C.
• For each a with Sa non-empty, except for possibly S−∞ , we have that k(p|Sa ) − (q|Sa )k1 <
ǫ/(CBq(Sa )).
We claim that if this holds, then kp − qk1 < ǫ. This is because, after modifying p by at most ǫ/C,
we may keep the restrictions to each category the same and make it so that pS = qS . Once this is
true, it will be the case that
X
kp − qk1 =
q(Sa )k(p|Sa ) − (q|Sa )k1 < ǫ/C.
a

This completes the proof of correctness.
It remains to analyze the sample complexity. Step 1 clearly takes at most an appropriate
number of samples. Step 3 requires at most O(B/ǫ2 ) samples, which is sufficient for our purposes.
For Step 5, we may analyze the number of samples required for each category, Sa separately.
Note that approximating k(q|Sa )k2 to within a factor of 2 requires at most O(kq[Sa ]k−1
2 log(B))
samples. If a ≥ 0 and Sa in non-empty, it will consist of at least one bin of mass at least (1/(Cm)),
so the sample complexity will be sufficiently small. For a = −∞, kq[Sa ]k−1
2 ≤ kq[Sa ]k0 kq[Sa ]k2 ,
and this is within our desired sample complexity bound.
We note that C|Sa |k(q|Sa )k2 B 3 /ǫ2 samples are indeed enough to run our ℓ2 -tester. We can
obtain this many samples by taking at most
polylog(n/ǫ)|Sa |k(q|Sa )k2 /q(Sa )/ǫ2 = polylog(n/ǫ)|Sa |kq[Sa ]k2 /ǫ2
samples from each of p and q. Now, if a > 0, all bins in Sa have mass xpolylog(n) for some
appropriate value of x. We will then have that
|Sa |kq[Sa ]k2 = x|Sa |3/2 polylog(n) ≤ kq[Sa ]k2/3 polylog(n) ≤ kqk2/3 polylog(n),
which is sufficient.
Finally, for a = −∞, the number of samples required is
polylog(n/ǫ)|Sa |kq[Sa ]k2 /ǫ2 ≤ polylog(n/ǫ) · kq <1/m k0 · kq <1/m k2 /ǫ2 .
This completes the proof fo the case of a fixed value of m.
In order to obtain the minimum over all m we proceed as follows: First, since the product
kq <1/m k0 · kq <1/m k2 is decreasing in m, the minimum is attained (up to a constant factor) by
taking m to be the smallest power of 2 so that m > kqk2/3 /ǫ2 + kq <1/m k0 kq <1/m k2 /ǫ2 . Therefore,
it suffices to iterate the above procedure taking m to be increasingly large powers of 2 until the
algorithm terminates with O(mpolylog(n/ǫ)) samples. This completes the proof.
2.2.4 Testing Closeness in Hellinger Distance In this subsection, we use our reductionbased approach to obtain a nearly sample-optimal algorithm for testing closeness of two unknown
distributions with respect to the Hellinger distance. We prove:
Proposition 2.15. There exists an algorithm that given sample access to two distributions p and q
supported on [n] draws Õ(min(n2/3 /ǫ4/3 , n3/4 /ǫ)) samples from each and distinguishes between the
cases p = q and H 2 (p, q) ≥ ǫ with probability at least 2/3.

12

Proof. First, note that an O(n2/3 /ǫ4/3 ) upper bound follows immediately from the upper bound
on ℓ1 -testing and the fact that kp − qk1 ≥ H 2 (p, q). To prove the Õ(n3/4 /ǫ) lower bound, we use
ideas similar to those in our adaptive closeness tester from the previous subsection. In particular,
let m = n3/4 /ǫ. We take Õ(m) samples from q to divide [n] into O(log(m)) categories so with
high probability we have: (i) in all but one category, each bin in the category has the same mass
under q up to polylog(m) factors, and (ii) all bins in the remaining category have mass at most
1/m. We can then verify using Õ(n3/4 /ǫ) samples that either pS 6= qS or that kpS − qS k1 < ǫ/100.
In the former case, we output “NO”, while in the latter case it suffices to distinguish for each
category between the cases that p = q on that category, and that the contribution of that category
to H 2 (p, q) is at least ǫ/(C log(m)), for C some sufficiently large constant.
Suppose that we have a category S so that for each bin in S the mass of this bin under q is
within a polylog factor of x. Then, H 2 (p[S], q[S]) < polylog(m)kp[S] − q[S]k22 /x. Therefore, it
suffices to distinguish between the cases p[S] = q[S] and kp[S] − q[S]k22 ≥ xǫ/polylog(m). This can
be done as follows: We define the distribution p′ by taking a sample from p, leaving it where it is
if the sample lies in S, and randomly and uniformly placing it in one of N new bins (for some√very
large N ) otherwise. Defining q ′ similarly, we note that kp′ − q ′ k2 = kp[S] − q[S]k2 + O(1/ N ).
Therefore, we can distinguish between p = q and kp[S] − q[S]k2 > δ using O(kq[S]k2 /δ2 ) samples
with our standard ℓ2 -tester. In summary, the number of samples required to perform this test is
polylog(m)kq[S]k2 /(xǫ) ≤ Õ(n1/2 x/(xǫ)) = Õ(n1/2 /ǫ).
Finally, we need to consider the case of the last category. Here, we use that kp[S] − q[S]k1 ≥
H 2 (p[S], q[S]), and therefore it suffices to distinguish between p[S] = q[S] and kp[S] − q[S]k1 > ǫ.
Equivalently, it suffices to distinguish between (p|S) = (q|S) and k(p|S) − (q|S)k1 > ǫ/q(S). This
can be achieved using
O(max(n2/3 q(S)4/3 /ǫ4/3 , n1/2 q(S)2 /ǫ2 ))
samples from the conditional distributions. This is at most
O(max(n2/3 q(S)1/3 /ǫ4/3 , n1/2 q(S)/ǫ2 ))
samples from the original distribution. Since q(S) < n/m = n1/4 ǫ, this quantity is at most
O(n3/4 /ǫ) ,
which completes the proof.
2.2.5 Independence Testing In this subsection we study the problem of testing independence
of a d-dimensional discrete distribution p. More specifically, we want to design a tester that distinguishes between the case that p is a product distribution versus ǫ-far from any product distribution,
in ℓ1 -norm. We start by giving an optimal independence tester for the two-dimensional case, and
then handle the case of arbitrary dimension.
Our algorithm for testing independence in two dimensions is as follows:

13

Algorithm Test-Independence-2D
Input: Sample access to a distribution p on [n] × [m] with n ≥ m and ǫ > 0.
Output:“YES” with probability at least 2/3 if the coordinates of p are independent, “NO”
with probability at least 2/3 if p is ǫ-far from any product distribution on [n] × [m].
1. Let k = min(n, n2/3 m1/3 ǫ−4/3 ).
2. Let S1 be a multiset in [n] obtained by taking Poi(k) samples from p1 = π1 (p). Let
S2 be a multiset in [m] obtained by taking Poi(m) samples from p2 = π2 (p). Let S
be the multiset of elements of [n] × [m] so that
1 + {Number of copies of (a, b) in S} =

(1 + {Number of copies of a in S1 })(1 + {Number of copies of b in S2 }).
3. Let q be the distribution on [n] × [m] obtained by taking (x1 , y1 ), (x2 , y2 ) independent
samples from p and returning (x1 , y2 ). Run the tester from Lemma 2.3 to distinguish
between the cases pS = qS and kpS − qS k1 ≥ ǫ.
For correctness, we note that by Lemma 2.6, with probability at least 9/10 over our samples
from S1 and S2 , all of the above hold: (i) |S1 | = O(n) and |S2 | = O(m), and (ii) k(p1 )S1 k22 = O(1/k),
k(p2 )S2 k22 = O(1/m). We henceforth condition on this event. We note that the distribution q is
exactly p1 × p2 . Therefore, if the coordinates of p are independent, then p = q. On the other
hand, since q has independent coordinates, if p is ǫ-far from any product distribution, kp − qk1 ≥ ǫ.
Therefore, it suffices to distinguish between p = q and kp − qk1 ≥ ǫ. By Fact 2.5, this is equivalent
to distinguishing between pS = qS and kpS − qS k1 ≥ ǫ. This completes correctness.
We now analyze the sample complexity. We first draw samples when picking S1 and S2 . With
√
high probability, the corresponding number of samples is O(m+k) = O(max(n2/3 m1/3 ǫ−4/3 , nm/ǫ2 )).
Next, we note that qS = (p1 )S1 × (p2 )S2 . Therefore, by Lemma 2.3, the number of samples drawn
in the last step of the algorithm is at most
O(nmkqS k2 /ǫ2 ) = O(nmk(p1 )S1 × (p2 )S2 k2 /ǫ2 ) = O(nmk(p1 )S1 k2 k(p2 )S2 k2 /ǫ2 )
√
= O(nmk−1/2 m−1/2 /ǫ2 ) = O(max(n2/3 m1/3 ǫ−4/3 , nm/ǫ2 )).
Drawing a sample from q requires taking only two samples from p, which completes the analysis.
In the following proposition, we generalize the two-dimensional algorithm to optimally test
independence in any number of dimensions.
Proposition 2.16. Let p be a distribution on ×di=1 [ni ]. There is an algorithm that draws



!1/3
!1/2
d
d
Y
Y
1/3
/ǫ4/3 
O max 
ni
/ǫ2 , nj
ni
j

i=1

i=1

samples form p and with probability at least 2/3 distinguishes between the coordinates of p being
independent and p being ǫ-far from any such distribution.
Roughly speaking, our independence tester in general dimension uses recursion to reduce to the
2-dimensional case, in which case we may apply Test-Independence-2D. For the details, see the full
version.
14

Proof. We can assume that all ni ≥ 2, for otherwise removing that term does not affect the
problem. We first note that the obvious generalization of Test-Independence-2D (that is, draw
1/3 Q
min(ni , maxj nj ( di=1 ni )1/3 /ǫ4/3 ) samples from the i-th marginal and use them to subdivide the
domain in that dimension; then run the basic ℓ2 -closeness tester between pS and the product of the
marginals) allows us for any constant d to distinguish between p having independent coordinates
and kp − p∗ k1 > ǫ, where p∗ is the product of the marginals of p, with arbitrarily small constant
probability of failure. This generalization incurs an additional 2O(d) factor in the sample complexity,
hence is not optimal for super-constant d. To obtain the optimal sample complexity, we will use
the aforementioned algorithm for d = 2, 3 along with a careful recursion to reduce the dimension.
Our sample-optimal independence tester in d dimensions is as follows: First, let us assume for
simplicity that the maximum in the sample complexity is attained by the second term with j = 1.
Then, we use the algorithm Test-Independence-2D to distinguish between the cases that the first
coordinate is independent of the others from the case that p is at least ǫ/2-far from the product of
the distributions on the first coordinate and the distribution on the remaining coordinates. If it is
not, we return “NO”. Otherwise, we recursively test whether or not the coordinates (p2 , . . . , pd ) are
independent versus at least ǫ/2-far from the product of their marginals, and return the result. We
note that if (p2 , . . . , pd ) is ǫ/2-close to the product distribution on p2 , . . . , pd , and if p is ǫ/2-close
to the product distribution on its first coordinate with the remaining coordinates, then p is ǫ-close
to the product of its marginals.
Qd
We next deal with Q
the remaining
√ case. We let N = i=1 ni . We first partition [N ] into sets Si
for 1 ≤ i ≤ 3 so that j∈Si nj ≤ N . We do this by greedily adding elements to a single set S1
√
until the product is more than N . We then remove the most recently added element, place it in
S2 , and place all remaining elements in S3 . This clearly satisfies the desired property. We let pSi
be the distribution of p ignoring all but the coordinates in Si . We use the obvious independence
tester in three dimensions to distinguish whether the pSi are independent versus p differing from
the product by at least ǫ/4. In the latter case, we return “NO”. In the former, we recursively
distinguish between pSi having independent coordinates versus being ǫ/4-far from the product of
its marginals for each i and return “NO” unless all three pass.
In order to analyze the sample complexity, we note that our d-dimensional independence tester
Q
1/3 Q
uses O(max(( di=1 ni )1/2 /ǫ2 , nj ( di=1 ni )1/3 /ǫ4/3 )) samples on the highest level call to the 2 or 3dimensional version of the tester. It then needs to make O(1) recursive callsQto the high-dimensional
version of the algorithm on distributions with support of size at most ( di=1 ni )1/2 and error at
Q
most ǫ/4. These recursive calls take a total of at most O(( di=1 ni )1/3 /ǫ2 ) samples, which is well
within our desired bounds.
2.2.6 Testing Properties of Collections of Distributions In this subsection, we consider
the model of testing properties of collections of distributions [LRR11] in both the sampling and
query models.
We begin by considering the sampling model, as this is closely related to independence testing.
In fact, in the unknown-weights case, the problem is identical. In the known-weights case, the
problem is equivalent to independence testing, where the algorithm is given explicit access to one
of the marginals (say, the distribution on [m]). For this setting, we give a tester with sample
√
complexity O(max( nm/ǫ2 , n2/3 m1/3 /ǫ4/3 )). We also note that this bound can be shown the be
optimal. Formally, we prove the following:
Proposition 2.17. There is an algorithm that given sample access to a distribution p on [n] × [m]
and an explicit description of the marginal of p on [m] distinguishes between the cases that the
coordinates of p are independent and the case where p is ǫ-far from any product distribution on
15

√
[n] × [m] with probability at least 2/3 using O(max( nm/ǫ2 , n2/3 m1/3 /ǫ4/3 )) samples.
Proof. The algorithm is as follows:
Algorithm Test-Collection-Sample-Model
Input: Sample access to a distribution p on [n]× [m] with ǫ > 0, and an explicit description
of the marginal of p on [m].
Output:“YES” with probability at least 2/3 if the coordinates of p are independent, “NO”
with probability at least 2/3 if p is ǫ-far from any product distribution on [n] × [m].
1. Let k = min(n, n2/3 m1/3 ǫ−4/3 ).
2. Let S1 be a multiset in [n] obtained by taking Poi(k) samples from p1 = π1 (p). Let S2
be a multiset in [m] obtained by taking ⌊m(p2 )i ⌋ copies of i. Let S be the multiset of
elements of [n] × [m] so that
1 + {Number of copies of (a, b) in S} =

(1 + {Number of copies of a in S1 })(1 + {Number of copies of b in S2 }).
3. Let q be the distribution on [n] × [m] obtained by taking (x1 , y1 ), (x2 , y2 ) independent
samples from p and returning (x1 , y2 ). Run the tester from Lemma 2.3 to distinguish
between the cases pS = qS and kpS − qS k1 ≥ ǫ.
√
For the analysis,
at least 9/10, it holds
√
√ we note that k(p2 )S2 k2 = O(1/ m) and with probability
k(p1 )S1 k2 = O(1/ k). Therefore, we have that k(p1 × p2 )S k2 = O(1/ km). Thus, the ℓ2 -tester of
√
Lemma 2.3 draws O(nm1/2 k−1/2 /ǫ2 ) = O(max( nm/ǫ2 , n2/3 m1/3 /ǫ4/3 )) samples and the sample
complexity is bounded as desired.
Next, we consider the query model. In this model, we are essentially guaranteed that the distribution on [m] is uniform, but are allowed to extract samples conditioned on a particular value of the
second coordinate. Equivalently, there are m distributions q1 , . . . , qm on [n].. We wish to distinguish
between
the cases that the qi ’s are identical and the case where there is no distribution q so that
√
1 Pm
kq
− qi k1 ≤ ǫ. We show that we can solve this problem with O(max( n/ǫ2 , n2/3 /ǫ4/3 )) sami=1
m
ples for any m. This is optimal for all m ≥ 2, even if we are guaranteed that q1 = q2 = . . . = q⌊m/2⌋
and q⌊m/2+1⌋ = . . . = qm .
Proposition 2.18. There is an algorithm that given sample access to distributions q1 , . . . , qm on [n]
distinguishes
between the cases that the qi ’s are identical and the case where there is no distribution
√
1 Pm
q so that m i=1 kq−qi k1 ≤ ǫ with probability at least 2/3 using O(max( n/ǫ2 , n2/3 /ǫ4/3 )) samples.
Proof. The algorithm is as follows:

16

Algorithm Test-Collection-Query-Model
Input: Sample access to a distribution q1 , . . . , qm on [n] with ǫ > 0.
Output:“YES” with probability at least 2/3 if thePqi are identical, “NO” with probability
m
1
at least 2/3 if there is no distribution q so that m
i=1 kq − qi k1 ≤ ǫ.
1. Let C be a sufficiently large constant.

2. Let q∗ denote the distribution obtained by sampling from a uniformly random qi .
3. For k from 0 to ⌈log2 (m)⌉:

(a) Select 25k/4 C uniformly random elements i ∈ [m].
(b) For each selected i, use the ℓ1 -closeness tester to distinguish between q∗ = qi and
kq∗ − qi k1 > 2k−1 ǫ with failure probability at most C −2 6−k .
(c) If any of these testers returned “NO”, return “NO”.

4. Return “YES”.
To analyze this algorithm, we note that with probability 9/10 all the testers we call whose
hypotheses are satisfied output correctly. Therefore, if all qi are equal, they are equal to q∗ , and
thus our algorithm returns
“YES” with appropriately large probability.
On the other hand, if for
1 Pm
1 Pm
any q we have that m i=1 kq − qi k1 > ǫ, then in particular m i=1 kq∗ − qi k1 > ǫ. Note that
!
m
X |{i : kq∗ − qi k ≥ 2k−1 ǫ}|2k ǫ
1 X
kq∗ − qi k1 ≤ ǫ/2 + O
.
m
m
i=1

k

1 Pm
k−1 ǫ}| =
Therefore, since m
i=1 kq∗ − qi k1 > ǫ, we have that for some k it holds |{i : kq∗ − qi k ≥ 2
−5k/4
Ω(m2
). For this value of k, there is at least a 9/10 probability that some i with this property
was selected as one of our C25k/4 that were used, and then assuming that the appropriate tester
returned correctly, our algorithm will output “NO”.P
This establishes correctness. The total sample
√
25k/4 k · O( n/ǫ2 4−k + n2/3 /ǫ4/3 2−4k/3 ) =
complexity of this algorithm is easily seen to be
k
√
O(max( n/ǫ2 , n2/3 /ǫ4/3 )).

2.2.7 Testing k-Histograms Finally, in this subsection we use our framework to design a
sample-optimal algorithm for the property of being a k-histogram with known intervals.
Let I be a partition of [n] into k intervals. We wish to be able to distinguish between the cases
where a distribution p has constant density on each interval versus the case where it is ǫ-far from
any such distribution. We show the following:
Proposition 2.19. Let I be a partition of [n] into k intervals. Let p be a distribution on [n].
√
There exists an algorithm which draws O(max( n/ǫ2 , n1/3 k1/3 /ǫ4/3 )) independent samples from p
and distinguishes between the cases where p is uniform on each of the intervals in I from the case
where p is ǫ-far from any such distribution with probability at least 2/3.
Proof. First, we wish to guarantee that each of the intervals has reasonably large support. We can
achieve this as follows: For each interval I ∈ I we divide each bin within I into ⌈n/(k|I|)⌉ bins.
Note that this increases the number of bins in I by at most n/k, hence doing this to each interval
in I at most doubles the total size of the domain. Therefore, after applying this operation we get
a distribution over a domain of size O(n), and each of the k intervals in I is of length Ω(n/k).
17

Next, in order to use an ℓ2 -closeness tester, we want to further subdivide bins using our randomized transformation. To this end, we let m = min(k, n1/3 k1/3 /ǫ4/3 ) and take Poi(m) samples
from p. Then, for each interval Ii ∈ I, we divide each bin in Ii into ⌊nai /(k|Ii |)⌋+ 1 new bins, where
ai is the number of samples that were drawn from Ii . Let Ii′ denote the new interval obtained from
Ii . Note that after this procedure the total number of bins is still O(n) and that the number of bins
in Ii′ is now Ω((n/k)(ai + 1)). Let p′ be the distribution obtained from p under this transformation.
Let q ′ be the distribution obtained by sampling from p′ and then returning a uniform random bin
from the same interval Ii′ as the sample. We claim that the ℓ2 -norm of q ′ is small. In particular the
squared ℓ2 -norm will be the sum over intervals I ′ in our new partition (that is, after the subdivisions
described above) of O(p(I ′ )2 /((n/k)(ai + 1))). Recall that 1/(ai + 1) has
P expectation at most
1/(mp(I ′ )). This implies that the expected squared ℓ2 -norm of q ′ is at most I ′ O(p(I ′ )/(nm/k)) =
O(k/(nm)). Therefore, with large constant probability, we have that kq ′ k22 = O(k/(nm)).
We can now apply the tester from Lemma 2.3 to distinguish between the cases where p′ = q ′
√
and kp′ − q ′ k1 > ǫ with O(n1/2 k1/2 m−1/2 /ǫ2 ) = O(max( n/ǫ2 , n1/3 k1/3 /ǫ4/3 )) samples. We have
that p′ = q ′ if and only if p is flat on each of the intervals in I, and kp′ − q ′ k1 > ǫ if p is ǫ-far from
any distribution which is flat on I. This final test is sufficient to make our determination.

3

Sample Complexity Lower Bounds

We illustrate our lower bound technique by proving tight information-theoretic lower bounds for
testing independence (in any dimension), testing closeness in Hellinger distance, and testing histograms.
3.1

Lower Bound for Two-Dimensional Independence Testing

Theorem 3.1. Let n ≥ m ≥ 2 be integers and ǫ > 0 a sufficiently small universal constant. Then,
any algorithm that draws samples from a distribution p on [n] × [m] and, with probability at least
2/3, distinguishes between the case that the coordinates of p are independent and the case where p
√
is ǫ-far from any product distribution must use Ω(max( nm/ǫ2 , n2/3 m1/3 /ǫ4/3 )) samples.
We split our argument into two parts proving each of the above lower bounds separately.
√
3.1.1 The Ω( nmǫ−2 ) Lower Bound We start by proving the easier of the two bounds. It
should be noted that this part of the lower bound can essentially be obtained using known results.
We give a proof using our technique, in part as a guide to the somewhat more complicated proof
in the next section, which will be along similar lines.
First, we note that it suffices to consider the case where n and m are each sufficiently large since
Ω(ǫ−2 ) samples are required to distinguish the uniform distribution on [2]×[2] from the distribution
which takes value (i, j) with probability (1 + (2δi,j − 1)ǫ)/2.
Our goal is to exhibit distributions D and D ′ over distributions on [n] × [m] so that all distributions in D have independent coordinates, and all distributions in D ′ are ǫ-far from product
√
distributions, so that for any k = o( nm/ǫ2 ), no algorithm given k independent samples from a
random element of either D or D ′ can determine which family the distribution came from with
greater than 90% probability.
Although the above will be our overall approach, we will actually analyze the following generalization in order to simplify the argument. First, we use the standard Poissonization trick. In
particular, instead of drawing k samples from the appropriate distribution, we will draw Poi(k)
samples. This is acceptable because with 99% probability, this is at least Ω(k) samples. Next, we
relax the condition that elements of D ′ be ǫ-far from product distributions, and simply require that
18

they are Ω(ǫ)-far from product distributions with 99% probability. This is clearly equivalent upon
accepting an additional 1% probability of failure, and altering ǫ by a constant factor.
Finally, we will relax the constraint that elements of D and D ′ are probability distributions.
Instead, we will merely require that they are positive measures on [n] × [m], so that elements of D
are product measures and elements of D ′ are Ω(ǫ)-far from being product measures with probability
at least 99%. We will require that the selected measures have total mass Θ(1) with probability
at least 99%, and instead of taking samples from these measures (as this is no longer as sensible
concept), we will use the points obtained from a Poisson process of parameter k (so the number
of samples in a given bin is a Poisson random variable with parameter k times the mass of the
bin). This is sufficient, because the output of such a Poisson process for a measure µ is identical to
the outcome of drawing Poi(kµk1 k) samples from the distribution µ/kµk1 . Moreover, the distance
from µ to the nearest product distribution is kµk1 times the distance from µ/kµk1 to the nearest
product distribution.
We are now prepared to describe D and D ′ explicitly:
• We define D to deterministically return the uniform distribution µ with µ(i, j) =
(i, j) ∈ [n] × [m].

1
nm

for all

• We define D ′ to return the positive measure ν so that for each (i, j) ∈ [n] × [m] the value
1−ǫ
ν(i, j) is either 1+ǫ
nm or nm each with probability 1/2 and independently over different pairs
(i, j).
It is clear that kµk1 , kνk1 = Θ(1) deterministically. We need to show that the relevant Poisson
processes return similar distributions. To do this, we consider the following procedure: Let X be a
uniformly random bit. Let p be a measure on [n] × [m] drawn from either D if X = 0 or from D ′
if X = 1. We run a Poisson process with parameter k on p, and let ai,j be the number of samples
drawn from bin (i, j). We wish to show that, given access to all ai,j ’s, one is not able to determine
the value of X with probability more than 51%. To prove this, it suffices to bound from above the
mutual information between X and the set of samples (ai,j )(i,j)∈[n]×[m] . In particular, this holds
true because of the following simple fact:
Lemma 3.2. If X is a uniform random bit and A is a correlated random variable, then if f is any
function so that f (A) = X with at least 51% probability, then I(X : A) ≥ 2 · 10−4 .
Proof. This is a standard result in information theory, and the simple proof is included here for
the sake of completeness. We begin by showing that I(X : f (A)) ≥ 2 · 10−4 . This is because the
conditional entropy, H(X|f (A)), is the expectation over f (A) of h(q) = −q log(q)−(1−q) log(1−q),
where q is the probability that X = f (A) conditional on that value of f (A). Since E[q] ≥ 51% and
since h is concave, we have that H(X|f (A)) ≤ h(0.51) < log(2) − 2 · 10−4 . Therefore, we have that
I(X : f (A)) = H(X) − H(X|f (A)) ≥ log(2) − (log(2) − 2 · 10−4 ) = 2 · 10−4 .

The lemma now follows from the data processing inequality, i.e., the fact that I(X : A) ≥ I(X :
f (A)).
In order to bound I(X : {ai,j }) from above, we note that the ai,j ’s are independent conditional
on X, and therefore that
X
I(X : (ai,j )(i,j)∈[n]×[m] ) ≤
I(X : ai,j ).
(1)
(i,j)∈[n]×[m]

By symmetry, it is clear that all of the ai,j ’s are the same, so it suffices to consider I(X : a) for a
being one of the ai,j . We prove the following technical lemma:
19

Lemma 3.3. For all (i, j) ∈ [n] × [m], it holds I(X : ai,j ) = O(k2 ǫ4 /(m2 n2 )).
The proof of this lemma is technical and is deferred to Appendix A. The essential idea is that
we condition on whether or not λ := k/(nm) ≥ 1. If λ < 1, then the probabilities of seeing 0 or 1
samples are approximately the same, and most of the information comes from how often one sees
exactly 2 samples. For λ ≥ 1, we are comparing a Poisson distribution to a mixture of Poisson
distributions with the same average mean, and we can deal with the information theory by making
a Gaussian approximation.
By Lemma 3.3, (1) yields that I(X : (ai,j )(i,j)∈[n]×[m] ) = O(k2 ǫ4 /mn) = o(1). In conjunction
√
with Lemma 3.2, this implies that o( mn/ǫ2 ) samples are insufficient to reliably distinguish an
element of D from an element of D ′ . To complete the proof, it remains to show that elements of
D are all product distributions, and that most elements of D ′ are far from product distributions.
The former follows trivially, and the latter is not difficult. We show:
Lemma 3.4. With 99% probability a sample from D ′ is Ω(ǫ)-far from being a product distribution.
Proof. For this, we require the following simple claim:
Claim 3.5. Let µ be a measure on [n] × [m] with marginals µ1 and µ2 . If kµ − µ1 × µ2 /kµk1 k1 >
ǫkµk1 , then µ is at least ǫkµk1 /4-far from any product measure.
Proof. By normalizing, we may assume that kµk1 = 1. Suppose for the sake of contradiction that
for some measures ν1 , ν2 it holds kµ − ν1 × ν2 k1 ≤ ǫ/4. Then, we must have that kµi − νi k1 ≤ ǫ/4.
This means that
kµ − µ1 × µ2 k1 ≤ kµ − ν1 × ν2 k1 + kν1 × ν2 − µ1 × ν2 k1 + kµ1 × ν2 − µ1 × µ2 k1
≤ ǫ/4 + kν2 k1 kµ1 − ν1 k1 + kµ1 k1 kµ2 − ν2 k1

≤ ǫ/4(3 + ǫ/4) ≤ ǫ ,
which yields the desired contradiction.

In light of the above claim, it suffices to show that with 99% probability over the choice of ν
from D ′ we have kν − ν1 × ν2 /kνkk1 = Ω(ǫ). For this, we note that when n and m are sufficiently
large constants, with 99% probability we have that: (i) |kνk1 − 1| ≤ ǫ/10, (ii) ν1 has mass in the
range [(1 − ǫ/10)/n, (1 + ǫ/10)/n] for at least half of its points, and (iii) ν2 has mass in the range
[(1 − ǫ/10)/m, (1 + ǫ/10)/m] for at least half of its points. If all of these conditions hold, then for
at least a quarter of all points the mass assigned by ν1 × ν2 /kνk1 is between (1 − ǫ/2)/(nm) and
(1 + ǫ/2)/(nm). In such points, the difference between this quantity and the mass assigned by ν is
at least ǫ/(2mn). Therefore, under these conditions, we have that
kν − ν1 × ν2 /kνk1 k1 ≥ (nm/4)(ǫ/(2mn)) = ǫ/8 = Ω(ǫ).
This completes the proof.
3.1.2 The Ω(n2/3 m1/3 ǫ−4/3 ) Lower Bound In this subsection, we prove the other half of the
lower bound. As in the proof of the previous subsection, it suffices to exhibit a pair of distributions
D, D ′ over measures on [n] × [m], so that with 99% probability each of these measures has total
mass Θ(1), the measures from D are product measures and those from D ′ are Ω(ǫ)-far from being
product measures, and so that if a Poisson process with parameter k = o(n2/3 m1/3 /ǫ−4/3 ) is used
to draw samples from [n] × [m] by way of a uniformly random measure from either D or D ′ , it is
impossible to reliably determine which distribution the measure came from.
We start by noting that it suffices to consider only the case where k ≤ n/2, since otherwise the
bound follows from the previous subsection. We define the distributions over measures as follows:
20

• When generating an element from either D or D ′ , we generate a sequence c1 , . . . , cn , where
ci is 1/k with probability k/n and 1/n otherwise. Furthermore, we assume that the ci ’s are
selected independently of each other.
• Then D returns the measure µ where µ(i, j) = ci /m.
• The distribution D ′ generates the measure ν, where ν(i, j) = 1/(km) if ci = 1/k and otherwise
ν(i, j) is randomly either (1 + ǫ)/(nm) or (1 − ǫ)/(nm).
It is easy to verify that with 99% probability that kµk1 , kνk1 = Θ(1). It is also easy to see that
D only generates product measures. We can show that D ′ typically generates measures far from
product measures:
Lemma 3.6. With 99% probability a sample from D ′ is Ω(ǫ)-far from being a product distribution.
Proof. If ν is a random draw from D ′ and ν2 is second marginal distribution, it is easy to see
that with high probability it holds ν2 (j)/kνk1 ∈ [(1 − ǫ/3)/m, (1 + ǫ/3)/m] for at least half of
the j ∈ [m]. Also, with high probability, for at least half of the i ∈ [n] we have that ν1 (i) ∈
[(1 − ǫ/3)/n, (1 + ǫ/3)/n]. For such pairs (i, j), we have that |ν(i, j) − ν1 (i)ν2 (j)/kνk1 | ≥ ǫ/(4nm),
and thus
kν − ν1 × ν2 /kνk1 k1 ≥ (nm/4)(ǫ/4nm) ≥ ǫ/16 = Ω(ǫ).
The lemma follows by Claim 3.5.
It remains to show that the Poisson process in question is insufficient to distinguish which
distribution the measure came from with non-trivial probability. As before, we let X be a uniformly
random bit, and let µ be a measure drawn from either D if X = 0 or D ′ if X = 1. We run the
Poisson process and let ai,j be the number of elements drawn from bin (i, j). We let Ai be the
vector (ai,1 , ai,2 , . . . , ai,m ). It suffices to show that the mutual information I(X : A1 , A2 , . . . , An ) is
small.
Note that the Ai ’s are conditionally independent on X (though that ai,j ’s are not, because ai,1
and ai,2 are correlated due to their relation to ci ). Therefore, we have that
I(X : A1 , A2 , . . . , An ) ≤

n
X

I(X : Ai ) = nI(X : A) ,

(2)

i=1

by symmetry where A = Ai . To complete the proof, we need the following technical lemma:
Lemma 3.7. We have that I(X : A) = O(k3 ǫ4 /(n3 m)).
Morally speaking, this lemma holds because if all the c’s were 1/n, we would get a mutual
information of roughly O(k2 ǫ4 /(n2 m)), by techniques from the last section. However, the possibility
that c = 1/k adds sufficient amount of “noise” to somewhat decrease the amount of available
information. The formal proof is deferred to Appendix A. Combining (2) and the above lemma,
we obtain that
I(X : A1 , . . . , An ) = O(k3 ǫ4 /(n2 m) = o(1).
This completes the proof.

21

3.2 Lower Bound for Hellinger Closeness Testing We prove that our upper bound for
Hellinger distance closeness is tight up to polylogarithmic factors.
Proposition 3.8. Any algorithm that given sample access to distributions p and q on [n] that distinguishes between p = q and H 2 (p, q) > ǫ with probability at least 2/3 must take Ω(min(n2/3 /ǫ4/3 , n3/4 /ǫ))
samples.
Proof. The proof of this lower bound follows our direct information-theoretic approach. We let X
be randomly either 0 or 1. We then describe a distribution of pairs of pseudo-distributions p, q on
[n] so that if X = 0 then p = q and if X = 1, H 2 (p, q) ≫ ǫ with 99% probability, and so that
kpk1 , kqk1 = Θ(1) with 99% probability. We then show that the mutual information between X
and the output of Poi(k) samples from each of p and q is o(1) for k = o(min(n2/3 /ǫ4/3 , n3/4 /ǫ)).
We begin by describing this distribution. For i = 1, . . . , n − 1 with probability min(k/n, 1/2)
we set pi = qi = 1/(2k), otherwise if X = 0, we set pi = qi = ǫ/n, and if X = 1 randomly set either
pi = 2ǫ/n, qi = 0 or pi = 0, qi = 2ǫ/n. pn = qn = 1/3.
First, we note that X = 0, we have p = q and if X = 1, H 2 (p/kpk1 , q/kqk1 ) ≫ ǫ with high
probability. Furthermore, kpk1 , kqk1 = Θ(1) with high probability.
Let ai , bi be the number of samples drawn from bin i under p and q respectively. We wish to
bound I(X : a1 , b1 , . . . , an , bn ) from below. By conditional independence, this is
X
I(X : ai , bi ) .
i

Note that I(X : an , bn ) = 0, otherwise the distribution on (X, ai , bi ) is independent of i, so we will
analyze it ignoring the subscript i.
It is not hard to see that if k = o(n/ǫ),
X  (Pr((a, b) = (i, j)|X = 0) − Pr((a, b) = (i, j)|X = 1))2 
O
I(X : a, b) =
Pr((a, b) = (i, j)|X = 0) + Pr((a, b) = (i, j)|X = 1)
i,j

=

X
i,j

(O(kǫ/n)max(2,i+j) )2
i!j!Ω(min(k/n, 1)(1/(2))i+j )

= O(max(1, n/k))(ǫk/n)4 .
If k = o(n), this is O(ǫ4 k3 /n3 ), so the total mutual information with the samples is O(ǫ4 k3 /n2 ),
which is o(1) if k = o(n2/3 /ǫ4/3 ). Note that n2/3 /ǫ4/3 is smaller than n3/4 /ǫ if and only if it is less
than n, so the lower bound in proved in this case. Otherwise, if k > n and k = o(n3/4 /ǫ), then the
mutual information is O(n(ǫk/n)4 ) = O(ǫ4 k4 /n3 ) = o(1), proving the other case of our bound.
Lower Bound q
for High Dimensional Independence Testing We need to show two
1/3

Qd
1/3 Qd
2
lower bounds, namely
/ǫ4/3 . We can obtain both of these from
j=1 nj
i=1 ni /ǫ and ni
the lower bound constructions from the 2-variable case. In particular, for the first bound, we
have Q
shown that it takes this many samples to distinguish between the uniform distribution on
N = di=1 ni inputs (which is a product distribution), from a distribution that assigns probability
(1 ± ǫ)/N randomly to each input (which once renormalized is probably Ω(ǫ)-far from being a
product distribution). For the latter bound, we think of [n1 ] × · · · × [nd ] as [ni ] × ([n1 ] × · · · [ni−1 ] ×
[ni+1 ] × · · · × [nd ]), and consider the lower bound construction for 2-variable independence testing.
1/3
It then takes at least ni N 1/3 /ǫ4/3 samples to reliably distinguish a “YES” instance from a “NO”
instance. Note that in a “YES” instance the first and second coordinates are independent and
3.3

22

the distribution on the second coordinate is uniform. Therefore, in a “YES” instance we have a
d-dimensional product distribution. On the other hand, a “NO” instance is likely Ω(ǫ)-far from any
distribution that is a product distribution over just this partition of the coordinates, and therefore
Ω(ǫ) far from any d-dimensional product distribution. This completes the proof.
3.4 Lower Bound for k-Histograms We can use the above construction to show that our
upper bound for k-histograms is in fact tight. In particular, if we rewrite [n] as [k] × [n/k]
and let the intervals be given by the subsets [n/k] × {i} for 1 ≤ i ≤ k, we need to show that
√
Ω(max( n/ǫ2 , n1/3 k1/3 /ǫ4/3 )) samples are required from a distribution p on [k] × [n/k] to distinguish between the coordinates of p being independent with the second coordinate having the
uniform distribution, and p being ǫ-far from any such distribution. We note that in the lower bound
distributions given for each part of our lower bound constructions for the independence tester, the
“YES” distributions all had uniform marginal over the second coordinate. Therefore, the same hard
√
distributions give a lower bound for testing k-histograms of Ω(max( n/ǫ2 , k2/3 (n/k)1/3 /ǫ4/3 )) =
√
Ω(max( n/ǫ2 , n1/3 k1/3 /ǫ4/3 )). This completes the proof.
Acknowledgment. We would like to thank Oded Goldreich for numerous useful comments and
insightful conversations that helped us improve the presentation of this work. We are grateful to Oded for his excellent exposition of our reduction-based technique in his recent lecture
notes [Gol16b].

References
[ADJ+ 11] J. Acharya, H. Das, A. Jafarpour, A. Orlitsky, and S. Pan. Competitive closeness
testing. Journal of Machine Learning Research - Proceedings Track, 19:47–68, 2011.
[ADJ+ 12] J. Acharya, H. Das, A. Jafarpour, A. Orlitsky, S. Pan, and A. Suresh. Competitive
classification and closeness testing. In COLT, 2012.
[ADK15]

J. Acharya, C. Daskalakis, and G. Kamath. Optimal testing for properties of distributions. CoRR, abs/1507.05952, 2015.

[AJOS14] J. Acharya, A. Jafarpour, A. Orlitsky, and A. T. Suresh. Sublinear algorithms for outlier
detection and generalized closeness testing. In 2014 IEEE International Symposium on
Information Theory, pages 3200–3204, 2014.
[Bat01]

T. Batu. Testing Properties of Distributions. PhD thesis, Cornell University, 2001.

[BDKR02] T. Batu, S. Dasgupta, R. Kumar, and R. Rubinfeld. The complexity of approximating
entropy. In ACM Symposium on Theory of Computing, pages 678–687, 2002.
[BFF+ 01] T. Batu, E. Fischer, L. Fortnow, R. Kumar, R. Rubinfeld, and P. White. Testing
random variables for independence and identity. In Proc. 42nd IEEE Symposium on
Foundations of Computer Science, pages 442–451, 2001.
[BFR+ 00] T. Batu, L. Fortnow, R. Rubinfeld, W. D. Smith, and P. White. Testing that distributions are close. In IEEE Symposium on Foundations of Computer Science, pages
259–269, 2000.
[BFR+ 13] T. Batu, L. Fortnow, R. Rubinfeld, W. D. Smith, and P. White. Testing closeness of
discrete distributions. J. ACM, 60(1):4, 2013.
23

[BKR04]

T. Batu, R. Kumar, and R. Rubinfeld. Sublinear algorithms for testing monotone and
unimodal distributions. In ACM Symposium on Theory of Computing, pages 381–390,
2004.

[BV15]

B. B. Bhattacharya and G. Valiant. Testing closeness with unequal sized samples.
CoRR, abs/1504.04599, 2015.

[Can15]

C. L. Canonne. A survey on distribution testing: Your data is big. but is it blue?
Electronic Colloquium on Computational Complexity (ECCC), 22:63, 2015.

[CDGR16] C. L. Canonne, I. Diakonikolas, T. Gouleakis, and R. Rubinfeld. Testing shape restrictions of discrete distributions. In 33rd Symposium on Theoretical Aspects of Computer
Science, STACS, pages 25:1–25:14, 2016.
[CDVV14] S. Chan, I. Diakonikolas, P. Valiant, and G. Valiant. Optimal algorithms for testing
closeness of discrete distributions. In SODA, pages 1193–1203, 2014.
[DDS+ 13] C. Daskalakis, I. Diakonikolas, R. Servedio, G. Valiant, and P. Valiant. Testing k-modal
distributions: Optimal algorithms via reductions. In SODA, pages 1833–1852, 2013.
[DKN15a] I. Diakonikolas, D. M. Kane, and V. Nikishkin. Optimal algorithms and lower bounds
for testing closeness of structured distributions. In 56th Annual IEEE Symposium on
Foundations of Computer Science, FOCS 2015, 2015.
[DKN15b] I. Diakonikolas, D. M. Kane, and V. Nikishkin. Testing Identity of Structured Distributions. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete
Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, 2015.
[GGR98]

O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to
learning and approximation. Journal of the ACM, 45:653–750, 1998.

[GMV09]

S. Guha, A. McGregor, and S. Venkatasubramanian. Sublinear estimation of entropy
and information distances. ACM Trans. Algorithms, 5(4):35:1–35:16, November 2009.

[Gol16a]

O. Goldreich. The uniform distribution is complete with respect to testing identity
to a fixed distribution. Electronic Colloquium on Computational Complexity (ECCC),
23:15, 2016.

[Gol16b]

O. Goldreich. Lecture Notes on Property Testing of Distributions. Available at
http://www.wisdom.weizmann.ac.il/ oded/PDF/pt-dist.pdf, March, 2016.

[GR00]

O. Goldreich and D. Ron. On testing expansion in bounded-degree graphs. Technical
Report TR00-020, Electronic Colloquium on Computational Complexity, 2000.

[ILR12]

P. Indyk, R. Levi, and R. Rubinfeld. Approximating and Testing k-Histogram Distributions in Sub-linear Time. In PODS, pages 15–22, 2012.

[LR05]

E. L. Lehmann and J. P. Romano. Testing statistical hypotheses. Springer Texts in
Statistics. Springer, 2005.

[LRR11]

R. Levi, D. Ron, and R. Rubinfeld. Testing properties of collections of distributions.
In ICS, pages 179–194, 2011.

24

[NP33]

J. Neyman and E. S. Pearson. On the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series
A, Containing Papers of a Mathematical or Physical Character, 231(694-706):289–337,
1933.

[Pan08]

L. Paninski. A coincidence-based test for uniformity given very sparsely-sampled discrete data. IEEE Transactions on Information Theory, 54:4750–4755, 2008.

[RRSS09] S. Raskhodnikova, D. Ron, A. Shpilka, and A. Smith. Strong lower bounds for approximating distribution support size and the distinct elements problem. SIAM J. Comput.,
39(3):813–842, 2009.
[RS96]

R. Rubinfeld and M. Sudan. Robust characterizations of polynomials with applications
to program testing. SIAM J. on Comput., 25:252–271, 1996.

[Rub12]

R. Rubinfeld. Taming big probability distributions. XRDS, 19(1):24–28, 2012.

[Val11]

P. Valiant. Testing symmetric properties of distributions.
40(6):1927–1968, 2011.

[VV14]

G. Valiant and P. Valiant. An automatic inequality prover and instance optimal identity
testing. In FOCS, 2014.

A
A.1

SIAM J. Comput.,

Omitted Proofs from Section 3
Proof of Lemma 3.3 We note that
I(X : a) =

X
ℓ



Pr(a = ℓ|X = 0)
O Pr(a = ℓ) 1 −
Pr(a = ℓ|X = 1)

2 !

.

A simple computation yields that
Pr(a = ℓ|X = 0) = e−k/mn

Pr(a = ℓ|X = 1) =



ℓ
−k/mn (k/mn)

e

ℓ!



(k/mn)ℓ
,
ℓ!

e−kǫ/mn (1 + ǫ)ℓ + ekǫ/mn (1 − ǫ)ℓ
2

!

.

We condition based on the size of k/mn. First, we analyze the case that k/mn ≤ 1.
Expanding the above out as a Taylor series in ǫ we note that the odd degree terms cancel.
Therefore, we can see that if ℓ ≤ 2
!


e−kǫ/mn (1 + ǫ)ℓ + ekǫ/mn (1 − ǫ)ℓ
(3)
= 1 + O ǫ2 (k/mn)2−ℓ ,
2
and for 2ǫ−1 ≥ ℓ ≥ 2,
e−kǫ/mn (1 + ǫ)ℓ + ekǫ/mn (1 − ǫ)ℓ
2

25

!


= 1 + O ǫ2 ℓ2 .

Hence, we have that
4

2

4

2

I(X : a) ≤ O(ǫ (k/mn) ) +

−1
2ǫ
X

Pr(a = ℓ)O(ǫ4 ℓ4 ) + Pr(a > 2ǫ−1 )

ℓ=2

= O(ǫ (k/mn) ) + O(ǫ4 E[a(a − 1) + a(a − 1)(a − 2)(a − 3)]) + (ǫk/(mn))1/ǫ

= O(ǫ4 (k/mn)2 ),

where in the last step we use that E[a(a − 1) + a(a − 1)(a − 2)(a − 3)] = (k/mn)2 + (k/mn)4 , and
the last term is analyzed by case analysis based on whether or not ǫ√> (mn)−1/8 .
For λ = k/mn ≥ 1, we note that the probability that |a − λ| > λ log(mn) is o(1/(mn)). So,
it suffices to consider only ℓ at least this close to λ. We note that for ℓ in this range,
e±λǫ (1 ∓ ǫ)ℓ = exp(±ǫ(λ − ℓ) + O(λǫ2 )) = 1 ± ǫ(λ − ℓ) + O(λǫ2 ).
This implies that



Pr(a = ℓ|X = 0)
1−
Pr(a = ℓ|X = 1)

2

= O(λ2 ǫ4 ),

(4)

which completes the proof.
A.2

Proof of Lemma 3.7 As before,
I(X : A) =

X
v



Pr(A = v|X = 0)
O Pr(A = v) 1 −
Pr(A = v|X = 1)

2 !

.

We break this sum up into pieces based on whether or not |v|1 ≥ 2.
If |v|1 < 2, note that Pr(A = v|ci = 1/k, X = 0) = Pr(A = v|ci = 1/k, X = 1). Therefore,


Pr(A = v|X = 0)
1−
Pr(A = v|X = 1)

2

≤



Pr(A = v|X = 0, ci = 1/n)
1−
Pr(A = v|X = 1, ci = 1/n)

2

.

Hence, the contribution coming from all such v is at most


Pr(A = v|X = 0, ci = 1/n)
Pr(|A|1 = 1|ci = 1/n)) max O 1 −
Pr(A = v|X = 1, ci = 1/n)
|v|1 =1

2



Pr(A = 0|X = 0, ci = 1/n)
+O 1 −
Pr(A = 0|X = 1, ci = 1/n)

Note that the ai,j are actually independent of each other conditionally on both X and ci . We have
by Equation (3) that

if |v|1 = 1, and


Pr(A = v|X = 0, ci = 1/n)
= exp O(ǫ2 k2 n−2 m−1 + ǫ2 kn−1 m−1 ) ,
Pr(A = v|X = 1, ci = 1/n)

Pr(A = 0|X = 0, ci = 1/n)
= exp O(ǫ2 k2 n−2 m−1 ) .
Pr(A = 0|X = 1, ci = 1/n)

We have that Pr(|A|1 = 1|ci = 1/n) is the probability that a Poisson statistic with parameter
k/n(1 + O(ǫ)) gives 1, which is O(k/n). Therefore, the contribution to I(X : A) coming from these
terms is
O(ǫ4 k4 n−4 m−2 + ǫ4 k3 n−3 m−2 ) = o(kn−2 ) + o(n−1 ) = o(n−1 ).
26

2

.

Next, we consider the contribution coming from terms with |v|1 ≥ 2. We note that
Pr(A = v, ci = 1/k|X = x)
is (for either x = 0 or x = 1)

m

Y 1
ke−1
(m)−|v|1
.
n
vi !
i=1

However, Pr(A = v, ci = 1/n|X = x) is at most

|v|1

((1 + ǫ)k/nm)

m
Y
1
.
vi !
i=1

This is at most 2k/n times Pr(A = v, ci = 1/k|X = x). Therefore, we have that


Pr(A = v|X = 0)
Pr(A = v) 1 −
Pr(A = v|X = 1)

2



Pr(A = v|X = 0, ci = 1/n)
= O(k/n) Pr(A = v|ci = 1/n) 1 −
Pr(A = v|X = 1, ci = 1/n)

Note that
−k/n

Pr(A = v|X = 0, ci = 1/n) = e

|v|1

(k/nm)

m
Y
1
vi !
i=1

and
−k(1+ǫ)/n

Pr(A = v|X = 1, ci = 1/n) ≥ e

|v|1

(k/nm)

m
Y
1
≫ Pr(A = v|X = 0, ci = 1/n).
vi !
i=1

Therefore,
X
v



Pr(A = v|X = 0, ci = 1/n)
Pr(A = v|ci = 1/n) 1 −
Pr(A = v|X = 1, ci = 1/n)

2

= Θ(I(A : X|ci = 1/n)).

Finally, we have that
I(X : A|ci = 1/n) ≤

m
X
j=1

I(X : ai,j |ci = 1/n) = O(k2 ǫ4 /(n2 m)) ,

by Equation (4). This means that the contribution from these terms to I(X : A) is at most
O(k3 ǫ4 /(n3 m)) ,
and the proof is complete.

27

2

.

