Comparing Population Means under Local Differential Privacy:
with Significance and Power
Bolin Ding, Harsha Nori, Paul Li, Joshua Allen

arXiv:1803.09027v1 [cs.CR] 24 Mar 2018

{bolind, hanori, paul.li, joshuaa}@microsoft.com
Microsoft, One Microsoft Way, Redmond, WA 98052

Abstract
A statistical hypothesis test determines whether a hypothesis should be rejected based on samples from populations. In
particular, randomized controlled experiments (or A/B testing) that compare population means using, e.g., t-tests, have
been widely deployed in technology companies to aid in making data-driven decisions. Samples used in these tests are
collected from users and may contain sensitive information.
Both the data collection and the testing process may compromise individuals’ privacy. In this paper, we study how to conduct hypothesis tests to compare population means while preserving privacy. We use the notation of local differential privacy (LDP), which has recently emerged as the main tool to
ensure each individual’s privacy without the need of a trusted
data collector. We propose LDP tests that inject noise into every user’s data in the samples before collecting them (so users
do not need to trust the data collector), and draw conclusions
with bounded type-I (significance level) and type-II errors
(1− power). Our approaches can be extended to the scenario
where some users require LDP while some are willing to provide exact data. We report experimental results on real-world
datasets to verify the effectiveness of our approaches.

Introduction
Randomized controlled experiments (or A/B testing) and hypothesis tests are used by many companies, e.g., Google,
Facebook, Amazon, and Microsoft, to design and improve
their products and services (Tang et al. 2010; Panger 2016;
Kohavi and Round 2004; Kohavi et al. 2012). These statistical techniques base business decisions on samples of actual
customer data collected during experiments to draw more
informed conclusions. However, such data samples usually
contain sensitive information, e.g., usage statistics of certain
apps or services; in order to meet users’ privacy expectations
and tightening privacy regulations (e.g., European GDPR
law), ensuring that these experiments and tests do not breach
the privacy of individuals is an important problem.
Differential privacy (DP) (Dwork et al. 2006) has emerged
as a standard for the privacy guarantees, and been used by,
e.g., Apple (Apple 2017), Google (Erlingsson, Pihur, and
Korolova 2014), and Uber (Greenberg 2017). In a wellstudied DP model used by, e.g., (Gaboardi et al. 2016), users
Copyright c 2018, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved.

trust and send exact data to a data collector, who then injects noise in the testing process to ensure DP. However,
this model is not applicable in our setup, as users may not
trust the data collector (e.g., a tech company) due to potential hacks and leaks (Hackett 2015), and prefer not to have
unprivatized data leave their devices. Therefore, we adopt
the local model of differential privacy (LDP) (Duchi, Jordan, and Wainwright 2013). Under LDP, users do not need to
trust the data collector. Before sent to the data collector, each
user’s data is privatized by a randomized algorithm with the
property that the likelihood of any specific output of the algorithm varies little with the input, i.e., the exact data.
In this paper, we study how to conduct hypothesis tests
to compare population means (e.g., in A/B testing), while
ensuring LDP for each user. We focus on the class of t-tests
when presenting our solutions – they can be easily extended
for Z-tests if populations follow Normal distributions.
An A/B test splits users randomly into two populations,
to give them two different experiences, a control and a treatment, respectively, and then tests for differences between the
two population means in a measure of interest (clicks, usage,
monetization, etc.). A null hypothesis H0 is that the two population means are equal or differ by a fixed constant. Statistical tests (e.g., t-tests) are used to determine whether the
null hypothesis should be rejected based on random samples
from the populations. To measure errors in the conclusions,
type-I error is the probability of falsely rejecting H0 when it
is true, and type-II error, or complement of statistical power,
is the probability of failing to reject H0 when it is false. We
want a test to have type-I error bounded by a pre-specified
threshold, called significance level, and have high power.
A typical test has three common steps: 1) compute the
observed value of a test statistic from samples; 2) calculate
the p-value, i.e., the probability, under H0 , of a test statistic
being more extreme than the observed one; 3) reject H0 if
and only if the p-value is less than the significance level.
Challenges and our contributions. In t-tests (as well as Ztests when population variances are unknown) that compare
population means, sample means and sample variances are
the essential terms in the test statistic to be computed in step
1). While there are several approaches, e.g., (Duchi, Jordan,
and Wainwright 2013), to estimate means, there is no known
technique to estimate sample variances under LDP. In fact,
we show that any estimator to variances based on a previous

LDP mechanism (Ding, Kulkarni, and Yekhanin 2017) has a
very large worst-case error (Proposition 3).
Our first approach, called estimation-based LDP test, is
based on a seemingly direct idea. We propose a new LDP
mechanism to estimate sample variances, using which we
obtain an estimation of the observed test statistic in step 1)
to calculate the p-value and then draw the conclusion.
One of the most important goals of hypothesis testing is to
control the probability of drawing a false conclusion in terms
of type-I and type-II errors. While our new LDP variance estimator is of independent interest, the first approach is unsatisfying in achieving this goal, especially when the size of the
data domain is large. As errors in both the estimator to sample means and the one to variances are proportional to the
domain size, it is hard to bound the error in estimating the
test statistic in step 1), so there is no theoretical guarantee
on type-I and type-II errors in our first approach.
The second approach we propose, called transformationbased LDP test, aims to provide an upper bound of type-II
error at a pre-specified significance level, i.e., a hard constraint of type-I error. The main idea is to look into the
relationship between the original distribution of a population and the distribution on the outputs of the LDP datacollection algorithm on users’ data, called transformed distribution. Instead of estimating sample means and sample
variances under LDP, we directly conduct tests based on
LDP samples from the transformed distributions – the conclusion can then be translated into a conclusion of the test on
the original population (i.e., rejecting or accepting H0 ). The
upper bound on type-II error during A/B testing is critical in
estimating the number of users needed in the samples to detect significant differences between the control and the treatment populations. We derive such an estimation of sample
sizes needed to reduce type-II error below a threshold at the
specified significance level. This approach can be extended
to a hybrid-privacy scenario where some users require LDP
while some are willing to provide exact data.
Experiments are conducted on real datasets to verify our
theoretical results and the effectiveness of our approaches.
Related work. There are a long line of works on hypothesis testing under the DP model with a trusted data collector,
with genome-wide association studies as a primary application. In this setup, the data collector receives exact samples from users. The first type of approaches inject noise
into aggregates (or marginal tables) of data to ensure DP,
and compute or estimate the test statistic in step 1) from
these noisy aggregates (Fienberg, Rinaldo, and Yang 2010;
Karwa and Slavković 2012; Johnson and Shmatikov 2013;
Karwa and Slavković 2016). The intuition is that the impact
of the DP noise is small when the sample size is large enough
(Vu and Slavkovic 2009). However, it is shown that certain tests, e.g., χ2 -tests, perform poorly when used with the
estimated statistic (Gaboardi et al. 2016), leading to much
higher type-I error than the specified amount. The second
type of approaches (Uhlerop, Slavković, and Fienberg 2013;
Yu et al. 2014; Wang, Lee, and Kifer 2015; Gaboardi et al.
2016) try to derive the asymptotic distribution of the estimated test statistic. Since this asymptotic distribution cannot
be written analytically, Monte Carlo simulations or numeri-

