Learning Powers of Poisson Binomial Distributions
Dimitris Fotakis1,2 , Vasilis Kontonis1 , Piotr Krysta3 , and Paul Spirakis3,4
1

arXiv:1707.05662v1 [] 18 Jul 2017

National Technical University of Athens, School of Electrical and Computer Engineering, Iroon Polytechneiou 9,
15780 Athens, Greece. Email: fotakis@cs.ntua.gr, vkonton@gmail.com
2
Yahoo Research, 229 West 23rd Street, 10036 NY. Email: dfotakis@yahoo-inc.com
3
University of Liverpool, Department of Computer Science, Ashton Building, Ashton Street Liverpool L69 3BX,
U.K. Email: p.krysta@liverpool.ac.uk, spirakis@liverpool.ac.uk
4
CTI, Greece. Email: spirakis@cti.gr
Abstract. We introduce the problem of simultaneously learning all powers
P of a Poisson Binomial
Distribution (PBD). A PBD over {1, . . . , n} is the distribution of a sum X = n
i=1 Xi , of n independent
Bernoulli 0/1 random variables Xi , where E[Xi ] = pi . The k’th power of this distribution, for k in
Pn
(k)
a range {1, . . . , m}, is the distribution of Pk =
i=1 Xi , where each Bernoulli random variable
(k)
(k)
k
Xi ∈ {0, 1} has E[Xi ] = (pi ) . The learning algorithm can query any power Pk several times and
succeeds in simultaneously learning all powers in the range, if with probability at least 1 − δ: given any
k ∈ {1, . . . , m}, it returns a probability distribution Qk with total variation distance from Pk at most
ε.
We provide almost matching upper and lower bounds on the query complexity for this problem. We
first show an information theoretic lower bound on the query complexity on PBD powers instances with
many distinct parameters pi which are significantly separated. This lower bound shows that essentially
a constant number of queries is required per each distinct parameter. We almost match this lower
bound by examining the query complexity of simultaneously learning all the powers of a special class
of PBD’s resembling the PBD’s of our lower bound.
We extend the classical minimax risk definition from statistics, dating back to 1930s [Wald 1939], to
introduce a framework to study sample complexity of estimating functions of sequences of distributions.
Within this framework we show how classic lower bounding techniques, such as Le Cam’s and Fano’s,
can be applied to provide sharp lower bounds in our learning model.
We study the most fundamental setting of a Binomial distribution, i.e., pi = p, for all i, and provide
an optimal algorithm which uses O(1/ε2 ) samples, independent of n, m. Thus, we show how to exploit
the additional power of sampling from other powers, that leads to a dramatic increase in efficiency. We
also prove a matching lower bound of Ω(1/ε2 ) samples for the Binomial powers problem, by employing
our minimax framework.
Estimating the parameters of a PBD is known to be hard. Diakonikolas, Kane and Stewart [COLT’16]
showed an exponential lower bound of Ω(21/ε ) samples to learn the pi ’s within error ε. Thus, a natural
question is whether sampling from powers of PBDs can reduce this sampling complexity. Using our
minimax framework we provide a negative answer to this question, showing that the exponential number
of samples is inevitable. We then give a nearly optimal algorithm that learns the pi ’s of a PBD using
2O(n max(log(1/ε),log(n))) samples from the powers of the PBD, which P
almost matches our lower bound.
n
k
The Newton-Girard formulae give relations between
the
power
sums
i=1 zi , k = 1, . . . , n, of the roots,
Qn
and the coefficients of a polynomial P (x) = i=1 (x − zi ). Thus, if we know the power sums exactly,
we can first find the coefficients of P (x) and then compute the roots z1 , . . . , zn with an arbitrarily
good accuracy. In our problem we only have access to approximate values for the power sums since
they correspond to the means of the PBD powers. An intriguing question is to which extent these
“noisy” power sum estimations can be used to recover the actual values of p1 , . . . , pn within sufficient
accuracy. We answer this question by providing close lower and upper bounds on the sample complexity
of estimating the parameters of a PBD using samples from its powers.

1
1.1

Introduction
Our Model and the PBD Powers Problem

A Poisson Binomial Distribution (PBD) is the discrete probability distribution of a sum of n
independent Bernoulli indicator P
random variables, and n is the order of the distribution. So if X
is a PBD of order n then X = ni=1 Xi where X1 , ..., Xn are independent Bernoulli 0/1 random
variables. The expectations (E[Xi ] = pi )i , called the parameters of the PBD, do not need to be the
same and thus PBD’s capture a quite wide class of distributions. It is believed that Poisson was
the first to consider PBD’s, hence their name. Let now a random variable Yi,k be the product of k
Bernoulli independent
random variables, each distributed as Xi . The expectation of Yi,k is (pi )k . If
Pn
Pk is the sum
P i=1 Yi,k , we call the PBD Pk the kth power of the PBD X. The expectation of Pk
is equal to ni=1 (pi )k . The powers of a PBD clearly relate to the moments of the PBD.
Suppose an unsupervised learning algorithm knows n but not the pi ’s, and aims at approximately
and simultaneously learning all the powers Pk of a PBD X for k ∈ {1, . . . , m}, where m is given
and can even be greater than n. The algorithm can ask for independent samples from any Pk
for k in any subset of the range {1, . . . , m}. A query to Pk returns an independent sample from
distribution Pk . Each such sample has log n bits since by definition the maximum value of Pk is n.
The algorithm can proceed in an adaptive way, by getting some samples from some powers, then
computing, then asking for more samples, depending on the computations and previous samples.
The algorithm is said to succeed with probability at least 1−δ, for given δ > 0, if the following holds
with probability at least 1 − δ: Given any k ∈ {1, . . . , m}, the algorithm outputs a distribution Qk
whose Total Variation Distance from Pk is at most ε. Here, δ, ε ∈ (0, 1) are given as input. Note,
Qk is not needed to be a PBD itself. The query complexity of the algorithm is the total number of
samples obtained and is a function of n, m, 1/δ, 1/ε. To compare different algorithms that query
for independent samples from a subset in the range and manage to learn all powers in the range,
we consider the query complexity per learned power to be the total number of queries divided by
the number of powers we learn. We study this problem of simultaneously learning all the powers
of a PBD in a given range in terms of query and time complexity efficiency. Ideally, our learning
algorithm runs in time polynomial in n, m, 1/δ, 1/ε, but our primary focus is query complexity.
The problem can of course be solved by taking samples per power to learn it approximately for
each power in the range. The challenging question is if we can do much better than this in terms of
query and time complexity, given the fact that the powers of the unknown PBD are related because
they are defined over the same unknown parameters pi ’s.
1.2

Motivation

Random Coverage Valuations The PBD powers problem arises from the problem of learning
a natural class of random coverage valuations. Given a ground set X = {e1 , . . . , en }, a function
v : 2U → N is a coverage valuation if there are A1 , . . . , Am ⊆ X such that for all S ⊆ [m],
S
v(S) =
j∈S Aj . Coverage valuations are monotone and submodular and have received considerable attention in optimization (maximizing a coverage valuation under a cardinality constraint),
learning and algorithmic mechanism design, see e.g., [2,13,20] and the references therein.
Let now each element ei ∈ X be associated with a probability pi ∈ [0, 1] and we generate m
random subsets A1 , . . . , Am ⊆ X by including each ei ∈ X in each Aj independently with probability
pi . The random sets A1 , . . . , Am are selected independently and are identically distributed. Random
S
sets A1 , . . . , Am define a random coverage valuation function v : 2[m] → N with v(S) = j∈S Aj .
Suppose we are interested in approximately learning the distribution of the values of such random
1

coverage valuations v evaluated over subsets S ⊆ [m]. Namely, given a ground set X = {e1 , . . . , en }
and the probabilities p1 , .h. . , pn , we want
i to find a family of probability distributions D(S) so
S
that Pr[D(S) = i] ≈ Pr
j∈S Aj = i , for all i ∈ {0, . . . , n} and S ⊆ [m] (the probability
in the right-hand-side is taken over the random sets Aj with j ∈ S). Each D(S) approximates
the distribution of the values v(S) of a coverage valuation function v chosen randomly from the
family of coverage valuations described above. Since the random sets A1 , . . . , Am are independently
identically distributed, only the cardinality of S, and not S itself, matters for the union’s cardinality.
Hence, given X and
pi ’s, we aim to compute probability distributions Dk so that
h Sthe probabilities
i
k
Pr[Dk = i] ≈ Pr
j=1 Aj = i , for all i ∈ {0, . . . , n} and k ∈ N. Each Dk approximates the
distribution of the cardinality of the union of k sets selected randomly and independently from X.
Learning random coverage valuations can be reduced to the PBD powers problem, by observing
that each distribution Dk is the sum of n independent Bernoulli variables with expectations 1 −
(1 − p1 )k , . . . , 1 − (1 − pn )k , where each such Bernoulli variable i indicates whether element ei is
included in at least one of the k random sets considered in the union. A natural sampling model
is that the learning algorithm selects an index k ∈ N and receives the cardinality of the union of k
random sets, which is exactly the sampling model in the PBD powers problem.
P
Newton’s identities The Newton-Girard formulae give relations between
power sums ni=1 zik ,
Qthe
k = 1, . . . , n, of the roots, and the coefficients of a polynomial P (x) = ni=1 (x − zi ). Thus, if we
know the power sums exactly, we can first find the coefficients of P (x) and then compute the roots
z1 , . . . , zn with an arbitrarily good accuracy. A similar approach was used in [12] to derive sparse
covers for PBDs. In our problem we only have access to approximate values for the power sums
since they correspond to the means of the PBD powers. An intriguing question is to which extent
these “noisy” power sum estimations can be used to recover the actual values of p1 , . . . , pn within
sufficient accuracy. We answer this question by providing close lower and upper bounds on the
sample complexity of estimating the parameters of a PBD using samples from its powers.
1.3

Our Results

We now state our first lower bound. A vector p = (p1 , . . . , pn ) ∈ [0, 1]n is called (ν, κ, m)-separated,
for some positive integers m and κ > ν, with n/m also a positive integer, if there are m positive
integers a1 , . . . , am ∈ [ν] so that p contains a group of n/m values pi = 1 − ai /κi for each i ∈ [m].
Thus, a (ν, κ, m)-separated vector p has n/m entries of value p1 = 1 − a1 /κ, n/m entries of value
p2 = 1 − a2 /κ2 , . . . , and n/m entries of value pm = 1 − am /κm . A PBD X is (ν, κ, m)-separated if
the parameters defining X are given by a (ν, κ, m)-separated vector p.
Our results indicate that when the separation of the pi ’s is substantial the problem of estimating
the densities of the PBD powers is equivalent to approximate the PBD’s parameters. The following
information-theoretic lower bound shows that for any integer m ≤ n/(ln n)4 , learning an appropriate
collection of m powers of an (ln n, (ln n)4 , m)-separated PBD p requires Ω(m ln ln n/ ln n) samples
in the worst case. Hence, for the special case of separated PBDs, the sampling complexity should
increase almost linearly with the number m of different pi values in p, at least as long as m ≤
n/(ln n)4 .
Theorem 1.1. For any positive integer m ≤ n/(ln n)4 so that n/m is an integer, any algorithm
that succeeds in learning all powers with indices (ln n)4i−2 , i = 1, . . . , m, of an (ln n, (ln n)4 , m)separated PBD, within total variation distance ε ∈ (0, 1/4] and with failure probability δ ≤ 1/2,
requires Ω(m ln ln n/ ln n) samples in the worst case.
2

To almost match this lower bound, we show how to learn the following class of PBD’s resembling
our lower bound PBD. Let pi = 1 − αi /(c · ln(n))s−i , with c > 1 any constant, and s a number
such that p
(c · ln(n))s = n, i = 0, 1, . . . , s − 1. Notice, s ≈ ln(n)/ ln(ln(n)), and assume αi ∈
{1, 2, . . . , ⌊ ln(n)⌋} for each i. The class P of PBD’s instances has ni probabilities equal to pi
for i = 0, 1, . . . , s − 1, where ni = n/s for each i = 0, 1, . . .P
, s − 1. We assume that n and s are
s−1
known.
The
mean
of
the
first
power
of
a
PBD
from
P
is
i=0 ni pi . This PBD is defined by a
p
( ln(n), c · ln(n), s)-separated vector p. We call a block i, all the ni probabilities equal to pi , and
note that p0 > p1 > · · · > ps−1 .
√
Theorem 1.2. Let c ≥ 2 be a constant, ε ≤ 1/(6c), and n ≥ max{e2c , 4/((2 − 2)2 ε2 )}. Given an
unknown PBD X ∈ P,
i = 0, 1, . . . , s−1 can be learned by Algorithm 1
 the exact values of αi for each
2
ℓ
i
using O log(s/δ)/ε samples from each power X , where ℓi = (c·ln(n))s−i /c for i = 0, 1, . . . , s−1,
with success probability at least 1 − δ. The total number of samples is O s log(s/δ)/ε2 .

Although our algorithm finds exact values of pi ’s, thus learning all the powers, it uses at most
O(ln(ln(n)/(δ ln ln(n)))/ε2 ) samples per sampled power, which is very close to our lower bound.
Interestingly, our lower bound proof shows that the claimed number of samples recover the exact
values of pi ’s. Thus, it essentially shows that Ω(1) samples are required per distinct value of pi , and
our upper bound uses roughly O (ln(ln(n))) samples per distinct value of pi .
The lower bound of Theorem 1.1 implies that the problem is hard in general, which motivates
us to consider the PBD powers problem with few distinct parameters. We ask: does the additional
power of the algorithm of being able to sample from many powers make the parameter estimation
easier? We answer this question in the negative, by proving an exponential lower bound in this
case.
The classic minimax risk framework from statistics is used for investigating lower and upper
bounds on the sample complexity of testing and learning a single distribution, cf. [28, Chapter 2].
We generalise and extend this framework from testing and learning a single distribution to sequences
of distributions. This generalisation is new to the best of our knowledge. The main ingredients of
our framework are generic theorems that reduce the problem of learning a sequence of distributions
to testing such sequence and provide generic lower bounds on the minimax risk based on classical
results from statistics, see, e.g., [29,32,4,30] and [28, Chapter 2]. For precise formulations of these
new theorems, see Proposition 5.1, Lemma 5.1 and Lemma 5.2.
Crucial to our framework and our main conceptual contribution here, is the new definition, Definition 5.1, of the minimax risk for sequences of distributions. This definition unveils the structure
of any learning algorithm in our model. Namely, such algorithm has two distinct types of operations
related to sampling, that of deciding from which distributions in the sequence to sample, and that
of using the samples in its computation phase. The two operations’ types might alternate and the
algorithm may be adaptive or non-adaptive about further sampling and using the samples.
Our framework is of independent interest since it can be used for proving lower bounds for
estimation of functions of distribution sequences such as their densities or their parameters. It
can be instantiated with the classic methods for proving sample lower bounds, that is, Le Cam’s,
Fano’s or Assouad’s methods [32]. We present two applications of this framework to prove two lower
bounds, in Theorems 1.3 and 1.6. To prove an exponential lower bound for parameter estimation
in our model, we use our framework with the Le Cam’s method and a PBD instance introduced in
Proposition 15 of [15].

Theorem 1.3. If n ≥ 1/ε, then any learning algorithm that draws N samples from any powers of
an PBD of order n and returns estimates of the parameters of this PBD within additive error ε
with success probability at least 2/3 must have N ≥ 2Ω(1/ε) .
3

