Sample-Optimal Identity Testing with High Probability

arXiv:1708.02728v1 [] 9 Aug 2017

Ilias Diakonikolas∗
CS, USC
diakonik@usc.edu

Themis Gouleakis†
CSAIL, MIT
tgoule@mit.edu

John Peebles‡
CSAIL, MIT
jpeebles@mit.edu

Eric Price
CS, UT Austin
ecprice@cs.utexas.edu
August 10, 2017

Abstract
We study the problem of testing identity against a given distribution (a.k.a. goodness-of-fit) with a
focus on the high confidence regime. More precisely, given samples from an unknown distribution p
over n elements, an explicitly given distribution q, and parameters 0 < ε, δ < 1, we wish to distinguish,
with probability at least 1 − δ, whether the distributions are identical versus ε-far in total variation (or
statistical) distance. Existing work has focused on the constant confidence regime,
√ i.e., the case that
δ = Ω(1), for which the sample complexity of identity testing is known to be Θ( n/ε2 ).
Typical applications of distribution property testing require small values of the confidence parameter
δ (which correspond to small “p-values” in the statistical hypothesis testing terminology). Prior work
achieved arbitrarily small values of δ via black-box amplification, which multiplies the required number
of samples by Θ(log(1/δ)). We show that this upper bound is suboptimal for any δ = o(1), and give a
new identity tester that achieves the optimal sample complexity. Our new upper and lower bounds show
that the optimal sample complexity of identity testing is
 

1 p
Θ 2
n log(1/δ) + log(1/δ)
ε
for any n, ε, and δ. For the special case of uniformity testing, where the given distribution is the uniform
distribution Un over the domain, our new tester is surprisingly simple: to test whether p = Un versus
dTV (p, Un ) ≥ ε, we simply threshold dTV (b
p, Un ), where pb is the empirical probability distribution. We
believe that our novel analysis techniques may be useful for other distribution testing problems as well.

∗

Supported by NSF Award CCF-1652862 (CAREER) and a Sloan Research Fellowship.
Supported by the NSF under Grant No. 1420692.
‡
Supported by the NSF Graduate Research Fellowship under Grant No. 1122374, and by the NSF under Grant No. 1065125.
†

1 Introduction
1.1 Background
Distribution property testing [GR00, BFR+ 00, BFR+ 13] studies the following family of problems: given
sample access to one or more unknown distributions, determine whether they satisfy some global property
or are “far” from satisfying the property. This broad inference task originates from the field of statistics and
has been extensively studied in hypothesis testing [NP33, LR05] with somewhat different formalism. In this
work, we study the following standard formalization of this statistical task:
T (P, n, ε, δ): Given a family of distributions P with domain D of size n, parameters 0 < ε, δ < 1,
and sample access to an unknown distribution p over the same domain, we want to distinguish with
probability at least 1 − δ between the following cases:
• Completeness: p ∈ P.
• Soundness: dTV (p, P) ≥ ε.
We call this the problem of (ε, δ)-testing property P.
We denote by dTV (p, q) the total variation distance or statistical distance between distributions p and q, i.e.,
def

dTV (p, q) = (1/2) · kp − qk1 . Similarly, we denote by dTV (p, P) the minimum total variation distance between p and any q ∈ P. The goal is to characterize the sample complexity of the problem T (P, n, ε, δ), i.e.,
the number of samples that are necessary and sufficient to correctly distinguish between the completeness
and soundness cases with high probability.
During the past two decades the above general problem has received significant attention within the
computer science community, where the emphasis has been on pinning down the sample complexity of
testing in the constant probability of success regime – i.e., the setting where δ = Ω(1). See [GR00, BFR+00,
BFF+ 01, Bat01, BDKR02, BKR04, Pan08, Val11, DDS+ 13, ADJ+ 11, LRR11, ILR12, CDVV14, VV14,
DKN15b, DKN15a, CDGR16, DKN17, CDKS17, CDS17] for a sample of works, and [Rub12, Can15] for
two surveys. The constant confidence regime is fairly well understood: for a range of fundamental properties
we now have sample-optimal testers (and matching information-theoretic lower bounds) [Pan08, CDVV14,
VV14, DKN15b, DKN15a, ADK15, DK16, DGPP16]. In sharp contrast, as we explain below, the high
confidence regime – i.e., the case that δ = o(1) – is poorly understood even for the most basic properties.
Since testing is a decision problem, any algorithm that succeeds with probability 2/3 can be used along
with standard “BPP amplification” to boost the success probability to any desired accuracy. Specifically,
if S(n, ε) is a sample complexity upper bound for T (P, n, ε, 1/3), this black-box method implies that
S(n, ε) · Θ(log(1/δ)) is a sample complexity upper bound for T (P, n, ε, δ). For essentially all distribution
properties studied in the literature, the standard amplification method is the only known way to achieve high
confidence probability. This discussion naturally leads us to the following questions: For a given distribution
property P, does black-box amplification give sample-optimal testers for T (P, n, ε, δ)? Specifically, is the
Θ(log(1/δ)) multiplicative increase in the sample size the best possible? If not, can we design testers whose
sample complexity is information-theoretically optimal, as a function of all parameters, i.e., n, ε, and δ?
We believe that this is a fundamental question that merits theoretical investigation in its own right. In
most settings, the sample size m is known a priori, i.e., we are presented with a sample of size m and we
are not able to draw more samples from the distribution. In such cases, we are interested in characterizing
the optimal tradeoff curve between the proximity parameter ε and the error probability δ. Previous work in
distribution testing characterized the very special case of this tradeoff corresponding to δ = Ω(1). We note
here that the analogous question in the context of distribution learning has been intensely studied in statistics
and probability theory (see, e.g., [vdVW96, DL01]) and tight bounds are known in a range of settings.
1

Moreover, understanding the regime of “small δ” is of critical practical importance in applications of
hypothesis testing (e.g., in biology), as it corresponds to bounding the probabilities of Type I and Type
II errors. Perhaps surprisingly, with one exception [HM13], this basic problem has not been previously
investigated in the finite sample regime. A conceptual contribution of this work is to raise this problem as a
fundamental goal in distribution property testing.

1.2 Our Results
In this paper, we characterize the aforementioned tradeoff for the problem of identity testing (a.k.a. goodness
of fit). Identity testing corresponds to the property P = {q}, where q is an explicitly given distribution on a
domain of size n. The important special case that q is the uniform distribution over the domain is referred to
as uniformity testing. Identity testing is arguably the most fundamental distribution testing problem. For this
problem, we show that the black-box amplification is suboptimal for any δ = o(1), and give a new identity
tester that achieves the optimal sample complexity. Specifically, we prove the following theorem:
Theorem 1 (Main Result). There exists a computationally efficient (ε, δ)-identity tester for distributions of
support size n with sample complexity
 

1 p
n log(1/δ) + log(1/δ)
.
(1)
Θ 2
ε

Moreover, this sample size is information-theoretically optimal, up to a constant factor, for all n, ε, δ.
√
Since the sample complexity of identity testing is Θ( n/ε2 ) for δ = 1/3 [VV14, DKN15b], standard
√
amplification gives a sample upper bound of Θ( n log(1/δ)/ε2 ) for this problem. It is not hard to observe
that this bound cannot be optimal for all values of δ. For example, in the extreme case that δ = 2−Θ(n) ,
this gives a sample complexity of Θ(n3/2 /ε2 ). On the other hand, for such values of δ, we can learn the
underlying distribution (and therefore test for identity) with O(n/ε2 ) samples1 .
The case where 1 ≫ δ ≫ 2−Θ(n) is more subtle, and it is not a priori clear how to improve upon naive
√
amplification. Theorem 1 provides a smooth transition between the extremes of Θ( n/ε2 ) for constant δ
and Θ(n/ε2 ) for δ = 2−Θ(n) . It thus provides a quadratic improvement in the dependence on δ over the
naive bound for all δ ≥ 2−Θ(n) , and shows that this is the best possible. For δ < 2−Θ(n) , it turns out that the
additive Θ(log(1/δ)/ε2 ) term is necessary, as outlined in Section 1.4, so learning the distribution is optimal.
Our main technical contribution here is to obtain the first sample-optimal uniformity tester for the high
confidence regime. Our sample-optimal identity tester follows from our uniformity tester by applying the
recent result of Goldreich [Gol16], which provides a black-box reduction of identity to uniformity. We also
show a matching information-theoretic lower bound on the sample complexity.
The sample-optimal uniformity tester we introduce is remarkably simple: to distinguish between the
cases that p is the uniform distribution Un over n elements versus dTV (p, Un ) ≥ ε, we simply compute
dTV (b
p, Un ) for the empirical distribution pb. The tester accepts that p = Un if the value of this statistic
is below some well-chosen threshold, and rejects otherwise. It should be noted that such a tester was not
previously known to work with sub-learning sample complexity, even in the constant confidence regime.
Surprisingly, in a literature with several different uniformity testers [GR00, Pan08, VV14, DKN15b], no
one previously proposed using the empirical total variation distance. In fact, it would be natural to assume –
as was suggested in [BFR+ 00, BFR+13] – that such a tester cannot possibly work. A likely reason for this
is the following observation: When the sample size m is smaller than the domain size n, the empirical total
variation distance is very far from the true distance to uniformity. This suggests that the empirical distance
statistic gives little, if any, information in this setting.
1