cal approximations are used to calculate the p-value in step
2). More recently, for χ2 -tests, unit circle mechanism (Kakizaki, Fukuchi, and Sakuma 2017) utilizes the geometrical
property of the test statistics and achieves a sharp reduction
on the type-II errors; and independently, new test statistics
(Rogers and Kifer 2017) are proposed, so that their asymptotic distributions with DP noise injected are close to the
asymptotics of the classical (non-private) tests.
To our best knowledge, our work is the first on statistical
hypothesis tests to compare population means under LDP.
One of our primary applications is A/B testing in software
companies, so LDP is a proper privacy guarantee for each
user without the need of trusting the data collector. LDP χ2 testing is studied in (Rogers 2017), to test goodness of fit and
independence for multinomial distributions. LDP hypothesis tests to distinguish between two specific distributions are
studied in (Kairouz, Oh, and Viswanath 2014).
Another relevant line of works are about parameter estimations under LDP, including, e.g., mean/density estimations (Duchi, Jordan, and Wainwright 2013; Duchi, Wainwright, and Jordan 2016; Ding, Kulkarni, and Yekhanin
2017), and histogram estimations (Duchi, Wainwright, and
Jordan 2013; Kairouz, Bonawitz, and Ramage 2016; Wang
et al. 2016; Wang, Wu, and Hu 2016). Communication and
computation-efficient mechanisms are developed for histogram estimations over large domains to find heavy hitters (Bassily and Smith 2015; Wang et al. 2017; Bassily et
al. 2017). Industrial deployments of LDP techniques on this
line enhance privacy using memorization (Erlingsson, Pihur,
and Korolova 2014; Fanti, Pihur, and Erlingsson 2016). How
to find heavy hitters is also studied in a hybrid-privacy model
with both LDP and DP users (Avent et al. 2017).

Preliminaries
Each user has a private real-valued counter x ∈ Σ =
[0, m] (to measure, e.g., app usage). Our approaches can
be easily extended for general domains like [−m, m], but
we focus on [0, m] for the simplicity of presentation. Let
[n] = {1, 2, . . . , n} and X = {xi }i∈[n] bePa (sample)
set of counters
from n users. We use µX =
i xi /n and
P
s2X = i (xi − µX )2 /(n − 1) to denote the sample mean
and sample variance of X, respectively. We use X (or A,
B) to denote both a population and the distribution of this
population, from which a sample X (or A, B) is drawn.
Hypothesis testing to compare population means. Let A
and B be the distributions of counters in the control and the
treatment populations, respectively. Let µA and µB be the
population means (expectations). The null hypothesis H0 is
µA − µB = d0 , and the alternative hypothesis H1 is, e.g.,
µA −µB 6= d0 . We randomly pick nA and nB users from the
populations A and B, respectively, and let A = {ai }i∈[nA ]
and B = {bi }i∈[nB ] be the corresponding samples.
A test is an algorithm T that takes the two samples A
and B and decides whether to reject or accept H0 at a prespecified significance level α. We require T to have type-I error at most α, i.e., Pr[T(A, B; α, H0 ) = reject | H0 ] ≤ α,
and type-II error Pr[T(A, B; α, H0 ) = accept | H1 ] = β as
small as possible. 1 − β is called the statistical power of T.

The probability is taken over the randomness from the data
generation (of A and B) and the possible randomness in T.
A key step in a test is to compute the observed value of
a test statistic from samples. To compare population means,
it is usually a function of six parameters: sample means µA
and µB , sample variances s2A and s2B , and sample sizes nA
and nB . In t-tests, we also need to obtain the degrees of freedom. For example, in Welch’s t-test, they are, respectively
(µA − µB ) − d0
(s2 /nA + s2B /nB )2
t= p 2
and df = (s2A/n )2
.
(s2B /nB )2
2
A
A
sA /nA + sB /nB
+
nA −1
nB −1
(1)
Local model of differential privacy (LDP). In the local
model of differential privacy (LDP) (Duchi, Wainwright, and
Jordan 2013; Bassily and Smith 2015), also called randomized response model (Warner 1965), γ-amplification (Evfimievski, Gehrke, and Srikant 2003), or FRAPP (Agrawal
and Haritsa 2005), private data from each user is randomized
by an algorithm A before being sent to data collector.
Definition 1 (Local model of differential privacy) A randomized algorithm A : Σ → Z is -locally differentially
private (-LDP) if for any pair of values x, y ∈ Σ and any
subset of output S ⊆ Z, we have that
Pr[A(x) ∈ S] ≤ e · Pr[A(y) ∈ S] .
One interpretation of LDP is that no matter what output
is released from A, it is approximately equally as likely to
have come from one value x ∈ Σ as any other. Unlike the
DP model used in (Gaboardi et al. 2016; Rogers and Kifer
2017), users do not need to trust the data collector in LDP.
Problem statement: LDP mean-comparison test. Each
user in the control and the treatment has a counter. Two random samples of counters A and B are drawn from the control and the treatment distributions A and B, respectively.
With the null hypothesis H0 : µA − µB = d0 , we want to design a test, such that: i) each counter in A and B is collected
from the user in an ε-LDP way, ii) its type-I error ≤ significance level α, and iii) type-II error is as small as possible.
Building block: 1-bit LDP data collection. We will utilize
the following ε-LDP mechanism Mε,m from (Ding, Kulkarni, and Yekhanin 2017) to privatize each counter in samples
A and B. For each user with a counter x, it generates a noisy
bit (0 or 1), independently, and sends to the data collector


x
1, with probability e1+1 + m
· ee −1
+1 ;
Mε,m (x) =
(2)
0, otherwise.
Proposition 1 The mechanism Mε,m is ε-LDP.
This mechanism can be interpreted as firstly rounding x
to a bit 1 with probability x/m or 0 otherwise, and flipping the bit with probability e1+1 . It is communicationefficient (only one bit is sent) and can be seen as a simplification of the multidimensional mean-estimation mechanism
in (Duchi, Jordan, and Wainwright 2013).
Mε,m can be used for mean estimation. Suppose there are
0
n users: X = {xi }i∈[n] . We collect
P xi = Mε,m (xi ) from
each user i. The mean µX =
i xi /n can be estimated

from the noisy bits X 0 = Mε,m (X) = {x0i }i∈[n] as:
n

µ̂ε,m (X 0 ) =

m X x0i · (eε + 1) − 1
.
n i=1
eε − 1

(3)

It is shown in (Ding, Kulkarni, and Yekhanin 2017) that:
Proposition 2 The estimator µ̂ε,m (X 0 ) is unbiased:

i) E[µ̂ε,m (X 0 )] = µX , and ii) Var[µ̂ε,m (X 0 )] = O

m2
nε2

.