We see that parameter estimation remains very difficult even if we enrich the power of the
algorithm to allow for sampling from any power of the PBD with n = Θ(1/ε). In sharp contrast,
observe, that using the density estimation algorithms from [9,16] for each of the n powers of this
PBD, we can learn the densities of all these powers with only Õ(n/ε2 ) = Õ(1/ε3 ) samples. This
gives a provable separation in the sampling complexity between parameter and density estimation
in our model, even if the PBD has a constant number of distinct parameters. This also implies that
we cannot use parameter estimation in our model as means for density estimation if the underlying
PBD has a constant number of distinct parameters.
We almost match the exponential lower bound of Theorem 1.3 for parameter estimation with
a close upper bound in the most general version of the PBD powers model. We use the NewtonGirard identities to reduce our problem to the classical polynomial root finding problem. We present
an analysis of the error of this reduction from power sums to coefficients of the polynomial and
then to its roots, when power sums are known only approximately. The main obstacle in this
approach is that to find the roots of a polynomial with inexact coefficients we need extremely good
approximations of the coefficients and this leads to an exponential number of samples. Since the
algorithms for root finding are almost optimal, this exponential upper bound cannot be improved,
unless one uses a different technique. This leads to the following result with details in Appendix
6.2.
Theorem 1.4. Let X be a PBD with probability vector p. There exists an algorithm which draws
2O(n max(log(1/ε),log n)) samples from the powers of X and computes a vector p̂ such that kp− p̂k∞ ≤ ε.
Given the two lower bounds we turn our attention to investigating the model with few distinct
paramaters, focusing on a single parameter, i.e., the Binomial case. Here, we prove that the parameter and density estimations are essentially equivalent. That is, we get a dramatic increase in
efficiency and design an elegant algorithm which learns all powers of a given Binomial using only a
constant O(1/ε2 ) number of samples. Crucial for our solution is to generalise the PBD powers problem allowing for any positive real powers. Below B(n, p) is the PBD with all parameters equal to p.
(Algorithm 2 can be generalised to allow p ∈ [ε2 /nd , 1 − ε2 /nd ], for any constant d, see Section C.2.)
Theorem 1.5. Let ε ∈ (0, 1/6), n ∈ N. Then, for any p ∈ [ε2 /n, 1 − ε2 /n], Algorithm 2 uses

O(ln(1/δ)2 /ε2 ) samples and outputs â ∈ R++ , q̂1, q̂2 ∈ (0, 1) such that dtv B(n, q̂1l ), B(n, pâl ) =
O(ε) for l ∈ (1, +∞) and dtv B(n, q̂2l ), B(n, pâl ) = O(ε) for l ∈ (0, 1) with probability at least
1 − δ.
It’s well known that to distinguish two given Binomial distributions, Ω(1/ε2 ) samples are required, e.g., [9], implying the same lower bound for learning a single Binomial. This lower bound
does not apply to our model, because in our setting the input of the algorithm contains samples
from many different distributions. To prove a matching lower bound we use our minimax framework
with Fano’s method.
Theorem 1.6. Let A be an algorithm that returns probability distributions which are within total
variation distance ε from B(n, pi ) for all i ∈ {1, 2, 3, . . .}, using samples
from the distributions

B(n, pi ) with probability of success at least 2/3. Then A uses Ω 1/ε2 samples.
1.4

Related Work

The problem of approximately learning a PBD, within a given total variation distance ε, in a sample and time efficient way, is a fundamental problem in unsupervised learning and has received
4

significant attention. Chebyshev’s inequality gives an optimal bound of O(1/ε2 ) on the number
of samples for learning a Binomial distribution of known order n with constant failure probability. Birgé [3] gave an efficient algorithm for learning any continuous unimodal distribution over
{0, . . . , n} with O(log n/ε3 ) samples (this result can be extended to PBDs [9]), and proved that this
sample complexity is essentially best possible for unimodal distributions. By an elegant combinatorial construction, Daskalakis and Papadimitriou [12] proved that the family of all PBDs admits a
2
sparse cover, i.e., there is a small subset of PBDs, of size n2 + n(1/ε)O(log (1/ε)) , so that every PBD
is within a total variation distance of ε to some PBD in the subset. They used the sparse cover
of PBDs to efficiently compute an approximate Nash equilibrium in anonymous multiplayer games
[11]. Daskalakis, Diakonikolas and Servedio [9] exploited the sparse cover of PBDs (and several
other ideas and techniques) to show that a PBD can be learned approximately with O(ln(1/δ)/ε2 )
samples, where δ is the probability of failure, and in O((1/ε)poly(log(1/ε)) log n) time. Other applications of the sparse cover of PBDs include efficient testing of whether a given distribution is ε-close
to some PBD [1]. The result and the techniques of [9] were generalised to learning sums of independent integer random variables [8] and to learning Poisson Multinomial Distributions (PMDs)
[10]. Very recently, efficient algorithms have been shown for learning PMDs [7,17], PBDs [15], and
sums of independent integer random variables [16], by using Fourier
Transforms. The paper [16]
p
implies that PBDs can be learned approximately with O((1/ε2 ) log(1/ε)) samples and with the
same running time.
In this very active research area (see also [14] for a survey and references on efficient approximate
learning of structured probability distributions), we consider the problem of approximately learning,
in a sample and time efficient way, a family of many closely related PBDs (instead of a single one).
Given some samples, we need to extract information not only about the parameters of the PBD from
which the samples come, but also about the relation of the different probability distributions that
they generate the samples. To the best of our knowledge, this is the first time that a similar question
has been studied in the area of unsupervised learning of structured probability distributions.
1.5

Notation

Our model and the basic definitions are introduced at the beginning of Section 1. We introduce
here some additional notation used throughout the paper. Additional notation will be introduced
per Section. For any positive integer k, we let [k] = {1, . . . , k}. We let log n be the base-2 logarithm
of n and let ln n be the natural logarithm of n. We let E[X] and Var[X] denote the mean value
and the variance, respectively, of a probability distribution X. We let B(n, p) denote a binomial
distribution of order n and probability p. We usually identify a PBD
p with the vector p = (p1 , . . . , pn )
of expectations of its Bernoulli trials. We denote err (n, p, ε) = ε p(1 − p)/n. Let R++ = {a ∈ R :
a > 0}. Given two probability distributions X and Y over the set of natural numbers
N, the
P
total variation distance (TVD) of X and Y , denoted by dtv (X, Y ) is dtv (X, Y ) = i∈N |Pr[X =
i] − Pr[Y = i]|/2. For brevity, we often refer to the total variation distance simply the distance of
X and Y or TVD of X and Y . We often use X(i) to denote Pr[X = i], i.e., the probability that X
takes the value i.

2
2.1

Lower Bound for Learning PBD Powers: Separated Case
Preliminaries

We show a simple lower bound on the total variation distance of two PBDs based on the difference
of their expected values. Its proof can be found in Section A.1 of the Appendix.
5

Lemma 2.1. Let X and Y be two PBDs with expected values µX = E[X] and µY = E[Y ] and
2 = Var[X] and σ 2 = Var[Y ]. Then, for any ε > 0 such that σ 2 , σ 2 ≥ ln( 2 ), if
variances σX
Y
X
Y
1−ε
q
2
|µY − µX | > 2 ln( 1−ε )(σX + σY ), then dtv (X, Y ) > ε.
2.2

The Proof of Theorem 1.1

We show that learning m appropriately selected powers of an (ln n, (ln n)4 , m)-separated PBD p
requires Ω(m ln ln n/ ln n) samples, i.e., almost as many as the number of different pi values in
p, provided m ≤ n/(ln n)4 . We assume that n is large enough and consider an (ln n, (ln n)4 , m)separated PBD defined by m ≤ n/(ln n)4 integers a1 , . . . , am , with 1 ≤ ai ≤ ln n. The corresponding
vector p consists of m groups with n/m entries pi = 1 − ai /(ln n)4i in each group i = 1, . . . , m (note,
p1 < p2 < · · · < pm ). For simplicity, we assume that ln n, n/m ∈ N. The intuition behind the proof
is that given a distribution that approximates the (ln n)4i−2 -th power of p, we can extract the exact
value of ai . Lemma 2.2 helps towards formalizing this intuition.
Lemma 2.2. For any m ∈ N, m ≤ n/(ln n)4 , let p and q be two (ln n, (ln n)4 , m)-separated vectors
defined by positive integers a1 , . . . , am and b1 , . . . , bm , resp. For any ε ∈ (0, 1/2] and any i ∈ [m], if
the (ln n)4i−2 -th power of p and the (ln n)4i−2 -th power of q are within TVD at most ε, then ai = bi .
Proof. (sketch) For contradiction, assume that there is i ∈ [m] so that the (ln n)4i−2 -th power of p
and the (ln n)4i−2 -th power of q are within TVD at most ε and ai < bi (case ai > bi is symmetric).
Let xi = bi − ai , with 1 ≤ xi ≤ ln n, k = (ln n)4i−2 , and let X and Y be the k-th power of p and q,
respectively. Let also ν = ln n and s = n/m, with (ln n)4 ≤ s ≤ n; for simplicity, let ν, s ∈ N.
We prove that for each power k = ν 4i−2 and for both p and q, (i) the Bernoulli trials in each
group j < i contribute essentially 0 to the mean value and the variance of both X and Y (because
4i−2
≤ n− ln n ); (ii) the Bernoulli trials in each group j > i increase
for any j < i, (1 − aj /ν 4(i+1) )ν
the variance of X and Y by at most 2s/ν 5 ; and (iii) the difference in the mean values of X and
Y due to the Bernoulli trials in each group j > i is roughly s/ν 5 . As for the Bernoulli trials in
group i, they contribute roughly s/ν to the variance of X and Y and increase the difference in
their means by roughly sxi /ν 2 . If xi ≥ 1, since s ≥ (ln n)4 = ν 4 and since n is sufficiently large,
the difference in the mean valuespof X and Y , which is Ω(s/ν 2 ), is greater than the sum of their
standard deviations, which is O( s/ν). Thus, by Lemma 2.1, the k-th powers X and Y of p and
q are at distance larger than ε, a contradiction. So, an ε-approximation to the ν 4i−2 -th power of p
by q is possible only if pi = qi ; thus, only if ai = bi . The details can be found in Section A.2.
⊔
⊓
To prove Theorem 1.1, we show that given ε-approximations to the powers of p with indices
(ln n)4i−2 , for all i ∈ [m], we can determine the exact values of a1 , . . . , am , defining p. Namely, given
distributions Y1 , . . . , Ym , each Yi at distance at most ε ≤ 1/4 to the (ln n)4i−2 -th power of p, we
can obtain a (ln n, (ln n)4 , m)-separated vector q defined by m positive integers (b1 , . . . , bm ) so that
for all i ∈ [m], the (ln n)4i−2 -th power of q is within TVD at most ε to Yi . To find such a vector
q, we perform exhaustive search, in time O((ln n)m ). That is, we try all possible tuples (b1 , . . . , bm )
and find a tuple whose (ln n)4i−2 -th power is within TVD at most ε to the corresponding power Yi ,
for all i ∈ [m]. At least one such tuple exists, since (a1 , . . . , am ) has this property. By the triangle
inequality, we have that for all i ∈ [m], the (ln n)4i−2 -th power of q and the (ln n)4i−2 -th power of
p are at distance at most 2ε ≤ 1/2. Thus, if the learning algorithm succeeds in computing an εapproximation Yi to each (ln n)4i−2 power of p, which happens with probability at least 1 − δ ≥ 1/2,
we can find an (ln n, (ln n)4 , m)-separated vector q whose (ln n)4i−2 -th powers are within distance
2ε ≤ 1/2 to the corresponding powers of p. So, by Lemma 2.2, we have ai = bi for all i ∈ [m].
6

Since we need m log log n bits to represent a1 , . . . , am and a sample from a PBD power has
log n bits, such an ε-approximation to the powers of p with indices (ln n)4i−2 , for i ∈ [m], requires
Ω(m log log n/ log n) samples in total. Otherwise, we could use samples from the PBD powers,
provided to the learning algorithm as input, as an economic representation of a1 , . . . , am . Then,
the learning algorithm together with the exhaustive search procedure for finding q can be used
as a “decoding” algorithm to obtain a1 , . . . , am from their economic representation with the input
samples. Since we can use any values for a1 , . . . , am , such a compression scheme is impossible, see,
e.g., [23]. Note, such a learning algorithm would have a certain probability of failure, if the input
samples were truly random. But here, since we know p and want to use the learning algorithm as
a compression scheme for a1 , . . . , am , we can compute input samples deterministically, so that the
learning algorithm satisfies its error guarantees with certainty (such a sample collection exist, since
the learning algorithm has a positive probability of success). We have thus shown that the worst-case
sample complexity of any learning algorithm for this class of instances is Ω(m log log n/ log n).

3
3.1

Upper Bound for Learning PBD Powers: Separated Case
Preliminaries

To estimate the mean of a PBD we use the following Proposition from [9]Lemma 6.
Proposition 3.1 (Lemma 6 from [9]). For all n, ε, δ > 0, there exists an algorithm A(n, ε, δ)
with the following properties: given access to a PBD X of order n, it produces estimates µ̂, σ̂ 2 for µ =
2
2
2
E[X],
q σ = Var[X] respectively such that with probability at least 1 − δ: |µ − µ̂| ≤ ǫσ and |σ − σ̂ | ≤
ǫσ 2

4+

1
.
σ2

Moreover, A uses O(log(1/δ)/ε2 ) samples and runs in time O(log n log(1/δ)/ε2 ).

Fact 3.1. Let m and y be any real numbers such that m ≥ 1 and |y| ≤ m. Then we have that
ey (1 − y 2 /m) ≤ (1 + y/m)m ≤ ey .
Proof. See e.g. page 435 of [25].

We will give here the main ideas leading to Theorem 1.2. The sketch of its proof can be found
in Section 3.2 and its full proof in Appendix B.2.
Let X ∈ P be an unknown PBD from the defined class P (see Section 1). To learn X means
that we essentially need to learn (approximate) values αi for each i = 0, 1, . . . , s − 1. We will sample
from the following s powers of X: ℓi = (c · ln(n))s−i /c for i = 0, 1, . . . , s − 1. We will in fact prove
that all values αi ’s can be learned exactly.
The main idea is to learn pi ’s starting from the largest and proceeding towards the smallest.
Suppose that we have already exactly learned the values of α0 , . . . , αi−1 for some i ≥ 1. To learn
αi we sample from the power X ℓi by using sampler A(n, ε, δ/s) from Lemma 6 in [9] that employs
“weak” mean and variance estimators
(cf. Proposition 3.1). It draws O(log(s/δ)/ε2 ) independent
P
√
s−1 ℓi
samples from X ℓi . Since µℓi /ni =
i=0 pi , the error of this estimate is roughly ε/ n. Now,
√
p0 , . . . , pi−1 are precisely known, the value of pℓi i , to be learned, is much larger than the error ε/ n,
i
i
and the values of all remaining pℓi+1
, . . . , pℓs−1
are very small and they together sum up to at most
√
2/n and thus much smaller than the error ε/ n. These facts let us learn αi exactly. Then we
proceed to the next pi+1 and so on. The description of the algorithm can be found as Algorithm 1
and the proof of Theorem 1.2 follows essentially the algorithm. Interestingly, our algorithm solves
an instance of the polynomial root finding problem where roots pi are separated enough without
using coefficients of the polynomial, only by using the approximate powers sums (cf. motivation in
Section 1).
7

Algorithm 1 Exact Learning Algorithm for Special Class of PBDs
Input:Random samples from powers of an unknown PBD X ∈ P, parameter n, any constant
c ≥ 2, error bound ε ∈ (0, 1/(6c)], confidence bound δ > 0.
Output:Exact values of (p0 , p1 , . . . , ps−1 ) from X output with success prob. at least 1 − δ.
1: for i = 0, 1, . . . , s − 1 do

