Differentially Private Testing of Identity and Closeness of
Discrete Distributions
Jayadev Acharya
Ziteng Sun
Huanyu Zhang

acharya@cornell.edu
zs335@cornell.edu
hz388@cornell.edu

arXiv:1707.05128v3 [cs.LG] 31 Oct 2017

Cornell University
Ithaca, NY

Editor:

Abstract
We study the fundamental problems of identity testing (goodness of fit), and closeness testing (two
sample test) of distributions over k elements, under differential privacy. While the problems have
a long history in statistics, finite sample bounds for these problems have only been established
recently.
In this work, we derive upper and lower bounds on the sample complexity of both the problems
under (ε, δ)-differential privacy. We provide optimal sample complexity algorithms for identity
testing problem for all parameter ranges, and the first results for closeness testing. Our closeness
testing bounds are optimal in the sparse regime where the number of samples is at most k.
Our upper bounds are obtained by privatizing non-private estimators for these problems. The
non-private estimators are chosen to have small sensitivity. We propose a general framework to
establish lower bounds on the sample complexity of statistical tasks under differential privacy. We
show a bound on differentially private algorithms in terms of a coupling between the two hypothesis
classes we aim to test. By constructing carefully chosen priors over the hypothesis classes, and
using Le Cam’s two point theorem we provide a general mechanism for proving lower bounds. We
believe that the framework can be used to obtain strong lower bounds for other statistical tasks
under privacy.

1. Introduction
Testing whether observed data conforms to an underlying model is a fundamental scientific problem.
In a statistical framework, given samples from an unknown probabilistic model, the goal is to
determine whether the underlying model has a property of interest.
This question has received great attention in statistics as hypothesis testing Neyman and Pearson
(1933); Lehmann and Romano (2006), where it was mostly studied in the asymptotic regime when
the number of samples m → ∞. In the past two decades there has been a lot of work from the
computer science, information theory, and statistics community on various distribution testing
problems in the non-asymptotic (small-sample) regime, where the domain size k could be potentially
larger than m (See Batu et al. (2000, 2001); Goldreich and Ron (2000); Batu (2001); Paninski
(2008); Acharya et al. (2013, 2014); Chan et al. (2014); Diakonikolas et al. (2015b); Bhattacharya
and Valiant (2015); Canonne et al. (2016); Diakonikolas and Kane (2016); Batu and Canonne (2017),
references therein, and Canonne (2015) for a recent survey). Here the goal is to characterize the
1

minimum number of samples necessary (sample complexity) as a function of the domain size k, and
the other parameters.
At the same time, preserving the privacy of individuals who contribute to the data samples has
emerged as one of the key challenges in designing statistical mechanisms over the last few years.
For example, the privacy of individuals participating in surveys on sensitive subjects is of utmost
importance. Without a properly designed mechanism, statistical processing might divulge the
sensitive information about the data. There have been many publicized instances of individual data
being de-anonymized, including the deanonymization of Netflix database Narayanan and Shmatikov
(2008), and individual information from census-related data Sweeney (2002). Protecting privacy for
the purposes of data release, or even computation on data has been studied extensively across several
fields, including statistics, machine learning, database theory, algorithm design, and cryptography
(See e.g., Warner (1965); Dalenius (1977); Dinur and Nissim (2003); Wasserman and Zhou (2010);
Duchi et al. (2013); Wainwright et al. (2012); Chaudhuri et al. (2011)). While the motivation is
clear, even a formal notion of privacy is not straight-forward. We use differential privacy Dwork
et al. (2006), a notion which rose from database and cryptography literature, and has emerged as
one of the most popular privacy measures (See Dwork et al. (2006); Dwork (2008); Wasserman
and Zhou (2010); Dwork et al. (2010); Blum et al. (2013); McSherry and Talwar (2007); Li et al.
(2015); Kairouz et al. (2017), references therein, and the recent book Dwork and Roth (2014)).
Roughly speaking, it requires that the output of the algorithm should be statistically close on two
neighboring datasets. For a formal definition of differential privacy, see Section 2.
A natural question when designing a differentially private algorithm is to understand how the
data requirement grows to ensure privacy, along with the same accuracy level. In this paper, we
study the sample size requirements for differentially private discrete distribution testing.
1.1 Results and Techniques
We consider two fundamental statistical tasks for testing distributions over [k]: (i) identity testing,
where given sample access to an unknown distribution p, and a known distribution q, the goal is
to decide whether p = q, or dT V (p, q) ≥ α, and (ii) closeness testing, where given sample access
to unknown distributions p, and q, the goal is to decide whether p = q, or dT V (p, q) ≥ α. (See
Section 2 for precise statements of these problems). Given differential privacy constraints (ε, δ), we
provide (ε, δ)-differentially private algorithms for both these tasks. For identity testing, our bounds
are optimal up to constant factors for all ranges of k, α, ε, δ, and for closeness testing the results are
tight in the small sample regime where m = O(k). Our upper bounds are based on various methods
to privatize the previously known tests. A critical component is to design and analyze test statistic
that have low sensitivity, in order to preserve privacy.
We first state that any (ε + δ, 0)-DP algorithm is also an (ε, δ) algorithm. Cai et al. (2017)
showed that for testing problems, any (ε, δ) algorithm will also imply a (ε + cδ, 0)-DP algorithm.
Therefore, for all the problems, we simply consider (ε, 0)-DP algorithms, and we can replace ε with
ε + δ in both the upper and lower bounds without loss of generality.
One of the main contributions of our work is to propose a general framework for establishing lower
bounds the sample complexity of statistical problems such as property estimation and hypothesis
testing under privacy constraints. We describe this, and the other results below. A summary of the
results is presented in Table 1, which we now describe in detail.
1. DP Lower Bounds via Coupling. We establish a general method to prove lower bounds
for distribution testing problems. Suppose X1m , and Y1m are generated by two statistical
2

sources. Further suppose there is a coupling between the two sources such that the expected
hamming distance between the coupled samples is at most D, then if D = o(1/(ε + δ)), there
is no (ε, δ)-differentially private algorithm to distinguish between the two sources. This result
is stated precisely in Theorem 11.
Using carefully designed coupling schemes, we provide lower bounds for binary testing, identity
testing, and closeness testing.
2. Binary Testing. To study the problem of identity testing, we warm up with the binary
1
testing problem, where k = 2. The sample complexity of this problem is Θ( α12 + αε
). The
upper bound is extremely simple, and can be obtained by the Laplace mechanism Dwork
and Roth (2014), and the lower bound follows as an application of our general lower bound
argument. The result is stated in Theorem 12. We construct a coupling between binary
1
distributions, and apply Theorem 11 to obtain a lower bound of Ω( α12 + αε
) samples for binary
testing problem, which is tight up to a constant factor.
3. Reduction from identity to uniformity. We reduce the problem of ε-DP identity testing
of distributions over [k] to ε-DP uniformity testing over distributions over [6k]. Such a
reduction, without privacy constraints was shown in Goldreich (2016), and we use their result
to obtain a reduction that also preserves privacy, with at most a constant factor blow-up in
the sample complexity. This result is given in Theorem
14.
√
k
4. Identity Testing. It was recently shown that O( α2 ) Paninski (2008); Valiant and Valiant
(2014); Diakonikolas et al. (2015b); Acharya et al. (2015) samples are necessary and sufficient
for identity testing without privacy constraints. The statistic used in these papers are variants
of chi-squared tests, which could have a high global sensitivity.
Given the reduction from identity to uniformity, it suffices to consider the statistic in Paninski
(2008) for uniformity testing. We show that privatizing
this statistic yields a sample optimal
√
√ 
k
k
testing algorithm with sample complexity O α2 + α√ε , in the sparse regime where m ≤ k.
This result is stated in Section C. However, Paninski’s test fails when m = Ω(k). We therefore
consider the test statistic studied by Diakonikolas et al. (2017) which is simply the distance of
the empirical distribution to the uniform distribution. This statistic also has a low sensitivity,
and futhermore has the optimal sample complexity in all parameter ranges, without privacy
constraints. In Theorem 13, we state the optimal sample complexity of identity testing.
The upper bounds are derived by privatizing the statistic in Diakonikolas et al. (2017). We
design a coupling between the uniform distribution u[k], and a mixture of distributions, which
are all at distance α from u[k] in total variation distance. In particular, we consider the
mixture distribution used in Paninski (2008). Much of the technical details go into proving
the existence of couplings with small expected Hamming distance. Cai et al. (2017) studied
identity
testing
under pure differential
privacy, and obtained an algorithm with complexity


√
√

O

k
α2

+

k log k
α3/2 ε

+

(k log k)1/3
α5/3 ε2/3

. Our bounds improve their bounds significantly.

5. Closeness Testing. Closeness testing
 problem was proposed by Batu et al. (2000), and
k2/3 k1/2
optimal bound of Θ max{ α4/3 , α2 } was shown in Chan et al. (2014). They proposed a
chi-square based statistic, which we show has a small sensitivity. We privatize their algorithm
to obtain the
sample√complexity
bounds. In the sparse regime we prove a sample
complexity
 2/3


√
k
k
k
1
√
bound of Θ α4/3 + α ε , and in the dense regime, we obtain a bound of O α2 + α2 ε . These
results are stated in Theorem 19. Since closeness testing is a harder problem than identity

3

Problem
Is p =

Sample Complexity Bounds


B( 12 )?

Non-private: Θ


ε-DP: Θ

1
α2

+

1
αε



1
α2



[Dwork and Roth (2014), and Theorem 12]
√ 

k
Paninski (2008)

 √ α2 √

Non-private : Θ

Identity Testing

k
α2

ε-DP algorithms: O

k log k
α3/2 ε

+

Cai et al. (2017)

(ε, δ)-DP algorithms for any ε, δ

√

S(IT, k, α, ε) = Θ
Closeness
Testing

k

α2

+ max

n


Non-private: Θ

k1/2
k1/3
,
, 1
α(ε+δ)1/2 α4/3 (ε+δ)2/3 α(ε+δ)
k2/3
α4/3

+


1/2

k
α2

o

[Theorem 13]

Chan et al. (2014)

ε-DP:


IF α2 = Ω

√1
k



 

and α2 ε = Ω

1
k

S(CT, k, α, ε) = Θ
ELSE
Ω

√

k

α2

+

√
√k
α ε

+

1
αε



k2/3
α4/3

+

√ 
√k
α ε

≤ S(CT, k, α, ε) ≤ O

[Theorem 19]