Estimation-based LDP Test
Given two samples A = {ai }i∈[nA ] and B = {bi }i∈[nB ] ,
one straightforward starting point is to use Mε,m to collect
each counter, to preserve ε-LDP for each user, and estimate
parameters (sample means µA and µB and sample variances
s2A and s2B ) in, e.g., (1), based on Mε,m (A) = {Mε,m (ai )}
and Mε,m (B) = {Mε,m (bi )} to conduct a t-test.
We can obtain estimators to µA and µB using µ̂ε,m (3).
However, it is difficult to estimate the sample variances from
the LDP data collection Mε,m (A) and Mε,m (B). The intuition is as follows. Consider two distributions: a counter
from distribution X is always a constant m/2; a counter
from Y is 0 with probability 1/2, and m otherwise. After
applying Mε,m on two samples X and Y from X and Y,
respectively, the LDP samples Mε,m (X) and Mε,m (Y ) follow the same distribution (cannot be distinguished from each
other), but the gap between s2X and s2Y is Ω m2 with high
probability. In general, we have a hardness result:
Proposition 3 If each counter in X = {xi } is collected using Mε,m , any estimator ŝ2 to s2X based on Mε,m (X) =

{Mε,m (xi )} has worst-case error |ŝ2 −s2X | at least Ω m2 .
Proof: In the appendix.
LDP Data Collection for Variance Estimation. The above
proposition essentially says that estimating the sample variance of a sample X based on Mε,m (X) leads to unbounded

error, as a sample variance itself is bounded by O m2 . In
order to obtain a reasonable estimation for sample variances,
we need to collect two LDP bits from each user.
Indeed, the sample variance s2X can be rewritten as

1 X
n
2
s2X =
(xi − µX ) =
µX 2 − µ2X , (4)
n−1 i
n−1
P
where X 2 is defined to be {x2i }i∈[n] and µX 2 = n1 i x2i .
The sequential composability (McSherry 2009) of DP
also holds for LDP (considering a dataset with one user). We
split the privacy budget into ε = ε1 + ε2 . For each user with
a counter xi , the first bit to be collected is x0i = Mε1 ,m (xi ),
which can be also used to estimate mean µX . The second bit
is x00i = Mε2 ,m2 (x2i ), which will be used to estimate µX 2
(the range of x2i is [0, m2 ]). Note that the two bits are collected with independent randomnesses. From the sequential
composability, we preserve (ε1 + ε2 )-LDP for each user.
After collecting X 0 = {x0i }i∈[n] and X 00 = {x00i }i∈[n]
from users in X, the sample variance can be estimated as

n µ̂ε2 ,m2 (X 00 ) − µ̂2ε1 ,m (X 0 )
2
0
00
ŝε1 ,ε2 ,m (X , X ) =
, (5)
n−1

where µ̂ε1 ,m and µ̂ε2 ,m2 are defined as in (3). We have the
following result about the accuracy of ŝ2ε1 ,ε2 ,m .
Proposition 4 s2ε1 ,ε2 ,m (X 0 , X 00 ) is an estimator to s2X :
 2


m
i) s2X − O nε
≤ E ŝ2ε1 ,ε2 ,m (X 0 , X 00 ) ≤ s2X , and
2
1
 4



m4
ii) Var ŝ2ε1 ,ε2 ,m (X 0 , X 00 ) = O nm2 ε4 + nε
.
2
1

2

Proof: In the appendix.
Using Mean/Variance Estimation in Tests. The test Test
ε1 ,ε2
uses the above mechanism to collect data and estimate µA ,
µB , s2A , and s2B under LDP (consider X = A, B), and put
the estimates back into (1) to calculate t and df in order to
conduct t-tests. Refer to the appendix for detailed description. There is no theoretical guarantee on the testing errors,
but from the above discussion, we have:
Theorem 1 Test
ε1 ,ε2 satisfies (ε1 + ε2 )-LDP.

Transformation-based LDP Test
In this section, we give a LDP testing algorithm with guaranteed significance and power. The main idea is that, if a
counter x follows some (unknown) population distribution
with a (unknown) mean µ, the LDP bit Mε,m (x) follows a
Bernoulli distribution with the mean determined by µ and ε.
So in order to compare population means, we can conduct
tests directly on the LDP bits and compare Bernoulli means.
The following proposition firstly gives the relationship between the original population distribution and the resulting
Bernoulli distribution on the outputs of Mε,m .
Proposition 5 If a counter x ∈ [0, m] follows a distribution
X with mean µX , the LDP bit xbin = Mε,m (x) (as in (2))
follows a Bernoulli distribution with the mean

 µX eε − 1
1
pX = Pr xbin = 1 =
·
+
. (6)
m eε + 1 eε + 1
Proof: Let f be the PDF of X. We have
Z m
 bin



Pr x = 1 =
Pr xbin = 1 | x f (x)dx
0

Z m
x e − 1
1
+
·
f (x)dx
=
e + 1 m e + 1
0
Z m
Z
1
1 e − 1 m
f (x)dx +
xf (x)dx
· 
= ε
e +1 0
m e +1 0
1 e − 1
1
·1+
·
· E[x]
= ε
e +1
m e + 1
µX eε − 1
1
=
·
+
.
m eε + 1 eε + 1
Therefore, xbin follows a Bernoulli distribution.
The test process Tbin
ε is described in Algorithm 1. Two
samples, A = {ai }i∈[nA ] and B = {bi }i∈[nB ] , are drawn
from two distributions A and B with means µA and µB .
After applying the mechanism Mε,m , the LDP bits Abin =
Mε,m (A) = {Mε,m (ai )}i∈[nA ] and B bin = Mε,m (B) collected (lines 1-5) are two samples from Bernoulli distributions with means pA and pB . With µA − µB = d0 , from (6),
ε
ε
we have pA − pB = dbin
0 = (d0 /m) · ((e − 1)/(e + 1)). An

Input: Two samples A = {ai }i∈[nA ] and B = {bi }i∈[nB ] .
Null hypothesis H0 : µA − µB = d0 .
Parameters: privacy budget ε and significance level α.
1: For users i = 1 to nA do
bin
2:
Encode abin
i = Mε,m (ai ) and send ai to the server.
3: For users i = 1 to nB do
bin
4:
Encode bbin
i = Mε,m (bi ) and send bi to the server.
bin
bin
bin
5: Server receives A = {ai } and B = {bbin
i }.
6: Let the transformed null hypothesis be
H0bin : pA − pB =

d0 eε − 1
·
,
m eε + 1