This follows from the fact that, for any distribution p over n elements, the empirical probability distribution pbm obtained after
m = Ω((n + log(1/δ))/ε2 ) samples drawn from p is ε-close to p in total variation distance with probability at least 1 − δ.

2

We show in this paper that, in contrast to the above intuition, the natural “plug-in” estimator relying on
the empirical distance from uniformity actually works for the following reason: the empirical distance from
uniformity is noticeably smaller for the uniform distribution than for “far from uniform” distributions, even
with a sub-linear sample size. Moreover, we obtain the stronger statement that the “plug-in” estimator is a
sample-optimal uniformity tester for all parameters n, ε and δ.

1.3 Discussion and Prior Work
Uniformity testing is the first and one of the most well-studied problems in distribution testing [GR00,
Pan08, VV14, DKN15b, DGPP16]. As already mentioned, the literature has almost exclusively focused on
the case of constant error probability δ. The first uniformity tester, introduced by Goldreich and Ron [GR00],
√
counts the number of collisions among the samples and was shown to work with O( n/ε4 ) samples [GR00].
A related tester proposed by Paninski [Pan08], which relies on the number of distinct elements in the set
√
of samples, was shown to have the optimal m = Θ( n/ε2 ) sample complexity, as long as m = o(n).
√
Recently, a χ2 -based tester was shown in [VV14, DKN15b] to achieve the optimal Θ( n/ε2 ) sample complexity without any restrictions. Finally, the original collision-based tester of [GR00] was very recently
√
shown to also achieve the optimal Θ( n/ε2 ) sample complexity [DGPP16]. Thus, the situation for constant values of δ is well understood.
Uniformity is, to our knowledge, the only property for which the high-probability regime has previously
been considered. In [HM13], itp
was shown that the distinct-elements tester of [Pan08] achieves the optimal
sample complexity of m = Θ( n log(1/δ)/ε2 ) , as long as m = o(n). We emphasize that for m = Ω(n),
as is the case in many practically relevant settings (see, e.g., the Polish lottery example in [Rub14]), the tester
of [Pan08] is known to fail completely even in the constant confidence regime (also see next paragraph).
It is important to note that all previously considered uniformity testers [GR00, Pan08, VV14, DKN15b]
do not achieve the optimal sample complexity (as a function of all parameters, including δ), and this is
inherent, i.e., not just a failure of previous analyses. Roughly speaking, since the collision statistic [GR00]
and the χ2 -based statistic [VV14, DKN15b] are not Lipschitz, it can be shown that their high-probability
performance is poor. Specifically, in the completeness case (p = Un ), if many samples happen to land in the
same bucket (domain element), these test statistics become quite large, leading to their suboptimal behavior
for all δ = o(1). (For a formal justification, the reader is referred to Section V of [HM13]). On the other
hand, the distinct-elements tester [Pan08] does not work well at all for m = ω(n). For example, if ε or δ
are sufficiently small to necessitate m ≫ n log n, then typically all n domain elements will appear in both
the completeness and soundness cases, hence the test statistic provides no information.
Interestingly, our empirical total variation distance statistic can be seen to be closely related to the
distinct-elements tester of [Pan08] for m ≪ n. In this regime, we show that the empirical total variation
distance can be written as a linear function of the number of elements that are never sampled. In contrast, the
distinct-elements statistic of [Pan08] is the number of elements seen exactly once. However, as we prove,
our tester is in fact optimal in all parameter settings, whereas the distinct elements tester is not.
The problem of identity testing against an arbitrary (explicitly given) distribution was studied in [BFF+ 01],
who gave an (ε, 1/3)-tester with sample complexity Õ(n1/2 )/poly(ε). The tight bound of Θ(n1/2 /ε2 ) was
first given in [VV14] using a chi-squared type tester (inspired by [CDVV14]). In subsequent work, a similar
chi-squared tester that also achieves the same sample complexity bound was given in [ADK15]. (We note
that the [VV14, ADK15] testers have sub-optimal sample complexity in the high confidence regime, even
for the case of uniformity.) In a related work, [DKN15b] obtained a reduction of identity to uniformity that
preserves the sample complexity, up to a constant factor, in the constant error probability regime. More
recently, Goldreich [Gol16], building on [DK16], gave a different reduction of identity to uniformity that
preserves the error probability. We use the latter reduction in this paper to obtain an optimal identity tester
starting from our new optimal uniformity tester.
3

1.4 Our Techniques
Upper Bound for Uniformity Testing We would like to show that the test statistic dTV (b
p, Un ) is with high
probability larger when dTV (b
p, Un ) ≥ ε than when p = Un . We start by showing that among all possible
alternative distributions p with dTV (p, Un ) ≥ ε, it suffices to consider those in a very simple family. We
then show that the test statistic is highly concentrated around its expectation, and that the expectations are
significantly different in the two cases.
To simplify the structure of p, we show (Section 4) that if p “majorizes” another distribution q, then
the test statistic dTV (b
p, Un ) stochastically dominates dTV (b
q , Un ). (In fact, this statement holds for any test
statistic that is a convex symmetric function of the empirical histogram.) Therefore, for any p, if we average
out the large and small entries of p, the test statistic becomes harder to distinguish from uniform. This lets
us reduce to only considering p either Un or of the form 1±ε
n in each coordinate.
We remark that the aforementioned stochastic domination lemma may also be very useful in rigorous
empirical comparisons of test statistics. A major difficulty in empirical studies of distribution testing is that
the space of alternative hypotheses is large, and it is therefore impossible to experiment on all such distributions. Our structural lemma reduces the space dramatically for uniformity testing: for any convex symmetric
test statistic (which includes all existing ones), the worst case distribution will have αn coordinates of value
(1 + ε/α)/n, and the rest of value (1 − ε/(1 − α))/n, for some α. Hence, there are only n possible worstcase distributions for any ε. Notably, this reduction does not lose any absolute constants, so it could be used
to identify the non-asymptotic optimal constants for a given set of parameters.
Returning to our uniformity tester, we now need to separate the expectation of the test statistic in our
two situations. We achieve this by providing an explicit expression for the Hessian of this expectation, as
a function of p. We note that the Hessian is diagonal, and for our two situations of pi ≈ 1/n each entry is
within constant factors of the same value, giving a lower bound on its eigenvalues. Since the expectation is
minimized at p = Un , we use strong
p convexity to show the desired expectation gap. Specifically, we prove
2
2
2
that this gap is ε · min(m /n , m/n, 1/ε).
Finally, we need to show that the test statistic concentrates about its expectation. For m ≥ n, this follows
from McDiarmid’s
p inequality: since the test statistic is 1/m-Lipschitz in the m samples, with probability 1−
δ it lies within log(1/δ)/m of its expectation. When m is larger than the desired sample complexity (1),
this is less than the expectation gap above. The concentration is trickier when m < n, since the expectation
gap is smaller, so we need to establish tighter concentration. We get this by using a Bernstein variant of
McDiarmid’s inequality, which is stronger than the standard version of McDiarmid in this context.
Upper Bound for Identity Testing In [Gol16], it was shown how to reduce ε-testing of an arbitrary
distribution q over [n] to ε/3-testing of U6n . This reduction preserves the error probability δ, so applying it
gives an identity tester with the same sample complexity as our uniformity tester, up to constant factors.
Sample Complexity Lower Bound To match our upper bound (1), we need two lower bounds. The lower
bound of Ω( ε12 log(1/δ)) is straightforward from the same lower bound as for distinguishing a fair coin from
p
2 bound is more challenging.
an ε-biased coin, while the n log(1/δ)/ε
p
For intuition, we start with a n log(1/δ) lower bound for constant ε. When p = Un , the chance that
p
2
all m samples are distinct is at least (1 − m/n)m ≈ e−m /n . Hence, if m ≪ n log(1/δ), this would
happen with probability significantly larger than 2δ. On the other hand, if p is uniform over a random subset
of n/2 coordinates, the m samples will also all be distinct with probability (1 − 2m/n)m > 2δ. The two
situations thus look the same with 2δ probability, so no tester could have accuracy 1 − δ.
This intuition can easily be extended to include a 1/ε dependence, but getting the desired 1/ε2 dependence requires more work. First, we Poissonize the number of samples, so we independently see Poi(mpi )