√

k

α2

+

1
α2 ε



[Theorem 19]

Table 1: Summary of the sample complexity bounds for the problems of identity testing, and
closeness testing of discrete distributions.

testing, all the lower bounds from identity testing port over to closeness testing. The closeness
testing lower bounds are given in Theorem 19.
1.2 Related Work
A number of papers have recently studied hypothesis testing problems under differential privacy
guarantees Wang et al. (2015); Gaboardi et al. (2016); Rogers and Kifer (2017). Some works analyze
the distribution of the test statistic in the asymptotic regime. The work most closely related to ours
is in Cai et al. (2017), which studied identity testing in the finite sample regime. We mentioned
their guarantees along with our results on identity testing in the previous section.
There has been a line of research for statistical testing and estimation problems under the notion
of local differential privacy Wainwright et al. (2012); Duchi et al. (2013); Erlingsson et al. (2014);
Pastore and Gastpar (2016); Kairouz et al. (2016); Wang et al. (2016a); Ye and Barg (2017). These
papers study some of the most basic statistical problems and also provide minimax lower bounds
using Fano’s inequality. Diakonikolas et al. (2015a) study structured distribution estimation under
differential privacy.
Information theoretic approaches to data privacy have been studied recently using quantities like
mutual information, and guessing probability to quantify privacy Mir (2012); Sankar et al. (2013);
Cuff and Yu (2016); Wang et al. (2016b); Issa and Wagner (2017).
In a contemporaneous and independent work, Aliakbarpour et al. (2017), the authors study
the same problems that we consider, and obtain the same upper bounds for the sparse case, when
m ≤ k. They also provide experimental results to show the performance of the privatized algorithms.
4

However, their results are sub-optimal for m = Ω(k) for identity testing, and they do not provide
any lower bounds for the problems. Both Cai et al. (2017), and Diakonikolas et al. (2017) consider
only pure-differential privacy, which are a special case of our results.
1.3 Organization of the paper
In Section 2, we discuss the definitions and notations. A general technique for proving lower bounds
for differentially private algorithms is described in Section 3. In Section 4, we study differentially
private binary hypothesis testing as a warm-up. Section 5 gives upper and lower bounds for identity
testing, and closeness testing is studied in Section 6. Section C proves that the original uniformity
tester of Paninski (2008) is optimal in the sparse sample regime.

2. Preliminaries
We consider discrete distributions over a domain of size k, which we assume without loss of generality
∆
to be [k] = {1, . . . ,k}. We denote length-m samples X1 , . . . ,Xm by X1m . For x ∈ [k], let px be the
probability of x under p. Let Mx (X1m ) be the number of times x appears in X1m . For A ⊆ [k], let
P
p(A) = x∈A px . Let X ∼ p denote that the random variable X has distribution p. Let u[k] be the
uniform distribution over [k], and B(b) be the Bernoulli distribution with bias b.
Definition 1 The total variation distance between distributions p, and q over a discrete set [k] is
1
∆
dT V (p, q) = sup p(A) − q(A) = kp − qk1 .
2
A⊂[k]
Definition 2 Let p, and q be distributions over X , and Y respectively. A coupling between p and q
is a distribution over X × Y whose marginals are p and q respectively.
∆

Definition 3 The Hamming distance between two sequences X1m and Y1m is d(X1m , Y1m ) =
the number of positions where X1m , and Y1m differ.

Pm

i=1 I{Xi

We now define (ε, δ)-differential privacy.
Definition 4 A randomized algorithm A on a set X m → S is said to be (ε, δ)-differentially private
if for any S ⊂ range(A), and all pairs of X1m , and Y1m with d(X1m , Y1m ) ≤ 1
Pr (A(X1m ) ∈ S) ≤ eε · Pr (A(Y1m ) ∈ S) + δ.
The case when δ = 0 is called pure differential privacy. For simplicity, we denote pure differential
privacy as ε-differential privacy (ε-DP). The next lemma states a relationship between (ε, δ)differential privacy and ε-differential privacy. The result is implicitly present in Cai et al. (2017),
but we state here for completeness.
Lemma 5 There is an (ε, δ)-DP algorithm for a testing problem if and only if there is an (O(ε+δ), 0)DP algorithm for the same testing problem.
Proof The proof has two parts.
5

6= Yi },

• The first is to show that any (ε + δ, 0)-DP algorithm is also (ε, δ)-DP. This is perhaps folklore,
and is shown below. Suppose A is a (ε + δ)-differentially private algorithm. Then for any X1m
and Y1m with d(X1m , Y1m ) ≤ 1 and any S ⊂ range(A), we have
Pr (A(X1m ) ∈ S) ≤ eε+δ · Pr (A(Y1m ) ∈ S) = eε · Pr (A(Y1m ) ∈ S) + (eδ − 1) · eε Pr (A(Y1m ) ∈ S).
If eε ·Pr (A(Y1m ) ∈ S) > 1−δ, then Pr (A(X1m ) ∈ S) ≤ 1 < eε ·Pr (A(Y1m ) ∈ S)+δ. Otherwise,
eε · Pr (A(Y1m ) ∈ S) ≤ 1 − δ. To prove (eδ − 1) · eε · Pr (A(Y1m ) ∈ S) < δ, it suffices to show
(eδ − 1)(1 − δ) ≤ δ, which is equivalent to e−δ ≥ 1 − δ, completing the proof.
• Consider an (ε, δ)-DP algorithm with error probability at most 0.05. Consider an algorithm
that finally flips the answer with probability 0.05. This algorithm has error probability at
most 0.1, and for any input, each outcome has probability at least 0.05. Cai et al. (2017)
essentially showed that this new algorithm is (ε + 10δ, 0)-DP.

A notion that is often useful in establishing bounds for differential privacy is sensitivity, defined
below.
∆

Definition 6 The sensitivity of a function f : [k]m → R is ∆(f ) = maxd(X1m ,Y1m )≤1 |f (X1m ) − f (Y1m )| .
∆

Definition 7 The sigmoid-function σ : R → (0, 1) is σ(x) =

1
1+exp(−x)

=

exp(x)
1+exp(x) .

We need the following result for the sigmoid function.
Lemma 8
1. For all x, γ ∈ R, exp(− |γ|) ≤ σ(x+γ)
σ(x) ≤ exp(|γ|).
1
1
2. Let 0 < η < 2 . Suppose x ≥ log η . Then σ(x) > 1 − η.
Proof
σ(x+γ)
σ(x)

Since σ(x) is an increasing function, it suffice to assume that γ > 0. In this case,
1+exp(x)
1
1
= exp(γ) · 1+exp(x+γ)
< exp(γ). For the second part, σ(x) = 1 − 1+e
x ≥ 1 − ex ≥ 1 − η.

Identity Testing (IT). Given description of a probability distribution q over [k], parameters α,
and ε, and m independent samples X1m from an unknown distribution p. An algorithm A is an
(k, α) - identity testing algorithm for q, if
• when p = q, A outputs “p = q” with probability at least 0.9, and
• when dT V (p, q) ≥ α, A outputs “p 6= q” with probability at least 0.9.
Furthermore, if A is (ε, 0)-differentially private, we say A is an (k, α, ε)-identity testing algorithm.
Definition 9 The sample complexity of DP-identity testing problem, denoted S(IT, k, α, ε), is the
smallest m for which there exists an (k, α, ε)-identity testing algorithm A that uses m samples.
When privacy is not a concern, we denote the sample complexity as S(IT, k, α). When q = u[k], the
problem reduces to uniformity testing, and the sample complexity is denoted S(UT, k, α, ε).
Closeness Testing (CT). Given parameters α, and ε, and m independent samples X1m , and Y1m
from unknown distributions p, and q. An algorithm A is an (k, α)-closeness testing algorithm if
• If p = q, A outputs p = q with probability at least 0.9, and
• If dT V (p, q) ≥ α, A outputs p 6= q with probability at least 0.9.
6

Furthermore, if A is (ε, 0)-differentially private, we say A is an (k, α, ε)-closeness testing algorithm.
Definition 10 The sample complexity of an (k, α, ε)-closeness testing problem, denoted S(CT, k, α, ε),
is the least values of m for which there exists an (k, α, ε)-closeness testing algorithm A. When
privacy is not a concern, we denote the sample complexity of closeness testing as S(CT, k, α).
We note again that by Lemma 5, we need to only consider pure differential privacy for both
upper and lower bounds.

3. Privacy Bounds Via Coupling
Recall that coupling between distributions p and q over X , and Y, is a distribution over X × Y
whose marginal distributions are p and q (Definition 2). For simplicity, we treat coupling as a
randomized function f : X → Y such that if X ∼ p, then Y = f (X) ∼ q. Note that X, and Y are
not necessarily independent.
Example 1 Let B(b1 ), and B(b2 ) be Bernoulli distributions with bias b1 , and b2 such that b1 < b2 .
Let p, and q be distributions over {0, 1}m obtained by m i.i.d. samples from B(b1 ), and B(b2 )
respectively. Let X1m be distributed according to p. Generate a sequence Y1m as follows: If Xi = 1,
then Yi = 1. If Xi = 0, we flip another coin with bias (b2 − b1 )/(1 − b1 ), and let Yi be the output of
this coin. Repeat the process independently for each i, such that the Yi ’s are all independent of each
other. Then Pr (Yi = 1) = b1 + (1 − b1 )(b2 − b1 )/(1 − b1 ) = b2 , and Y1m is distributed according to q.
We would like to use coupling to prove lower bounds on differentially private algorithms for
testing problems. Let p and q be distributions over X m . If there is a coupling between p and q
with a small expected Hamming distance, we might expect that the algorithm cannot have strong
privacy guarantees. The following theorem formalizes this notion, and will be used to prove sample
complexity bounds of differentially private algorithms.
Theorem 11 Suppose there is a coupling between distributions p and q over X m , such that
E [d(X1m , Y1m )] ≤ D. Then, any ε-differentially private algorithm
that distinguishes between p
 
1
and q with error probability at most 1/10 must satisfy D = Ω ε .
Proof Let (X1m , Y1m ) be a coupling of p, and q with E [d(X1m , Y1m )] ≤ D. Then, Pr (A(X1m ) = p) ≥
0.9, and Pr (A(Y1m ) = q) ≥ 0.9 implies that Pr (A(X1m ) = p ∩ A(Y1m ) = q) ≥ 0.9 + 0.9 − 1 = 0.8.
By Markov’s inequality, Pr (d(X1m , Y1m ) > 10D) < Pr (d(X1m , Y1m ) > 10 · E [d(X1m , Y1m )]) < 0.1.
Therefore,
Pr (A(X1m ) = p ∩ A(Y1m ) = q ∩ d(X1m , Y1m ) < 10D) ≥ 0.8 + 0.9 − 1 = 0.7.