where pA (pB ) is the distribution mean of Abin (B bin ).
7: Conduct a t-test with null hypothesis H0bin on Abin and
B bin at significance level α: accept (or reject) H0 if and
only if H0bin is accepted (or rejected).
Algorithm 1: Tbin
ε : Transformation-based LDP Test
important observation here is that the relative order between
µA and µB is the same as the one between pA and pB , i.e.,
µA − µB ≥ d0 ⇔ pA − pB ≥ dbin
0 . Therefore, we can conduct a test on Abin and B bin to compare pA and pB with a
null hypothesis H0bin : pA − pB = dbin
0 (line 6), in order to
compare µA and µB and reject or accept H0 (line 7).
Indeed, Tbin
ε preserves ε-LDP for each user from Proposition 1 and the way how Abin and B bin are collected.
Theorem 2 Tbin
ε satisfies ε-LDP.
We do need a larger sample size in Tbin
ε to get a satisfactory statistical power than the size needed in a non-private
t-test on the real values in A and B. Intuitively, for a fixed
gap between population means µA and µB , the gap between
pA and pB is smaller if the domains size m is larger or ε is
smaller; note that the smaller the gap between pA and pB is,
the harder for the test Tbin
ε to draw a significant conclusion.
Lower bounds of the power of Tbin
ε (or sample sizes needed)
are derived in Theorem 3 at a significance level α.
Theorem 3 Tbin
ε (Algorithm 1) has a significance level α,
i.e., type-I error ≤ α. Suppose the alternative H1 : µA −
µB > d0 is true with (µA − µB ) − d0 = θ. The statistical
power (1− type-II error) of Tbin
ε , denoted by P (θ), is
 bin

P (θ) , Pr Tε (A, B) = reject | (µA − µB ) − d0 = θ ≥

!2 
r
r
ε
θ(e
−
1)
2n
n
1
A
B
 , (7)
1 − exp −
− ln
m(eε + 1) nA + nB
α
 2

1
if the samples are large enough: nA + nB = Ω θm
2 ε2 ln α .
If we use Normal distributions to approximate Binomial
distributions and Student’s t-distributions (under the condition that nA and nB are large enough), we have:


pθ
−1
P (θ) ≥ 1 − F F (1 − α) −
≥
(8)
σ̂A+B


s
4(nA − 1)(nB − 1) 
−1
1 − F F (1 − α) − pθ ·
(9)
nA + nB − 2

ε

θ
where pθ = m
· eeε −1
+1 , F (·) is the CDF of the Normal distribution N(0, 1), and the sample variance σ̂A+B =
s
1Abin /nA − 12Abin /n2A
1B bin /nB − 12B bin /n2B
+
, where
nA − 1
nB − 1

1X = |{x ∈ X | x = 1}| is the number of 1’s in X. (10)
In particular, if nA = nB = n and we require that the
statistic power P (θ) ≥ 1 − β, it suffices to have
n = F −1 (1 − α) − F −1 (β)

2

·

1
+ 1.
2p2θ

(11)

Proof: Let’s focus on the case d0 = 0. The proof can be
easily generalized for d0 > 0 by adding a constant.
Consider a test with a null hypothesis H0bin (in line 7 of
Algorithm 1) using the following test statistic:
z(Abin , B bin ) =

1
1
1 bin −
1 bin
nA A
nB B

(1X is defined
in (10)). Using the linearity of expectation,

we have E z(Abin , B bin ) = pA − pB (pX is defined in (6)).
The proof of (7) is in the appendix, using a weaker test
and McDiarmid’s inequality.
We now focus on (8)-(9). Let’s first state the Normal approximation: a Binomial distribution B(n, p) with n trials
and success probability p can be approximated by a normal
distribution N(np, np(1 − p)), if n is large enough.
From Proposition 5, we have 1Abin ∼ B(nA , pA ) and
1B bin ∼ B(nB , pB ). Using Normal approximations to 1Abin
and 1B bin , under H0bit (when d0 = 0), we have
z(Abin , B bin )
∼ N(0, 1),
σA+B
p
where σA+B = pA (1 − pA )/nA + pB (1 − pB )/nB .
In the test (line 7), we use σ̂A+B in (10) to approximate
σA+B . When nA and nB are large enough,
z(Abin , B bin )
∼ N(0, 1),
σ̂A+B
from the Normal approximation to Student’s t-distribution.
At a significance level of α, we need to find an rejection
threshold
z0 of z(Abin ,B bin ), s.t., under H0bin , Pr[reject] =

bin
Pr z(A , B bin ) ≥ z0 ≤ α. Therefore, based on the CDF
of the Normal distribution N(0, 1), we reject H0bit iff
z(Abin , B bin ) ≥ z0 = F −1 (1 − α) · σ̂A+B .
Now let’s estimate the statistical power under the alternative hypothesis with µA − µB = θ, or equivalently,
pA − pB =

θ eε − 1
·
, pθ .
m eε + 1

Under the above condition, we have
z(Abin , B bin ) − pθ
∼ N(0, 1).
σ̂A+B

And thus the statistical power P (θ) =


z(Abin , B bin )
= Pr
≥ F −1 (1 − α) pA − pB = pθ
σ̂A+B


z(Abin , B bin ) − pθ
pθ
= Pr
≥ F −1 (1 − α) −
σ̂A+B
σ̂A+B


pθ
= 1 − F F −1 (1 − α) −
σ̂A+B


s
4(n
−
1)(n
−
1)
A
B
.
≥ 1 − F F −1 (1 − α) − pθ ·
nA + nB − 2
The sample size lower bound in (11) is directly from (9).
How to use Theorem 3. All three of (7)-(9) can be used to
estimate the lower bound of statistical power, and the largest
one can be picked. (8) is likely to be the tightest one, but it
needs the sample variance σ̂A+B (10) in the LDP samples
Abin and B bin , while the other two only need the sample
sizes. Before we draw samples from populations, (11) can be
used to estimate the sample sizes needed. As will be verified
in the experiments, the estimated sample sizes are sufficient
to guarantee the required statistical power. It is interesting
bin
to note that
√ the type-II error of Tε has a dominated term
O(− exp( n)) similar to the one of unit circle mechanism
(Kakizaki, Fukuchi, and Sakuma 2017) for a different test
1
(χ2 -test) under DP. The additional term m
is from LDP.
bin
About Laplace mechanism. Tε can be adapted if each
user’s counter is collected using the Laplace-perturbation
mechanism (Duchi, Jordan, and Wainwright 2013). However, sending Laplace-perturbed counters is costly and we
cannot expect better statistical power from it.

Extensions for Hybrid Privacy Requirements
Hybrid privacy model. The transformation-based LDP test
Tbin
ε can be extended for population with hybrid privacy requirements: more formally, in a random sample A = {ai }
(or B = {bi }) drawn from the distribution A (or B), some
users require ε-LDP, while the others do not.
Rescaling LDP bits. Indeed, for users who do not require
ε-LDP, we can simply send their exact counter aj (or bj )
to the server. The question is, for those who require ε-LDP,
e.g., ai , how to combine their LDP bits Mε,m (ai ) ∈ {0, 1}
with exact counters aj ∈ [0, m] to conduct hypothesis tests.
The proposed test Tmix
in Algorithm 2 “re-scales” LDP
ε
bits Mε,m (ai ) to form a mixed sample Amix together with
the exact counters. For a user ai who requires ε-LDP, if
Mε,m (ai ) = 0, amix
= −m/(eε − 1) is sent (line 3), and
i
mix
if Mε,m (ai ) = 1, ai = meε /(eε − 1) is sent (line 4). If
a user ai does not requires ε-LDP, simply send amix
= ai
i
(line 5). The same process is applied for sample B (lines 712). This process can be easily extended if different users
require different values of the privacy parameter ε.
mix
We can show that Amix = {amix
= {bmix
i } and B
i }
received by the server (line 13) can be considered as being
drawn from distributions Amix and Bmix , with means µmix
A =
µA and µmix
=
µ
,
respectively,
but
higher
variances.
B
B