4

samples of each coordinate i; with exponentially high probability, this Poissonization only affects the sample
complexity by constant factors. Then, in the alternative hypothesis, we set each pi independently at random
to be 1±ε
n . This has the unfortunate property that p no longer sums to 1, so it is a “pseudo-distribution”
rather than an actual distribution. Still, it is exponentially likely to sum to Θ(1), and using techniques
from [WY16, DK16] this is sufficient for our purposes.
At this point, we are considering a situation where the number of times we see each coordinate is
m
either Poi(m/n) or 21 (Poi((1 − ε) m
n ) + Poi((1 + ε) n )), and every coordinate is independent of the others.
These two distributions have Hellinger distance at least ε2 m/n in each coordinate.
Then the composition
p
property for Hellinger distance over n independent coordinates implies m ≥ n log(1/δ)/ε2 is necessary
for success probability 1 − δ.

1.5 Notation and Basic Definitions
We write [n] to denote the P
set {1, . . . , n}. We consider discrete distributions over [n], which are functions
p : [n] → [0, 1] such that ni=1 pi = 1. We use the notation
pi to denote the probability of element i in
P
distribution p. For S ⊆ [n], we will denote p(S) =
p
i∈S i . We will also sometimes think of p as an
n-dimensional vector. We will denote by Un the uniform distribution over [n].
For r ≥ 1, the ℓr –norm of a distribution is identified with the ℓr –norm of the corresponding vector,
P
i.e., kpkr = ( ni=1 |pi |r )1/r . The ℓr -distance between distributions p and q is defined as the the ℓr -norm
of the vector of their difference. The total variation distance between distributions p and q is defined as
def
dTV (p, q) = maxS⊆[n] |p(S) − q(S)| = (1/2) · kp − qk1 . The Hellinger distance between p and q is
qP
√
√
√
√
√ 2
√
def
n
H(p, q) = (1/ 2) · k p − qk2 = (1/ 2) ·
i=1 ( pi − qi ) . We denote by Poi(λ) the Poisson
distribution with parameter λ.

1.6 Structure of this Paper
In Section 2, we formally describe and analyze our sample-optimal uniformity tester. In Section 3, we give
our matching sample complexity lower bound. Finally, Section 4 establishes our stochastic domination result
that is crucial for the analysis of the soundness in Section 2, and may be useful in the rigorous empirical
evaluation of test statistics.

2 Sample-Optimal Uniformity Testing
In this section, we describe and analyze our optimal uniformity tester. Given samples from an unknown
distribution p over [n], our tester returns “YES” with probability 1 − δ if p = Un , and “NO” with probability
1 − δ if dTV (p, Un ) ≥ ε.

2.1 Our Test Statistic
We define a very natural statistic that yields a uniformity tester with optimal dependence on the domain
size n, the proximity parameter ε, and the error probability δ. Our statistic is a thresholded version of the
empirical total variation distance between the unknown distribution p and the uniform distribution. Our
tester T EST-U NIFORMITY is described in the following pseudocode:

5

Algorithm T EST-U NIFORMITY(p, n, ε, δ)
Input: sample access to a distribution p over [n], ε > 0, and δ > 0.
Output: “YES” if p = Un ; “NO” if dTV (p, Un ) ≥ ε.

p

1. Draw m = Θ (1/ε2 ) ·
n log(1/δ) + log(1/δ) iid samples from p.

2. Let X = (X1 , X2 , . . . , Xn ) ∈ Zn>0 be the histogram of the samples. That is, Xi is the number
of times domain element i appears in the (multi-)set of samples.

3. Define the random variable S =

1
2

Pn

i=1

Xi
m

−

1
n


2 m2

ε · p
n2
t = µ(Un ) + C · ε2 · m
n


ε

and set the threshold
for m ≤ n
for n < m ≤
for εn2 ≤ m

n
ε2

,

where C is a universal constant (derived from the analysis of the algorithm), and µ(Un ) is the
expected value of the statistic in the completeness case.
4. If S ≥ t return “NO”; otherwise, return “YES”.
The main part of this section is devoted to the analysis of T EST-U NIFORMITY, establishing the following
theorem:
Theorem 2. There exists a universal constant C > 0 such that the following holds: Given

p
n log(1/δ) + log(1/δ)
m ≥ C · (1/ε2 )

samples from an unknown distribution p, Algorithm T EST-U NIFORMITY is an (ε, δ) uniformity tester for p.
As we point out in Appendix A, the value µ(Un ) can be computed efficiently, hence our overall tester is
computationally efficient. To prove correctness of the above tester, we need to show that the expected value
of the statistic in the completeness case is sufficiently separated from the expected value in the soundness
case, and also that the value of the statistic is highly concentrated around its expectation in both cases. In
Section 2.2, we bound from below the difference in the expectation of our statistic in the completeness
and soundness cases. In Section 2.3, we prove the desired concentration which completes the proof of
Theorem 2.

2.2 Bounding the Expectation Gap
The expectation of the statistic in algorithm T EST-U NIFORMITY can be viewed as a function of the n
def
variables p1 , . . . , pn . Let µ(p) = E[S(X1 , . . . , Xn )] be the aforementioned function when the samples are
drawn from distribution p.
Our analysis has a number of complications for the following reason: the function µ(p) − µ(Un ) is a
linear combination of sums that have no indefinite closed form, even if the distribution p assigns only two
possible probabilities to the elements of the domain. This statement is made precise in Appendix B. As
such, we should only hope to obtain an approximation of this quantity.
A natural approach to try and obtain such an approximation would be to produce separate closed form
approximations for µ(p) and µ(Un ), and combine these quantities to obtain an approximation for their
6

difference. However, one should not expect such an approach to work in our context. The reason is that the
difference µ(p) − µ(Un ) can be much smaller than µ(p) and µ(Un ); it can even be arbitrarily small. As
such, obtaining separate approximations of µ(p) and µ(Un ) to any fixed accuracy would contribute to much
error to their difference.
To overcome these difficulties, we introduce the following technique, which is novel in this context.
We directly bound from below the difference µ(p) − µ(Un ) using strong convexity. Specifically, we show
that the function µ is strongly convex with appropriate parameters and use this fact to bound the desired
expectation gap. The main result of this section is the following lemma:
Lemma 3. Let p be a distribution over [n] and ε = dTV (p, Un ). For all m ≥ 6 and n ≥ 2, we have that:

2 m2

for m ≤ n
ε · p
n2
m
2
µ(p) − µ(Un ) ≥ Θ(1) · ε · n for n < m ≤ εn2 .


ε
for εn2 ≤ m

We note that the bounds in the right hand side above are tight, up to constant factors. Any asymptotic
improvement would yield a uniformity tester with sample complexity that violates our tight informationtheoretic lower bounds.
The proof of Lemma 3 requires a number of intermediate lemmas. Our starting point is as follows: By
the intermediate value theorem, we have the quadratic expansion
1
µ(p) = µ(Un ) + ∇µ(Un )⊺ (p − Un ) + (p − Un )⊺ Hp′ (p − Un ) ,
2
where Hp′ is the Hessian matrix of the function µ at some point p′ which lies on the line segment between
Un and p. This expression can be simplified as follows: First, we show (Fact 18) that our µ is minimized
over all probability distributions on input Un . Thus, the gradient ∇µ(Un ) must be orthogonal to being a
direction in the space of probability distributions. In other words, ∇µ(Un ) must be proportional to the
all-ones vector. More formally, since µ is symmetric its gradient is a symmetric function, which implies
it will be symmetric when given symmetric input. Moreover, (p − Un ) is a direction within the space of
probability distributions, and therefore sums to 0, making it orthogonal to the all-ones vector. Thus, we have
that ∇µ(Un )⊺ (p − Un ) = 0, and we obtain
1
1
1
µ(p) − µ(Un ) = (p − Un )⊺ Hp′ (p − Un ) ≥ kp − Un k22 · σ ≥ kp − Un k21 /n · σ ,
2
2
2

(2)

where σ denotes the minimum eigenvalue of the Hessian of µ on the line segment between Un and p.
The majority of this section is devoted to proving a lower bound for σ. Before doing so, however,
we must first address a technical consideration. Because we are considering a function over the space of
probability distributions – which is not full-dimensional – the Hessian and gradient of µ with respect to Rn
depend not only on the definition of our statistic
 x also 1its parameterization. For the purposes of this