(1)

The condition of differential privacy states that for any X1m , and Y1m ,
m ,Y m )
1

e−ε·d(X1

<

Pr (A(X1m ) = p)
m
m
< eε·d(X1 ,Y1 ) .
Pr (A(Y1m ) = p)

Consider one sequence pair X1m , and Y1m that satisfies (1). Then, we know that Pr (A(X1m ) = p) >
0.7, and Pr (A(Y1m ) = q) > 0.7. By the condition of differential privacy,
m ,Y m )
1

0.3 ≥ Pr (A(Y1m ) = p) ≥ Pr (A(X1m ) = p) · e−ε·d(X1
7

= 0.7 · e−10εD .

Taking logarithm we obtain
ln(7/3) 1
1
,
=Ω
10 ε
ε
 

D≥
completing the proof.

4. Binary Identity Testing
We start with a simple testing problem. Given b0 , α > 0, and ε > 0, and samples X1m ∈ {0, 1}m
from B(b), distinguish between the cases b = b0 , and |b − b0 | ≥ α. We prove the following theorem
(stated for ε-DP without loss of generality).
Theorem 12
 Given b0 ∈ [0, 1], and ε > 0, δ ≥ 0, and α > 0. There is an (ε, δ)-DP algorithm
1
that takes O α12 + αε
samples from a distribution B(b) and distinguishes between b = b0 , and
|b − b0 | ≥ α with probability at least 9/10. Moreover, any algorithm for this task requires Ω
samples.



1
α2

+

1
αε



Simple bias and variance arguments show that the sample complexity of this problem is Θ(1/α2 ).
In this section, we study the sample complexity with privacy constraints. We note that the upper
bound can simply be achieved by the well known Laplace mechanism in differential privacy. We
add a Lap(1/ε) random variable to the number of 1’s in X1m , and then threshold the output
appropriately. The privacy is guaranteed by privacy guarantees of the Laplace mechanism. A small
bias variance computation also gives the second term. For completeness, we provide a proof of
the upper bound using our techniques in Section A. The lower bound is proved using the coupling
defined in Example 1 with Theorem 11.
4.1 Binary Testing Lower Bound via Coupling
Suppose b0 = 0.5. Then least Ω 1/α2 samples are necessary totest whether b = b0 , or |b − b0 | > α.
1
using a coupling.
We will prove the second term, namely a lower bound of Ω αε


Consider the special case of Example 1 with b2 = 12 +α, and b1 = 12 . Then, D = (b2 −b1 )m = αm,
and E [d(X1m , Y1m )] = αm. Applying Theorem 11, we know
that any ε-DP algorithm must satisfy

1
E [d(X1m , Y1m )] ≥ Ω 1ε , which implies that m ≥ Ω αε
.

5. Identity Testing
In this section, we prove the bounds for identity testing. Our main result is the following (stated for
ε-DP without loss of generality):
Theorem 13
S(IT, k, α, ε) =

 √

k
k1/2

+
,
Θ

2
1/2

α
αε
 √

1/3

Θ

k

+

k

α2
α4/3

√
 ε2/3


Θ 2k + 1
αε
α

8

when m ≤ k
,

when k < m ≤
when m ≥

k
.
α2

k
α2

We can combine the three bounds to obtain
k 1/2
S(IT, k, α, ε) = Θ
+ max
α2

(

k 1/2
k 1/3
1
,
,
1/2
4/3
2/3
αε
αε
α ε

)!

.

Our bounds are tight up to constant factors in all parameters, including pure differential privacy
when δ = 0.
For proving upper bounds, by Lemma
prove them
 only in pure differential privacy
 √ 5, it √suffices to
k
k
1
k1/3
√
case, which means S(IT, k, α, ε) = O α2 + α ε + α4/3 ε2/3 + αε . In Theorem 14 we will show a
reduction from identity to uniformity testing under pure differential privacy. Using this, it will be
enough to design algorithms for uniformity testing, which is done in Section 5.2 where we will prove
the upper bound.
Moreover since uniformity testing is a special case of identity testing, any lower bound for
uniformity will port over to identity, and we give such bounds in Section 5.3.
5.1 Uniformity Testing implies Identity Testing
√

The sample complexity of testing identity of any distribution is O( α2k ), a bound that is tight for the
uniform distribution. Recently Goldreich (2016) proposed a scheme to reduce the problem of testing
identity of distributions over [k] for total variation distance α to the problem of testing uniformity over
[6k] with total variation parameter α/3. In other words, they show that S(IT, k, α) ≤ S(UT, 6k, α/3).
Our upper bounds use (ε + δ, 0)-DP, and therefore we only need to prove this result for pure
differential privacy. Building up on the construction of Goldreich (2016), we show that such a bound
also holds for differentially private algorithms.
Theorem 14
S(IT, k, α, ε) ≤ S(UT, 6k, α/3, ε).
The theorem is proved in Section B.
5.2 Identity Testing – Upper Bounds
We had mentioned in the results that we can use the statistic of Paninski (2008) to achieve the
optimal sample complexity in the sparse case. This result is shown in Section D. In this section, we
will show that by privatizing the statistic proposed in Diakonikolas et al. (2017) we can achieve
the sample complexity in Theorem 13 for all parameter ranges. The procedure is described in
Algorithm 1.
Recall that Mx (X1m ) is the number of appearances of x in X1m . Let
∆

S(X1m ) =

n
1 X
Mx (X1m ) 1
·
− ,
2 x=1
m
k

(2)

be the distance of the empirical distribution from the uniform distribution. Let µ(p) = E [S(X1m )]
when the samples are drawn from distribution p. They show the following separation result on the
expected value of S(X1m ).
9

Lemma 15 (Diakonikolas et al. (2017)) Let p be a distribution over [k] and α = dT V (p, u[k]),
then there is a constant c such that

µ(p) − µ(u[k]) ≥


2


cα2 · m
,

k2

q

when m < k




 cα,

when m ≥

cα2

m
k,

·

when k < m ≤

k
α2

k
α2

Diakonikolas et al. (2017) used this result to show that thresholding S(X1m ) at 0 is an optimal
algorithm for identity testing. Their result is stronger than what we require in our work, since we
only care about making the error probability at most 0.1. We first normalize the statistic to simplify
the presentation of our DP algorithm. Let
 

m ) − µ(u[k]) − 1 cα2 · m2 ,