Algorithm 2: Tmix
ε : For Hybrid Privacy Requirements
Proposition 6 If a counter x ∈ [0, m] follows a distribution X with mean µX , xmix (derived as amix
or bmix
in Algoi
i
mix
rithm 2) follows a distribution X with mean µmix
X = µX .
2
Let σX
be the variance of X. If each user in X requires
ε-LDP with probability r, the variance of Xmix is

2
2
2 2
σX
· r.
(12)
mix = σX · (1 − r) + O m /ε
Proof: µmix
X = µX is from (6) and the fact that if x requires
mix
LDP, x = Mε,m (x) · m · (eε + 1)/(eε − 1) − m/(eε − 1).
The variance of Xmix can be then calculated as follows:
 mix

 
2
σX
− E xmix )2
mix = E (x




=E (xmix − E xmix )2 | x does not require LDP ·(1 − r)




+E (xmix − E xmix )2 | x requires LDP ·r
m2 (eε + 1)2
· Var[Mε,m (x)] · r,
(eε − 1)2
where Var[Mε,m (x)] = O(1) follows from (2).
Since the distributions A and Amix (or, B and Bmix ) have
the same mean, we can conduct a t-test with the null hypothmix
mix
esis H0mix : µmix
and B mix in order to
A − µB = d0 on A
accept or reject H0 on A and B (line 14) – this is because H0
is a necessary and sufficient condition of H0mix . For the same
reason, the significance and the power of Tmix
are guaranε
teed to be the same as those of the t-test on line 14.
Theorem 4 Tmix
(Algorithm 2) satisfied the hybrid privacy
ε
model. It has a significance level α, i.e., type-I error ≤ α.
Its power is the same as the power of the t-test on line 14.
Proof: The significance/power guarantee is from the above
discussion. The privacy guarantee for each user follows from
Proposition 1 and how Amix and B mix are collected.
We do not give a closed-form lower bound of Tmix
ε ’s statistical power. Since it is equal to the power of the test conducted on line 14 of Algorithm 2, it depends on the variances

0.6
0.5
0.4
0.3
0.2
0.1
0.0

Empirical Type-I Error

Input: Two samples A = {ai }i∈[nA ] and B = {bi }i∈[nB ] .
Null hypothesis H0 : µA − µB = d0 .
Parameters: privacy budget ε and significance level α.
1: For users i = 1 to nA do
2:
If ai requires ε-LDP then:
3:
If Mε,m (ai ) = 0 then: amix
= −m/(eε − 1);
i
mix
ε
ε
4:
Else: ai = me /(e − 1).
5:
Else: amix
= ai .
i
to
the server.
6:
Send amix
i
7: For users i = 1 to nB do
8:
If bi requires ε-LDP then:
9:
If Mε,m (bi ) = 0 then: bmix
= −m/(eε − 1);
i
mix
ε
ε
10:
Else: bi = me /(e − 1).
11:
Else: bmix
= bi .
i
12:
Send bmix
to
the server.
i
mix
= {bmix
13: Server receives Amix = {amix
i }.
i } and B
14: Conduct a t-test with the null hypothesis H0mix : µmix
A −
mix
mix
µmix
=
d
on
A
and
B
at
significance
level
α:
0
B
accept (or reject) H0 iff H0mix is accepted (or rejected).

2bitLDP | = 5
NonPrivate
LDP | = 5
LDP | = 2
LDP | = 1
LDP | = 0.5
50% Hybrid | = 1

100

1000

10000

Sample Size

100000

1000000

Figure 1: Empirical type-I error of different approaches
2
2
of Amix and Bmix , which are determined by σA
, σB
, r (the
fraction of users requiring LDP), and m as in (12). And since
2
2
σA
and σB
are usually much smaller than m2 , r has a significant impact on the power: the smaller r is, the smaller
2
2
the variances σA
mix and σBmix are, and the larger the power
is. This property will be verified in our experiments.
More general hybrid privacy models. Tmix
can be easily
ε
extended for the model where each user i requires a different
privacy budget εi (just replacing ε with εi in lines 3-4 and
9-10 of Algorithm 2). In a different model considered for the
heavy-hitter problem (Avent et al. 2017), some users require
LDP while others only require DP on the testing output: how
to conduct effective tests in this model remains open.

Experimental Evaluation
Dataset and parameters. There are 20 million users in this
real-world dataset. Each user has a counter with the value in
[0, 15000], i.e., m = 15000. There are categorical attributes,
e.g., country, associated with each user’s counter.
We vary the privacy parameter ε from 0.5 to 5. The prespecified significance level α = 0.05, and the null hypothesis is H0 : µA − µB = 0. We draw samples from control/treatment with equal sizes nA = nB . For each value
of sample sizes, we repeat drawing samples and conducting
(LDP) tests 1000 times, and report the average (empirical)
type-I error and statistical power (1 − type-II error).

2
=σX
· (1 − r) +

Evaluating Significance
In the first set of experiments, we draw samples from distributions with the same means, and thus H0 holds. We report
the average type-I error of different approaches in Figure 1,
i.e., the empirical probability that H0 is rejected.
We conduct Welch’s t-test on the non-privatized samples
(NonPrivate in Figure 1), estimation-based LDP test Test
ε1 ,ε2
mix
(2bitLDP), LDP test Tbin
ε in Algorithm 1 (LDP), and Tε in
Algorithm 2 when 50% users require LDP (50% Hybrid).
Since it is required that type-I error ≤ significance level
α, ideally, the empirical type-I error should be close to α
or less. Figure 1 verifies Theorems 3-4: for different sammix
ple sizes and ε, both Tbin
always have empirical
ε and Tε
type-I errors close to 0.05. However, Test
ε does not perform
well, even with large sample sizes and large ε = ε1 + ε2 =
2.5 + 2.5; the reason is that although the sample variance
estimator (5) used in Test
ε has bounded bias (Proposition 4),
its variance is too high as m is large, and thus its empirical

0.8

0.6

NonPrivate
LDP | = 5
LDP | = 2
LDP | = 1
LDP | = 0.5

1.0
0.8

1000

10000 100000 1000000

Sample Size

0.0
100

(a) Gap θ = 60

0.4

NonPrivate
LDP | = 5
LDP | = 2
LDP | = 1
LDP | = 0.5

0.2

0.2

0.0
100

0.6

0.4

0.4

0.2

0.8

0.6

0.6

0.4

1.0

1000

10000 100000 1000000

Sample Size

(b) Gap θ = 120

0.0
100

Empirical Power (1- )

0.8

1.0

Empirical Power (1- )

Empirical Power (1- )

NonPrivate
LDP | = 5
LDP | = 2
LDP | = 1
LDP | = 0.5

Empirical Power (1- )

1.0

1000

10000 100000 1000000

Sample Size

(c) Gap θ = 300

NonPrivate
LDP | = 5
LDP | = 2
LDP | = 1
LDP | = 0.5

0.2
0.0
100

1000

10000 100000 1000000

Sample Size

(d) Gap θ = 600

Empirical Power (1- )

Figure 2: Empirical power (1 − type-II error) of different approaches in different scenarios for varying θ and ε
1.0
0.8
0.6
0.4
0.2
0.0

NonPrivate
1% Hybrid
10% Hybrid
20% Hybrid
50% Hybrid
LDP

100

1000

10000

Sample Size

100000

1000000

for
Figure 3: Empirical power (1 − type-II error) of Tmix
ε
hybrid privacy requirements with varying LDP fraction
error has a non-negligible impact on the test statistic, leading
to much higher type-I error than the pre-specified α.

Evaluating Power
We will evaluate the power of Tbin
ε (LDP in Figure 2) and
(x%
Hybrid
in
Figure
3)
in
the
rest experiments, as they
Tmix
ε
have been shown to satisfy the significance level empirically.
We draw samples from two populations with means differing by some constant θ, and thus H0 should be rejected.
We report the average power in Figures 2-3, i.e., the empirical probability that H0 is (correctly) rejected.
Varying gap θ between control and treatment. We vary θ
between two sub-populations from 60 to 600 in Figures 2(a)2(d). In particular, θ = 60 is a real scenario that we are
comparing populations between two countries A and B. We
inject shifts to create synthetic cases with θ = 120-600.
As θ grows, both Tbin
ε (for different ε) and non-privatized
Welch’s t-test need smaller samples to achieve an empirical
power 0.8 (a threshold commonly used in practice). Intuitively, the larger the mean gap θ is, the easier it is for a test to
distinguish the two populations. This trend is also consistent
with theoretical bounds of the power derived in Theorem 3.
For θ = 60, to achieve an empirical power 0.8, Tbin
ε (with
ε = 5) needs roughly three times as many samples as the
non-privatized Welch’s t-test does. It is totally acceptable,
because, with the strong LDP privacy guaranteed for each
user without the need of trusting the data collector, more
users would be willing to share their data (in an LDP way).
Theorem 3 gives a way (11) to estimate the sample size
needed to achieve certain power in Tbin
ε . We can verify this

analytical result here: in Figures 2(a)-2(d), for each ε, we
plot a dashed line in the same color as the color of the corresponding power curve – this dashed line, calculated by (11),
denotes the sample size needed to achieve a power of 0.8.
It turns out to be a “safe” estimation: samples with this size
always give the required or better power in Figure 2.
Hybrid privacy requirements. We evaluate our test Tmix
ε
for hybrid privacy requirements in the scenario with θ = 60
on a
and ε = 1 in Figure 3: “x% Hybrid” represents Tmix
ε
population with a random portion of x% users requiring 1LDP, and “LDP” represents Tbin
ε . Intuitively, the less users
require LDP, the easier it is for us to conduct tests. This intuition is consistent with the empirical performance of Tmix
ε ,
which calibrates noise for each LDP user and mixes them
with exact samples from those who do not require LDP.
Even within one sample, LDP users may follow a difstill needs
ferent distribution from non-LDP ones. So Tmix
ε
larger samples than the non-private test does. But the sample size needed to achieve a high power (e.g., 0.8) decreases
quickly as the LDP ratio goes down: when 50% users requires LDP, the sample size needed in Tmix
ε is around half of
the one in Tbin
ε ; and when 1% users requires LDP, the sample
size needed is close to the one in the non-private t-test.

Conclusion
We study how to conduct hypothesis testing for comparing
population means under LDP. We propose two approaches.
Both inject noise into each user’s data in the samples before
sending it to the data collector to ensure LDP. The first one,
called estimation-based LDP test, decodes LDP samples aggregatively at the data collector to recover the observed test
statistics. The second one, called transformation-based LDP
test, studies the relationship between the population distributions and the distributions of LDP samples. It conducts
transformed tests directly on LDP samples and converts conclusions for the original tests. The second one has provable
significance and lower bounds of power, and it can be extended for population with hybrid privacy requirements.

References
[Agrawal and Haritsa 2005] Agrawal, S., and Haritsa, J. R. 2005.
A framework for high-accuracy privacy-preserving mining. In Pro-

ceedings of the 21st International Conference on Data Engineering
(ICDE), 193–204.
[Apple 2017] Apple. 2017. https://developer.apple.
com/library/content/releasenotes/General/
WhatsNewIniOS/Articles/iOS10.html.
[Avent et al. 2017] Avent, B.; Korolova, A.; Zeber, D.; Hovden, T.;
and Livshits, B. 2017. BLENDER: enabling local search with a
hybrid differential privacy model. In 26th USENIX Security Symposium (USENIX Security), 747–764.
[Bassily and Smith 2015] Bassily, R., and Smith, A. D. 2015. Local, private, efficient protocols for succinct histograms. In Proceedings of the 47th ACM Symposium on Theory of Computing (STOC),
127–135.
[Bassily et al. 2017] Bassily, R.; Nissim, K.; Stemmer, U.; and
Thakurta, A. 2017. Practical locally private heavy hitters. CoRR
abs/1707.04982.
[Ding, Kulkarni, and Yekhanin 2017] Ding, B.; Kulkarni, J.; and
Yekhanin, S. 2017. Collecting telemetry data privately. In Advances in Neural Information Processing Systems 30 (NIPS).
[Duchi, Jordan, and Wainwright 2013] Duchi, J. C.; Jordan, M. I.;
and Wainwright, M. J. 2013. Local privacy and statistical minimax rates. In 54th Annual IEEE Symposium on Foundations of
Computer Science (FOCS), 429–438.
[Duchi, Wainwright, and Jordan 2013] Duchi, J. C.; Wainwright,
M. J.; and Jordan, M. I. 2013. Local privacy and minimax bounds:
Sharp rates for probability estimation. In Advances in Neural Information Processing Systems 26 (NIPS), 1529–1537.
[Duchi, Wainwright, and Jordan 2016] Duchi, J. C.; Wainwright,
M. J.; and Jordan, M. I. 2016. Minimax optimal procedures for
locally private estimation. CoRR abs/1604.02390.
[Dwork et al. 2006] Dwork, C.; McSherry, F.; Nissim, K.; and
Smith, A. 2006. Calibrating noise to sensitivity in private data
analysis. In 3rd Theory of Cryptography Conference (TCC), 265–
284.
[Erlingsson, Pihur, and Korolova 2014] Erlingsson, Ú.; Pihur, V.;
and Korolova, A. 2014. RAPPOR: randomized aggregatable
privacy-preserving ordinal response. In Proceedings of the 2014
ACM SIGSAC Conference on Computer and Communications Security (CCS), 1054–1067.
[Evfimievski, Gehrke, and Srikant 2003] Evfimievski, A.; Gehrke,
J.; and Srikant, R. 2003. Limiting privacy breaches in privacy preserving data mining. In Proceedings of the 22nd ACM Symposium
on Principles of Database Systems (PODS), 211–222.
[Fanti, Pihur, and Erlingsson 2016] Fanti, G. C.; Pihur, V.; and Erlingsson, Ú. 2016. Building a RAPPOR with the unknown:
Privacy-preserving learning of associations and data dictionaries.
PoPETs 2016(3):41–61.
[Fienberg, Rinaldo, and Yang 2010] Fienberg, S. E.; Rinaldo, A.;
and Yang, X. 2010. Differential privacy and the risk-utility tradeoff for multi-dimensional contingency tables. In Proceedings of
Privacy in Statistical Databases (PSD) 2010, 187–199.
[Gaboardi et al. 2016] Gaboardi, M.; Lim, H.; Rogers, R. M.; and
Vadhan, S. P. 2016. Differentially private chi-squared hypothesis testing: Goodness of fit and independence testing. In Proceedings of the 33nd International Conference on Machine Learning
(ICML), 2111–2120.
[Greenberg 2017] Greenberg, A. 2017. https://www.wired.
com/story/uber-privacy-elastic-sensitivity/.
[Hackett 2015] Hackett, R. 2015. http://fortune.com/
2015/08/26/ashley-madison-hack/.

[Johnson and Shmatikov 2013] Johnson, A., and Shmatikov, V.
2013. Privacy-preserving data exploration in genome-wide association studies. In The 19th ACM SIGKDD International Conference
on Knowledge Discovery and Data Mining (KDD), 1079–1087.
[Kairouz, Bonawitz, and Ramage 2016] Kairouz, P.; Bonawitz, K.;
and Ramage, D. 2016. Discrete distribution estimation under local
privacy. 2436–2444.
[Kairouz, Oh, and Viswanath 2014] Kairouz, P.; Oh, S.; and
Viswanath, P. 2014. Extremal mechanisms for local differential
privacy. In Advances in Neural Information Processing Systems
27 (NIPS), 2879–2887.
[Kakizaki, Fukuchi, and Sakuma 2017] Kakizaki, K.; Fukuchi, K.;
and Sakuma, J. 2017. Differentially private chi-squared test by
unit circle mechanism. In Proceedings of the 34th International
Conference on Machine Learning (ICML), 1761–1770.
[Karwa and Slavković 2012] Karwa, V., and Slavković, A. B. 2012.
Differentially private graphical degree sequences and synthetic
graphs. In Proceedings of Privacy in Statistical Databases (PSD)
2012, 273–285.
[Karwa and Slavković 2016] Karwa, V., and Slavković, A. 2016.
Inference using noisy degrees: Differentially private β-model and
synthetic graphs. Ann. Statist. 44(1):87–112.
[Kohavi and Round 2004] Kohavi, R., and Round, M. 2004. Front
line internet analytics at amazon.com. Emetrics Summit.
[Kohavi et al. 2012] Kohavi, R.; Deng, A.; Frasca, B.; Longbotham,
R.; Walker, T.; and Xu, Y. 2012. Trustworthy online controlled
experiments: five puzzling outcomes explained. In The 18th ACM
SIGKDD International Conference on Knowledge Discovery and
Data Mining (KDD), 786–794.
[McSherry 2009] McSherry, F. 2009. Privacy integrated queries: an
extensible platform for privacy-preserving data analysis. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD), 19–30.
[Panger 2016] Panger, G. 2016. Reassessing the facebook experiment: critical thinking about the validity of big data research. Information, Communication & Society 19(8):1108–1126.
[Rogers and Kifer 2017] Rogers, R., and Kifer, D. 2017. A new
class of private chi-square hypothesis tests. In Proceedings of the
20th International Conference on Artificial Intelligence and Statistics (AISTATS), 991–1000.
[Rogers 2017] Rogers, R. 2017. Leveraging privacy in data analysis. PhD Dissertation.
[Tang et al. 2010] Tang, D.; Agarwal, A.; O’Brien, D.; and Meyer,
M. 2010. Overlapping experiment infrastructure: more, better,
faster experimentation. In Proceedings of the 16th ACM SIGKDD
International Conference on Knowledge Discovery and Data Mining (KDD), 17–26.
[Uhlerop, Slavković, and Fienberg 2013] Uhlerop, C.; Slavković,
A.; and Fienberg, S. E. 2013. Privacy-preserving data sharing
for genome-wide association studies. The Journal of Privacy and
Confidentiality 5(1):137–166.
[Vu and Slavkovic 2009] Vu, D., and Slavkovic, A. 2009. Differential privacy for clinical trial data: Preliminary evaluations. In IEEE
International Conference on Data Mining Workshops, 138–143.
[Wang et al. 2016] Wang, S.; Huang, L.; Wang, P.; Nie, Y.; Xu,
H.; Yang, W.; Li, X.; and Qiao, C. 2016. Mutual information optimally local private discrete distribution estimation. CoRR
abs/1607.08025.
[Wang et al. 2017] Wang, T.; Blocki, J.; Li, N.; and Jha, S. 2017.
Locally differentially private protocols for frequency estimation. In
26th USENIX Security Symposium (USENIX Security), 729–745.