2:
Call A(n, ε, δ/s) (see Proposition 3.1) and draw O log(s/δ)/ε2 samples from X ℓi to obtain µ̂ℓi .
s−i
P
P
ℓi
ℓi
3:
ℓi ← (c ln(n))
, ni ← ns , τ̂i ← µ̂ℓi /ni − i−1
(* Note: −1
j=0 pj
j=0 pj = 0 *)
c
p
βi ℓi
i −1 ℓi
) ≤ τ̂i < (1 − βcℓ
)
4:
Let βi ∈ {1, 2, . . . , ⌊ ln(n)⌋} be the smallest number s.t. (1 − cℓ
i
i
5:
6:
7:

3.2

βi ℓi
i −1 ℓi
ai ← (1 − cℓ
) , bi ← (1 − βcℓ
)
i
i
ai +bi
if τ̂i < 2 then αi ← βi else αi ← βi − 1
αi
pi ← 1 − (c·ln(n))
s−i

The Proof of Theorem 1.2

The following technical lemma will be crucial in our proof of Theorem 1.2. Its proof can be found
in Appendix B.1.
p
Lemma 3.1. Let i ∈ {0, 1, . . . , s − 1}. If αi , βi ∈ {1, 2, . . . , ⌊ ln(n)⌋} and αi < βi , and c ≥ 2 and
β i ℓi
αi ℓi
) − (1 − cℓ
) > √4ε for all n ≥ e2c .
ε ≤ 1/(6c), then we have that (1 − cℓ
i
i
n/s

We next present only a sketch of the proof, its full version can be found in Appendix B.2.
The proof is by induction on i and we only sketch here the induction step. Assume that for some
i ∈ {1, 2 . . . , s − 1}, values of all p0 , p1 , . . . , pi−1 are known exactly, and we will show how to exactly
learn pi .
1/c
j−1
i
, and similarly, pℓi+j
for j = 1, 2, . . ..
≤ (1/n)(c ln(n))
By Fact 3.1, we observe pℓi i ≤ 1e

P
P
i
ℓ
s−1
ℓi
i
≤ n0 ·
By geometric series properties, this implies µℓi = E[X ℓi ] = n0 ·
p
+
p
j=i+1 j
P
P

 j=0 j
i−1 ℓi
ℓi
i−1 ℓi
ℓi
j=0 pj + pi + 2/n , and letting µℓi = n0 ·
j=0 pj + pi + rℓi , it implies rℓi ≤ 2/n.
m ≥ 1 − x, true for m ≥ 1, x ≤ m, and properties of geometric
By using inequality (1 − x/m)
P
s−1 ℓi
ℓ
series we obtain Var[X 0 ] = n0 j=0
pj (1 − pℓji ) < 2n0 . Thus, by Proposition 3.1, |µℓi − µ̂ℓi | ≤
p
Pi−1 ℓi
√
ℓi
εσℓi < ε 2n0 , with probability at least 1 − δ/s, so
j=0 pj + pi + rℓi − µ̂ℓi /n0 < ε 2/n0 . If

ℓi
p
P
ℓi
αi
we let αi ∈ {1, 2, . . . , ⌊ ln(n)⌋} be such that pℓi i = 1 − cℓ
, and denote τ̂i = µ̂ℓi /n0 − i−1
j=0 pj
i
(recall that p0 , . . . , pi−1 are known), the last inequality rewrites to


αi
1−
cℓi

ℓ i

p
+ rℓi − τ̂i < ε 2/n0 .

(1)


p
We can argue that there exists the smallest βi ∈ {1, 2, . . . , ⌊ ln(n)⌋} such that 1 −


βi
1−
cℓi

ℓi

≤ τ̂i <



βi − 1
1−
cℓi

ℓ i

.

βi
cℓi

ℓi

≤ τ̂i , so
(2)

ℓi

αi
Suppose now that βi ≥ αi + 2; then by (2), Lemma 3.1 and n ≥ e2c : 1 − cℓ
+ rℓi − τ̂i >
i
ℓi

ℓi

ℓi

ℓi

αi
αi
i −1
i +1
+ rℓi − 1 − βcℓ
≥ 1 − cℓ
+ rℓi − 1 − αcℓ
> √4ε . This is in contradic1 − cℓ
i
i
i
i
n/s

tion with (1); thus, βi ≤ αi + 1. If βi ≤ αi − 1, then by (2) and Lemma 3.1, τ̂i − pℓi i − rℓi =
8


τ̂i − 1 −

αi
cℓi

ℓi

− rℓi ≥

Thus, βi ∈ {αi , αi + 1}.


1−

αi −1
cℓi

 ℓi


− 1−

αi
cℓi

ℓi

− rℓi > √4ε − 2/n – contradiction with (1).
n/s


 ℓi 
ℓ 
βi −1 i
βi
, 1 − cℓi
in (2) can be lower
By Lemma 3.1 the length of the interval Ii = 1 − cℓi
 ℓi
ℓi


βi
i −1
−
1
−
> √4ε . If αi = βi , then by (1) the distance between
bounded as 1 − βcℓ
cℓi
i
n/s
ℓi

p
p
βi
and τ̂i is ≤ rℓi + ε 2/n0 ≤ 2/n + ε 2/n0 , i.e., strictly less than half of the length of Ii
1 − cℓ
i

 ℓi
i −1
by n > (2−√42)2 ε2 . On the other hand, if αi = βi − 1, then by (1) the distance between 1 − βcℓ
i
p
and τ̂i is ≤ ε 2/n0 , i.e., strictly less than half of the length of Ii . We can use this test to decide if
αi = βi − 1 or αi = βi . Thus the precise value of pi can be learned from τ̂i .
To finish the proof, observe that by the union bound all the sampling estimates hold with
probability at least 1 − δ. Moreover, because this sampling for each i = 0, 1, . . . , s − 1 takes ⌈ (ε2sδ) ⌉
samples from X ℓi , the total number of samples is s · ⌈ (ε2sδ) ⌉.

4
4.1

Upper Bound for Learning Binomial Powers
Preliminaries

To bound the Total Variation Distance of a Binomial and a PBD we shall use the following result
of Roos [27, Theorem 2].
P
Lemma 4.1 (Theorem 2 from [27]). Let X = di=1 be a PBD with probability vector p = (pi )ni=1
and let p ∈ (0, 1). Then
√

e
dtv (X, B(n, p)) ≤

2

p
τ (p)
γ1 (p)2 + 2γ2 (p)
,
,
where
τ
(p)
=

2
p
2np(1 − p)
1 − τ (p)

γj (p) =

n
X
i=1

(p − pi )j

In the special case of bounding the total variation distance of two Binomial distributions we have
the following Corollary of Lemma 4.1
Corollaryq4.1. Let ε < 1/2, n ≥ 1. Let B(n, p), B(n, q) be two Binomial distributions such that
√
|p − q| ≤ ε p(1−p)
then dtv (B(n, q), B(n, p)) ≤ 2 eε.
n

√
Proof. Following the notation of Lemma 4.1 we have γ1 (p)√ ≤ ε np(1 − p), γ2 (p) ≤ ε2 p(1 − p),
√
eε
τ (p) ≤ ε2 /2 + ε2 /(2n) ≤ ε2 . Thus dtv (B(n, q), B(n, p)) ≤ 2(1−ε)
eε when ε < 1/2.
2 ≤ 2
The proofs of the following two facts can be found in Section C.1.
Fact 4.1. For any ε, δ ∈ (0, 1/2), and ψ > 0, let m = ⌈4 ln(1/δ)/(ε2 ψ 2 )⌉ and let p̂ = (s1 + · · · +
sm )/(mn), where s1 , . . . , sm are m independent samples from a Binomial distribution B(n, p). Then,
Pr[p̂ < p + ψerr (n, p, ε)] ≥ 1 − δ, Pr[p̂ > p − ψerr (n, p, ε)] ≥ 1 − δ.

Fact 4.2. Let p ∈ P
[0, 1], ε, δ ∈ (0, 1/2), ψ > 0, k = ⌈ln(4/δ)/ ln(2)⌉, m = ⌈4 ln(⌈2k/δ⌉)/(ε2 ψ 2 )⌉.
For i ∈ [k] let wi = m
i=1 si /(nm), with s1 , . . . , sm m i.i.d. samples from B(n, p). If q̂1 = min1≤i≤k wi ,
q̂2 = max1≤i≤k wi , then Pr [p − ψerr (n, p, ε) < q̂1 < p] ≥ 1−δ, Pr [p < q̂2 < p + ψerr (n, p, ε)] ≥ 1−δ.
The overall number of samples to obtain q̂1 , q̂2 is km = O ln(1/δ)2 /(ε2 ψ 2 ) .
9

4.2

Discussion


We prove here that O 1/ǫ2 samples are sufficient to learn all the powers of a Binomial distribution
B(n, p) with constant probability of success. From Corollary 4.1 follows that to properly learn a
Binomial distribution B(n, p) within totalpvariation distance O (ε) it’s sufficient to approximate
its parameter p with error err (n, p, ε) = ε p(1 − p)/n. Suppose first that the unknown p ≈ 1 −
1/n, then it is not clear at all that sampling from a constant number of powers would suffice to
approximate all the powers. We could first sample from B(n, p) to obtain an approximation p̂1 ≈ p,
but in this case it is useless. On the other extreme, if p ≈ const, then roughly only the first log(n)
powers matter. In fact, it is not too difficult to show that there always exists a constant power, say
′
j, such that p̂1 raised to power j ′ ∈ {j + 1, j + 2, . . . , log(n)} approximates pj well enough. Then we
can sample from each power i = 2, 3, . . . , j separately. But how to solve the large case (p ≈ 1 − 1/n)
and bridge it with the small case (p ≈ const)?
If p is large, a natural idea is to use the approximation p̂1 ≈ p to find a power, ℓ∗ , such that
∗
∗
∗
p̂ℓ1 ≈ const. If we sample from B(n, pℓ ) and obtain an approximation q̂1 ≈ pℓ , then one can argue
∗
that p̂j := q̂1 j/ℓ approximates pj well enough, for j = 2, 3, . . . , ℓ∗ −1; that’s like using approximation
q̂1 backwards. Similarly to the case p ≈ const, it is possible to show that there exists a constant
∗
power k such that q̂1j approximates pjℓ well enough for j ≥ k + 1. The remaining powers jℓ∗ + i, for
∗
j = 2, . . . , k and i = 1, . . . , ℓ∗ − 1, can be approximated by sampling from B(n, pjℓ ) for j = 2, . . . , k
∗
∗
(obtaining q̂j ≈ pjℓ ), and approximating pjℓ +i by q̂j p̂i , where p̂i ≈ pi was found previously, for
i = 1, 2, . . . , ℓ∗ . That’s like using the approximations q̂j forwards, and filling the “gaps” between
powers jℓ∗ and (j + 1)ℓ∗ by p̂i ’s. It is possible to analyze the error of such method but it features
behaviour of five dimensional functions depending on n, p, ε, δ and powers ℓ, and thus is complex.
We show how to completely avoid these complications by generalising our problem to allow
for continuous powers, i.e., we learn B(n, pℓ ) for all ℓ ∈ R++ . Considering the powers to be
in R++ rather than N unveils the symmetric nature of the problem. To see that, notice that
B(n, pℓ ) eventually converges to “deterministic” distributions since limℓ→∞ B(n, pℓ ) = B(n, 0) and
limℓ→0 B(n, pℓ ) = B(n, 1). We are able to treat uniformly the backwards and forwards cases which
now correspond to powers smaller and greater than one, and there is no need to fill the “gaps”
now. This leads to an elegant algorithm that interestingly will need to sample from only two different powers. By Corollary 4.1, the problem of approximating the powers B(n, pℓ ) reduces to
approximating pℓ for all ℓ ∈ (0, +∞). We will explain the main idea of our algorithm. Suppose
that p = 1 − 1/n + c, where c < 1/n. We split the decimal representation of p in two parts. The
first part consists of roughly log n 9’s determining the p’s closeness to 1 (or to 0 in the symmetric
case p ≈ 0) and the second part, referred to as a “constant” part, corresponds to c. The decimal
458382
representation of such a p could for example be: p = 0. 99
. . . 9}
| {z } . It is clear that, for
| {z
# log n

“constant” part

the first powers, the bits of p’s “constant” part are insignificant but for higher powers ℓ these bits
should be learned in order to have an ε-approximation of B(n, pℓ ) in total variation distance. Using
Fact 4.1 to approximate p = 1 − 1/n + c using
p samples from the first power we see that we can
obtain an estimate p̂ with precision roughly p(1 − p)/n ≈ 1/n. Thus, we learn the first log n 9’s
of the representation of p. To learn the p’s “constant” part we have to sample from a higher power
to be able to distinguish the “higher” bits, given the error of Fact 4.1. To learn the “constant” part
of p in our example one should sample roughly from the n-th power. This idea suggests that to
approximate p sufficiently for all powers ℓ ∈ (0, +∞), we have to obtain a good approximation of
power −1/ log(p), corresponding to the number of initial 0’s or 9’s in the decimal representation
of p and an approximation of the “constant” part c. Our Algorithm 2 follows this intuition. The
proof of our upper bound is based on Lemmas 4.2 and 4.3. Lemma 4.3 shows that sampling from
10

the first power suffices to obtain an approximation â = −1/ log(p̂) of a = −1/ log(p). Lemma
4.2

ℓ
unveils the precision up to which one should approximate p to satisfy the error err n, p , ε for all
ℓ ∈ (0, +∞), and it is the key to handle the multidimensional analysis we face. Algorithm 2 draws

only O 1/ε2 samples from two powers, so the overall sampling (and time) complexity is O 1/ε2 .
Note that ψ(pâ ) in Algorithm 2 is a universal constant, as we prove below.
Algorithm 2 Binomial Powers
Input : O(ln(1/δ)2 /ε2 ) samples from the powers of B(n, p).
Output : â, q̂1 , q̂2 .
1: Draw O(ln(1/δ)/ε2 ) samples from B(n, p) to obtain the approximation p̂ using Fact 4.1.
2: Let â ← −1/ ln(p̂).

3: Draw O ln(1/δ)2 / ε2 ψ(pâ )2 samples from B(n, pâ ) to get estimations q̂1 , q̂2 of p, q̂1 ≤ p ≤ q̂2 , using Fact 4.2.
4: return â, q̂1 , q̂2

q

p
1−p

ln(1/p), where D ≈ 1.24263. Let p, q̂1 , q̂2 ∈ (0, 1) with q̂1 < p <

q̂2 . Then if p − q̂1 ≤ ψ(p)err (n, p, ε) , q̂2 − p ≤ ψ(p)err (n, p, ε) it holds pl − q̂1l ≤ err n, pl , ǫ for all
l ∈ (1, +∞) and q̂2l − pl ≤ err n, pl , ǫ for all l ∈ (0, 1).
Lemma 4.2. Let ψ(p) = D

Proof. As a direct consequence of the Mean Value Theorem applied to the mapping x 7→ xl we
obtain pl − q̂1l ≤ lpl−1 (p − q̂1 ) for l ∈ (0, 1) and q̂2l − pl ≤ lpl−1 (q̂2 − p) for l ∈ (1, +∞). Next we find
a function u(p) such that for all l > 0
u(p)lpl−1 err (() n, p, ε) ≤ err (() n, pl , ε)
r
r
p(1 − p)
pl (1 − pl )
l−1
u(p)lp
≤
n
n
2
2 2l−2
l
u (p)l p
p(1 − p) ≤ p (1 − pl )
u2 (p) ≤
Let f (l) =

p−l −1
,
l2

f ′ (l) =

(3)

p p−l − 1
1 − p l2

g(p) = 6 − 6pl + 4l ln p + l2 (ln p)2 . Then

p−l (−2 + 2pl − l ln p)
l3

p−l (6 − 6pl + 4l ln p + l2 (ln p)2 )
l4
l
2l(2 − 3p + l ln(p))
g′ (p) =
.
p
f ′′ (l) =

Set pl = y and notice that the maximum of the concave function y 7→ 2 − 3y + ln(y) is 1 − ln(3) < 0.
Thus g is a continuous, strictly decreasing function of p and limp→1 g(p) = 0. Therefore g(p) > 0
for all p ∈ (0, 1). Resultantly, f is a convex function of l and attains its minimum at ¯l = − lnCp (the
C
2
root of f ′ (l) = 0), where C = 2 + Wn (−2/e2 )5 ≈ 1.59362. It’s minimum value is f (¯l) = e C−1
2 (ln p) .
√
q
eC −1
p
ln(1/p), D = C
ensures that inequality 3 holds.
Choosing u(p) = D 1−p


p
Lemma 4.3. Let ε ∈ (0, 1/6), n ≥ 1, and p ∈ (τ, µ) where τ = 21 1 − 1 − 36ε2 /n ≤ ε2 /n,


p
µ = 21 1 + 1 − 36ε2 /n ≥ 1 − ε2 /n. Moreover, let a, â ∈ R++ such that pa = p̂â = 1/e. If
|p − p̂| ≤ err (n, p, ε) then
5

1
e2

≤ pâ ≤

1
.
e3/2

Wn denotes the Lambert W function.

11

Proof. Let h = err (n, p, ε). The Taylor approximation of f (x) = ln(x) for x ∈ (p − h, p + h) is
ln(x) = ln(p) + R0 (x). Since |f ′ (x)| = 1/x ≤ 1/|p − h|, we obtain
h
1
1
R0 (x)
≤
≤
=
ln p
| ln p| |p − h|
|(1 − p)p/h + p − 1|

√

1
p
n

ε

.

p(1 − p) + p − 1

√ p
n
To upper bound the above quantity by 1/2 we find the feasible
set
of
the
inequality
ε

p(1 − p) ≥ 3

p
p
1
1
2
2
which assuming that ε < 1/6 gives 2 1 − 1 − 36ε /n ≤ p ≤ 2 1 + 1 − 36ε /n . Therefore,
for every p̂ ∈ (p − h, p + h) we have

1
ln p̂
3
1
1
2 1
2
1
1
≤
≤
⇔ −2
≥−
≥−
⇔ 2a ≥ â ≥ a ⇔ 2 ≤ pâ ≤ 3/2 .
2
ln p
2
ln p
ln p̂
3 ln p
3
e
e

⊔
⊓
4.3

The Proof of Theorem 1.5

Corollary 4.1 implies that to approximate B(n, pℓ ) within total variation distance ε we need an
approximation p̂ℓ of pℓ with |pℓ − p̂ℓ | ≤ err n, pℓ , ε . We prove that Algorithm 2 outputs approximations q̂1 , q̂2 of p satisfying this bound. We use Lemma 4.3 to show that 1/e2 ≤ pâ ≤ 1/e3/2 , and
thus, ψ(pâ ) ≥ ψ(1/e2 ) = 0.983226. Using Fact 4.2 we draw O ln(1/δ)2 /(ε2 ) to obtain estimates
q̂1 , q̂2 such that Pr [p̂ − err (n, p, ε) < q̂1 < p] ≥ 1 − δ/2, Pr [p < q̂2 < p + err (n, p, ε)] ≥ 1 − δ/2,
and thus the probability of success of obtaining both q̂1 , q̂2 is at least 1 − δ. Having obtained the
estimates q̂1 , q̂2 the result follows directly from Lemma 4.2.
⊔
⊓
Remark 4.1. Algorithm 2 can be easily modified to the case where the powers we are allowed to
sample from are natural numbers, ℓ ≥ 1. In this case Notice that when p ≤ e−C ≤ 0.2, then
the function f of Lemma 4.2 is minimized for ℓ = 1, since f is convex and the position of its
−1
global minimum is ℓ̄ ≤ 1. So it suffices to choose u(p) = p(p1−p−1) = 1 and we can learn all powers
ℓ ≥ 1 using an estimation p̂ obtained by sampling from the first power using Fact 4.1. If p ≥ 0.2
2 ≤ p⌈â⌉ ≤ 1/e3/2 , thus
then we can simply run Algorithm 2 with ⌈â⌉ instead of â. Then, 0.2/e

ψ(p) ≥ ψ(0.2/e2 ), which means that Algorithm 2 uses O ln(1/δ)/ε2 samples to learn all powers
ℓ ≥ 1.
Remark 4.2. Algorithm 2 could use the approximation p̂ ≈ p from Fact 4.1 instead of approximations q̂1 , q̂2 of p, which imply a unified analysis by the Mean Value Theorem in Lemma 4.2.

5
5.1

Lower Bounds for Learning Functions of Sequences of Distributions
Preliminaries

The Kullback-Leibler divergence of two probability measures P, Q is
 
Z
P
dP.
Dkl (P kQ) = log
Q
Moreover, the Hellinger distance of P, Q with respect to another probability measure µ is
s
!2
Z s
dP
dQ
1
dhel (P, Q)2 =
dµ.
−
2
dµ
dµ
We shall use the well known decoupling identities of Hellinger distance and Kullback-Leibler divergence, for proofs see e.g. [19, Chapter 13].
12

Fact 5.1 (Hellinger Decoupling Identity). Let P = P1 × . . . × Pm and Q = Q1 × . . . × Qm be
two product distributions. Then
m 

Y
1 − dhel (Pi , Qi )2 .
dhel (P, Q)2 = 1 −
i=1

Fact 5.2 (KL-Divergence Decoupling Identity).

Dkl (P1 × . . . × Pk kQ1 × . . . × Qk ) =
5.2

k
X
i=1

Dkl (Pi kQi ) .

The definition of Minimax Risk for Sequences of Distributions

We give first notation for a definition of the minimax risk for learning functions of sequences of
distributions. Bellow we use calligraphic letters for sequences of distributions and gothic for sets
of sequences of distributions. Let P be a family of sequences of distributions, indexed by the
set I. Since we can sample from every distribution Pi of P we have the sample vector X m =
(X1,1 , . . . , X1,m1 , . . . , Xk,1 , . . . , Xk,mk ) where the i-th group of mi samples is drawn from Pi , and
define the multi-index m = (m1 , . . . , mk ). All samples are independent, so X m follows the |m|-fold
product distribution P m = P1m1 × P2m2 × . . . × Pkmk . Let θ : P → Θ be a function of sequences of
P to be estimated. Let θ̂ : X m → Θ be an estimator of θ, and ρ : Θ × Θ → R+ be a semimetric on
the space Θ. Let d denote a metric in the space of distributions. The natural choice for d on the
space of sequences of distributions is to define d(P, Q) = supi∈I d(Pi , Qi ). For example we define
the TVD of the two sequences to be dtv (P, Q) = supi∈I dtv (Pi , Qi ).
Definition 5.1. In the above setting we define the minimax risk to be
h 
i
MN (θ(P), ρ) := inf sup inf EP m ρ θ̂(X m ), θ(P) .
θ̂ P∈P |m|=N

(4)

There, the infimum over all multi-indices m such that |m| = N corresponds to the optimal selection
of samples from each Pi . Definition 5.1 captures the fact that the estimator θ̂ can be adaptive in
the sense that after the adversarial sequence of distributions is picked, the optimal algorithm for
the problem will choose the best distributions from the sequence to draw samples from.
Let us give some intuitions about this definition referring to Algorithm 2. This algorithm follows
this definition, in that, before seeing the input data, it samples from the first power, which then
allows it to decide from which further power to sample. Note, that the extension of this algorithm
to very large p (see Appendix C.2) shows that the first stage of deciding from which further power
to sample can be non-trivial and requires binary search. These operations of deciding from which
powers to sample correspond to the inner “inf” in the definition.
5.3

Le Cam and Fano Extensions

Let V be a finite set of indices and let FV ⊆ P be a set of |V| sequences indexed by V. Let V be
the random variable representing a uniform at random choice of a sequence of FV . Conditioned
on the choice V = v, the random sample X m is drawn from the |m|-fold product distribution Pvm .
Let ν m denote the joint distribution of V, X m . Let Ψ : X m → V be a testing function, namely
Ψ takes samples from the unknown sequence PV and outputs an index u ∈ V corresponding to
a candidate sequence of distributions. We remark that the following techniques are standard and
similar derivations can be found in [32], [28], and the very good lecture notes of John Duchi [19]. We
are now ready to prove the standard reduction from estimation to testing using our new definition
of minimax risk.
13

Proposition 5.1. Let FV ⊆ P be a family of sequences of distributions indexed by v ∈ V such that
ρ (θ(Pv , Pu )) ≥ 2δ for all Pv , Pu ∈ FV , where, v 6= u ∈ V and δ > 0. The minimax risk defined in
Definition 5.1 has lower bound
MN (θ(P), ρ) ≥ δ inf inf ν m (Ψ (X m ) 6= V ) .
m=|N | Ψ

Proof. Recall the definitions and the notation from Section 5 Fix an estimator θ̂. To simplify
notation we shall use θ for θ(P) when the sequence P is clear from the context, and θv for θ(Pv ).
From Markov’s inequality we have




h
i
(5)
EPvm ρ(θ̂, θ) ≥ δ Pvm ρ(θ̂, θ) ≥ δ = δ ν m ρ(θ̂, θ) ≥ δ|V = v

Now we proceed by defining the testing function Ψ (X m ) := argminv∈V {ρ(θ̂, θv )}. Using the fact
that ρ(θv , θu ) ≥ 2δ for every v 6= u ∈ V we have that ρ(θ̂, θv ) ≤ δ ⇔ Ψ (θ̂) = v. Now to bound the
minimax risk
h 
i
MN (θ(P), ρ) = inf sup inf EP m ρ θ̂(X m ), θ(P)
θ̂ P∈P |m|=N

h
i
X 1
inf EPvm ρ(θ̂, θv )
≥ inf
θ̂ v∈V |V| |m|=N


X 1
m
ρ(θ̂, θv ) ≥ δ | V = v
inf ν
≥ δ inf
θ̂ v∈V |V| |m|=N


X 1
ν m ρ(θ̂, θv ) ≥ δ | V = v
= δ inf inf
|V|
|m|=N θ̂
v∈V

= δ inf inf ν m (Ψ (X m ) 6= V ) ,
|m|=N Ψ

where for the first inequality we use the fact that, the supremum of a set is larger than the average
of a subset of the set, for the second inequality we use (5), and for the second equality we use the
fact that inf(A + B) = inf(A) + inf(B) for any nonempty sets A, B. The last equality follows from
Bayes’ Theorem.
⊔
⊓
Using Proposition 5.1 we prove an extension of Le Cam’s method for sequences of distributions.
Lemma 5.1. Let P, Q ∈ P and δ > 0 such that ρ (θ(P), θ(Q)) ≥ 2δ then after N observations
(samples) the minimax risk has lower bound
√ q
δ
MN (θ(P), ρ) ≥ (1 − 2 1 − (1 − dtv (P, Q))N ).
2
Proof. Since we are doing binary hypothesis testing and we want to distinguish the distributions P
and Q the random variable V now represents the uniform choice over the measures P and Q. We
define the probability measure µ to be the joint distribution of X m and V . The probability that
a testing algorithm Ψ outputs a wrong result in the binary testing problem is µ(Ψ (X m ) 6= V ) =
1 m
1 m
m
2 P (Ψ (X ) 6= 1) + 2 Q (Ψ (X) 6= 2). Le Cam’s inequality states that
inf {P m (Ψ (X m ) 6= 1) + Qm (Ψ (X m ) 6= 2)} = 1 − dtv (P m , Qm )
Ψ

14

(6)

Using (6) and Proposition 5.1 we obtain
δ
δ
inf (1 − dtv (P m , Qm )) =
MN (θ(P), ρ) ≥
2 |m|=N
2

m

m

!

1 − sup dtv (P , Q )
|m|=N

Notice that
v
u
N 

u
Y
m
m
1 − dhel (Pi , Qi )2
sup dtv (P , Q ) ≤ 2 sup t1 −
√

|m|=N

|m|=N

√

s

√

s

i=1



2

≤ 2 1 − 1 − sup dhel (Pi , Qi )
i∈I



≤ 2 1 − 1 − sup dtv (Pi , Qi )
i∈I

√ q
= 2 1 − (1 − dtv (P, Q))N
where we used the inequality dhel (P, Q)2 ≤ dtv (P, Q) ≤

√

N

N
(7)

2 dhel (P, Q) and Fact 5.1.

⊔
⊓

Lemma 5.1 has an intuitive explanation: to distinguish two sequences of distributions it suffices to
find an index i ∈ I such that dtv (Pi , Qi ) is large. Since our Definition 5.1 of the minimax risk allows
the algorithm to choose the element of the sequence to draw samples from, clearly, the hypothetical
optimal algorithm of Definition 5.1 will choose to sample from the index where the TVD of the
two tested sequences is largest. Therefore, to obtain a lower bound for the testing (and thus for the
estimation) problem we need to find two sequences of distributions such that all their elements are
close in TVD but their parameters are far.
We now state Fano’s Method modified to lower bound the minimax risk of Definition 5.1.
Lemma 5.2. Let P be a set of sequences of distributions. Let FV ⊆ P be a subset of P indexed
by v ∈ V such that ρ (θ(Pv ), θ(Pu )) ≥ 2δ for all Pv , Pu ∈ FV , where, v 6= u ∈ V and δ > 0. The
minimax risk from Definition 5.1 has lower bound
1
MN (θ(P), ρ) ≥ δ 1 −
ln |V|

!!

N sup Dkl (Pv kPu ) + ln 2
v,u∈V

.

Proof. Using Proposition 5.1 and Fano’s inequality (see e.g. [6]) we can lower bound inf Ψ ν m (Ψ (X m ) 6= V ),
and therefore




sup|m|=N I(V ; X m ) + ln 2
I(V ; X m ) + ln 2
=δ 1−
,
MN (θ(P), ρ) ≥ δ inf
1−
ln |V|
ln |V|
|m|=N
where I(V ; X m ) is the mutual information of V, X m . To upper bound the mutual information
I(V ; X m ) we use the standard inequality
I(V ; X m ) ≤

1 X
Dkl (Pvm kPum ) ≤ sup Dkl (Pvm kPum ) ,
|V|2
v,u∈V
v,u∈V

15

which can be found in [4] or [32] or page 149 of [19] We have
sup I(V ; X m ) ≤ sup sup Dkl (Pvm kPum )

|m|=N

|m|=N v,u∈V

= sup sup Dkl
|m|=N v,u∈V

= sup sup

k
X

v,u∈V m=|N | i=1

≤N

sup
v,u∈V,i∈I



m1
Pv,1

× ... ×

mk
m1
kPu,1
Pv,k

× ... ×

mk
Pu,k



mi Dkl (Pv,i kPu,i )

Dkl (Pv,i kPu,i )

= N sup Dkl (Pv kPu ) ,
v,u∈V

where to obtain the second equality we use Fact 5.2
5.4

Applications

Application 1: Parameter Estimation for PBDs (Theorem 1.3). Since we are estimating
the parameters of the PBD, Le Cam’s method is well suited for this problem. To prove Theorem 1.3,
using Lemma 5.1, we extend the argument given in Proposition 15 of [15] to prove that Ω(21/ε )
samples are required even in the case where we are allowed to sample from the powers of the PBDs.
The key idea is that the instance used in their proof suffices to prove that the TVD of all the
powers is O(2−1/ε ) whereas the separation of the parameter vector is Ω(ε).
Using the notation introduced in the beginning of this section we denote by P the sequence
of the powers of a PBD and since we want to estimate the parameters pi we have θ(P) = p. Our
metric in the space of vectors, (0, 1)n , is ρ(p, p̂) = kp − p̂k∞ since we want to approximate the vector
p in additive error at most ε.
We will follow the argument given in the proof of Proposition 15 in [15] and therefore we
will present it fully for the sake of completeness. We set the length n of the PBD vector to be
n = Θ(log(N/ε)) where N represents the number of samples in the minimax risk definition. We
:= (1 + cos( 2πj+π
take pj := (1 + cos( 2πj
n ))/8, qj
n ))/8, j ∈ [n]. Then for j = n/4 + O(1), we have that
2π(n−j)
2πi+π
.
|pi − pj | = Ω(1/ log(N/ε)) since for all i, n is at least Ω(1/ log(N/ε)) from 2πi
n and
n
Observe that p1 , . . . , pn resp. q1 , . . . , qn are roots of the Chebyshev’s polynomials, (Tn (8x − 1) −
1), resp. (Tn (8x − 1) + 1), where Tn is the n-th Chebyshev polynomial. Since these polynomials
agree
coefficients except from their constant terms, the Newton-Girard identities imply that
Pn inl all P
n
l
p
=
i
i=1
i=1 qi for all l ∈ {1, 2, . . . , n − 1} and moreover, for l ≥ n it is easy to see that
P
3l ( ni=1 (pli − qil )) ≤ n(3/4)n = log(N/ε)(3/4)log(N/ε) . For small enough ε using Lemma 9 of [15]
we have that dtv (P1 , Q1 ) ≤ c/N for some constant c. We will show that this in fact is true for all
powers Ps ,P
Qs of thesePtwo PBDs, To show this let us fix any power s ∈ {1, 2, . . . , n}. Then, we
n
sl
have that ni=1 psl
assuming that s ≤ n − 1. Moreover,
i =
i=1 qi , for any l = 1, 2, . . . , ⌊(n − 1)/s⌋
Pn
3l
3sl
3 n
sl
l
when l ∈ {⌊(n − 1)/s⌋ + 1, ⌊(n − 1)/s⌋ + 2, . . .}, we have 3 ( i=1 (psl
i − qi )) ≤ n 4sl ≤ n 4sl ≤ n( 4 ) ,
where the last inequality holds because sl ≥ n. It is easy to see that the same hold when s = n,
and once more by Lemma 9 in [15], dtv (Ps , Qs ) ≤ c/N . Since the separation of the parameters is
Ω(1/ log(N/ε)) and the Total Variation distance of the two sequences is less that c/N we can use
Lemma 5.1 to obtain a minimax lower bound rate of 1/ log(ε/N ). Notice that an upper bound of
c/N on the total variation distance of the two sequences implies a lower bound of Ω(δ) for the
minimax risk. Therefore, since we need to approximate the parameters to additive error ε, MN < ε
implies that the number of samples N should be Ω(21/ε ).
16

Application 2: Learning Powers of Binomials. (Theorem 1.6) We use Lemma 5.2 to prove a
matching lower bound of Ω(1/ε2 ) for the problem of learning the powers of a Binomial distribution.
Its quite technical proof (cf. Section D), is only sketched here.
Using the notation of Lemma 5.2 and since we do density estimation, we have θ(P) = (fi )i∈N .
ˆ
Therefore we will
√ use the metric ρ(θ(P), θ(Q)) = dtv (P, Q) = supi∈N dtv (fi , fi ).
Let δ = Θ(1/ n N ). Let p1 = 1/2, p2 = 1/2 + δ/4, p3 = 1/2 + δ/2. Let P1 = (B(n, (1/2)i ))i∈N ,
P2 = B(n, (1/2 +√δ/4)i )i∈N , P3 = B(n, (1/2 + δ/2)i )i∈N . The TVD of the first powers of these
Binomials is Ω(1/ N ). To see this notice that since the variance of the Binomials is O(n) we can
approximate the Binomials with Normals with insignificant error. When their variances are close,
the TVD of two Normals is roughly proportional
√ to the difference of their means divided by their
“common” standard deviation, which is Ω(1/ N ). Thus we obtain our lower bound for the TVD.
We then prove an upper bound for the KL-divergence between all powers, namely Dkl (P1 kP3 ) =
O(1/N ). It’s easy to see that this upper bound holds for the first power. To prove that it holds for
all the powers notice that Dkl (B(n, p)kB(n, q)) is an increasing function of |p − q| (for a proof see
Proposition D.2). Thus, since the distances of the pi ’s of our three Binomials roughly decrease for
higher powers the KL-Divergence of the first power is roughly
√ an upper bound for Dkl (P1 kP3 ). Now,
applying Lemma 5.2 we have that MN (θ(P), ρ) = Ω(1/ N ), which in turn implies that to have
an estimator that approximates all the powers in distance less than ǫ we need MN (θ(P), ρ) < ǫ
and therefore the number of samples N should be Ω(1/ε2 ).
⊔
⊓

6

Upper Bound for Parameter Estimation

Newton’s identities, a.k.a the Newton-Girard formulae, give relations between power sums and
elementary symmetric polynomials of variables x1 , ..., xn . In that setting, the kth power sum is
sk (x1 , . . . , xn ) = xk1 + · · · + xkn . The kth elementary symmetric polynomial ek (x1 , . . . , xn ) is the
sum of all distinct products of k distinct variables. Newton’s identities allow us to compute the
elementary symmetric
sums exactly. Moreover, the polynomial
Q polynomials if we know the power P
n
n+k e
k
with roots xi , i.e., ni=1 (x − xi ), may be expanded as
n−k x . Thus, if we know
k=0 (−1)
the power sums s1 (x1 , . . . , xn ), . . . , sn (x1 , . . . , xn ) exactly, we can first find the coefficients of the
elementary symmetric polynomials and then compute the roots x1 , . . . , xn with an arbitrarily good
accuracy. A similar approach was used in [12] to derive sparse covers for PBDs.
In this section we provide the analysis of the “noisy” version of Newton’s identities. Given query
access to PBD powers, we can obtain good estimations of the power sums sk (p1 , . . . , pn ) using a
reasonable number of samples, since the expectations of PBD powers are the power sums of the
unknown probabilities p1 , . . . , pn . An intriguing question is to which extent these “noisy” power sum
estimations can be used to recover the actual values of p1 , . . . , pn within sufficiently good accuracy.
In this Section we answer this question by providing an upper bound on the sampling complexity
of estimating the parameters of a PBD using samples from its powers. This upper bound matches
the corresponding lower bound of Theorem 1.3.
6.1

Preliminaries

Let x ∈ Rn be a P
vector, and A = (Aij )i,j∈[n] be a n × n matrix. Then kxk∞ = maxi∈[n] |xi |,
kAk∞ = maxi∈[n] j=1 aij , |x| = (|xi |)i∈[n] , |A| = (|Aij |)i,j∈[n] . We use “≤” in A ≤ B to denote
element-wise inequality of the matrices A, B, namely A ≤ B ⇔ Aij ≤ Bij for all i, j ∈ [n].
To compute the sensitivity of the solution of a linear system Ax = b to perturbations of A, b
we shall use Theorem 7.4 from [21], formulated bellow as Lemma 6.1.
17

Lemma 6.1 (Theorem 7.4 from [21]). Let Ax = b and (A+∆A)y = b+∆b, where |∆A| ≤ u E
and |∆b| ≤ u f , and assume that u
k |A−1 | E k < 1, where k · k is an absolute norm. Then
k |A−1 | (E|x| + f ) k
u
kx − yk
≤
−1
kxk
1 − u k |A | E k
kxk
and for the ∞-norm this bound is attainable to first order in u.
To approximate the roots of the univariate polynomial P (x) we use the nearly optimal root
finding algorithm of Pan [26](Theorem 2.1.1) formulated below as Lemma 6.2.
P
Q
Lemma 6.2 (Theorem 2.1.1 from [26]). Let P (x) = ni=0 ci xi = cn ni=1 (x − pi ), cn 6= 0, be
a polynomial of degree n such that all its complex roots satisfy |pj | ≤ 1 for all j . Let b be a fixed real
number, b ≥ n log n. Then complex numbers p̂j can be computed by using O (n log2 n)(log2 n + log b)
arithmetic operations performed with the precision of O (b) bits such that |p̂j − pj | < 22−b/n for
j = 1, . . . , n.
The following simple bound on the coefficient vector of a polynomial with roots in [−1, 1] will
be useful.
Fact 6.1. If all roots of a monic
polynomial P = xn + an−1 xn−1 + ... + a0 of degree n lie in the

interval [−1, 1] then |ak | ≤ nk ≤ 2n .
Proof. Using Vieta’s formulae we have

an−k = (−1)k

X

x i1 x i2 . . . x ik

1≤i1 <i2 <...<ik ≤n

Therefore, |an−k | is maximum when all xi are 1 and therefore |an−k | ≤
6.2

The proof of Theorem 1.4

n
k

=

n 
n−k .

We denote by Pj the j-th power of the PBD with probability vector p, namely Pj is the PBD with
Q
probability vector pj = (pji )ni=1 . Let P (x) = xn + cn−1 xn−1 + . . . + c0 = ni=1 (x − pi ) be the monic
polynomial of degree n. Notice that the mean value of Pj denoted by µj equals the j-th Newton
P
sum of the roots of P (x) since µj = ni=1 pji . Given that P (x) is monic, the coefficients of P (x)
and the means µ1 , µ2 , . . . , µn satisfy the following linear system of Newton’s identities:
µj +

j−1
X

cn−i µj−i + jcn−j = 0,

j = 1, 2, . . . , n

i=1

The system has the following matrix form, where we omit zero elements.


 

1
cn−1
−µ1
 µ1
 cn−2   −µ2 
2


 

 µ2 µ1 3
 cn−3   −µ3 


=
 ⇔ Ac = b
 ..
.. . . . .   ..   .. 
 .
. .  .   . 
.
µn−1 µn−2 . . . µ1 n
c0
−µn

(8)

Using the linear system 8 Algorithm 3 retrieves an approximation of the coefficient vector c
and then finds the roots of the corresponding univariate polynomial.
18

Algorithm 3 Parameter Estimation
Input: 2O(n max(log(1/ε),log(n)) samples from the powers Pj , j ∈ [n].
Output: An additive ε approximation of p.
1: Using A of Lemma 3.1 draw 2O(n max(log(1/ε),log n)) samples from each power Pj to obtain the approximations µ̂j
of µj .
2: Solve the system 8 and obtain ĉ.
3: P
Use Pan’s Algorithm of Lemma 6.2 to compute approximations p̂j to all the roots of the polynomial P (x) =
n
i
i=1 ci x .
4: return p̂.

We now proceed to the proof of Theorem 1.4.
Starting from the last step of root finding with Pan’s Algorithm of Lemma 6.2, we have that, to
obtain ε-approximations of the roots of the polynomial P (x) we need to obtain an approximating
vector ĉ of the coefficient vector c of P (x) such that
kc − ĉk∞ = 2O(−n max(log(1/ε),log(n)) .

(9)

Next, we proceed to computing the precision needed for the means µj so that the system of
Newton Identities (8) can be solved to provide a solution satisfying (9). Since in our setting the
error of approximating the j-th mean is proportional to the standard deviation of the j-th powers,
the errors E, f of Lemma 6.1 are
 
 




1
σ1
1
σ1
1
 σ2 
 σ2 σ1
  √  

 √ 1 1

 

 σ3 


n
E= . . .
f
=
≤

  ≤ n 1


. .
 .. 
 .. 
 .. .. . . . 
 .. .. . . 
.
 . 
1 1 ... 1
σn σ2 . . . σ1
σn
1

Since it holds µj ≤ n and it follows that Aij ≤ n. Since A is lower triangular, det(A) = n!, and
it holds that det(A) ≥ Mij , where Mij is the determinant of of (n − 1) × (n − 1) submatrix of A
after deleting row i and column j. It follows that |A−1 |ij ≤ 1. Moreover, since
the solution vector x
n 
corresponds to the coefficients of P (x) from Fact 6.1 it follows |x|i ≤ n−i . Using these inequalities
we bound





1
1
1
 1 1

 √ 2 1
√ 
1 1




n
|A−1 ||E| ≤ n  . . .
=





.
.
.
.
 .. .. . .   .. .. . . . 
 .. .. . . . 
1 1 ... 1

1 1 ... 1

n n − 1 ... 1

Moreover, |A−1 ||f | ≤ (n 2n . . . n2 )T . Combining the above inequalities we can estimate the
condition of A.


n


√
√ X
n
−1
−1
(n − i)
+ nn = n3/2 (2n−1 + 1) = O n3/2 2n
k |A | |A| |c| + |A | |b| k∞ ≤ n
n−i
i=0


k|A−1 ||E|k∞ = O n5/2

Thus, from Lemma 6.1 we obtain the following absolute error bound with respect to the ∞-norm


kc − ĉk∞ ≤ u O n3/2 2n
19

Since we need to run Algorithm A of Proposition 3.1 n times to obtain approximations µˆj such
that |µj − µˆj | ≤ uj σj for all j ∈ [n] with
 probability at least 1 − δ it follows from the union bound
that we have to draw O log(1/n)n/u2 from the powers Pj , j ∈ [n]. Therefore, since uO n3/2 2n
should satisfy (9) we conclude that overall we need 2O(n max(log(1/ε),log(n)) samples.

References
1. J. Acharya and C. Daskalakis. Testing Poisson Binomial Distributions. In Proc. of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA ’15), pages 1829–1840, 2015.
2. M.-F. Balcan and N.J.A. Harvey. Learning submodular functions. In Proc. of the 43rd ACM Symposium on
Theory of Computing (STOC ’11), pages 793–802, 2011.
3. L. Birgé. Estimation of unimodal densities without smoothness assumptions. Annals of Statistics, 25(3):970–981,
1997.
4. Lucien Birgé. Approximation dans les espaces mtriques et thorie de l’estimation. Zeitschrift fr Wahrscheinlichkeitstheorie und Verwandte Gebiete, 65(2):181–237, December 1983.
5. J.T. Chu. On bounds for the normal integral. Biometrika, 42:263–265, 1955.
6. Thomas M. Cover and Joy A. Thomas. Elements of Information Theory 2nd Edition. Wiley-Interscience, Hoboken,
N.J, 2 edition edition, July 2006.
7. C. Daskalakis, A. De, G. Kamath, and C. Tzamos. A size-free CLT for Poisson multinomials and its applications.
In Proc. of the 48th ACM Symposium on Theory of Computing (STOC ’16), pages 1074–1086, 2016.
8. C. Daskalakis, I. Diakonikolas, R. O’Donnell, R.A. Servedio, and L.-Y. Tan. Learning sums of independent integer
random variables. In Proc. of the 54th IEEE Symposium on Foundations of Computer Science (FOCS ’13), pages
217–226, 2013.
9. C. Daskalakis, I. Diakonikolas, and R.A. Servedio. Learning Poisson Binomial Distributions. Algorithmica,
72(1):316–357, 2015.
10. C. Daskalakis, G. Kamath, and C. Tzamos. On the Structure, Covering, and Learning of Poisson Multinomial
Distributions. In Proc. of the 56th IEEE Symposium on Foundations of Computer Science (FOCS ’15), pages
1203–1217, 2015.
11. C. Daskalakis and C.H. Papadimitriou. Approximate Nash equilibria in anonymous games. J. Economic Theory,
156:207–245, 2015.
12. C. Daskalakis and C.H. Papadimitriou. Sparse Covers for Sums of Indicators. Probability Theory and Related
Fields, 162(3):679–705, 2015.
13. C. Daskalakis and V. Syrgkanis. Learning in Auctions: Regret is Hard, Envy is Easy. In Proc. of the 57th IEEE
Symposium on Foundations of Computer Science (FOCS ’16), 2016.
14. I. Diakonikolas. Learning structured distributions. In P. Bühlmann, P. Drineas, M. Kane, and M.J. van der Laan,
editors, Handbook of Big Data, pages 267–283. Chapman and Hall/CRC, 2016.
15. I. Diakonikolas, D.M. Kane, and A.Stewart. Properly learning poisson binomial distributions in almost polynomial
time. In Proceedings of the 29th Conference on Learning Theory, (COLT’16), pages 850–878, 2016.
16. I. Diakonikolas, D.M. Kane, and A. Stewart. Optimal learning via the fourier transform for sums of independent
integer random variables. In Proceedings of the 29th Conference on Learning Theory, (COLT’16), pages 831–849,
2016.
17. I. Diakonikolas, D.M. Kane, and A. Stewart. The Fourier Transform of Poisson Multinomial Distributions and
its Algorithmic Applications. In Proc. of the 48th ACM Symposium on Theory of Computing (STOC ’16), pages
1060–1073, 2016.
18. D.P. Dubhashi and A. Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009.
19. John Duchi. Stats311, Lecture Notes. URL: https://stanford.edu/class/stats311/Lectures/full_notes.pdf.
20. V. Feldman and P. Kothari. Learning coverage functions and private release of marginals. In Proc. of the 27th
Conference on Learning Theory (COLT 2014), volume 35 of JMLR Proceedings, pages 679–702, 2014.
21. Nicholas J. Higham. Accuracy and Stability of Numerical Algorithms. SIAM: Society for Industrial and Applied
Mathematics, Philadelphia, 2nd edition edition, August 2002.
22. Kiyosi It and Henry P. jr Mckean. diffusion processes and their sample paths. springer, berlin ; new york, 1996
edition edition, February 1996.
23. M. Li and P.M.B. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications, 3rd Edition. Texts
in Computer Science. Springer, 2008.
24. Qi-Man Shao Louis H.Y. Chen, Larry Goldstein. Normal Approximation by Stein’s Method. Springer, 2010.
25. R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

20

26. Victor Pan. Univariate polynomials: Nearly optimal algorithms for numerical factorization and rootfinding.
Journal of Symbolic Computation, 33(5):701-733, 2002.
27. B. Roos. Binomial Approximation to the Poisson Binomial Distribution: The Krawtchouk expansion. Theory of
Probability and its Applications, 45(2):328–344, 2000.
28. Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer, New York ; London, 1 edition
edition, November 2008.
29. Abraham Wald. Contributions to the Theory of Statistical Estimation and Testing Hypotheses. The Annals of
Mathematical Statistics, 10(4):299–326, December 1939.
30. Yuhong Yang and Andrew Barron. Information-theoretic determination of minimax rates of convergence. The
Annals of Statistics, 27(5):1564–1599, October 1999.
31. Zhen-Hang Yang and Yu-Ming Chu. On approximating Mills ratio. Journal of Inequalities and Applications,
2015:273, September 2015.
32. Bin Yu. Assouad, Fano, and Le Cam. In Festschrift for Lucien Le Cam, pages 423–435. Springer, New York,
NY, 1997.

A

Appendix – Lower Bound for Learning PBD Powers: Separated Case

A.1

The Proof of Lemma 2.1
q
2
For simplicity, we let λ ≡ 2 ln( 1−ε
) and assume that µY > µX + λ(σX + σY ) (the other case is
symmetric). By the definition of TVD, we obtain that:
2dtv (X, Y ) =
≥

∞
X

|Pr[X = i] − Pr[Y = i]|

i=0
µXX
+λσX
i=0

(Pr[X = i] − Pr[Y = i]) +

∞
X

i=µY −λσY

(Pr[Y = i] − Pr[X = i])

= (Pr[X ≤ µX + λσX ] − Pr[Y ≤ µX + λσX ]) +
+ (Pr[Y ≥ µY − λσY ] − Pr[X ≥ µY − λσY ])

≥ (1 − Pr[X > µX + λσX ] − Pr[Y < µY − λσY ]) +

+ (1 − Pr[Y < µY − λσY ] − Pr[X > µX + λσX ])

> (1 − (1 − ε)/2 − (1 − ε)/2) + (1 − (1 − ε)/2 − (1 − ε)/2) = 2ε
For the second inequality, we use that µX + λσX < µY − λσY . Therefore, Pr[Y ≤ µX + λσX ] ≤
Pr[Y < µY − λσY ] and Pr[Xq
≥ µY − λσY ] ≤ Pr[X > µX + λσX ]. For the last inequality, we apply
2
) and obtain that Pr[X > µX + λσX ] < (1 − ε)/2 and that
Proposition C.1 with λ = 2 ln( 1−ε
Pr[Y < µY − λσY ] < (1 − ε)/2.
⊔
⊓

A.2

The Proof of Lemma 2.2: Technical Details

We use the notation introduced in the proof sketch, in the main part. For simplicity, we let X(j)
(resp. Y (j)) denote of the sum of s Bernoulli random variables with expectation pkj = (1 − aj /ν 4j )k
(resp. qjk = (1 − bj /ν 4j )k ), i.e., X(j) and Y (j) are the k-th PBD powers of the Bernoulli trials in
group j of p and q.
We first observe that for all j < i and for all a ∈ [ν],

4i−2 /ν 4j
a ν 4i−2
≤ s e−aν
s 1 − 4j
ν
4(i−j)−2
= s e−aν
≤ s/na ln n ,
21

where for the last inequality, we use that i − j ≥ 1 and that ν = ln n. Therefore, since aj , bj ≥ 1
and since m < n,
X
X
Var[Y (j)] ≤
E[Y (j)] ≤ s/n−1+ln n and
j<i

X
j<i

P

j<i

Var[X(j)] ≤

X

E[X(j)] ≤ s/n−1+ln n .

j<i

s/n−1+ln n .

Moreover, j<i |E[Y (j)] − E[X(j)]| ≤
We also have that the difference between the mean values of X(i) and Y (i) is:


ai ν 4i−2
xi ν 4i−2
ai
E[X(i)] − E[Y (i)] = s 1 − 4i
− s 1 − 4i − 4i
ν
ν
ν
!
 4i−2 2 
4i−3


ν
ν
xi
ai ν 4i−4
ai
4i−2 xi
1 − 4i
−
1 − 4i
≥s ν
ν 4i
ν
2ν 4i
ν


xi
1  xi  2
sxi
≥s
−
≥ 2
2
2
2ν
2 2ν
4ν

The first inequality holds because for any i, 1 ≥


ai
ν 2i

+

xi
ν2 .

Therefore,

 4i−2 2 

ν
xi
ai ν 4i−4
ai ν 4i−2
xi ν 4i−2 
ai ν 4i−3
ai
4i−2 xi
1
−
≤ 1 − 4i
−ν
+
1
−
1 − 4i − 4i
ν
ν
ν
ν 4i
ν 4i
2ν 4i
ν 4i
4i−3

4i−4

For the second inequality, we use that (1 − νa4ii )ν
≥ 1 − νa3i ≥ 1/2 and that (1 − νa4ii )ν
≥
xi
ai
1 − ν 4 ≥ 1/2. For the last inequality, we use that 2ν 2 ≤ 1/2.
As for the variance of X(i) and Y (i), since pki > qik > 1/2 (assuming that n is sufficiently large),

 4i−2
 4i−2 !

bi ν
bi ν
1 − 1 − 4i
Var[X(i)] ≤ Var[Y (i)] = s 1 − 4i
ν
ν
ν 4i−2 !

bi
≤ s 1 − 1 − 4i
ν
≤ sν 4i−2

bi
≤ s/ν ,
ν 4i

where for the last inequality we use that bi ≤ ν.
Moreover, we let xj = bj − aj , with 0 ≤ |xj | < ν, and observe that for all j > i,


xj ν 4i−2
aj
aj ν 4i−2
|E[X(j)] − E[Y (j)]| = s 1 − 4j
− s 1 − 4j − 4j
ν
ν
ν
|xj |
≤ sν 4i−2 4j
ν
s
≤ 4(j−i)+1
ν
P
Therefore, j>i |E[X(j)] − E[Y (j)]| ≤ 2s/ν 5 .
As for the variance of X(j) and Y (j), we have that for all a ∈ [ν],







a ν 4i−2
a ν 4i−2
a ν 4i−2
s 1 − 4j
1 − 1 − 4j
≤ s 1 − 1 − 4j
ν
ν
ν
a
≤ s 4(j−i)+2
ν
≤ s/ν 4(j−i)+1
22

P
where for the last inequality we use that a ∈ ν. Therefore, j>i (Var[X(j)] + Var[Y (j)]) ≤ 4s/ν 5 .
Putting everything together and assuming that n is large enough, we obtain that


X
3
xi s
xi
− 5 ≥ 2
|E[X] − E[Y ]| ≥ −
(E[X(j)] − E[Y (j)]) + (E[X(i)] − E[Y (i)]) ≥ s
2
4ν
ν
5ν

(10)

j6=i

The first inequalityPholds because for all numbers c, d, |c + d| ≥ c − |d| (here, we use c = E[X(i)] −
E[Y (i)] and d =
− E[Y (j)]) ). The second inequality holds because (i) E[X(i)] −
j6=i (E[X(j)]
P
P
2
E[Y (i)] ≥ sxi /(4ν ), (ii) j<i |E[Y (j)] − E[X(j)]| ≤ s/n−1+ln n , and (iii) j>i |E[X(j)] − E[Y (j)]| ≤
2s/ν 5 .
As for the variance of X and Y , we have that
Var[X] + Var[Y ] ≤

4s
ν

(11)

If we assume that n is sufficiently large, that s ≥ (ln n)4 and that ai > bi , and thus xi ≥ 1, we
obtain that for any ε ∈ (0, 1/2],
r
s
2 4s
|E[X] − E[Y ]| ≥ 2 > 4 ln(
)
5ν
1−ε ν
r
2
)(Var[X] + Var[Y ])
≥ 4 ln(
1−ε
r

p
p
2
Var[X] + Var[Y ]
)
≥ 2 ln(
1−ε

Therefore, by Lemma 2.1, we obtain that X and Y are at distance larger than ε, for any ε ∈ (0, 1/2],
a contradiction. Hence, it must be ai = bi , which concludes the proof of the lemma.
⊔
⊓

B
B.1

Upper Bound for Learning PBD Powers: Separated Case
The proof of Lemma 3.1

To prove this lemma we will first show the following.
γ x−1
Lemma B.1. Let us consider the following function h(x) = 1 − cx
, where c ≥ 2 is a fixed
constant, γ ≥ 1 and x ≥ γ. If γ ≥ 2c, then function h is increasing in [γ, +∞).


γ
γ
γ x−1
ln(1 − cx
) + 1−cxγ · x−1
. Because we have that
Proof. Let us observe that h′ (x) = 1 − cx
x

h(x) ≥ 0, to show the claim it suffices to prove that

γ

γ
x−1
ln 1 −
+ cx γ ·
≥0
cx
1 − cx
x

when x ≥ γ ≥ 2c.
This inequality can be rewritten to
γ

x−1
γ −1
≤ cx γ ·
ln 1 −
,
cx
1 − cx
x

23

cx

which after variable change z =

γ
cx

∈ (0, 1c ] is equivalent to


1
z
c
ln
≥
· 1− z .
1−z
1−z
γ

P
1
zi
We now use the Taylor’s series expansion ln 1−z
= ∞
i=1 i , which leads to the following inequality


c
z2 z3 z4
1−z
+
+
+ . . . ≤ 1 − z,
z+
z
2
3
4
γ
or equivalently


c
1
−
γ 2



z+



1 1
−
3 2



2

z +



1 1
−
4 3



3

z +



1 1
−
4 5



z 4 + . . . ≤ 0.

Note that our operations on these infinite series are legitimate because they converge: for inP∞
P∞
1
1
i
stance taking series
i=1 i+1 − i z =
i=1 ai and using the d’Alembert’s ratio test we see
that limi→∞

ai+1
ai

= limi→∞

i
i+2 z

= z < 1, so the series converges.

Let us now observe that because ai < 0 for all i and
P∞ 1
1 i
1
i=2 ( i+1 − i )z ≤ 0 is true for all z ∈ (0, c ].

c
γ

−

1
2

≤ 0, the inequality ( γc − 21 )z +

Now we are ready to prove Lemma 3.1.

Proof. Let f (x) = (1 −

x ℓi
cℓi ) ,

then f ′ (x) = − 1c (1 −

x ℓi −1
, and so by the Mean Value Theorem
cℓi )
β i ℓi
′
cℓi ) = f (γ)(αi − βi ). Using this, and that fact

αi ℓi
) − (1 −
there exists γi ∈ (αi , βi ) such that (1 − cℓ
i
that βi − αi ≥ 1, the claimed inequality is implied if the following inequality


γi ℓi −1
4cε
1−
>p
cℓi
n/s
p
holds for all n ≥ e2c . Now because γi ≤ ln(n), the last inequality is implied by

1−

p

ln(n)
cℓi

!ℓi −1

4cε
,
>p
n/s

and by ℓi ≥ ln(n) and by Lemma B.1 this inequality is implied by
p

ln(n)
1−
c ln(n)

!ln(n)−1

The last inequality is equivalent to
1

1− p
c ln(n)

!ln(n)

4cε
>p
n/s

4cε
.
>p
n/s
1

1− p
c ln(n)

!

,

which by using a known inequality (1 + y/m)m ≥ ey (1 − y 2 /m), see Fact 3.1, is implied by
 
1
e

√

ln(n)
c

4cε
>p
n/s

1
1− p
c ln(n)
24

! 

1
/ 1− 2 .
c

We now observe that



1 − √1

 
1
e

c

√

ln(n)
c

ln(n)



/ 1−

1
c2



< 3/2 and so the last inequality is implied by

ln(n)
6cε
≡
≥p
≥
2
n/s

p

ln(n) ln(s)
+
+ ln(6cε).
c
2

The last inequality can easily be checked to hold when n ≥ e2c .
B.2

Proof of Theorem 1.2

Proof. The main idea of the proof follows that of Algorithm 1. That is as it learns pi ’s starting
from the largest and proceeding towards the smallest, the proofs follows the same order.
Recall that we assume that n ≥ e2c and n ≥ (2−√42)2 ε2 .
First we show how to exactly learn p0 . Observe that by the inequality from Fact 3.1, we obtain
pℓ00

=



α0 /c
1−
(c ln(n))s /c

(c ln(n))s /c

 α0 /c  1/c
1
1
≤
≤
< 1.
e
e
i−1

Similarly we see that pℓ10 ≤ 1/n and pℓ20 ≤ (1/n)c ln(n) , and in general pℓi 0 ≤ (1/n)(c ln(n))
for
i = 1, 2, . . ..
By this observation we can upper bound the mean of X ℓ0 as follows (note that ni = n0 = n/s
for all i):
!
s−1
s−1
s−1
X
X
X
(12)
pℓi 0 ≤
pℓi 0 = n0 · pℓ00 +
ni pℓi 0 = n0
E[X ℓ0 ] =
n0 ·

pℓ00

s−1
X
i−1
(1/n)(c ln(n))
+
i=1

i=1

i=0

i=0

!

≤ n0 ·

pℓ00

∞
X
(1/n)i
+
i=1

!



≤ n0 · pℓ00 + 2/n ,

where the last estimate holds if n ≥ 2.
Similarly we can bound the variance σℓ20 = Var[X ℓ0 ]:
ℓ0

Var[X ] = n0

s−1
X
i=0

We now draw O



log(s/δ)
ε2





pℓi 0 (1 − pℓi 0 ) ≤ n0 · pℓ00 + 2/n < n0 · (1 + 2/n) ≤ 2n0 .

samples from X ℓ0 and obtain by Proposition 3.1 the estimate µ̂ℓ0 of the

mean µℓ0 = E[X ℓ0 ] such that

√
|µℓ0 − µ̂ℓ0 | ≤ εσℓ0 < ε 2n0 ,



with probability at least 1 − δ/s. This estimate, after letting µℓ0 = n0 · pℓ00 + rℓ0 , implies
p
|pℓ00 + rℓ0 − µ̂ℓ0 /n0 | < ε 2/n0 ,


p
and rℓ0 ≤ 2/n by (12). Let α0 ∈ {1, 2, . . . , ⌊ ln(n)⌋} be such that pℓ00 = 1 −
we obtain


p
µ̂ℓ
α0 ℓ0
+ rℓ0 − 0 < ε 2/n0 .
1−
cℓ0
n0
25

(13)
α0
cℓ0

 ℓ0

, then by (13)
(14)


 ℓ0
ℓ0

β0
0 −1
By n ≥ e2c , Lemma 3.1 implies that 1 − βcℓ
−
1
−
> √4ε , for any β0 ∈
cℓ0
0
n/s
p
p
{1, 2, . . . , ⌊ ln(n)⌋}. This, together with (14), gives us that there exists the smallest β0 ∈ {1, 2, . . . , ⌊ ln(n)⌋}

ℓ0
β0
such that 1 − cℓ
≤ µ̂ℓ0 /n0 ; thus, we have that
0



α0
1−
cℓ0

β0
1−
cℓ0

ℓ 0

µ̂ℓ
≤ 0 <
n0





ℓ 0


β0 − 1 ℓ0
,
(15)
1−
cℓ0
p
and let indeed β0 be such smallest number from {1, 2, . . . , ⌊ ln(n)⌋}.
We will now prove that α0 ∈ {β0 −1, β0 } and we will also show how to decide if in fact α0 = β0 −1
or α0 = β0 , which means that we can learn the precise value of p0 from µ̂ℓ0 /n0 .
Suppose first that β0 ≥ α0 + 2; then by (15) we obtain that


ℓ 0

µ̂ℓ
+ rℓ 0 − 0 >
n0



ℓ 0

α0
1−
cℓ0

α0
1−
cℓ0



β0 − 1
+ rℓ 0 − 1 −
cℓ0



α0 + 1
+ rℓ 0 − 1 −
cℓ0

ℓ 0

ℓ 0

≥

4ε
,
>p
n/s

where the last inequality follows by Lemma 3.1 because n ≥ e2c . But then this is in contradiction
with (14); thus, we must have that β0 ≤ α0 + 1.
Similarly, if β0 ≤ α0 − 1, then by (15)
µ̂ℓ0 /n0 − pℓ00


α0 − 1
1−
cℓ0

− rℓ 0

ℓ 0



α0
= µ̂ℓ0 /n0 − 1 −
cℓ0


α0
− 1−
cℓ0

ℓ 0

ℓ 0

− rℓ0 ≥

4ε
− 2/n,
− rℓ 0 > p
n/s

where the last inequality follows by Lemma 3.1. This again is in contradiction with (14); thus, we
have that β0 ≥ α0 . We have shown that β0 ∈ {α0 , α0 + 1}.
What remains to show is how to decide if α
= β0 − 1 or α0 = β0 . By Lemma 3.1 the length
ℓ0 
ℓ0 0

β0
0 −1
, 1 − βcℓ
1 − cℓ
in (15) containing number µ̂ℓ0 /n0 can be lower
of the interval I0 =
0
0
bounded as follows





β0 ℓ0
4ε
β0 − 1 ℓ0
− 1−
>p
1−
.
cℓ0
cℓ0
n/s

ℓ0

β0
and µ̂ℓ0 /n0
If we had α0 = β0 , then (14) implies that the distance between numbers 1 − cℓ
0
p
p
is at most rℓ0 + ε 2/n0 ≤ 2/n + ε 2/n0 , which is strictly less than half of the length of interval
I0 by our assumption that n > (2−√42)2 ε2 . On the other hand if we had that α0 = β0 − 1, then
ℓ0

p
0 −1
and µ̂ℓ0 /n0 is most ε 2/n0 , which
(14) implies that the distance between numbers 1 − βcℓ
0
again is strictly less than half of the length of interval I0 . We can therefore use this test to decide
if α0 = β0 − 1 or α0 = β0 .
This finishes the argument of how to exactly learn p0 . We will now assume that for some
i ∈ {1, 2 . . . , s − 1}, values of all p0 , p1 , . . . , pi−1 are known exactly, and we will show how to learn
exactly the value of the next pi .
26

The high-level argument will be quite similar to the case of learning p0 because we now can
assume that values of p0 , p1 , . . . , pi−1 are known.
By the inequality from Fact 3.1, we obtain
(c ln(n))s−i /c  αi /c  1/c

1
1
αi /c
ℓi
≤
≤
< 1.
pi = 1 −
(c ln(n))s−i /c
e
e
j−1

i
i
i
for
Similarly we see that pℓi+1
≤ 1/n and pℓi+2
≤ (1/n)c ln(n) , and in general pℓi+j
≤ (1/n)(c ln(n))
j = 1, 2, . . ..
We thus can upper bound the mean of X ℓi as follows (note that nj = n0 = n/s for all j):


s−1
i−1
s−1
s−1
X
X
X
X
pℓji  ≤
(16)
pℓji + pℓi i +
pℓji = n0 · 
nj pℓji = n0
E[X ℓi ] =

n0 ·

pℓ00 +

s−1
X

i−1

(1/n)(c ln(n))

i=1

!



≤ n0 · 

i−1
X
j=0

j=i+1

j=0

j=0

j=0




i−1
∞
X
X
pℓji + pℓi i + 2/n ,
(1/n)j  ≤ n0 · 
pℓji + pℓi i +
j=0

j=1

where the last estimate holds if n ≥ 2.
We will now bound the variance σℓ2i = Var[X ℓi ]. By the inequality (1 − x/n)n ≥ 1 − x, which
holds for any n ≥ 1 and x ≤ n, and by using that αj ≤ ln(n), for all j, we obtain

(c ln(n))s−i /c
αi−1
2
1
αi−1
c ln(n)
i
pℓi−1
= 1 − (c ln(n))s−i+1 
≥1− p
.
≥1− 2
c ln(n)
c2 ln(n)
2
c ln(n)

i
Similarly we see that pℓi−2
≥ 1−

i
pℓi−j
≥1−

c2

√

1
ln(n)·(c ln(n))j−1

Var[X ℓ0 ] = n0

√

1
ln(n)·c ln(n)

i
and pℓi−3
≥ 1−

c2

√

1
,
ln(n)·(c ln(n))2

and in general

for j = 1, 2, . . .. Thus we obtain
s−1
X
j=0


i−1
X


n0 ·

c2


s−1
i−1
X
X
pℓji  ≤
pℓji (1 − pjℓi ) ≤ n0  (1 − pℓji ) + pℓi i +


j=i+1

j=0





1
 + pℓi + 2/n < n0 · (1/7 + 1 + 2/n) ≤ 2n0 ,
i
j
ln(n) · (c ln(n))
j=0

 
Pi−1
P∞
1
2c
√
√
where we used that n ≥ e and c ≥ 2 to bound
≤
j=0 2
j=0 2
j
c2

p

c

ln(n)·(c ln(n))

c

1
ln(n)·(c ln(n))j



1/7.


samples from X ℓi and obtain by Proposition 3.1 the estimate µ̂ℓi of
We now draw O log(s/δ)
ε2
the mean µℓi = E[X ℓi ] such that

√
|µℓi − µ̂ℓi | ≤ εσℓi < ε 2n0 ,

with probability at least 1−δ/s. This estimate, after letting µℓi = n0 ·
i−1
X
j=0

P
i−1

p
pℓji + pℓi i + rℓi − µ̂ℓi /n0 < ε 2/n0 ,
27


ℓi
ℓi
p
+
p
+
r
ℓi implies
j=0 j
i
(17)

≤


p
and rℓi ≤ 2/n by (16). Let αi ∈ {1, 2, . . . , ⌊ ln(n)⌋} be such that pℓi i = 1 −
Pi−1 ℓi
denote τ̂i = µ̂ℓi /n0 − j=0
pj . Then by (17) we obtain


p
αi ℓi
+ rℓi − τ̂i < ε 2/n0 .
1−
cℓi

αi
cℓi

ℓi

, and let us also

(18)

Recall that the values p0 , . . . , pi−1 are known. Suppose next that we find the smallest βi ∈
ℓi

p
βi
≤ τ̂i (such βi exists by the same argument as that for
{1, 2, . . . , ⌊ ln(n)⌋} such that 1 − cℓ
i
β0 ); thus, we have that




βi ℓi
βi − 1 ℓi
1−
≤ τ̂i < 1 −
.
(19)
cℓi
cℓi
We will now prove that αi ∈ {βi − 1, βi } and we will also show how to decide if αi = βi − 1 or
αi = βi , which will imply that the precise value of pi can be learned from τ̂i .
Suppose first that βi ≥ αi + 2; then by (19) we obtain that






αi ℓi
βi − 1 ℓi
αi ℓi
+ rℓi − τ̂i > 1 −
+ rℓi − 1 −
≥
1−
cℓi
cℓi
cℓi




αi ℓi
αi + 1 ℓi
4ε
,
1−
+ rℓi − 1 −
>p
cℓi
cℓi
n/s

where the last inequality follows by Lemma 3.1 because n ≥ e2c . But then this is in contradiction
with (18); thus, we must have that βi ≤ αi + 1.
Similarly, if βi ≤ αi − 1, then by (19)


αi ℓi
ℓi
− rℓ i ≥
τ̂i − pi − rℓi = τ̂i − 1 −
cℓi


αi − 1
1−
cℓi

ℓ i



αi
− 1−
cℓi

ℓ i

4ε
− rℓi > p
− 2/n,
n/s

where the last inequality follows by Lemma 3.1. This again is in contradiction with (18); thus, we
have that βi ≥ αi . We have shown that βi ∈ {αi , αi + 1}.
The
is to decide 
if αi = βi − 1 or αi = βi . By Lemma 3.1 the length of the interval
 next step
ℓi 
ℓi
βi
i −1
Ii = 1 − cℓ
, 1 − βcℓ
in (19) containing number τ̂i can be lower bounded as follows
i
i


βi − 1
1−
cℓi

ℓ i



βi
− 1−
cℓi

ℓ i

4ε
.
>p
n/s


ℓi
βi
If αi = βi , then (18) implies that the distance between numbers 1 − cℓi
and τ̂i is at most
p
p
rℓi + ε 2/n0 ≤ 2/n + ε 2/n0 , which is strictly less than half of the length of interval Ii by our
assumption that n > (2−√42)2 ε2 . On the other hand, if αi = βi − 1, then (18) implies that the
ℓi

p
i −1
and
τ̂
is
most
ε
2/n0 , which again is strictly less than
distance between numbers 1 − βcℓ
i
i
half of the length of interval Ii . We can therefore use this test to decide if αi = βi − 1 or αi = βi .
To finish the proof, observe that by the union bound all the sampling estimates for the mean
values µˆℓi hold with probability
 at least 1 − δ. Moreover, because this sampling for
 each i =

0, 1, . . . , s − 1 draws O

log(s/δ)
ε2

samples from X ℓi , the total number of samples is O
28

s log(s/δ)
ε2

.

C
C.1

Upper Bound for Learning Binomial Powers
Preliminaries

We start by stating a useful variant of the standard Chernoff Bound.
Proposition C.1 (Chernoff Bound). Let X = X1 + · · · + Xn , Xi ∈ [0, 1]. Let µ = E[X] and
2
2
σ 2 = Var(X). Then, for all λ ∈ (0, 2σ), Pr[X > µ + λσ] < e−λ /4 and Pr[X < µ − λσ] < e−λ /4 .
Proof. See, e.g., page 8 in the book [18].
We now prove Fact 4.1 and Fact 4.2 on estimating the parameter p of a Binomial B(n, p) using
Chernoff’s Bound.
Proof of Fact 4.1.
P
m
Proof. Let X = m
i=1 si /n. Then si /n ∈ [0, 1] and E[X] = mp, Var[X] = n p(1 − p), since the
samples are i.d.d. We show only that Pr[p̂ − p > ψ err (n, p, ε)] ≤ δ since the other case is similar.
From C.1 we obtain with t = mψ err (n, p, ε)
Pr[p̂ − p > ψerr (n, p, ε)] =Pr[p̂ − p > t/m]

p
√
mψε Var[X]]

≤ exp −mε2 ψ 2 /4

=Pr[X − E[X] >
≤δ,

where, for the last inequality, we use that m = ⌈4 ln(1/δ)/(ε2 ψ 2 )⌉.

⊔
⊓

Proof of Fact 4.2.
Proof. We only prove that Pr [p < q̂2 < p + err (n, p, ε)] ≥ 1−δ since the proof for q̂1 = min1≤i≤k wi
is essentially the same.

 [ 

Pr max wi < p
max wi > p + ψerr (n, p, ε)
i
i




≤Pr max wi < p + Pr max wi > p + ψerr (n, p, ε)
i
i
#
#
" k
" k
[
\
(wi > p + ψerr (n, p, ε))
(wi < p) + Pr
=Pr
i=1

i=1

 k
1
≤
+ ku
2
≤δ,

where the last inequality follows from k = ⌈ln(2/δ)/ ln(2)⌉ and by choosing u ≤ δ/(2k). From
Fact 4.1 we have that



ln(2)⌉


ln 2⌈ln(2/δ)/
δ
ln(1/δ)
2 2


m = ⌈4 ln(1/u)/(ε ψ )⌉ = 4
=O
ε2 ψ 2
ε2 ψ 2


is sufficient to ensure that Pr [wi < p + ψerr (n, p, ε)] ≤ δ/(2k).
29

⊔
⊓

C.2

The Case where p ∈ [ε2 /nd , 1 − ε2 /nd ].

We generalise Algorithm 2 and its analysis to the case where the value of p is very close to 1 or 0
and lies in [ε2 /nd , 1 − ε2 /nd ], for some fixed constant integer d ∈ N+ . Hence, we cover all values of
p that can be represented by O(log n) bits.
This will lead to the following theorem.
Theorem C.1. Let ε ∈ (0, 1/6) and d ∈ N+ be fixed constants, and let n ∈ N, n ≥ 5. For any
2 ) samples and
p ∈ [ε2 /nd , 1 − ε2 /nd ], an extension of Algorithm 2 uses O(log(d) log(log(d)/δ)/ε

outputs t, â ∈ (0, +∞),qˆ1 , qˆ2 ∈ (0, 1) such that dtv B(n, q̂2l ), B(n, pltâ ) ≤ O(ε) for l ∈ (0, 1) and
dtv B(n, q̂1l ), B(n, pltâ ) for l ∈ (1, +∞) with probability at least 1 − δ.

Proof. We will first describe the extension of Algorithm 2. Notice that, in this case we only need
to find t ∈ (0, +∞) such that pt ∈ [ε2 /n, 1 − ε2 /n]. Then, we simply call Algorithm
2 using B(n, pt )

as the ”first” power to obtain q̂1 , q̂2 , â such that dtv B(n, q̂2l ), B(n, pltâ ) ≤ O(ε) for l ∈ (0, 1) and
dtv B(n, q̂1l ), B(n, pltâ ) for l ∈ (1, +∞). To find t we first sample from B(n, p) and using Fact 4.2
we obtain q̂1,1 , q̂1,2 such that Pr [p − err (n, p, ε) < q̂1,1 < p < q̂1,2 < p + err (n, p, ε)] ≥ 1 − δ. We
have the following cases:
– q̂1,1 > ε2 /n and q̂1,2 < 1 − ε2 /n. In this case we can use directly Algorithm 2.
– q̂1,1 < ε2 /n. Let I1 = {1/(i ln n) : i ∈ {2, . . . , d}}. Using Fact 4.2 draw O(d ln2 (d/δ)/ε2 ) samples
from the powers B(n, pl ), l ∈ I1 , and obtain the set of approximations Q1 = {q̂
 i,1 : i ∈ I1 }i such
i
i
that with probability 1 − δ/2 all q̂i,1 ∈ Q1 satisfy the bounds p − err n, p , ε < q̂i,1 < p . We
first prove that there exists an element t of I1 such that q̂t,1 ≥ ε2 /n. It suffices to show that such
a t exists when p = ε2 /nd . Then p1/(d ln n) = ε2/(d ln n) /e and q̂1/(d ln n) ≥ p1/(d ln n) − 2√ε n ≥ ε2 /n,
for all n ≥ 7.
Let t be the largest element of I1 such that q̂t,1 ≥ ε2 /n. Then pt > ε2 /n since q̂t,1 < pt . Moreover,
pt < 1 − ε2 /n. To
that
ln n) for some ρ ≥ 2 and t′ = 1/((ρ − 1) ln n). Then,
 write t = 1/(ρ
 show
ρ−1
1
√
√
′
′
pt ≤ q̂t′ ,1 + err n, pt , ε ≤ ε2 /n + ε/(2 n) ≤ ε/ n. Thus, pt = p1/(ρ log n) = p (ρ−1) log n ρ =
 √ 1/ρ
√
√ ρ−1
′ ρ−1
ε
≤ n1/4
(pt ) ρ ≤ (ε/ n) ρ = √εn εn
≤ 1 − ε2 /n, where the last inequality holds for
n ≥ 2, ε < 1/2.
– q̂1,2 > 1 − ε2 /n. Consider now the set I2 = {ni/3 : i ∈ {0} ∪ [3d]}. Using Fact 4.2 draw
O(d ln2 (d/δ)/ε2 ) samples and obtain the set of approximations Q2 = {q̂i,2 : i ∈ I2} such that
with probability 1 − δ/2 all q̂i,2 ∈ Q2 satisfy the bounds pi < q̂i,2 < pi + err n, pi , ε . As we did
in the previous case we first prove that there exists a t ∈ I2 such that q̂t,2 ≤ 1 − ε2 /n. It suffices
2
d
to prove it for p = 1 − ε2 /nd . Take t = nd . Then pt = (1 − ε2 /nd )n ≤ e−ε ≤ 1 − ε2 /2 ≤ 1 − ε2 /n
for ε < 0.85, n ≥ 2.
Starting from 1 find the smallest element t of I2 such that q̂t,2 < 1 − ε2 /n. We argue that
ε2 /n < pt < 1 − ε2 /n. Obviously pt < 1 − ε2 /n since pt < q̂t,2 . To prove the other inequality,
write t = nρ/3 and t′ = n(ρ−1)/3 for some ρ ∈ [3d]. We have that q̂t′ ,2 ≥ 1 − ε2 /n and therefore
√
√
ρ/3
′
pt ≥ 1 − ε2 /n − err (n, p, ε) ≥ 1 − ε2 /n − ε/(2 n) ≥ 1 − ε/ n, for n ≥ 4. Thus, pt = pn =
√ 1/3
1/6
1/3
1/2
1/3
′
(ρ−1)/3+1/3
≥ ε2 /n, where for the
= e−2ε/n
≥ e−2εn /n
≥ (1 − ε/ n)n
= (pt )n
pn
−2x
second inequality we used 1 − x ≥ e
for x ∈ [0, 0.75] and the last inequality holds for
ε ≤ 1/e, n ≥ 1.
It is easy to see that we can improve the sampling complexity by doing binary search on d, which
means for each ρ tested, the algorithm chooses O(log(log(d)/δ)/ε2 ) independent samples, which
leads to O(log(d) log(log(d)/δ)/ε2 ) total number of samples.
⊔
⊓
30

D
D.1

Lower Bound for Learning Binomial Powers
Notation

We denote by N (µ, σ) the Normal distribution with mean µ and variance σ 2 . The density function
(x−µ)2

1
e− 2σ2 . We denote by erf (x) the Gauss error function, namely erf (x) =
of N (µ, σ) is f (x) = √2πσ
R
R +∞ −t2
x −t2
√2
√2
dt,
by
erfc
(x)
the
complementary
error
function,
erfc
(x)
=
1
−
erf
(x)
=
e
e dt.
0
π
π x

D.2

Preliminaries

We prove the following proposition which provides an exact expression for the KL-Divergence of
two Binomial distributions.
Proposition D.1 (Binomial KL-Divergence). Let X = B(n, p), Y = B(n, q) be two Binomial
distributions. Then



 
1−q
q
Dkl (XkY ) = −n (1 − p) log
+ p log
1−p
p
Proof. We have

Dkl (XkY ) =

n
X

X(k) ln

k=0

n  
X
n

X(k)
Y (k)


pk (1 − p)n−k
=
p (1 − p)
ln
k
q k (1 − q)n−k
k=0



 
n  
X
n k
1−p
p
n−k
p (1 − p)
=
+ (n − k) ln
k ln
k
q
1−q
k=0

 



 X
n
n
n k
n k
1−p X
p
n−k
k
(n − k)
p (1 − p)
+ ln
p (1 − p)n−k
= ln
k
k
q
1−q
k=0
k=0
 


p
1−p
= np ln
+ n(1 − p) ln
.
q
1−q
k

n−k



⊔
⊓

The following simple proposition formalizes an intuition that when the distance of the parameters p, q of two Binomial distributions is large, then the Kullback-Leibler divergence of the these
distributions is large.
Proposition D.2. Let X ∼ B(n, p), Y ∼ B(n, q). Then Dkl (XkY ) and Dkl (Y kX) are both
increasing functions of |p − q|.
Proof. Write q = p+x. We start with Dkl (B(n, p)kB(n, p + x)). The derivative of h(x) := Dkl (B(n, p)kB(n, p + x))
with respect to x is
n(1 − p)
np
h′ (x) =
−
.
−p − x + 1 p + x
It’s easy to see that h′ (x) > 0 for x ∈ (0, 1 − p) and h′ (x) < 0 for x ∈ (−p, 0). Therefore h(x) is
minimized at x = 0. Similarly if we let g(x) = Dkl (B(n, p + x)kB(n, p)) we have




−p − x + 1
p+x
′
− n ln
.
g (x) = n ln
p
1−p
Again we have g′ (x) < 0 for x ∈ (−p, 0) and g ′ (x) > 0 for x ∈ (0, 1 − p). Thus, g(x) is minimized
at x = 0.
⊔
⊓
31

D.3

Discretized Normal Approximation

We first start with some basic results about continuous Normal distributions. Chu [5] proved the
following inequality for the Normal Integral
Proposition D.3 (Chu’s Inequalities). For any x ≥ 0:
p
p
1 − e−ax2 ≤ erf (x) ≤ 1 − e−bx2 ,

where a = 1 and b = 4/π.

The folowing Corollary of D.3 provides a slightly weaker lower bound for erf (x).
Corollary
p D.1. If 0 ≤ x ≤ 1, then we have that erf (x) ≥ x/c, where c is any fixed constant such
that c ≥ e/(e − 1).
Proof. Using lower bound of the inequality of Proposition D.3 with a = 1 we want to prove that
r
1
x
≤ 1 − x2 ,
c
e

for any x ∈ [0, 1]. This inequality is equivalent to
2

f (x) := ex (c2 − x2 ) − c2 ≥ 0.

√
2
if x ≤ c2 − 1 and
We have that f ′√
(x) = 2xex (c2 − 1 − x2 ), therefore we see that f ′ (x) ≥ 0 √
f ′ (x) ≤ 0 if x ≥ c2 − 1. This means that function f has a maximum at x0 = c2 − 1 and thus its
smallest value in [0,p
1] is min{f (0), f (1)} = {0, (e − 1)c2 − e}. Now we demand that (e − 1)c2 − e ≥ 0,
which leads to c ≥ e/(e − 1) and under this condition f (x) ≥ 0 for all x ∈ [0, 1].
⊔
⊓
To bound erfc (z) we shall use Komatsu’s inequality stated e.g. as Problem 1, page 17 in [22]. See
[31] for more such results.
Proposition D.4 (Komatsu’s Inequalities). For all a ≥ 0 it holds
Z +∞
2
2
e−a /2
e−a /2
2
√
e−t /2 dt ≤ √
≤
2 a2 + 4 + a
2 a2 + 2 + a
a
When two continuous Normal distributions have the same standard deviation a simple argument
gives an exact expression for their total variation distance.
Proposition D.5. Let X ∼ N (µ1 , σ), Y ∼ N (µ2 , σ). Then


|µ1 − µ2 |
√
dtv (X, Y ) = erf
2 2σ
Proof. Let fX resp. fY be the density functions for X resp. Y . We can assume that µ1 < µ2 since
the proof for the other case is essentially the same. Then
(x−µ1 )2
(x−µ2 )2
1
1
µ1 + µ2
fX (x) ≥ fY (x) ⇔ √
e− 2σ2 ≥ √
e− 2σ2 ⇔ |x − µ1 | ≤ |x − µ2 | ⇔ x ≤
2
2πσ
2πσ

Therefore,
dtv (X, Y ) =

Z

µ1 +µ2
2

−∞

(fX (x) − fY (x)) dx = erf

32



µ2 − µ1
√
2 2σ



⊔
⊓

When the variances of two Normal distributions differ the following Proposition from [8] provides
an upper bound for their total variation distance.
Proposition D.6 (Proposition B.4 from [8]). Let µ1 , µ2 ∈ R and 0 < σ1 ≤ σ2 . Then
1
dtv (N (µ1 , σ1 ) , N (µ2 , σ2 )) ≤
2



|µ1 − µ2 | σ22 − σ12
+
σ1
σ12



Let X ∼ N (µ, σ). We denote by DN (µ, σ) the discretized Normal distribution, namely if
Xd ∼ DN (µ, σ) then Xd is a discrete random variable with mass function


1
1
Pr [Xd = k] = Pr k − < X ≤ k +
,
2
2
where k is any integer.
The following recent result of Chen and Leong [24] (Theorem 7.1) shows that a continuity
corrected discretized Normal distribution approximates very well a PBD provided that the variance
of the PBD is not very small.
Lemma D.1 (Theorem 7.1 from [24]). Let X be a PBD and let µ = E[X], σ 2 = Var [X]. Let
Y ∼ DN (µ, σ). Then
dtv (X, Y ) ≤

7.6
.
σ

The next Lemma shows that 2 discretized Normal distributions are close if and only if the corresponding continuous Normals are close. The needed condition for this to hold is that the variance
of the 2 Normals is not too small.
Lemma D.2 (Discrete-Continuous Error). Let X = N (µ1 , σ1 ), Y = N (µ2 , σ2 ) be two Normal
distributions such that dtv (X, Y ) ≥ ε, where ε > 0. Let Xd ∼ DN (µ1 , σ1 ), Yd ∼ DN (µ2 , σ2 ). Then
ε − (ℓ + m + u) ≤ dtv (Xd , Yd ) ≤ ε

(20)

where
1
ℓ=
4



erfc









µ2
n − µ2
n − µ1
1
+ erfc √
u=
+ erfc √
erfc √
4
2σ2
2σ1
2σ2



 
1
1
1
m=
+ erf √
erf √
2
2σ1
2σ2

µ
√ 1
2σ1





R +∞
Proof. Let fX , resp. fY be the density function of X, resp. Y . We have that −∞ |fX (x) −
fY (x)|dx = 2dtv (X, Y ) = 2ε. Since the density of a Normal distribution with mean µ is increasing
in (−∞, µ] and decreasing in [µ, +∞) we have that there exist at most 2 points r1 , r2 where the
sign of the difference d(x) := fX (x) − fY (x) changes. Without loss of generality we assume that
d(x) is positive in (−∞, r1 ) and (r2 , +∞) and negative in [r1 , r2 ]. Now assume that k1 = ⌊r1 ⌋ and
33

k2 = ⌈r2 ⌉. Now we can lower bound the total variation distance of Xd , Yd




n
X
1
1
1
1
Pr k − < Xd ≤ k +
2dtv (Xd , Yd ) =
− Pr k − < Yd ≤ k +
2
2
2
2
k=0
n Z k+1/2
X
=
fX (x) − fY (x) dx

(21)

k−1/2

≥
≥

k=0
k1 Z k+1/2
X

Z
k2
X

d(x) dx +

−d(x) dx +

k=k1 +1 k−1/2

k=0 k−1/2
Z k1

d(x) dx +

Z

k2 −1

k1 +1

0

Z
n
X

k+1/2

−d(x) dx +

Z

k+1/2

d(x) dx

k=k2 +1 k−1/2

n

d(x) dx.
k2

R∞
Since dtv (X, Y ) = −∞ |fX (X) − fY (x)| dx we need to upper bound the “missing” integrals in the
above expression. We have





Z 0
Z 0
1
µ1
µ2
|d(x)|dx ≤
(fX (x) + fY (x)) dx =
erfc √
+ erfc √
2
2σ1
2σ2
−∞
−∞
Similarly,
Z

+∞

n

1
|d(x)| dx ≤
2



erfc



n − µ1
√
2σ1



+ erfc



n − µ2
√
2σ2



. Moreover,
Z

k1 +1
k1

|d(x)| dx +

Z

k2

k2 −1

|d(x)| dx ≤

Z

µ1 +1

Z

µ2 +1

fY (x)dx
fX (x)dx +
µ2 −1
µ1 −1




1
1
√
√
+ erf
≤erf
2σ1
2σ2

To prove the upper bound of inequality (20) notice that using (21) we have
2dtv (Xd , Yd ) =
≤
≤

n Z
X

k+1/2

k=0 k−1/2
n Z k+1/2
X

k=0 k−1/2
Z +∞
−∞

fX (x) − fY (x) dx
|fX (x) − fY (x) | dx

|fX (x) − fY (x) | dx

= 2ε

⊔
⊓
D.4

The proof of Theorem 1.6

We remark that finding a family of sequences satisfying ρ(θ(P), θ(Q)) = Ω (δ) instead of 2δ changes
the lower bound only by a constant factor. Thus, to simplify our analysis, we shall not compute
the constants for the lower bound. Note that these will be absolute constants, independent from
any parameter, like ε, δ, etc., in our setting.
34

We restate√explicitly our family of Binomial power sequences for the shake of completeness.
Let δ = Θ(1/ n N). Let p1 = 1/2, p2 = 1/2 + δ/4, p3 = 1/2 + δ/2. Let P1,1 = B(n, p1 ), P2,1 =
B(n, p2 ), P1,3 = B(n, p3 ) be three Binomial distributions with corresponding power sequences P1 =
(B(n, pi1 ))i∈(1,+∞) , P2 = (B(n, pi2 ))i∈(1,+∞) , P3 = (B(n, pi3 ))i∈(1,+∞) .
For the total variation
distance of any of the above pairs i, j ∈ {1, 2, 3}, i 6= j, we have
√ 
√
dtv (Pi , Pj ) = Ω 1/ N . Without loss of generality we prove that dtv (P1 , P2 ) = Ω(1/ N ).
From the definition of total variation distance for sequences of distributions we see that to √
lower
bound the metric ρ we just need to prove that the total variation distance of P1,1 , P2,1 is Ω(1/ N ),
namely we need to consider only the first power of the sequences.
Let µ1 = E[P1,1 ], µ2 = E[P2,1 ], σ12 = Var[P1,1 ], σ22 = Var[P2,1 ].
We first use Lemma D.1 to approximate P1,1 , P2,1 with discretized Normal distributions DN (µ1 , σ1 ),
√
DN (µ2 , σ2 ). Since σ1 , σ2 are both O( n) the error of the two discretized Normal approximations
√
is O(1/ n). From Proposition D.6 we obtain that we can approximate N (µ2 , σ2 ) using a Normal
with the same mean but with variance σ12 . Applying Proposition D.6 yields
dtv (N (µ2 , σ2 ) , N (µ2 , σ1 )) ≤


1 n/4 − n(1/4 − δ2 /16)
1 σ12 − σ22
2
=
O
δ
= O (1/n)
=
2
2 σ2
2
n(1/4 − δ2 /16)

Consider now the pair of continuous Normals N (µ1 , σ1 ) N (µ2 , σ1 ). Using Proposition D.5 we have
that


√ 


nδ
1
nδ
1
√ √
√
dtv (N (µ1 , σ1 ) , N (µ2 , σ1 )) = erf
= erf
= erf
√ √
≥ √ ,
4 2 n
4 2
4 2 N
9 N
by Corollary D.1. Therefore, by the triangle inequality, we have
 
1
1
dtv (N (µ1 , σ1 ) , N (µ2 , σ2 )) ≥ √ − O
n
9 N
 
√
Applying Lemma D.2 when σ1 , σ2 are O ( n) yields ℓ + m + u = O √1n , since from Komatsu’s
 −n 
√
inequalities (Proposition D.4) we have erfc ( n) = Θ e√n and from Proposition D.3 we have that
 
√
erf (1/ n) = Θ √1n . Therefore


1
1
dtv (DN (µ1 , σ1 ) , DN (µ2 , σ2 )) ≥ √ − O √
n
9 N
Overall, using triangle inequality and the above bounds we have that


1
1
dtv (P1,1 , P2,1 ) ≥ √ − O √
n
9 N
We continue with proving an upper bound for the Kullback-Leibler divergence between all
powers, namely the supa∈N Dkl (P1,a kP3,a ). To apply Theorem 5.2 it suffices to show that the following holds supi,j∈[3], a∈N Dkl (Pi,a kPj,a ) = O (1/N ). From Proposition D.2 it is clear that we
only need to bound the Kullback-Leibler distance for the most distant pi ’s, namely the distances
supa∈N Dkl (P1,a kP3,a ), supa∈N Dkl (P3,a kP1,a ). We remark that is easy to verify that Dkl (P1,a kP3,a ) ≈
Dkl (P3,a kP1,a ) for all a ∈ N and therefore we will bound Dkl (P1,a kP3,a ).
Applying Proposition D.1 for P1,a and P3,a gives
!
!a !
−a

1
−
2
1
+ 1 − 2−a n ln
Dkl (P1,a kP3,a ) = 2−a n ln 2−a δ 1
a
+
1 − 2δ + 12
2
2
35

Let f (δ) = Dkl (P1,a kP3,a ) defined by the above expression. Taylor Expanding f (δ) around 0 gives
f (δ) = 0 + R1 (z) for a z ∈ [−δ, δ]. To bound the error of the Taylor approximation we bound the
derivative f ′′ (δ)
an ((2a − 1) a(δ + 1)a − (2a − (δ + 1)a ) ((δ + 1)a − 1))
(δ + 1)2 (2a − (δ + 1)a )2
an ((2a − 1) a(δ + 1)a )
≤
(δ + 1)2 (2a − (δ + 1)a )2
na2 (2a − 1)(3/2)a
≤
(2a − (3/2)a )2
na2 3a
2
a
≤
2 = 16n a (3/4) ≤ 105n
a
(2 /4)

f ′′ (δ) =

Therefore, Dkl (P1,i kP3,i ) ≤ |R1 (z)| ≤ 105n δ2 ≤ 105/N for all i ∈ N.

36

⊔
⊓