k
S(X

2
1

2
kq
 

m ∆
m
m ) − µ(u[k]) − 1 cα2 ·
,
m
S(X
Z(X1 ) =
1
2
k





m S(X m ) − µ(u[k]) − 1 cα ,
1

2

when m ≤ k
when k < m ≤
when m ≥

k
α2

(3)

k
α2

where c is the constant in Lemma 15, and µ(u[k]) is the expected value of S(X1m ) when X1m are
drawn from uniform distribution.
Therefore, for X1m drawn from u[k],
E [Z(X1m )]

≤


1
2 m2


− 2 cα · k ,

when m ≤ k

3/2
− 1 cα2 · m
,
k1/2
 2

− 1 cmα,
2

when k < m ≤ αk2
when m ≥ αk2 .

(4)

For X1m drawn from p with dT V (p, u[k]) ≥ α,
E [Z(X1m )]

≥


1
2 m2

 2 cα · k ,


1
2 m3/2
2 cα · k1/2 ,


 1 cmα,
2

when m ≤ k
when k < m ≤ αk2
when m ≥ αk2 .

(5)

Algorithm 1 Uniformity testing
Input: ε, α, δ be i.i.d. samples X1m from p
1: Let Z(X1m ) be evaluated from (2), and (3).
2: Generate Y ∼ B(σ(ε · Z)), σ is the sigmoid function.
3: if Y = 0, return p = u[k]
4: else, return p = u[k]
In order to prove the privacy bounds, we need the following (weak) version of the result
of Diakonikolas et al. (2017), which is sufficient to prove the sample complexity bound for constant
error probability.
√
Lemma 16 There is a constant C > 0, such that when m > C k/α2 , then for X1m ∼ p, where
either p = u[k], or dT V (p, u[k]) ≥ α,


Pr |Z(X1m ) − E [Z(X1m )]| >
10

2E [Z(X1m )]
3



< 0.01.

The proof of this result is in Section D.
We now prove that this algorithm is ε-DP. We need the following sensitivity result.
Lemma 17 ∆(Z) ≤ 1 for all values of m, and k.
∆ 1
2

Proof Recall that S(X1m ) =

·

Pn

x=1

Mx (X1m )
m

−

1
k

. Changing any one symbol changes at most two

1
of the Mx (X1m )’s. Therefore at most two of the terms change by at most m
. Therefore, ∆(S(X1m ) ≤
1
observation
that Mx (X1m )/m≥ k1 , for all
m , for any m. When m ≤ k, this can bestrengthened with


M (X m )

Φ (X m )

x
1
− k1 + x:Mx (X1m )=0 k1 = 0 k 1 ,
Mx (X1m ) ≥ 1. Therefore, S(X1m ) = 12 ·
x:Mx (X1m )≥1
m
where Φ0 (X1m ) is the number of symbols not appearing in X1m . This changes by at most one when
one symbol is changed, proving the result.

P

P

Using this lemma, ε · Z(X1m ) changes by at most ε when X1m is changed at one location. Invoking
Lemma 8, the probability of any output changes by a multiplicative exp(ε), and the algorithm is
ε-differentially private.
√
We now proceed to prove the sample complexity bounds. Assume that m > C k/α2 , so
Lemma 16 holds. Suppose ε be any real number such that ε|E [Z(X1m )] | > 3 log 100. Let A(X1m )
be the output of Algorithm 1. Denote the output by 1 when A(X1m ) is “p 6= u[k]”, and 0 otherwise.
Consider the case when X1m ∼ p, and dT V (p, u[k]) ≥ α. Then,
Pr (A(X1m )



= 1) ≥ Pr

A(X1m )

= 1 and

Z(X1m )

E [Z(X1m )]
>
3



E [Z(X1m )]
E [Z(X1m )]
= Pr
>
· Pr A(X1m ) = 1|Z(X1m ) >
3
3
  


E [Z(X1m )]
≥ 0.99 · Pr B σ ε ·
=1
3
≥ 0.99 · 0.99 ≥ 0.9,




Z(X1m )





where the last step uses that εE [Z(X1m )] /3 > log 100, along with Lemma 8. The case of p = u[k]
follows from the same argument.
√
Therefore, the algorithm is correct with probability at least 0.9, whenever, m > C k/α2 , and
ε|E [Z(X1m )] | > 3 log 100. By (5), note that ε|E [Z(X1m )] | > 3 log 100 is satisfied when,
cα2 · m2 /k ≥(6 log 100)/ε, for m ≤ k,
cα2 · m3/2 /k 1/2 ≥(6 log 100)/ε, for k < m ≤ k/α2 ,
cα · m ≥(6 log 100)/ε, for m ≥ k/α2 .
This gives the upper bounds for all the three regimes of m.
5.3 Sample Complexity Lower bounds for Uniformity Testing
In this section, we will show that for any value of k, α, ε,
k 1/2
S(IT, k, α, ε) = Ω
+ max
α2
11

(

k 1/2
k 1/3
1
,
,
αε1/2 α4/3 ε2/3 αε

)!

,

which can be rewritten as:

S(IT, k, α, ε) =

 √

k
k1/2

+
,
Ω


α2
αε1/2
 √

1/3
k

Ω

k

+

α2
α4/3

 ε2/3
√


k
1
Ω 2 +
αε
α

when m ≤ k

,

when k < m ≤
when m ≥

k
α2

k
.
α2

The first term is the lower bound without privacy constraints, proved in Paninski (2008). In this
section, we will prove the terms associated with privacy.
1
The simplest argument is for m ≥ αk2 . From Theorem 12, αε
is a lower bound for binary identity
testing, which is a special case of identity testing for distributions over [k] (when k − 2 symbols
have probability zero). This proves the lower bound for this case.
We now consider the cases m ≤ k and k < m ≤ αk2 .
To this end, we invoke LeCam’s two point theorem, and design a hypothesis testing problem
that will imply a lower bound on uniformity testing. The testing problem will be to distinguish
between the following two cases.
Case 1: We are given m independent samples from the uniform distribution u[k].
Case 2: Generate a distribution p with dT V (p, u[k]) ≥ α according to some prior over all such
distributions. We are then given m independent samples from this distribution p.
Le Cam’s two point theorem Yu (1997) states that any lower bound for distinguishing between
these two cases is a lower bound on identity testing problem.
We now describe the prior construction for Case 2, which is the same as considered by Paninski
(2008) for lower bounds on identity testing without privacy considerations. For each z ∈ {±1}k/2 ,
define a distribution pz over [k] such that
pz (2i − 1) =

1 + zi · 2α
1 − zi · 2α
, and pz (2i) =
.
k
k

Then for any z, dT V (Pz , u[k]) = α. For Case 2, choose p uniformly from these 2k /2 distributions.
Let Q2 denote the distribution on [k]m by this process. In other words, Q2 is a mixture of product
distributions over [k].
In Case 1, let Q1 be the distribution of m i.i.d. samples from u[k].
To obtain a sample complexity lower bound for distinguishing the two cases, we will design a
coupling between Q1 , and Q2 , and bound its expected Hamming distance. While it can be shown
that the Hamming distance of the coupling between the uniform distribution with any one of the
2k/2 distributions grows as αm, it can be significantly smaller, when we consider the mixtures. In
particular, the following lemma shows that there exist couplings with bounded Hamming distance.
Lemma 18 There is a coupling between X1m generated by Q1 , and Y1m by Q2 such that
(

E [d(X1m , Y1m )]

≤

2 2

8 m kα ,

when m ≤ k

C·

when k < m ≤

3/2
α2 m
,
k1/2

The lemma is proved in Appendix
11,
  E. Now applying
 Theorem

m2 α2
1
k1/2
1. For m ≤ k, 8 k = Ω ε , implying m = Ω αε1/2 .
2. For k < m ≤

k
,
α2

3/2

 

C · α2 m
=Ω
k1/2

1
ε



, implying m = Ω
12

k1/3
α4/3 ε2/3



.

k
.
α2

(6)

6. Closeness Testing
Recall the closeness testing problem from Section 2, and the tight non-private bounds from Table 1.
Our main result in this section is the following theorem characterizing the sample complexity of
differentially private algorithms for closeness testing.
Theorem 19 If α > 1/k 1/4 , and εα2 > 1/k,
!

k 2/3
k 1/2
S(CT, k, α, ε) = Θ 4/3 + √ ,
α ε
α
otherwise,
!

1
k 1/2
+ 2 .
S(CT, k, α, ε) = O
α2
α ε
and

!

k 1/2
1
k 1/2
√ +
+
.
S(CT, k, α, ε) = Ω
2
α
α ε αε
This theorem shows that in the sparse regime, when m = O(k), our bounds are tight up to
constant factors in all parameters.
6.1 Closeness Testing – Upper Bounds
In this section, we only consider the case when δ = 0, which would suffice by lemma 5.
To prove the upper bounds, we privatize the closeness testing algorithm of Chan et al. (2014).
To reduce the strain on the readers, we drop the sequence notations explicitly and let
∆

∆

µi = Mi (X1m ), and νi = Mi (Y1m ).
Variants of the chi-squared test have been used to test closeness of distributions in the recent
years Acharya et al. (2012); Chan et al. (2014). In particular, the statistic used by Chan et al.
(2014) is
2
∆ X (µi − νi ) − µi − νi
Z(X1m , Y1m ) =
,
µi + νi
i∈[k]
where we assume that ((µi − νi )2 − µi − νi )/(µi + νi ) = 0, when µi + νi = 0.
The results in Chan et al. (2014) were proved under Poisson sampling, and we also use Poisson
sampling, with only a constant factor effect on the number of samples for the same error probability.
They showed the following bounds:
E [Z(X1m , Y1m )] = 0 when p = q,
Var(Z(X1m , Y1m ))

(7)

≤ 2 min{k, m} when p = q,

E [Z(X1m , Y1m )] ≥

m2 α2

when dT V (p, q) ≥ α,
4k + 2m
 
1
1
m
m
m
m 2
Var(Z(X1 , Y1 )) ≤
E [Z(X1 , Y1 )] when p 6= q, and m = Ω 2 .
1000
α
13

(8)
(9)
(10)

Algorithm 2
Input: ε, α, sample access to distribution p and q
m 2 α2
1: Z 0 ← Z(X1m , Y1m ) − 12 4k+2m
2: Generate Y ∼ B(σ(exp(ε · Z 0 ))
3: if Y = 0, return p = q
4: else, return p 6= q

We use the same approach with the test statistic as with binary testing and uniformity testing
to obtain a differentially private closeness testing method, described in Algorithm 2.
We will show that Algorithm 2 satisfies sample complexity upper bounds described in theorem 19.
We first bound the sensitivity (Definition 6) of the test statistic to prove privacy bounds.

Lemma 20 ∆(Z(X1m , Y1m )) ≤ 14.
Proof Since Z(X1m , Y1m ) is symmetric, without loss of generality assume that one of the symbols is
changed in Y1m . This would cause at most two of the νi ’s to change. Suppose νi ≥ 1, and it changed
to νi − 1. Suppose, µi + νi > 1, the absolute change in the ith term of the statistic is
(µi − νi )2 (µi − νi + 1)2
(µi + νi )(2µi − 2νi + 1) + (µi − νi )2
−
=
µi + νi
µi + νi − 1
(µi + νi )(µi + νi − 1)
µi − νi
2µi − 2νi + 1
+
≤
µi + νi − 1
µi + νi − 1
3 |µi − νi | + 1
≤
µi + νi − 1
4
≤3 +
≤ 7.
µi + νi − 1
When µi + νi = 1, the change can again be bounded by 7. Since at most two of the νi ’s change, we
obtain the desired bound.
Since the sensitivity of the statistic is at most 14, the input to the sigmoid changes by at most 14ε
when any input sample is changed. Invoking Lemma 8, the probability of any output changes by a
multiplicative exp(14ε), and the algorithm is 14ε-differentially private.
We now prove the correctness of the algorithm:
√1 , and α2 ε
k
k1/2
+ α√ε ≤ 2k.

Case 1: α2 >
In this case,

k2/3
α4/3

> k1 . In this case, we will show that S(CT, k, α, ε) = O



k2/3
α4/3

+

k1/2
√
α ε



.

We consider the case when p = q, then Var(Z(X1m , Y1m )) ≤ 2 min{k, m}. Let Var(Z(X1m , Y1m )) ≤
cm for some constant c. By the Chebychev’s inequality,
14

1
m2 α2
Pr Z 0 > − ·
6 4k + 2m

!

1
m2 α 2
≤ Pr Z(X1m , Y1m ) − E [Z(X1m , Y1m )] > ·
3 4k + 2m
≤ Pr

Z(X1m , Y1m )

−

E [Z(X1m , Y1m )]

1 m2 α 2
> ·
3
8k
1/2

≤ Pr Z(X1m , Y1m ) − E [Z(X1m , Y1m )] > (cm)
≤576c ·

!

!

m3/2 α2
·
24c1/2 k

!

k2
,
m3 α4

where we used that 4k + 2m ≤ 8k.

Therefore, there is a C1 such that if m ≥ C1 k 2/3 /α4/3 , then under p = q, Pr Z 0 > − 16 ·

m 2 α2
4k+2m



2 2

m α
is at most 1/100. Now furthermore, if ε · m2 α2 /48k > log(20), then for all Z 0 < − 16 · 4k+2m
, with
probability at least 0.95, the algorithm outputs the
p
=
q.
Combining
the
conditions,
we
obtain
 2/3

1/2
that there is a constant C2 such that for m = C2 αk 4/3 + αk √ε , with probability at least 0.9, the
algorithm outputs the correct answer when the input distributions satisfy p = q. The case of
dT V (p, q) > α distribution is similar and is omitted.
√

Case 2: α2 < √1k , or α2 ε < k1 . In this case, we will prove a bound of O α2k + α12 ε on the

sample complexity. We still consider the case when p = q. We first note that when α2 <
√

√1 ,
k

or

α2 ε < k1 , then either α2k + α12 ε > k. Hence we can assume that the sample complexity bound we
aim for is at least Ω(k). So Var(Z(X1m , Y1m )) ≤ ck for constant c. By the Chebychev’s inequality,
1
m2 α 2
Pr Z > − ·
6 4k + 2m
0

!

≤ Pr

Z(X1m , Y1m )

≤ Pr

Z(X1m , Y1m )

−

E [Z(X1m , Y1m )]

m2 α2
1
> ·
3 4k + 2m

−

E [Z(X1m , Y1m )]

1 mα2
> ·
3
6

!

!

mα2
≤ Pr Z(X1m , Y1m ) − E [Z(X1m , Y1m )] > (ck)1/2 ·
18c1/2 k 1/2
k
≤144 · c · 2 4 .
m α


Therefore, there is a C1 such that if m ≥ C1 k 1/2 /α2 , then under p = q, Pr Z 0 > − 16 ·

!

m 2 α2
4k+2m

2 2



m α
is at most 1/100. In this situation, if ε · mα2 /36 > log(20), then for all Z 0 < − 16 · 4k+2m
, with
probability at least 0.95, the algorithm outputs the p = q. Combining
with
the
previous
conditions,

√
we obtain that there also exists a constant C2 such that for m = C2 α2k + α12 ε , with probability at
least 0.9, the algorithm outputs the correct answer when the input distribution is p = q. The case
of dT V (p, q) > α distribution is similar and is omitted.

6.2 Closeness Testing – Lower Bounds
To show the lower bound part of Theorem 19, we need the following simple result.
15

Lemma 21 S(IT, k, α, ε) ≤ S(CT, k, α, ε).
Proof Suppose we want to test identity with respect to q. Given X1m from p, generate Y1m
independent samples from q. If p = q, then the two samples are generated by the same distribution,
and otherwise they are generated by distributions that are at least ε far in total variation. Therefore,
we can simply return the output of an (k, α, ε)-closeness testing algorithm on X1m , and Y1m .
By Lemma 21 we know that a lower bound for identity testing is also a lower bound on closeness
testing.
We first consider the sparse case, when α2 > √1k , and α2 ε > k1 . In this case, we show that
√ !
k 2/3
k
S(CT, k, α, ε, δ) = Ω 4/3 + √ .
α ε
α


2/3

2/3

√



1
When α > k1/4
, αk 4/3 is the dominating term in the sample complexity S(CT, k, α) = Θ αk 4/3 + α2k ,
giving us the first term. By Lemma 21 we know that a lower bound for identity testing is also
a lower bound on closeness testing giving the second term, and the lower bound of Theorem 13
contains the second term as a summand.
In the dense case, when α2 < √1k , or α2 ε < k1 , we show that

√

!
√
k
1
S(CT, k, α, ε, δ) = Ω
+ √ +
.
α2
α ε αε

k

√ 
k2/3
k
+
along with the identity
α2
α4/3
√
1
lower bounds of note that α√kε + αε
gives a lower bound of
√
√ 
2/3
in the dense case, it is easy to see that αk 4/3 = O α2k + α√kε



In the dense case, using the non-private lower bounds of Ω
testing bound of sample complexity


2/3

√

√

Ω αk 4/3 + α2k + α√kε +
giving us the bound.

1
αε



. However,

References
J. Acharya, A. Orlitsky, A. T. Suresh, and H. Tyagi. Estimating Rényi entropy of discrete
distributions. IEEE Transactions on Information Theory, 63(1):38–56, Jan 2017. ISSN 0018-9448.
Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, Shengjun Pan, and
Ananda Theertha Suresh. Competitive classification and closeness testing. In COLT, 2012.
Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. A competitive
test for uniformity of monotone distributions. In Proceedings of the 16th International Conference
on Artificial Intelligence and Statistics (AISTATS), 2013.
Jayadev Acharya, Ashkan Jafarpour, Alon Orlitksy, and Ananda Theertha Suresh. Sublinear
algorithms for outlier detection and generalized closeness testing. In Proceedings of the 2014
IEEE International Symposium on Information Theory (ISIT), 2014.
Jayadev Acharya, Constantinos Daskalakis, and Gautam C Kamath. Optimal testing for properties
of distributions. In NIPS, 2015.
16

Maryam Aliakbarpour, Ilias Diakonikolas, and Ronitt Rubinfeld. Differentially private identity and
closeness testing of discrete distributions. arXiv preprint arXiv:1707.05497, 2017.
Tugkan Batu. Testing properties of distributions. PhD thesis, Cornell University, 2001.
Tugkan Batu and Clément L. Canonne. Generalized uniformity testing. In FOCS, 2017.
Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White. Testing that
distributions are close. In FOCS, pages 259–269, 2000.
Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, and Patrick White.
Testing random variables for independence and identity. In FOCS, pages 442–451, 2001.
Bhaswar Bhattacharya and Gregory Valiant. Testing closeness with unequal sized samples. In
Advances in Neural Information Processing Systems, pages 2611–2619, 2015.
Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to noninteractive
database privacy. Journal of the ACM (JACM), 60(2):12, 2013.
Bryan Cai, Constantinos Daskalakis, and Gautam Kamath. Priv’it: Private and sample efficient
identity testing. In ICML, 2017.
Clément L. Canonne. A survey on distribution testing: Your data is big. but is it blue? Electronic
Colloquium on Computational Complexity (ECCC), 22:63, 2015. URL http://eccc.hpi-web.
de/report/2015/063.
Clément L Canonne, Ilias Diakonikolas, Themis Gouleakis, and Ronitt Rubinfeld. Testing shape
restrictions of discrete distributions. In 33rd Symposium on Theoretical Aspects of Computer
Science, 2016.
Siu-On Chan, Ilias Diakonikolas, Gregory Valiant, and Paul Valiant. Optimal algorithms for testing
closeness of discrete distributions. In SODA, pages 1193–1203, 2014.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical
risk minimization. Journal of Machine Learning Research, 12:1069–1109, 2011.
Paul Cuff and Lanqing Yu. Differential privacy as a mutual information constraint. In ACM SIGSAC
Conference on Computer and Communications Security, pages 43–54, 2016.
Tore Dalenius. Towards a methodology for statistical disclosure control. Statistisk Tidskrift, 15:
429–444, 1977.
Frank den Hollander. Probability theory: The coupling method. 2012.
Ilias Diakonikolas and Daniel M Kane. A new approach for testing properties of discrete distributions.
arXiv preprint arXiv:1601.05557, 2016.
Ilias Diakonikolas, Moritz Hardt, and Ludwig Schmidt. Differentially private learning of structured
discrete distributions. In NIPS, pages 2566–2574, 2015a.
Ilias Diakonikolas, Daniel M. Kane, and Vladimir Nikishkin. Testing identity of structured distributions. In SODA, pages 1841–1854, 2015b.
17

Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price. Sample-optimal identity testing
with high probability. arXiv preprint arXiv:1708.02728, 2017.
Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In Proceedings of the
22nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS
’03, pages 202–210, New York, NY, USA, 2003. ACM.
John C Duchi, Michael I Jordan, and Martin J Wainwright. Local privacy and statistical minimax
rates. In FOCS, pages 429–438. IEEE, 2013.
Cynthia Dwork. Differential privacy: A survey of results. In Proceedings of the 5th International
Conference on Theory and Applications of Models of Computation, TAMC ’08, pages 1–19, Berlin,
Heidelberg, 2008. Springer.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations
and Trends R in Theoretical Computer Science, 9(3–4):211–407, 2014.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity
in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptography, TCC
’06, pages 265–284, Berlin, Heidelberg, 2006. Springer.
Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In FOCS,
pages 51–60, 2010.
Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacypreserving ordinal response. In Proceedings of the 2014 ACM SIGSAC conference on computer
and communications security, pages 1054–1067. ACM, 2014.
Marco Gaboardi, Hyun Woo Lim, Ryan Rogers, and Salil P Vadhan. Differentially private chisquared hypothesis testing: goodness of fit and independence testing. In ICML, pages 2111–2120,
2016.
Oded Goldreich. The uniform distribution is complete with respect to testing identity to a fixed
distribution. In Electronic Colloquium on Computational Complexity (ECCC), volume 23, 2016.
Oded Goldreich and Dana Ron. On testing expansion in bounded-degree graphs. Electronic
Colloquium on Computational Complexity (ECCC), 7(20), 2000.
Ibrahim Issa and Aaron B. Wagner. Operational definitions for some common information leakage
metrics. In ISIT, 2017.
Peter Kairouz, Keith Bonawitz, and Daniel Ramage. Discrete distribution estimation under local
privacy. arXiv preprint arXiv:1602.07387, 2016.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential
privacy. IEEE Transactions on Information Theory, 63(6):4037–4049, 2017.
Andreas Knoblauch. Closed-form expressions for the moments of the binomial probability distribution.
SIAM Journal on Applied Mathematics, 69(1):197–204, 2008. ISSN 00361399. URL http:
//www.jstor.org/stable/40233780.
18

Erich Lehmann and Joseph Romano. Testing statistical hypotheses. Springer Science & Business
Media, 2006.
Chao Li, Gerome Miklau, Michael Hay, Andrew McGregor, and Vibhor Rastogi. The matrix
mechanism: optimizing linear counting queries under differential privacy. The VLDB Journal, 24
(6):757–781, 2015.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In FOCS, pages
94–103. IEEE, 2007.
Darakhshan J Mir. Information-theoretic foundations of differential privacy. In International
Symposium on Foundations and Practice of Security, pages 374–381, 2012.
Arvind Narayanan and Vitaly Shmatikov. Robust de-anonymization of large sparse datasets. In
Security and Privacy.IEEE Symposium on, pages 111–125, 2008.
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:289–337, 1933.
Liam Paninski. A coincidence-based test for uniformity given very sparsely sampled discrete data.
IEEE Transactions on Information Theory, 54(10):4750–4755, 2008.
Adriano Pastore and Michael Gastpar. Locally differentially-private distribution estimation. In
Information Theory (ISIT), IEEE International Symposium on, pages 2694–2698, 2016.
Ryan Rogers and Daniel Kifer. A New Class of Private Chi-Square Hypothesis Tests. In Aarti Singh
and Jerry Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence
and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 991–1000, Fort
Lauderdale, FL, USA, 20–22 Apr 2017. PMLR.
Lalitha Sankar, S Raj Rajagopalan, and H Vincent Poor. Utility-privacy tradeoffs in databases: An
information-theoretic approach. IEEE Transactions on Information Forensics and Security, 8(6):
838–852, 2013.
Latanya Sweeney. k-anonymity: A model for protecting privacy. International Journal of Uncertainty,
Fuzziness and Knowledge-Based Systems, 10(05):557–570, 2002.
Gregory Valiant and Paul Valiant. An automatic inequality prover and instance optimal identity
testing. In FOCS, pages 51–60. IEEE, 2014.
Martin J Wainwright, Michael I Jordan, and John C Duchi. Privacy aware learning. In Advances in
Neural Information Processing Systems, pages 1430–1438, 2012.
Shaowei Wang, Liusheng Huang, Pengzhan Wang, Yiwen Nie, Hongli Xu, Wei Yang, Xiang-Yang Li,
and Chunming Qiao. Mutual information optimally local private discrete distribution estimation.
CoRR, abs/1607.08025, 2016a.
Weina Wang, Lei Ying, and Junshan Zhang. On the relation between identifiability, differential
privacy, and mutual-information privacy. IEEE Transactions on Information Theory, 62(9):
5018–5029, 2016b.
19

Yue Wang, Jaewoo Lee, and Daniel Kifer. Differentially private hypothesis testing, revisited. arXiv
preprint arXiv:1511.03376, 2015.
Stanley L Warner. Randomized response: A survey technique for eliminating evasive answer bias.
Journal of the American Statistical Association, 60(309):63–69, 1965.
Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. Journal of
the American Statistical Association, 105(489):375–389, 2010.
Min Ye and Alexander Barg. Optimal schemes for discrete distribution estimation under locally
differential privacy. CoRR, abs/1702.00610, 2017.
Bin Yu. Assouad, Fano, and Le Cam. In Festschrift for Lucien Le Cam. Springer New York, 1997.

Appendix A. Upper Bound for Binary Testing
Our ε-DP algorithm simply estimates the empirical bias, and decides if it is close to b0 . Let M1 (X1m )
be the number of one’s in X1m . Then,
E [M1 (X1m )] = mb, and Var(M1 (X1m )) = mb(1 − b).

(11)

We compute the deviation of M1 (X1m ) from its expectation, and use it as our statistic:
Z(X1m ) = M1 (X1m ) − mb0 .
Algorithm 3 Binary Testing
Input: ε, α, b0 i.i.d. samples X1m from B(b)
Generate Y ∼ B(σ ε · (|Z(X1m )| − αm
2 ) )
if Y = 0
return p = B(b0 )
else
return p 6= B(b0 )

Lemma 22 Algorithm A is an ε-differentially private algorithm for testing if a binary
distribution


1
1
is B(b0 ). Moreover, it has error probability at most 0.1, with sample complexity O α2 + αε
.
Proof We first prove the correctness. Consider the case when b = b0 . By Chebychev’s inequality,
Pr

|Z(X1m )|

√ !


m
1
≥β·
≤ Pr Z(X1m )2 ≥ β 2 mb(1 − b) ≤ 2 .
2
β

For β = 10, we have Pr (|Z(X1m )| ≥ β ·

√

m/2) < 1/100. Suppose m satisfies

√
αm − β m
1
ε
> log
,
2
0.05
20

m
then with probability at least 99/100, ε αm
2 − |Z(X1 )| > log 20. Under this condition, the
algorithm outputs p =
6 B(b0 ) with probability at most 1/20. Therefore, the total probability
of


1
error is at most .01 + .05 < 0.1. Note that there is a constant C, such that for m ≥ C α12 + αε
,

αm
m
ε 2 − |Z(X1 )| ≥ log(20). The case when |b − b0 | > α follows from similar arguments.
We now prove the privacy guarantee. When one of the samples is changed, Z(X1m ) changes by
at most one, and ε · (|Z(X1m )| − αm
2 ) changes by at most ε. Invoking Lemma 8, the probability of
any output changes by at most a multiplicative exp(ε), and the algorithm is ε-differentially private.



Appendix B. Proof of Theorem 14
Proof We first briefly describe the essential components of the construction of Goldreich (2016).
Given an explicit distribution q over [k], there exists a randomized function Fq : [k] → [6k] such
that if X ∼ q, then Fq (X) ∼ u[6k], and if X ∼ p for a distribution with dT V (p, q) ≥ α, then the
distribution of Fq (X) has a total variation distance of at least α/3 from u[6k]. Given s samples
X1s from a distribution p over [k]. Apply Fq independently to each of the Xi to obtain a new
∆

sequence Y1s = Fq (X1s ) = Fq (X1 ) . . . Fq (Xs ). Let A be an algorithm that distinguishes u[6k] from
0
all distributions with total variation distance at least α/3 from it. Then consider the algorithm A
that outputs p = q if A outputs “p = u[6k]”, and outputs p 6= q otherwise. This shows that without
privacy constraints, S(IT, k, α) ≤ S(UT, 6k, α/3) (See Goldreich (2016) for details).
0
We now prove that if further A was an ε-DP algorithm, then A is also an ε-DP algorithm.
0
Suppose X1s , and X1s be two sequences in [k]s that could differ only on the last coordinate, namely
0
0
X1s = X1s−1 Xs , and X1s = X1s−1 Xs .
0
0
Consider two sequences Y1s = Y1s−1 Ys , and Y1 s = Y1s−1 Ys in [6k]s that could differ on only the
last coordinate. Since A is ε-DP,
0

A(Y1s = u[6k]) ≤ A(Y1 s = u[6k]) · eε .

(12)

Moreover, since Fq is applied independently to each coordinate,




Pr (Fq (X1s ) = Y1s ) = Pr Fq (X1s−1 ) = Y1s−1 Pr (Fq (Xs ) = Ys ).
Then,


0

Pr A (X1s ) = q



= Pr (A(Fq (X1s )) = u[6k])
=

X

Pr (A(Y1s ) = u[6k]) Pr (Fq (X1s ) = Y1s ))

Y1s

=

X X





Pr (A(Y1s ) = u[6k]) Pr Fq (X1s−1 ) = Y1s−1 Pr (Fq (Xs ) = Ys )

Y1s−1 Ys ∈[k]



=

X
Y1s−1





Pr Fq (X1s−1 ) = Y1s−1 


X

Pr (A(Y1s ) = u[6k]) Pr (Fq (Xs ) = Ys ).

Ys ∈[k]

21

(13)

Similarly,



0

0



Pr A (X1s ) = q =

X

Y1s−1







Pr Fq (X1s−1 )=Y1s−1 

0



 X
Ys0 ∈[k]





0


0

Pr A(Y1 s ) = u[6k] Pr Fq (Xs ) = Ys .


(14)
For a fixed Y1s−1 , the term within the bracket in (13), and (14) are both expectations over the final
coordinate. However, by (12) these expectations differ at most by a multiplicative eε factor. This
implies that
0





Pr A0 (X1s ) = q ≤ Pr A0 (X1s ) = q eε .


The argument is similar for the case when the testing output is not u[6k], and is omitted here. We
only considered sequences that differ on the last coordinate, and the proof remains the same when
any of the coordinates is changed. This proves the privacy guarantees of the algorithm.

Appendix C. Identity Testing – Upper Bounds
In this section, we will show that we can also use the statistic of Paninski (2008) to achieve the
optimal sample complexity in the sparse case. By Theorem 14, any upper bound on uniformity
testing is a bound on identity testing. To obtain differentially private algorithms, we need test
statistic with small sensitivity. In the sparse regime, when m = O(k), Paninski (2008) gave such a
statistic under uniformity testing.
With these arguments, we propose Algorithm 4 for testing uniformity and show it achieves the
upper bound of Theorem 13 in sparse case.
Consider
the sparse case when α > 1/k 1/4 , and α2 ε > 1/k. We will prove an upper bound of
√
√ 
O α2k + α√kε .
Recall that Mx (X1m ) is the number of appearances of x in X1m , and let
Φj (X1m ) = {x : Mx (X1m ) = j}
be the number of symbols appearing j times in X1m . Paninski (2008) used Φ1 (X1m ) as the statistic.
For X1m ∼ u[k],
E [Φ1 (X1m )]

! 

m 1
1
=k·
1−
k
1 k

m−1

1
=m· 1−
k


m−1

.

(15)

For X1m generated from a distribution p with dT V (p, u) ≥ α, (Paninski, 2008, Lemma 1) showed
that:
E [Φ1 (X1m )]

1
≤m· 1−
k


m−1

−

m2 α2
.
k

(16)

They also showed that




Var(Φ1 (X1m )) = O m2 /k ,
22

(17)

√

and used Chebychev’s inequality to obtain the sample complexity upper bound of O k/ε2 without
privacy constraints. We modify their algorithm slightly to obtain a differentially private algorithm.
Let

Z(X1m )

1
=m· 1−
k


m−1

− Φ1 (X1m ) −

m2 α 2
2k

(18)

Suppose X1m ∼ p, then
E [Z(X1m )] = −

m2 α2
, if p = u[k],
2k

and X1m ∼ p,
E [Z(X1m )] ≥

m2 α 2
, if dT V (p, u[k]) ≥ α.
2k

Algorithm 4 Uniformity testing in the sparse sample regime
Input: ε, α, i.i.d. samples X1m from p
1: Let Z be the value of the statistic in (18).
2: Generate Y ∼ B(σ(ε · Z)), σ is the sigmoid function.
3: if Y = 0 then
4:
return p = u[k]
5: else
6:
return p 6= u[k]
7: end if
We first prove the privacy bound. If we change one symbol in X1m , Φ1 (X1m ) can change by at
most 2, and therefore ε · Z changes by at most 2ε. Invoking Lemma 8, the probability of any output
changes by a multiplicative exp(2ε), and the algorithm is 2ε-differentially private.
The error probability proof is along the lines of binary testing. We first consider when p = u[k].
Using (17) let Var(Φ1 (X1m )) ≤ cm2 /k for a constant c. By the Chebychev’s inequality
Pr

Z(X1m )

m2 α 2
>−
6k

!

≤ Pr

E [Φ1 (X1m )]

≤ Pr

E [Φ1 (X1m )]

≤9c2 ·

k
m2 α4

!

−

Φ1 (X1m )

m2 α 2
>
3k

−

Φ1 (X1m )

cm mα2
>√ · √
k 3c k

!

.

(19)

√

2
Therefore, there
is a C1 such that if m ≥ C1 k/α , then under the uniform distribution
2 2

Pr Z(X1m ) > − m6kα

is at most 1/100. Now furthermore, if ε · m2 α2 /6k > log(25), then for all X1m

2 2

with Z(X1m ) < − m6kα with probability at least 0.95, the algorithm outputs the uniformdistribution.

√

√

Combining the conditions, we obtain that there is a constant C2 such that for m = C2 α2k + α√kε ,
with probability at least 0.9, the algorithm outputs uniform distribution when the input distribution
is indeed uniform. The case of non-uniform distribution is similar since the variance bounds hold
for both the cases, and is omitted.
23

Appendix D. Proof of Lemma 16
In order to prove the lemma, we need the following lemma, which is proved in Diakonikolas et al.
(2017).
Lemma 23 (Bernstein version of McDiarmid’s inequality) Let Y1m be independent random variables
taking values in the set Y. Let f : Y m → R be a function of Y1m so that for every j ∈ [m], and
y1 , ...ym , yj0 ∈ Y, we have that:
f (y1 , ...yj , ...ym ) − f (y1 , ..., yj0 , ...ym ) ≤ B,
Then we have
!

−2z 2
Pr (f − E [f ] ≥ z) ≤ exp
.
mB 2
In addition, if for each j ∈ [m] and y1 , ...yj−1 , yj+1 , ...ym we have that
VarYj [f (y1 , ...yj , ...ym )] ≤ σj2 ,
then we have

!

−z 2
.
Pr (f − E [f ] ≥ z) ≤ exp Pm 2
j=1 σj + 2Bz/3

The statistic we use Z(X1m ) has sensitivity at most 1, hence we can use B = 1 in Lemma q
23.
k
1
2
m
We first consider the case when k < m ≤ α2 . When p = u[k], we get E [Z(X1 )] = − 2 cmα · m
k,
then by the first part of Lemma 23,
E [Z(X1m )]
3

r

m
k
r 

2
m
≤ Pr Z(X1m ) − E [Z(X1m )] > cmα2 ·
3
k
!
2
2
4
8c m α
≤ exp −
.
(20)
9k
√
2
Therefore, theremis a C1 such that if m ≥ C1 k/α , then under the uniform distribution
E[Z(X1 )]
Pr Z(X1m ) >
is at most 1/100. The non-uniform distribution part is similar and we
3


Pr Z(X1m ) >

omit the case.
Then we consider the case when
also by the first part of Lemma 23,


Pr Z(X1m ) >



k
α2

1
= Pr Z(X1m ) > − cmα2 ·
6




< m. When p = u[k], we get E [Z(X1m )] = − 12 cmα, then

E [Z(X1m )]
3



1
= Pr Z(X1m ) > − cmα
6




2
≤ Pr Z(X1m ) − E [Z(X1m )] > cmα
3
!
2
2
8c mα
≤ exp −
.
9


24



2
Using the same argument we can
 constant C2 such that for m ≥ C2 /α , then
 show that theremis a
E[Z(X1 )]
under the uniform distribution Pr Z(X1m ) >
is at most 1/100. The case of non-uniform
3

distribution is omitted because of the same reason.
At last we consider the case when m ≤ k. In this case we need another result proved in Diakonikolas et al. (2017):
VarXj [Z(x1 , x2 , ..., Xj , .., xm )] ≤
When p = u[k], we get E [Z(X1m )] = − 21 ckα2 ·


Pr

Z(X1m )

E [Z(X1m )]
>
3

m
, ∀j, x1 , x2 , ..., xj−1 , xj+1 , ...xn
k
m2
,
k2

then by the second part of Lemma 23,

= Pr

Z(X1m )

1
m2
> − cα2 ·
6
k

≤ Pr

Z(X1m )

E [Z(X1m )]



−

4

− 49 c2 α4 m
k2

≤ exp

m2
k

!

2
m2
> cα2 ·
3
k

!

!
2

+ 49 cα2 mk
!

2
m2
≤ exp − cα4
.
9
k
√
Therefore,
there
is
a
C
such
that
if
m
≥
C
k/α2 , then under the uniform distribution
3
3


m
E[Z(X1 )]
Pr Z(X1m ) >
is at most 1/100. The case of non-uniform distribution is similar and is
3
omitted.
Therefore, if we take C = max{C1 , C2 , C3 }, we prove the result in the lemma.

Appendix E. Proof of Lemma 18
E.1 m ≤ k
Before proving the lemma, we consider an example that will provide insights and tools to analyze
the distributions Q1 , and Q2 . Let t ∈ N. Let P2 be the following distribution over {0, 1}t :
• Select b ∈ { 12 − α, 21 + α} with equal probability.
• Output t independent samples from B(b).
Let P1 be the distribution over {0, 1}t that outputs t independent samples from B(0.5).
When t = 1, P1 and P2 both become B(0.5). For t=2, P1 (00) = P1 (11) = 14 + α2 , and
P1 (10) = P1 (01) = 14 − α2 , and dT V (P1 , P2 ) is 2α2 . A slightly general result is the following:
Lemma 24 For t = 1, dT V (P1 , P2 ) = 0 and for t ≥ 2, dT V (P1 , P2 ) ≤ 2tα2 .
Proof Consider any sequence X1t that has t0 zeros, and t1 = t − t0 ones. Then,
!

P1 (X1t )

=

25

t 1
,
t0 2t

and
!

P2 (X1t ) =

!

t 1 (1 − 2α)t0 (1 + 2α)t1 + (1 + 2α)t0 (1 − 2α)t1
.
t0 2t
2

The term in the parantheses above is minimized when t0 = t1 = t/2. In this case,
P2 (X1t ) ≥P1 (X1t ) · (1 + 2α)t/2 (1 − 2α)t/2 = P1 (X1t ) · (1 − 4α2 )t/2 .
Therefore,
dT V (P1 , P2 ) =

X

X

P1 (X1t ) − P2 (X1t ) ≤

P1 >P2





P1 (X1t ) 1 − (1 − 4α2 )t/2 ≤ 2tα2 ,

P1 >P2

where we used the Weierstrass Product Inequality, which states that 1 − tx ≤ (1 − x)t proving the
total variation distance bound.
As a corollary this implies:
Lemma 25 There is a coupling between X1t generated from P1 and Y1t from P2 such that E d(X1t , Y1t ) ≤
t · dT V (P1 , P2 ) ≤ 4(t2 − t)α2 .




Proof Observe that X1t min{P1 (X1t ), P2 (X1t )} = 1 − dT V (P1 , P2 ). Consider the following coupling
between P1 , and P2 . Suppose X1t is generated by P1 , and let R be a U [0, 1] random variable.
min{P (X t ),P2 (X1t )}
1. R < 1−dT V (P1 , P2 ) Generate X1t from the distribution that assigns probability 1−d1T V 1(P1 ,P
2)
to X1t . Output (X1t , X1t ).
P (X t )−min{P (X t ),P (X t )}
2. R ≥ 1−dT V (P1 , P2 ) Generate X1t from the distribution that assigns probability 1 1 dT V (P11 ,P21) 2 1
P

to X1t , and Y1t from the distribution that assigns probability
independently. Then output (X1t , Y1t ).
To prove the coupling, note that the probability of observing X1t is
(1 − dT V (P1 , P2 )) ·

P2 (Y1t )−min{P1 (Y1t ),P2 (Y1t )}
dT V (P1 ,P2 )

to Y1t

min{P1 (X1t ), P2 (X1t )}
P1 (X1t ) − min{P1 (X1t ), P2 (X1t )}
+ dT V (P1 , P2 ) ·
= P1 (X1t ).
1 − dT V (P1 , P2 )
dT V (P1 , P2 )

A similar argument gives the probability of Y1t to be P2 (Y1t ).
Then E d(X1t , Y1t ) ≤ t · dT V (P1 , P2 ) = 2t2 α2 ≤ 4(t2 − t)α2 when t ≥ 2, and when t = 1, the
distributions are identical and the Hamming distance of the coupling is equal to zero.
We now have the tools to prove Lemma 18 for m ≤ k.
Proof [Proof of Lemma 18 for m ≤ k.] The following is a coupling between Q1 and Q2 :
1. Generate m samples Z1m from a uniform distribution over [k/2].
2. For j ∈ [k/2], let Tj ⊆ [m] be the set of locations where j appears. Note that |Tj | = Mj (Z1m ).
3. To generate samples from Q1 :
• Generate |Tj | samples from a uniform distribution over {2j − 1, 2j}, and replace the
symbols in Tj with these symbols.
4. To generate samples from Q2 :
26

• Similar to the construction of P1 earlier in this section, consider two distributions over
{2j − 1, 2j} with bias 12 − α, and 21 + α.
• Pick one of these distributions at random.
• Generate |Tj | samples from it over {2j − 1, 2j}, and replace the symbols in Tj with these
symbols.
From this process the coupling between Q1 , and Q2 is also clear:
• Given X1m from Q2 , for each j ∈ [k/2] find all locations ` such that X` = 2j − 1, or X` = 2j.
Call this set Tj .
• Perform the coupling between P2 and P1 from Lemma 25, after replacing {0, 1} with {2j−1, 2j}.
Using the coupling defined above, by the linearity of expectations, we get:
E [d(X1m , Y1m )]

=

k/2
X

h

|T |

|Tj |

E d(X1 j , Y1

i

) =

j=1

i
h
i
k h
k
E d(X1R , Y1R ) ≤ · E 4α2 (R2 − R) ,
2
2

where R is a binomial random variable with parameters m and 2/k.
Now, a simple exercise

computing Binomial moments shows that for X ∼ Bin(n, s), E X 2 − X = s2 (n2 − n) ≤ n2 s2 . This
implies that
h
i
4m2
E R2 − R ≤ 2 .
k
Plugging this, we obtain
E [d(X1m , Y1m )] ≤

k 16α2 m2
8m2 α2
·
=
,
2
k2
k

proving the claim.

E.2 k ≤ m ≤ k/α2
Lemma 24 holds for all values of t, and α. The lemma can be strengthened for cases where α is
small.
Lemma 26 Let P1 , and P2 be the distributions over {0, 1}t defined in the last section. There is a
coupling between X1t generated by P1 , and Y1t by P2 such that
h

i

E d(X1t , Y1t ) ≤ C · (α2 t3/2 + α4 t5/2 + α5 t3 ).
E.2.1 Proof of Lemma 18 assuming Lemma 26
Given the coupling we defined in Section E.2.2 for proving Lemma 26, the coupling between Q1 ,
and Q2 uses the same technique in the last section for m ≤ k.
• Given X1m from Q2 , for each j ∈ [k/2] find all locations ` such that X` = 2j − 1, or X` = 2j.
Call this set Tj .
• Perform the coupling in Section E.2.2 between P2 and P1 on Tj , after replacing {0, 1} with
{2j − 1, 2j}.
27

Using the coupling defined above, by the linearity of expectations, we get:
E [d(X1m , Y1m )]

k/2
X

=

|T |

h

|Tj |

E d(X1 j , Y1

i

)

j=1

i
k h
E d(X1R , Y1R )
2
i
h

k
≤ · E 64 · α4 R5/2 + α2 R3/2 + α5 R3 ,
2

=

where R ∼ Bin(m, 2/k).
We now bound the moments of Binomial random variables. The bound is similar in flavor
to (Acharya et al., 2017, Lemma 3) for Poisson random variables.
Lemma 27 Suppose

m
k

> 1, and Y ∼ Bin(m, k1 ), then for γ ≥ 1, there is a constant Cγ such that
E [Y γ ] ≤ Cγ



m
k

γ

.

Proof For integer values of γ, this directly follows from the moment fomula for Binomial distribution Knoblauch (2008), and for other γ ≥ 1, by Jensen’s Inequality
γ

E [Y ] ≤ E



Y

dγe



γ
dγe



≤E

h

Y dγe

i

γ
dγe



≤ Cdγe E [Y ]dγe



γ
dγe

= C 0 (E [Y ])γ ,

proving the lemma.
Therefore, letting C = max{C5/2 , C3 , C3/2 }, we obtain
E [d(X1m , Y1m )]
Now, notice α

q

m
k

≤ 32kC · α

4



m
k

5/2

+α

2



m
k

3/2

+α

5



m
k

3 !

< 1. Plugging this,

E [d(X1m , Y1m )]

≤ 32C · k · α

4



m
k



5/2

m
= 32C · kα2 · α2 ·
k
m
≤ 96C · k
k


+α


m
k

2



m
k

3/2

3/2

+α


+

m
k

3/2

5



m
k

3 !

+ α3



m
k

3/2 

m
k

3/2




3/2

,

completing the argument.
E.2.2 Proof of Lemma 26
To prove Lemma 26, we need a few lemmas first:
Definition 28 A random variable Y1 is said to stochastically dominate Y2 if for all t, Pr (Y1 ≥ t) ≥
Pr (Y2 ≥ t).
28

1
1−α
Lemma 29 Suppose N1 ∼ Bin(t, 12 ), N2 ∼ 21 Bin(t, 1+α
2 )+ 2 Bin(t, 2 ). Then Z2 = max{N2 , t−N2 }
stochastically dominates Z1 = max{N1 , t − N1 }.

Proof
Pr (Z2 ≥ l) =

t−l
X
t

! "

i

i=0

1+α
2

i 

1−α
2

Pr (Z1 ≥ l) = 2 ·

t−i



+

1−α
2

i 

1+α
2

t−i #

! 
t−l
X
t
1 t

i

i=0

2

Define F (l) = Pr(Z2 ≥ l) − Pr (Z 1 ≥ l). What we need to show is F (l) ≥ 0, ∀l ≥ 2t . First we observe
1−α t
1 t
t
that Pr Z2 ≥ 2t = Pr Z1 ≥ 2t = 1 and Pr (Z2 ≥ t) = ( 1+α
2 ) + ( 2 ) ≥ 2( 2 ) = Pr (Z1 ≥ t).
t
Hence F ( 2 ) = 0, F (t) > 0. Let
! "

t
f (l) = F (l + 1) − F (l) = −
l
Let g(x) =



1+α
2

x 

1−α
2

t−x

+

1+α
dg(x)
= ln
dx
1−α




1−α
2

 "

·

1+α
2

x 

1+α
2

1+α
2

l 

t−x

x 

1−α
2
−2

1−α
2

t−l

 t
1
2



+

1−α
2

l 

1+α
2

 t #

t−l

−2

1
2

.

, x ∈ [t/2, t], then

t−x



−

1−α
2

x 

1+α
2

t−x #

≥0

We know
g(t/2) < 0, g(t) > 0, hence ∃x∗ , s.t.g(x) ≤ 0, ∀x < x∗ and g(x) ≥ 0, ∀x > x∗ . Because
t
f (l) = − l g(l), hence ∃l∗ , s.t.f (l) ≤ 0, ∀l ≥ l∗ and f (l) ≥ 0, ∀l < l∗ . Therefore, F (l) first increases
and then decreases, which means F (l) achieves its minimum at 2t or t. Hence F (l) ≥ 0, completing
the proof.
For stochastic dominance, the following definition den Hollander (2012) will be useful.
Definition 30 A coupling (X 0 , Y 0 ) is a monotone coupling if Pr (X 0 ≥ Y 0 ) = 1.
The following lemma states a nice relationship between stochastic dominance and monotone
coupling, which is provided as Theorem 7.9 in den Hollander (2012)
Lemma 31 Random variable X stochastically dominates Y if and only if there is a monotone
coupling between (X 0 , Y 0 ) with Pr (X 0 ≥ Y 0 ) = 1.
By Lemma 31, there is a monotone coupling between Z1 = max{N1 , t−N1 } and Z2 = max{N2 , t−
N2 }. Suppose the coupling is PZc 1 ,Z2 , we define the coupling between X1t and Y1t as following:
1. Generate X1t according to P2 and count the number of one’s in X1t as n1 .
2. Generate n2 according to P c [Z2 |Z1 = max{n1 , t − n1 }].
3. If n1 > t − n1 , choose n2 − n1 of the zero’s in X1t uniformly at random and change them to
one’s to get Y1t
4. If n1 < t − n1 , choose n2 − (t − n1 ) of the one’s in X1t uniformly at random and change them
to zero’s to get Y1t
5. If n1 = t − n1 , break ties uniformly at random and do the corresponding action.
6. Output (X1t , Y1t )
29

Since the coupling is monotone, and dT V (X1t , Y1t ) = Z2 − Z1 for every pair of (X1t , Y1t ), we get:
h

i

E dT V (X1t , Y1t ) = E [max{N2 , t − N2 }] − E [max{N1 , t − N1 }] .
Hence, to show lemma 26, it suffices to show the following lemma:
1
1−α
Lemma 32 Suppose N1 ∼ Bin(t, 21 ), N2 ∼ 12 Bin(t, 1+α
2 ) + 2 Bin(t, 2 ).

E [max{N2 , t − N2 }] − E [max{N1 , t − N1 }] < C · (α2 t3/2 + α4 t5/2 + α5 t3 ).
Proof
E [max{N2 , t − N2 }]
=

X

(t/2 + `)

t
2

0≤`≤t/2

X
t
= +
`
2 0≤`≤t/2

t
2

t
−`

t
−`

! 

! 

1−α
2

1−α
2

 t −` 
2

 t −` 
2

1+α
2

1+α
2

 t +`
2

+

 t +`
2





+

1+α
2

1+α
2

 t −` 
2

 t −` 
2

1−α
2

1−α
2

 t +` !
2

 t +` !
2

.

Consider a fixed value of t. Let
X

f (α) =

`

t
2

0≤`≤t/2

t
−`

! 

1−α
2

 t −` 
2

1+α
2

 t +`
2



+

1+α
2

 t −` 
2

1−α
2

 t +` !
2

.

The first claim is that this expression is minimized at α = 0. This is because of the monotone
coupling between Z1 and Z2 , which makes E [Z2 ] ≥ E [Z1 ]. This implies that f 0 (0) = 0, and by
intermediate value theorem, there is β ∈ [0, α], such that
1
f (α) = f (0) + α2 · f 00 (β).
2

(21)

We will now bound this second derivative. To further simplify, let


g(α) =

1−α
2

 t −` 
2

1+α
2

 t +`
2



+

1+α
2

 t −` 
2

1−α
2

 t +`
2

.

Differentiating g(α), twice with respect to α, we obtain,
 1 − α  2t −`−2  1 + α  2t +`−2
1  2 2
· α (t − t) − 4α`(t − 1) + 4`2 − t
16
2
2

g 00 (α) =

+

 1 + α  2t −`−2  1 − α  2t +`−2
1  2 2
· α (t − t) + 4α`(t − 1) + 4`2 − t
.
16
2
2

For any ` ≥ 0,


1+α
2

 t −`−2 
2

1−α
2

 t +`−2
2



≤
30

1−α
2

 t −`−2 
2

1+α
2

 t +`−2
2

.

Therefore g 00 (α) can be bound by,
!
  1 − α  2t −`−2  1 + α  2t +`−2  1 − α  2t −`−2  1 + α  2t +`−2
1  2 2
2
· α t + 4`
g (α) ≤
+
.
16
2
2
2
2
00

When α < 41 , (1 − α2 )2 > 12 , and we can further bound the above expression by


00

2 2

g (α) ≤ 2 · α t + 4`

2

  1 − α  2t −`  1 + α  2t +`

2

2



+

1−α
2

 t −` 
2

1+α
2

 t +` !
2

.

Suppose X is a Bin(t, 1+β
2 ) distribution. Then, for any ` > 0,


Pr

t
X−
=` =
2

t
−`



t
2

! 

1−β
2

 t −` 
2

1+β
2

 t +`
2



+

1+β
2

 t −` 
2

1−β
2

 t +` !
2

.

Therefore, we can bound (21), by
t
f (β) ≤ 2 · β t E X −
2
00

2 2

"





t
X−
2

+ 4E

3

#!

.

For X ∼ Bin(m, r),
h

i

h

i

m
, and
4

E (X − mr)2 =mr(1 − r) ≤

E (X − mr)4 =mr(1 − r)(3r(1 − r)(m − 2) + 1) ≤ 3

m2
.
4

We bound each term using these moments,
t
E X−
2


"



≤E

t
X−
2

2 #1/2

(1 − β 2 )
= t
+
4



tβ
2

2 !1/2

≤

√
t + tβ.

We similarly bound the next term,
"

E

t
X−
2

3

#

"

≤E

t
X−
2

4 #3/4

"

t(1 + β) tβ
X−
+
2
2

≤E

4 #3/4

 "


4 #3/4  3
t(1
+
β)
tβ

≤8E X −
+

2

≤8 t3/2 +



tβ
2

2

3 !

,

where we use (a + b)4 ≤ 8(a4 + b4 ). Therefore,






f 00 (β) ≤ 64 · β 2 t5/2 + t3/2 + (tβ)3 ≤ 64 · α2 t5/2 + t3/2 + (tα)3



As a consequence,
E [max{N2 , t − N2 }] − E [max{N1 , t − N1 }] = α2 f 00 (β) ≤ 64 · (α2 t3/2 + α4 t5/2 + α5 t3 ).
completing the proof.

31