[Wang, Lee, and Kifer 2015] Wang, Y.; Lee, J.; and Kifer, D.
2015. Differentially private hypothesis testing, revisited. CoRR
abs/1511.03376.
[Wang, Wu, and Hu 2016] Wang, Y.; Wu, X.; and Hu, D. 2016. Using randomized response for differential privacy preserving data
collection. In Proceedings of the Workshops of the EDBT/ICDT
2016 Joint Conference (EDBT/ICDT Workshops).
[Warner 1965] Warner, S. L. 1965. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the
American Statistical Association 60(309):63–69.
[Yu et al. 2014] Yu, F.; Fienberg, S. E.; Slavkovic, A. B.; and Uhler,
C. 2014. Scalable privacy-preserving data sharing methodology for
genome-wide association studies. Journal of Biomedical Informatics 50:133–141.

Description of Estimation-based Test
The estimation-based LDP test Test
ε1 ,ε2 is described in Algorithm 3. For the two samples A and B, we use privacy budget ε1 to collects A0 and B 0 , and ε2 to collects A00 and B 00
(lines 1-7). µ̂ε1 ,m (A0 ) and µ̂ε1 ,m (B 0 ) are used to estimate
sample means µA and µB , respectively; ŝ2ε1 ,ε2 ,m (A0 , A00 )
and ŝ2ε1 ,ε2 ,m (B 0 , B 00 ) are used to estimate sample variances
(lines 8-9). The four estimations are embedded into (1), to
estimate t and df in order to conduct a t-test with null H0
(lines 10-12). There is no theoretical guarantee on the errors
in the testing result, mainly because it is difficult to bound
the error in t̂, and the distribution of t̂ is unknown.
Input: Two samples A = {ai }i∈[nA ] and B = {bi }i∈[nB ] .
Null hypothesis H0 : µA − µB = d0 .
Parameters: privacy budget ε1 , ε2 and significance level α.
1: For users i = 1 to nA do
2:
Encode a0i = Mε1 ,m (ai ) and a00i = Mε2 ,m2 (a2i ).
3:
Send a0i and a00i to the server.
4: For users i = 1 to nB do
5:
Encode b0i = Mε1 ,m (bi ) and b00i = Mε2 ,m2 (b2i ).
6:
Send b0i and b00i to the server.
0
00
7: Server receives A0 = {a0i }, A00 = {a00
i }, B , and B .
8: Estimate µ̂A = µ̂ε1 ,m (A0 ) and ŝ2A = ŝ2ε1 ,ε2 ,m (A0 , A00 ).
9: Estimate µ̂B = µ̂ε1 ,m (B 0 ) and ŝ2B = ŝ2ε1 ,ε2 ,m (B 0 , B 00 ).
10: Compute t̂ = t(µ̂A , µ̂B , ŝ2A , ŝ2B , nA , nB ) as in (1).
ˆ = df (ŝ2 , ŝ2 , nA , nB ) as in (1).
11: Compute df
A B
ˆ
12: Conduct a t-test with null hypothesis H0 , using t̂ and df
as t and df at significance level α.
Algorithm 3: Test
ε1 ,ε2 : Estimation-based LDP Test