Pn S, but
subsection, we parameterize S as S(x) = i=1 max mi − n , 0 .
In the analysis we are about to perform, it will be helpful to sometimes think of n1 as a free parameter.
Thus, we define
n
1 X
St (x) ,
max{xi − t, 0}
m
i=1

and

n m  
1 XX m k
p (1 − pi )m−k (k − t) .
µt (p) , Ex∼Multinomial(m,p) [St (x)] =
m
k i
i=1 k=t

7

(3)

Note that when t = m/n we have St = S and µt = µ. Also note that when we compute the Hessian of
µt (p), we are treating µt (p) as a function of p and not of t. In the following lemma, we derive an exact
expression for the entries of the Hessian. This result is perhaps surprising in light of the likely nonexistence
of a closed form expression for µ(p). That is, while the expectation µ(p) may have no closed form, we
prove that the Hessian of µ(p) does in fact have a closed form.
Lemma 4. The Hessian of µt (p) viewed as a function of p is a diagonal matrix whose ith diagonal entry is
given by
hii = st,i ,
where we define st,i as follows: Let ∆t be the distance of t from the next largest integer, i.e., ∆t , ⌈t⌉ − t.
Then, we have that


for t = 0
0
m−2 t−1
m−t−1
.
st,i = (m − 1) t−1 pi (1 − pi )
for t ∈ Z>0


∆t · s⌊t⌋,i + (1 − ∆t) · s⌈t⌉,i
for t ≥ 0 and t 6∈ Z
In other words, we will derive the formula for integral t ≥ 1 and then prove that the value for nonintegral
t ≥ 0 can be found by linearly interpolating between the closest integral values of t.

Proof. Note that because St (x) is a separable function of x, µt (p) is a separable function of p, and hence the
Hessian of µt (p) is a diagonal matrix. By Equation 3, the i-th diagonal entry of this Hessian can be written
explicitly as the following expression:
st,i

m  
d2 1 X m k
∂2
= 2 µt (p) = 2
p (1 − pi )m−k (k − t) .
k i
∂pi
dpi m
k=t

Notice that if we sum starting from k = 0 instead of k = t, then the sum equals the expectation of Bin(m, pi )
minus t. That is, notice that:
m  
d2 1
d2 1 X m k
m−k
(pi m − t) = 0 .
p
(1
−
p
)
(k
−
t)
=
i
k i
dp2i m
dp2i m
k=0

By this observation and the fact that the summand is 0 when k = t, we can switch which values of k we are
summing over to k from 0 through t if we negate the expression:
st,i =

t  
1 d2 X m k
∂2
µ
(p)
=
p (1 − pi )m−k (t − k) .
t
∂ 2 pi
m dp2i
k i
k=0

We first prove the case when t ∈ Z+ . In this case, we view st,i as a sequence with respect to t (where
i is fixed), which we denote st . We now derive a generating function for this sequence.2 Observe that
derivatives that are not with respect to the formal variable commute with taking generating functions. Then,
the generating function for the sequence {st } is
!


d
x dx
(pi x + 1 − pi )m
d (pi x + 1 − pi )m
d2 1
x
= (m − 1)(pi x + 1 − pi )m−2 x .
−
dx
1−x
1−x
dp2i m
2

To avoid potential convergence issues, we view generating functions as formal polynomials from the ring of infinite formal
polynomials. Under this formalism, there is no need to deal with convergence at all.

8

Note that the coefficient on x0 is 0, so s0,i = 0 as claimed. For t ∈ Z>0 , the right hand side is the generating
function of


m − 2 t−1
(m − 1)
p (1 − p)m−t−1 .
t−1
Thus, this expression gives the i-th entry Hessian in the t ∈ Z≥0 , as claimed.
Now consider the case when t is not an integer. In this case, we have:
st,i

m  
d2 1 X m k
, 2
p (1 − pi )m−k (k − t)
k i
dpi m
k=⌈t⌉
m  
d2 1 X m k
= 2
p (1 − pi )m−k (k − ⌈t⌉ + ∆t)
k i
dpi m
k=⌈t⌉
m  
d2 1 X m k
= s⌈t⌉,i + ∆t 2
p (1 − pi )m−k .
k i
dpi m
k=⌈t⌉

⌈t⌉−1  
d2 1 X m k
= s⌈t⌉,i − ∆t 2
p (1 − pi )m−k .
k i
dpi m
k=0

The last equality is because if we change bounds on the sum so they are from 0 through m, we get 1 which
has partial derivative 0. Thus, we can flip which terms we are summing over if we negate the expression.
Note that this expression we are subtracting above can be alternatively written as:
⌈t⌉−1  
d2 1 X m k
p (1 − pi )m−k = ∆t · (s⌈t⌉ − s⌊t⌋ ) .
∆t 2
k i
dpi m
k=0