Proof to Proposition 1
This original proof is from (Ding, Kulkarni, and Yekhanin
2017), and we include it here for the completeness.
Each user sends only one bit Mε,m (x) to the data collector if her/his counter is x. According to (2), for any x ∈
[0, m], the probability of sending 0 varies from 1/(eε + 1)
to eε /(eε + 1); similarly, the probability of sending 1 is in
the same range. So the ratio between respective probabilities
for any two different values of x is at most eε . So the privacy
guarantee Mε,m follows from Definition 1.

Proof to Proposition 3
Suppose X = {xi } is a random sample drawn from a distribution X such that Pr[xi = m/2] = 1, and Y = {yi }
is a sample drawn from Y such that Pr[yi = 0] = 1/2 and
Pr[yi = m] = 1/2. So X has a sample variance s2X = 0,
while with high probability,
Y has a sample variance at

least s2Y = Ω m2 . However, the LDP bits Mε,m (X) =
{Mε,m (xi )} and Mε,m (Y ) follows the same distribution:
∀xi ∈ X : Pr[Mε,m (xi ) = 0] = Pr[Mε,m (xi ) = 1] = 1/2;
∀yi ∈ Y : Pr[Mε,m (yi ) = 0] = Pr[Mε,m (yi ) = 1] = 1/2.
The conclusion follows from the fact that X and Y cannot be
distinguished from each other based on their ε-LDP collections Mε,m (X)
 and Mε,m (Y ), while their sample variances