Thus, we have
st,i = s⌈t⌉,i − ∆t · (s⌈t⌉,i − s⌊t⌋,i ) = ∆t · s⌊t⌋,i + (1 − ∆t) · s⌈t⌉,i ,
as desired. This completes the proof of Lemma 4.
It will be convenient to simplify the exact expressions of Lemma 4 into something more manageable.
This is done in the following lemma:
Lemma 5. Fix any constant c > 0. The Hessian of µ(p), viewed as a function of p, is a diagonal matrix
whose i-th diagonal entry is given by
( 2
m
for m ≤ n
hii = st:=m/n,i ≥ Θ(1) · √n
,
mn for n < m ≤ c · εn2
assuming pi =

1±ε
n ,

m ≥ 6, n ≥ 2, and ε ≤ 1/2.

Similarly, these bounds are tight up to constant factors, as further improvements would violate our
sample complexity lower bounds.
Proof. By Lemma 4, we have an exact expression st,i for the ith entry of the Hessian of µt (p).
First, consider the case where m ≤ n. Then we have
st,i = (1 − ∆t) · s⌈t⌉,i .
9

Substituting t = m/n, ⌈t⌉ = 1, and ∆t = ⌈t⌉ − t = 1 − m/n gives
st,i =

m
m2
· (m − 1)(1 − pi )m−2 = Θ(1) ·
.
n
n

Now consider the case where n < m ≤ Θ(1) · εn2 . Note that the case where n < m < 2n follows from (1)
the fact that st,i for fractional t linearly interpolates between the value of st′ ,i the nearest two integral values
of t′ and (2) the analyses of the cases where m ≤ n and 2n ≤ m ≤ Θ(1) εn2 . Thus, all we have left to do is
prove the case where 2n ≤ m ≤ Θ(1) · εn2 .
Since st,i is a convex combination of s⌈t⌉,i and s⌊t⌋,i , it suffices to bound from below these quantities
for t = m/n. Both of these tasks can be accomplished simultaneously by bounding from below the quantity
st=m/n+γ,i for arbitrary γ ∈ [−1, 1].
We do this as follows: Let t = m/n + γ. Note that Stirling’s approximation is tight up to constant
factors as long as the number we are taking the factorial of is not zero. Note that m − 2 ≥ 1, t − 1 ≥ 1, and
m − t − 1 ≥ m/2 − 2 ≥ 1. Thus, if we apply Stirling’s approximation to the factorials in the definition of
the binomial coefficient and substitute t = m/n + γ, we obtain the following approximation, which is tight
up to constant factors:


m − 2 t−1
(m − 1)
pi (1 − pi )m−t−1
t−1
s
m/n−1+γ
(m − 2)m pi
(1 − pi )m−m/n−1−γ
(m − m/n − 1 − γ)(m/n − 1 + γ)
·
= Θ(1) · (m − 1) ·
(m − 2)3
(m − m/n − 1 − γ)m−m/n−γ (m/n + γ)m/n−1+γ
r
m/n−1+γ
mm p i
(1 − pi )m−m/n−1−γ
m
·
= Θ(1) ·
n (m − m/n − 1 − γ)m−m/n−γ (m/n − 1 + γ)m/n+γ
= Θ(1) ·
= Θ(1) ·
= Θ(1) ·

m/n+γ
√
mm/n+γ pi
(1 − pi )m−m/n−1−γ
mn ·
1 m−m/n−γ
)
(m/n)m/n+γ
(1 − n1 − m

√
(npi )m/n+γ (1 − pi )m−m/n−1−γ
mn ·
(1 − n1 )m−m/n−γ

m−m/n−γ
√
(1 ± ε)m/n+γ (1 − 1±ε
n )
mn ·
(1 − n1 )m−m/n−γ

m−m/n
√
(1 ± ε)m/n (1 − 1±ε
n )
mn ·
(1 − n1 )m−m/n

m−m/n
√
ε
m/n
1∓
= Θ(1) · mn · (1 ± ε)
n−1
m
√
− m
m/n
(1 ∓ ε) n−1 n(n−1)
≥ Θ(1) · mn · (1 ± ε)
√
= Θ(1) · mn · (1 ± ε)m/n (1 ∓ ε)m/n
√
= Θ(1) · mn · (1 − ε2 )m/n
√
2
= Θ(1) · mn · e−Θ(1)·ε m/n
√
≥ Θ(1) · mn .

= Θ(1) ·

This completes the proof of Lemma 5.
We are now ready to prove the desired expectation gap.

10

Proof of Lemma 3: We start by reducing the soundness case to a much simpler setting. To do this, we use
the following fact, established in Section 4:
Fact 6. For any distribution p on [n], there exists a distribution p′ supported on [n] whose probability mass
′ 1 1−ε′
1
′
values are in the set { 1+ε
n , n , n } for some ε ≥ dTV (p, Un )/2, with at most one element having mass n ,
and such that µ(p′ ) ≤ µ(p).

Fact 6 is proven in Section 4. By Fact 6, there is a distribution p′ that satisfies the conditions of Lemma
5, has total variation distance Θ(ε) to the uniform distribution, and µ(p′ ) ≤ µ(p). Therefore, it suffices to
prove a lower bound on the expectation gap between the completeness and soundness cases for distributions
p of this form.
Note that all probability distributions on the line from p to Un are also of this form for different (no
larger) values of ε. Thus, Lemma 5 gives a lower bound on the diagonal entries of the Hessian at all points
on this line. Since the Hessian is diagonal, this also bounds from below the minimum eigenvalue of the
Hessian on this line. Therefore, by this and Equation (2), we obtain the first two cases of this lemma, as well
as the third case for εn2 ≤ m ≤ 4 · εn2 .
The final case of this lemma for 4 · εn2 ≤ m follows immediately from the folklore fact that if one takes
at least this many samples, the empirical distribution approximates the true distribution with expected ℓ1
error at most ε/2. For completeness, we give a proof. We have
X
Xp
Var[Xi /m − pi ]
E[kX/m − pk1 ] =
E[|Xi /m − pi |] ≤
i

≤

=

Xp

i

mpi

/m2

i

p

n/m ≤ ε/2 ,

≤

Xp

m(1/n)/m2

(4)

i

where Equation (4) follows from the fact that the sum is a symmetric concave function of p, so it is maximized by setting all the pi ’s to be equal.

2.3 Concentration of Test Statistic: Proof of Theorem 2
Let the m samples be Y1 , . . . , Ym ∈ [n], and let Xi , i ∈P
[n], be the number of j ∈ [m] for which Yj = i. Let
1
1
i
S be our empirical total variation test statistic, S = 2 ni=1 | X
m − n |. We prove the theorem in two parts,
one when m ≥ n, and one when m ≤ n.
We will require a “Bernstein” form of the standard bounded differences (McDiarmid) inequality:
Lemma 7 (Bernstein version of McDiarmid’s inequality [Yin04]). Let Y1 , . . . , Ym be independent random
variables taking values in the set Y. Let f : Y m → R be a function of Y1 , . . . , Ym so that for every j ∈ [m]
and y1 , . . . , ym , yj′ ∈ Y, we have that:
|f (y1 , . . . , yj , . . . , yn ) − f (y1 , . . . , yj′ , . . . , yn )| ≤ B .

Then, we have:
Pr [f − E[f ] ≥ z] ≤ exp



−2z 2
mB 2



.

(5)

If in addition, for each j ∈ [m] and y1 , . . . , yj−1 , yj+1 , . . . , ym we have that
VarYj [f (y1 , . . . , Yj , . . . , ym )] ≤ σj2 ,

then we have
Pr [f − E[f ] ≥ z] ≤ exp
11

−z 2
Pm 2
2 j=1 σj + 2Bt/3

!

.

(6)

2.3.1

Case I: m ≥ n

1
-Lipschitz in them, the first form of McDiarmid’s inequality
Since the Yj ’s are independent and S is m
implies that
Pr[S − E[S] ≥ z] ≤ exp(−2mz 2 ) ,

and similarly, by applying it to −S, we have Pr[S − E[S] ≤ −z] ≤ exp(−2mz 2 ).
Let R be the right-hand side of the Equation in Lemma 3, so µ(p) − µ(Un ) ≥ R in the soundness case.
Since we threshold the tester at t = µ(Un ) + R/2, we find in both the completeness and soundness cases
that the success probability will be at least
1 − exp(−mR2 /2) ,
and hence we just need to show
mR2 /2 ≥ log(1/δ) .

(7)

Since we are in the regime that m ≥ n, there are two possible cases in Lemma 3.
For n ≤ m ≤ n/ε2 , we need that
m
· Θ(1) · ε4 m/n ≥ log(1/δ)
2
or
m ≥ Θ(1) ·
For m ≥ n/ε2 , we need that

p

n log(1/δ)
.
ε2

m
· Θ(1) · ε2 ≥ log(1/δ)
2

or

log(1/δ)
.
ε2
The theorem’s assumption on m implies that both conditions hold, which completes the proof of Theorem 2
in this case.
m ≥ Θ(1) ·

2.3.2

Case II: m ≤ n

To establish Theorem 2 for m ≤ n, we will require the Bernstein form of McDiarmid’s inequality (Equation
(6) in Lemma 7).
To apply this form of Lemma 7, it suffices to compute B and σj for our test statistic as a function of the
Xi
1
1
i
Yj ’s. Note that for m ≤ n, | X
m − n | is equal to m − n whenever Xi 6= 0. In particular, this implies
n

1 X Xi
1
−
2
m
n
i=1



n
1
Xi
2
1X
−
+ · 1Xi =0
=
2
m
n
n

S=

i=1

1
= · |{i : Xi = 0}| .
n

Hence, the value of the parameter B for our test statistic is 1/n, since each Yj will affect the number of
nonzero Xi ’s by at most 1. In particular, the function value as Yj varies and the other Yj ′ ’s are kept fixed can
12

be written as the sum of a deterministic quantity plus (1/n) · b, where b is a Bernoulli random variable that
is 1 if sample Yj collides with another sample Yj ′ and 0 otherwise. Thus, the variance of S as Yj varies and
the other Yj ′ ’s are kept fixed is given by Var[(1/n) · b]. This variance is (1/n2 ) · r(1 − r), where r ≤ m/n
is the probability that Yj collides with another Yj ′ . Thus, the variance of S as Yj varies and the other Yj ′ ’s
are kept fixed is at most
1
· r(1 − r) ≤ r/n2 ≤ m/n3 =: σj2 .
n2
Applying Equation (6) of Lemma 7 we find


−z 2
Pr[|S − E[S]| ≥ z] ≤ 2 exp
.
2 · m2 /n3 + (2/3) · z/n
By Lemma 3 in the soundness case we have expectation gap µ(p) − µ(Un ) ≥ R :=Cε2 m2 /n2 for some
constant C < 1. Substituting z = R/2 in the above concentration inequality yields that our tester will be
correct with probability 1 − δ as long as
m ≥ Θ(1) ·

1p
n log(2/δ),
ε2

for an appropriately chosen constant, which is true by assumption. This completes the proof of Theorem 2.

3 Matching Information-Theoretic Lower Bound
In this section, we prove our matching sample complexity lower bound. Namely, we prove:
Theorem 8. Any algorithm that distinguishes with probability at least 1 − δ the uniform distribution on [n]
from any distribution that is ε-far from uniform, in total variation distance, requires at least


p
n log(1/δ) + log(1/δ) /ε2
Ω
samples.

Theorem
8 will immediately follow from separate sample complexity lower bounds of Ω(log(1/δ)/ε2 )
p
and Ω( n log(1/δ)/ε2 ) that we will prove. We start with a simple sample complexity lower bound of
Ω(log(1/δ)/ε2 ):
Lemma 9. For all n, ε, and δ, any (ε, δ) uniformity tester requires Ω(log(1/δ)/ε2 ) samples.
Proof. If n is odd, set the last probability to 1/n, subtract 1 from n, and invoke the following lower bound
instance on the remaining elements. If n is even, do the following. Consider the distribution p which has
n
1−ε
n
probability pi = 1+ε
n for each element 1 ≤ i ≤ 2 and pi = n for each element 2 ≤ i ≤ n. Clearly,
dTV (p, Un ) = ε. Note that the probability that a sample comes from the first half of the domain is 1+ε
2
and the probability that it comes from the second half of the domain is 1−ε
.
Therefore,
distinguishing
p
2
from Un is equivalent to distinguishing between a fair coin and an ε-biased coin. It is well-known (see, e.g.,
Chapter 2 of [BY02]) that this task requires m = Ω(log(1/δ)/ε2 ) samples.
The rest of this section is devoted to the proof of the following lemma, which gives our desired lower
bound:
p
Lemma 10. For all n, ε, and δ, any (ε, δ) uniformity tester requires at least Ω( n log(1/δ)/ε2 ) samples.
13

To prove Lemma 10, we will construct two indistinguishable families of pseudo-distributions. A
pseudo-distribution w is a non-negative measure, i.e., it is similar to a probability distribution except that
the “probabilities” may sum to something other than 1. We will require that our pseudo-distributions always sum to a quantity within a constant factor of 1. A pair of pseudo-distribution families is said to be
δ-indistinguishable using m samples if no tester exists that can, for every N
pair of pseudo-distributions
w, w′
N
– one from each of the two families – distinguish the product distributions
Poi(mwi ) versus
Poi(mwi′ )
with failure probability at most δ.
This technique is fairly standard and has been used in [WY16, VV14, DK16] to establish lower bounds
for distribution testing problems. The benefit of the method is that it is much easier to show that pseudodistributions are indistinguishable, as opposed to working with ordinary distributions. Moreover, lower
bounds proven using pseudo-distributions imply lower bounds on the original distribution testing problem.
We will require the following lemma, whose proof is implicit in the analyses of [WY16, VV14, DK16]:
Lemma 11. Let P ′ be a property of distributions. We extend P ′ to the unique property P of pseudodistributions which agrees with P ′ on true distributions and is preserved under rescaling. Suppose we have
two families F1 , F2 of pseudo-distributions with the following properties:
1. All pseudo-distributions in F1 have property P and all those in F2 are ε-far in total variation distance
from any pseudo-distribution that has the property.
2. F1 and F2 are δ-indistinguishable using m samples.
3. Every pseudo-distribution in each family has ℓ1 -norm within the interval [ c11 , c2 ], for some constants
c1 , c2 > 1.
Then there exist two families Fe1 , Fe2 of probability distributions with the following properties:
1. All distributions in Fe1 have property P and all those in Fe2 are
any distribution that has the property.

ε
c2 -far

in total variation distance from

2. Any tester that can distinguish Fe1 and Fe2 has worst-case error probability ≥ δ − 2−cm , for some
constant c > 0 or requires Θ(1) · m samples.

In our case, the property of distributions P ′ is simply being the uniform distribution. The families
of pseudo-distributions we will use for our lower bound are the family F1 that only contains thePuniform
distribution and the family F2 of all pseudo-distributions of the form wi = 1±ε
i wi | ≤
n such that |1 −
ε/2. Note that this constraint on the sum of the wi ’s ensures the first and last conditions needed to invoke
Lemma 113 .
Furthermore, by Lemma 9, the required number of samples m satisfies m ≥ Ω(log(1/δ)). Ignoring
constant factors, we may assume that m ≥ c′ log(1/δ) for any constant c′ > 0. In particular, by selecting c′
appropriately, we can guarantee that 2−cm ≤ δ/3, where c is the constant in the last statement of Lemma 11.
Thus, the error probability guaranteed by Lemma 11 for distinguishing the true distribution families is at
least (2/3)δ.
Thus, all that remains is to show that F1 and F2 are δ-indistinguishable using m samples. In order to
show these families
are indistinguishable, we show that it is impossible to distinguish whether the product
N
distribution
Poi(mwi ) has w uniform or w generated according to the following random process: we
1−ε
pick each wi independently by setting wi = 1+ε
n or wi = n each with probability 1/2.
A distribution generated by this process has a small probability of not being in F2 . Specifically, this
happens iff it fails to satisfy the constraint on having a sum within 1 ± ε/2. However, by an application of
3

If we did not have this constraint, the first condition would not be satisfied (because e.g., a w such that wi = (1 + ε)/n for all
i is not ε-far from being proportional to the all-ones vector.

14

the Chernoff bound, it follows that this happens with probability at mots ≤ 2−Θ(1)·n . Since the bound in
Lemma 9 is larger (up to constant factors) than the lower bound we presently wish to prove in the case that
δ/3 > 2−Θ(1)·n , we will assume δ ≤ 2−Θ(1)·n ; in which case, the following lemma implies that we can still
invoke Lemma 11, where the probability of not being in F2 is absorbed into our overall indistinguishability
probability, and we get a final indistinguishability probability of at least (2/3)δ − δ/3 = δ/3.
The following lemma is implicit in [WY16, VV14, DK16]:
Lemma 12. Let P be a property of pseudo-distributions. Suppose we have two families F1 , F2 of pseudodistributions and two distributions D1 , D2 on F1 and F2 respectively with the following properties:
1. With probability each at least 1 − δ1 , a distribution output by D1 is in F1 and a distribution output by
D2 is in F2 .
2. If we generate w according
to D1 or D2 , then any algorithm for determining which family w came
N
from given access to
Poi(mwi ) has worst case error probability at least δ2 .

Then F1 and F2 are (δ2 − δ1 )-indistinguishable using m samples.

Thus, we now simply need to show that D1 and D2 are hard to distinguish. Let Xi , Xi′ be the random
variables equal to the number of times the element i is sampled in the completeness and soundness cases
respectively. We will require a technical lemma that will be used to bound the Hellinger distance between
any pair of corresponding coordinates in the completeness and soundness cases. By 21 Poi(λ1 ) + 12 Poi(λ2 ),
we denote a uniform mixture of the corresponding distributions. We have
Fact 13 (Lemma 7 of [VV14]). For any λ > 0, ε < 1 we have


1
1
H 2 Poi(λ), Poi((1 + ε)λ) + Poi((1 − ε)λ) ≤ Cλ2 ε4 .
2
2
for some constant C.
We are now ready to prove Lemma 10.
Proof of Lemma 10: As follows from the preceding discussion, it suffices to show that D1 and D2 are hard
to distinguish. We will use Fact 13 to show that the Hellinger distance between the overall distributions is
small, which implies their total variation distance is small, and hence that they cannot be distinguished with
probability better than δ.
Recall that each of the n coordinates of the vectors output by these distributions is distributed according
to Poi(m/n) for D1 vs. a uniform mixture of Poi((1 ± ε)m/n) for D2 . A single coordinate then has
H 2 (X1 , X1′ ) ≤ C(m2 /n2 )ε4 ,
so the collection of all coordinates has
2 /n)ε4

H 2 (X, X ′ ) ≤ 1 − (1 − C(m2 /n2 )ε4 )n ≤ 1 − e−C(m
For this latter quantity to be at least 1 − δ, we need


p
m = Ω (1/ε2 ) · n log(1/δ)

.

samples, as desired. The result then follows from Lemma 12 and Lemma 11. This completes the proof.

15

4 Stochastic Domination for Statistics of the Histogram
In this section, we consider the set of statistics which are symmetric convex functions of the histogram (i.e.,
the number of times each domain element is sampled) of an arbitrary random variable Y . We start with the
following definition:
Definition 14. Let p = (p1 , . . . , pn ), q = (q1 , . . . , qn ) be probability distributions and p↓ , q ↓ denote the
vectors with the same values as p and q respectively, but sorted in non-increasing order. We say that p
majorizes q (denoted by p ≻ q) if
k
k
X
X
qi↓ .
(8)
p↓i ≥
∀k :
i=1

i=1

The following theorem from [Arn12] gives an equivalent definition:
Theorem 15. [Arn12] Let p = (p1 , . . . , pn ), q = (q1 , . . . , qn ) be any pair of probability distributions. Then,
p ≻ q if and only if there exists a doubly stochastic matrix A such that q = Ap.
Remark: It is shown in [Arn12] that multiplying the distribution p by a doubly stochastic matrix is equivalent to performing a series of so called “Robin hood operations” and permutations of elements. Robin hood
operations are operations in which probability mass in transferred from heavier to lighter elements. For
more details, the reader is referred to [Arn12, MOA79].
Note that Definition 14 defines a partial order over the set of probability distributions. We will see that the
uniform distribution is a minimal element for this partial order, which directly follows as a special case of
the following lemma.
Lemma 16. Let p be a probability distribution over [n] and S ⊆ [n]. Let q be the distribution which is
identical to p on [n] \ S, and for every i ∈ S we have qi = p(S)
|S| , where |S| denotes the cardinality of S.
Then, we have that p ≻ q.
Proof. Let A = (aij ) be the doubly stochastic matrix A = (aij ) with entries:

if i = j 6∈ S

1
1
aij = |S| if i ∈ S ∧ j ∈ S .


0
otherwise

Observe that q = Ap. Therefore, Theorem 15 implies that p ≻ q.

In the rest of this section, we use the following standard terminology: We say that a real random variable
A stochastically dominates a real random variable B if for all x ∈ R it holds Pr[A > x] ≥ Pr[B > x]. We
now state the main result of this section (see Section 4.1 for the proof):
Lemma 17. Let f : Rn → R be a symmetric convex function and p be a distribution over [n]. Suppose that
we draw m samples from p, and let Xi denote the number of times we sample element i. Let g(p) be the
random variable f (X1 , X2 , . . . , Xn ). Then, for any distribution q over [n] such that p ≻ q, we have that
g(p) stochastically dominates g(q).
As a simple consequence of the above, we obtain the following:
Fact 18. Let p be a distribution on [n] and S ⊆ [n]. Let p′ be the distribution which is identical to p in
′
[n] \ S and the probabilities in S are averaged (i.e., p′i = p(S)
|S| ). Then, we have that µ(p ) ≤ µ(p), where
µ(·) denotes the expectation of our statistic as defined in Section 2. In particular, µ(Un ) ≤ µ(p) for all p.
16

Proof. Recall that our statistic applies a symmetric convex function f to the histogram of the sampled
distribution. Since p′ is averaging the probability masses on a subset S ⊆ [n], Lemma 16 gives us that
p ≻ p′ . Therefore, by Lemma 17 we conclude that g(p) stochastically dominates g(p′ ), which implies that:
µ(p) = E[g(p)] ≥ E[g(p′ )] = µ(p′ ), as was to be shown.
The following lemma shows that given an arbitrary distribution p over [n] that is ε-far from the uniform
distribution Un , if we average the heaviest ⌊n/2⌋ elements and then the lightest ⌊n/2⌋ elements, we will get
a distribution that is ε′ > ε/2-far from uniform.
Lemma 19. Let p be a probability distribution and p′ be the distribution obtained from p after averaging
the ⌊ n2 ⌋ heaviest and the ⌊ n2 ⌋ lightest elements separately. Then, the following holds:
kp − Un k1
≤ kp′ − Un k1 ≤ kp − Un k1 .
2
We note that by doing the averaging as suggested by the above lemma, we obtain a distribution p′ that is
′ 1 1−ε′
ε
′
supported on the following set of three values: { 1+ε
n , n , n }, for some 2 ≤ ε ≤ ε. Hence, we can reduce
the computation of the expectation gap for an arbitrary distribution p, to computing the gap for a distribution
of this form. Fact 6 is an immediate corollary of Lemmas 16, 17, and 19.

4.1 Proof of Lemma 17
To establish Lemma 17, we are going to use the following intermediate lemmas:
Lemma 20. Let f : Rn → R be a symmetric convex function, and a, b, c ∈ R such that 0 < a < b and
c > 0. Then,
f (a, b + c, x3 , . . . , xn ) ≥ f (a + c, b, x3 , . . . , xn ) .
Proof. Consider the set of convex functions fx′ 3 ,...,xn : R2 → R defined as:
fx′ 3 ,...,xn (x1 , x2 ) = f (x1 , x2 , x3 , . . . , xn ) .
We will show that for every possible choice of x3 , . . . , xn it holds that:
fx′ 3 ,...,xn (a, b + c) ≥ fx′ 3 ,...,xn (a + c, b) .
Since f is symmetric, so is f ′ . Therefore, we have that fx′ 3,...,xn (a, b + c) = fx′ 3 ,...,xn (b + c, a). The 3 points:
P1 = (a, b + c), P2 = (a + c, b), P3 = (b + c, a) are collinear since their coordinates satisfy the equation
x1 + x2 = a + b + c.
We have that P2 is between P1 and P3 since:
hP1~P2 , P2~P3 i = h(c, −c), (b − a, a − b)i > 0 .
By applying Jensen’s inequality, we get that
fx′ 3 ,...,xn (a + c, b) ≤

fx′ 3 ,...,xn (a, b + c) + fx′ 3 ,...,xn (b + c, a)
= fx′ 3 ,...,xn (a, b + c) .
2

as desired.
The stochastic domination between the two statistics is established in the following lemma:

17

Lemma 21. Let f : Rn → R be a symmetric convex function, p be a distribution over [n], and a, b ∈ [n] be
such that pa < pb . Also, let q be the distribution which is identical to p on [n] \ {a, b}, and for which:
 
  
pa
qa
w
1−w
,
(9)
=
1−w
w
pb
qb
where w ∈ [ 12 , 1]. Suppose we take m samples from p and let Xi denote the number of times we sample
element i. Let g(p) be the random variable f (X1 , X2 , . . . , Xn ). Then, g(p) stochastically dominates g(q).
Proof. To prove stochastic domination between g(p) and g(q), we are going to define a coupling under
which it is always true that g(p) takes a larger value than g(q).
Initially, we define an auxiliary coupling between p and q as follows: To get a sample from q, we first
sample from p and use it as our sample, unless the output is element “b”, in which case we output “a” with
b −pa )
probability (1−w)(p
and “b” otherwise4 .
pb
Suppose now that we draw m samples from p, which we also convert to samples from q using the above
rule.
In relation to this coupling we define the following random variables:
• Xlow : The number of times element “a” is sampled.
• Xhigh : The number of times element “b” is sampled and is not swapped for element “a” in q.
• Xmid : The number of times element “b” is sampled and is swapped for element “a” in q.
From the above, we have that:
Xa = Xlow ,

Xb = Xhigh + Xmid ,

Xa′ = Xlow + Xmid ,

Xb′ = Xhigh ,

where Xi′ is the number of times element i is sampled in q.
We want to show that g(p) stochastically dominates g(q). That is, we want to show that5 :
∀t : Pr[f (Xlow , Xhigh + Xmid , X3 , . . . , Xn ) ≥ t] ≥ Pr[f (Xlow + Xmid , Xhigh , X3 , . . . , Xn ) ≥ t] .
We now condition on the events E{y,z} : {Xlow , Xhigh } = {y, z} and Ec,x3,...,xn : Xmid = c ∧ X3 =
x3 ∧ · · · ∧ Xn = xn }, where y ≤ z without loss of generality. Let B = E{y,z} ∧ Ec,x3 ,...,xn .
We have that:
Pr[f (Xlow , Xhigh + Xmid , X3 , . . . , Xn ) ≥ t]
X
=
Pr[f (Xlow , Xhigh + Xmid , X3 , . . . , Xn ) ≥ t | B] Pr[B] .
y≤z

So, it suffices to show that for every y, z, c, x3 , . . . , xn , t :
Pr[f (Xlow , Xhigh + Xmid , X3 , . . . , Xn ) ≥ t | B]

≥ Pr[f (Xlow + Xmid , Xhigh , X3 , . . . , Xn ) ≥ t | B] .

(10)

At this point, we have conditioned on everything except which of Xlow and Xhigh is y and which is z. That
is, after conditioning on the event B = E{y,z} ∧ Ec,x3 ,...,xn , we have that:
{f (Xlow + Xmid , Xhigh , X3 , . . . , Xn ), f (Xlow , Xhigh + Xmid , X3 , . . . , Xn )} = {u, w} ,
4

Note that this coupling does not fix the value of g(q) given a fixed value for g(p), and is defined for convenience. We still have
to show stochastic domination for the coupled random variables using a second coupling.
5
To simplify notation, we pick a = 1 and b = 2 without loss of generality.

18

where u = f (y + c, z, x3 , . . . , xn ), w = f (y, z + c, x3 , . . . , xn ). Since by assumption y ≤ z, we have by
Lemma 20 that u ≤ w. Then (10) holds trivially as an equality for t ≤ u and for t > w. For the remaining
values of t, it is equivalent to:
Pr[f (Xlow , Xhigh + Xmid , X3 , . . . , Xn ) = w | B] ≥ Pr[f (Xlow + Xmid , Xhigh , X3 , . . . , Xn ) = w | B],
and hence to
Pr[Xlow = y, Xhigh = z | B] ≥ Pr[Xlow = z, Xhigh = y | B].

Now, this is also equivalent to a version with less restricted conditioning,

Pr[Xlow = y, Xhigh = z | Ec,x3,...,xn ] ≥ Pr[Xlow = z, Xhigh = y | Ec,x3 ,...,xn ],
because neither event occurs in the added regime where E{y,z} is false. But if we rethink how our samples
were drawn, we find that this is equivalent to showing that
pya qbz ≥ pza qby .

This holds since qbz−y > pz−y
a , concluding the proof.

Proof of Lemma 17: Since p ≻ q, we have by Theorem 15 (and the remark that follows it) that q can
be constructed from p by repeated applications of (9). Therefore, Lemma 21 and the fact that stochastic
domination is transitive imply that g(p) stochastically dominates g(q).

4.2 Proof of Lemma 19
Recall that p↓i denotes the vector p with entries rearranged in non-increasing order. Suppose that at least n/2
elements have at least 1/n probability mass6 . Therefore, if p is not the uniform distribution, we have
⌊n/2⌋

X

1 + ε′
1
> ,
2
2

p↓k =

k=1

for some ε′ > 0.
Thus, we have that

p′↓
k

=

when n is even, and
p′↓
k =

(

1+ε′
n
1−ε′
n

 ′
1+ε

 n

for k ≤
for k >

for k ≤
for k =
for k >

1

n

 1−ε′
n

n
2
n
2

n−1
2
n+1
2
n+1
2

when n is odd.
P⌊n/2⌋
P⌊n/2⌋
1+ε′
Moreover, since we are just averaging, we have that k=1 p↓k = k=1 p′↓
k = 2 . Since we have
assumed that the majority of elements has mass at least n1 , we know that the total variation distance is given
by:
dTV (p, Un ) =

X

i:pi >1/n

⌊n/2⌋

(pi −1/n) ≤ 2

X
k=1

⌊n/2⌋

(p↓i −1/n)

=2

X
k=1

(p′↓
i −1/n) ≤ 2

X

i:p′i >1/n

Thus, dTV (p′ , Un ) ≥ (1/2)dTV (p, Un ) or kp − Un k1 /2 ≤ kp′ − Un k1 , as desired.
6

This is without loss of generality, since we can use essentially the same argument in the other case.

19

′
(p′↓
i −1/n) = 2dTV (p , Un ) .

5 Conclusions and Future Work
In this paper, we gave the first uniformity tester that is sample-optimal, up to constant factors, as a function
of the confidence parameter. Our tester is remarkably simple and our novel analysis may be useful in other
related settings. By using a known reduction of identity to uniformity, we also obtain the first sample-optimal
identity tester in the same setting.
Our result is a step towards understanding the behavior of distribution testing problems in the highconfidence setting. We view this direction as one of fundamental theoretical and important practical interest.
A number of interesting open problems remain. Perhaps the most appealing one is to design a general
technique (see, e.g., [DK16]) that yields sample-optimal testers in the high confidence regime for a wide
range of properties. From the practical standpoint, it would be interesting to perform a detailed experimental
evaluation of the various algorithms (see, e.g., [HM13, BW17]).

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.
[ADK15]

J. Acharya, C. Daskalakis, and G. Kamath. Optimal testing for properties of distributions. In
Advances in Neural Information Processing Systems (NIPS), pages 3591–3599, 2015.

[Arn12]

Barry Arnold. Majorization and the Lorenz order: A brief introduction, volume 43. Springer
Science & Business Media, 2012.

[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.
[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.

[BW17]

S. Balakrishnan and L. A. Wasserman. Hypothesis testing for densities and high-dimensional
multinomials: Sharp local minimax rates. CoRR, abs/1706.10003, 2017.

[BY02]

Z. Bar-Yossef. The Complexity of Massive Data Set Computations. PhD thesis, Berkeley, CA,
USA, 2002.

[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.

20

[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
2016, pages 25:1–25:14, 2016.
[CDKS17] C. L. Canonne, I. Diakonikolas, D. M. Kane, and A. Stewart. Testing bayesian networks. In
Proceedings of the 30th Conference on Learning Theory, COLT 2017, pages 370–448, 2017.
[CDS17]

C. L. Canonne, I. Diakonikolas, and A. Stewart. Fourier-based testing for families of distributions. CoRR, abs/1706.05738, 2017.

[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.
[DGPP16] I. Diakonikolas, T. Gouleakis, J. Peebles, and E. Price. Collision-based testers are optimal
for uniformity and closeness. Electronic Colloquium on Computational Complexity (ECCC),
23:178, 2016.
[DK16]

I. Diakonikolas and D. M. Kane. A new approach for testing properties of discrete distributions.
In FOCS, pages 685–694, 2016. Full version available at abs/1601.05557.

[DKN15a] I. Diakonikolas, D. M. Kane, and V. Nikishkin. Optimal algorithms and lower bounds for
testing closeness of structured distributions. In IEEE 56th Annual Symposium on Foundations
of Computer Science, FOCS 2015, pages 1183–1202, 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, pages 1841–1854, 2015.
[DKN17]

I. Diakonikolas, D. M. Kane, and V. Nikishkin. Near-optimal closeness testing of discrete
histogram distributions. CoRR, abs/1703.01913, 2017. To appear in ICALP 2017.

[DL01]

L. Devroye and G. Lugosi. Combinatorial methods in density estimation. Springer Series in
Statistics, Springer, 2001.

[Gol16]

O. Goldreich. The uniform distribution is complete with respect to testing identity to a fixed
distribution. ECCC, 23, 2016.

[Gos78]

R. William Gosper. Decision procedure for indefinite hypergeometric summation. Proceedings
of the National Academy of Sciences, 75(1):40–42, 1978.

[GR00]

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

[HM13]

D. Huang and S. Meyn. Generalized error exponents for small sample universal hypothesis
testing. IEEE Trans. Inf. Theor., 59(12):8157–8181, December 2013.

[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.
21

[LRR11]

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

[MOA79] Albert W Marshall, Ingram Olkin, and Barry C Arnold. Inequalities: theory of majorization
and its applications, volume 143. Springer, 1979.
[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.

[PS95]

Peter Paule and Markus Schorn. A mathematica version of zeilberger’s algorithm for proving
binomial coefficient identities. Journal of Symbolic Computation, 20(5):673 – 698, 1995.

[PWZ97]

M. Petkovsek, H.S. Wilf, and D. Zeilberger. A = B (Online Edition). Ak Peters Series. Taylor
& Francis, 1997.

[Rub12]

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

[Rub14]

R. Rubinfeld.
Taming probability distributions over big domains.
at STOC’14 Workshop on Efficient Distribution Estimation, 2014.
http://www.iliasdiakonikolas.org/stoc14-workshop/rubinfeld.pdf.

[Val11]

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

Talk given
Available at

[vdVW96] A. W. van der Vaart and J. A. Wellner. Weak convergence and empirical processes. Springer
Series in Statistics. Springer-Verlag, New York, 1996. With applications to statistics.
[VV14]

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

[WY16]

Y. Wu and P. Yang. Minimax rates of entropy estimation on large alphabets via best polynomial
approximation. IEEE Transactions on Information Theory, 62(6):3702–3720, June 2016.

[Yin04]

Y. Ying. Mcdiarmid’s inequalities of bernstein and bennett forms. City University of Hong
Kong, 2004.

22

Appendix
A

Computation of the Expectation in Completeness Case

Our statistic can be written as: S =
E[S] =

Pn

i=1 max{Xi

−

m
n , 0}.

Therefore, by linearity of expectation, we get:

n
h
i
h
i
X
m
m
E max{Xi − , 0} = n · E max{Xi − , 0} .
n
n
i=1



So, all we need to do is to compute: E max{Xi − m
n , 0} for a single value of i in the completeness case.
Note that Xi ∼ Bin(m, n1 ) and that the above expectation can be written as:
m
i
h
X
m
m
E max{Xi − , 0} =
Pr[Xi = k](k − ) ,
n
n
m

(11)

k=⌈ n ⌉

(1− 1 )m−k

n
where Pr[Xi = k] =
. This is a sum of O(m) terms each of which can be computed in constant
nk
time, giving an O(m) runtime overall.

B Non-Existence of Indefinite Closed-Form for Components of Expectation
In this appendix, we formalize and prove our assertion from Section 2.2 that the function µ(p) − µ(Un ) is a
linear combination of sums each of which has no indefinite closed form.
Recall Equation
(3) which says that the expectation is a linear combination of sums with summands of

m k
the form k q (1 − q)m−k (k − t) for various values of q – where the values of q are themselves different
variables that any closed form would need to depend on (in addition to the other variables). A sum is said
to have an indefinite closed form if, when the upper and lower limits of the sum are replaced with new
variables, the resulting sum has a closed form valid for all values of all variables.
By closed form, we mean a closed form as defined in [PWZ97, Definition 8.1.1] which, as far as we are
aware, is the main formal sense in which the phrase is used in combinatorics. This definition of closed form
says that a function can be written as a sum of a constant number of rational functions, where the numerator
and denominator in each is a linear combination of a constant number of products of exponentials, factorials,
k
5
+ k.
and constant degree polynomials. An example of such a function is n1 + 7 · 2 k!+2k
3k
(
)
k

k
m−k (k − t) has no indefinite closed form – where
To prove that a sum with summands m
k q (1 − q)
m, k, q, t, and the limits of the sum are the variables that the closed form would need to be a function of –
one can run Gosper’s algorithm on this summand – with k as the index of summation – and observe that
it returns that there is no indefinite closed form solution in the sense we have described [PWZ97, Theorem
5.6.3], [Gos78, PS95].

23