have a Ω m2 gap with high probability.

Proof to Proposition 4
Using Proposition 2 on X 00 , we have


E µ̂ε2 ,m2 (X 00 ) = µX 2 ;
and on X 0 , we have

m2
.
nε1
So using the linearity of expectation and (4)-(5), i) follows:


E ŝ2ε1 ,ε2 ,m (X 0 , X 00 )




n
E µ̂ε2 ,m2 (X 00 ) − E µ̂2ε1 ,m (X 0 )
=
n−1


n 
2
=
µX 2 − Var[µ̂ε1 ,m (X 0 )] + E[µ̂ε1 ,m (X 0 )]
n−1

n
n
=
µX 2 − µ2X −
Var[µ̂ε1 ,m (X 0 )]
n−1
n−1
 2
m
=s2X − O
.
nε1
Var[µ̂ε1 ,m (X 0 )] = O



To bound the variance of ŝ2ε1 ,ε2 ,m (X 0 , X 00 ) as in ii), because X 0 and X 00 are generated independently, we have


Var ŝ2ε1 ,ε2 ,m (X 0 , X 00 )
(13)
2




n
Var µ̂ε2 ,m2 (X 00 ) + Var µ̂2ε1 ,m (X 0 ) .
=
(n − 1)2
From Proposition 2 and how each x00i is generated, we have
 2 2
 4


(m )
m
00
2
Var µ̂ε2 ,m (X ) = O
=O
. (14)
nε22
nε22
And from (3), we have

!2 
n
0
ε1
X
 2

m
x
·
(e
+
1)
−
1
i

Var µ̂ε1 ,m (X 0 ) = Var
n i=1
eε1 − 1

!2 
n
0
ε1
X
m4
x
·
(e
+
1)
−
1
i

= 4 · Var
ε1 − 1
n
e
i=1
 ε1
4
 4 
m4 2
e +1
m
= 4 · n · O(1) ·
=O 2 4 .
n
e ε1 − 1
n ε1
Putting (14) and (15) back to (13), ii) follows.

(15)

The First Part of Proof to Theorem 3
We first need to derive a threshold value z0 to determine
the regions of acceptance and rejection for the test statistic
z(Abin , B bin ). Under H0 : µA − µB = 0, or equivalently,

H0bin : pA − pB = 0, we have E z(Abin , B bin ) = 0. And
flipping the value of any of abin
∈ Abin (or bbin
∈ B bin )
i
i
bin
bin
changes the value of z(A , B ) by at most 1/nA (or
1/nB ). So from McDiarmid’s inequality, we can bound
!


2t2
bin
bin
Pr z(A , B ) ≥ t ≤ exp −
nA · n12 + nB · n12
A

 B
2t2
. (16)
= exp −
1/nA + 1/nB
A significance level ofα requires a threshold
 z0 , s.t., under
H0bin , Pr[reject] = Pr z(Abin , B bin ) ≥ z0 ≤ α. Therefore,
based on (16), H0bin should be rejected iff:
s

1
1
1
bin
bin
+
ln .
z(A , B ) ≥ z0 =
2nA
2nB
α
Now let’s estimate the statistical power under the alternative hypothesis with µA − µB = θ, or equivalently,


θ eε − 1
pA − pB = E z(Abin , B bin ) =
·
.
m eε + 1

(17)

The statistical power is the probability of rejection
s
"
#

1
1
1
bin
bin
P (θ) = Pr z(A , B ) ≥
,
+
ln
2nA
2nB
α


under (17). Let ∆ = E z(Abin , B bin ) − z(Abin , B bin ):
s
#
"

θ eε − 1
1
1
1
P (θ) = Pr ∆ ≤
·
−
+
ln
m eε + 1
2nA
2nB
α
(using McDiarmid’s inequality, again)

r

θ
eε −1
1
 2 m · eε +1 −
2nA +

≥1 − exp −
1
1

nA + nB

≥1 − exp −

ε

θ e −1
·
·
m eε + 1

r

1
2nB

2nA nB
−
nA + nB



ln

r
ln

1
α

1
α

2 




!2 
.

Note that a pre-condition here is that
r
r
θ eε − 1
2nA nB
1
·
·
− ln ≥ 0
m eε + 1
nA + nB
α
 2

m
1
⇐⇒ nA + nB = Ω 2 2 ln
.
θ ε
α
The upper bound in (7) holds under the above condition.

