1

Maximum Likelihood Estimation of Functionals of
Discrete Distributions

arXiv:1406.6959v7 [] 10 Aug 2017

Jiantao Jiao, Student Member, IEEE, Kartik Venkat, Student Member, IEEE, Yanjun Han, Student Member, IEEE,
and Tsachy Weissman, Fellow, IEEE

Abstract—We consider the problem of estimating functionals
of discrete distributions, and focus on tight (up to universal multiplicative constants for each specific functional) nonasymptotic
analysis of the worst case squared error risk of widely used
estimators. We apply concentration inequalities to analyze the
random fluctuation of these estimators around their expectations,
and the theory of approximation using positive linear operators
to analyze the deviation of their expectations from the true
functional, namely their bias.
We explicitly characterize the worst case squared error risk
incurred by the Maximum Likelihood Estimator
(MLE) in
PS
estimating the Shannon entropy
H(P
)
=
−p
i ln pi , and
i=1
P
α
the power sum Fα (P ) = S
i=1 pi , α > 0, up to universal multiplicative constants for each fixed functional, for any alphabet
size S ≤ ∞ and sample size n for which the risk may vanish.
As a corollary, for Shannon entropy estimation, we show that
it is necessary and sufficient to have n ≫ S observations for
the MLE to be consistent. In addition, we establish that it is
necessary and sufficient to consider n ≫ S 1/α samples for the
MLE to consistently estimate Fα (P ), 0 < α < 1. The minimax
rate-optimal estimators for both problems require S/ ln S and
S 1/α / ln S samples, which implies that the MLE has a strictly
sub-optimal sample complexity. When 1 < α < 3/2, we show
that the worst-case squared error rate of convergence for the
MLE is n−2(α−1) for infinite alphabet size, while the minimax
squared error rate is (n ln n)−2(α−1) . When α ≥ 3/2, the MLE
achieves the minimax optimal rate n−1 regardless of the alphabet
size.
As an application of the general theory, we analyze the Dirichlet prior smoothing techniques for Shannon entropy estimation.
In this context, one approach is to plug-in the Dirichlet prior
smoothed distribution into the entropy functional, while the
other one is to calculate the Bayes estimator for entropy under
the Dirichlet prior for squared error, which is the conditional
expectation. We show that in general such estimators do not
improve over the maximum likelihood estimator. No matter how
we tune the parameters in the Dirichlet prior, this approach
cannot achieve the minimax rates in entropy estimation. The
performance of the minimax rate-optimal estimator with n
samples is essentially at least as good as that of Dirichlet smoothed
entropy estimators with n ln n samples.
Manuscript received Month 00, 0000; revised Month 00, 0000; accepted
Month 00, 0000. Date of current version Month 00, 0000. This work was
supported in part by the Center for Science of Information (CSoI) under
grant agreement CCF-0939370. Materials of this paper were presented in part
at the 2015 International Symposium on Information Theory, Hong Kong,
China. Personal use of this material is permitted. However, permission to
use this material for any other purposes must be obtained from the IEEE by
sending a request to pubs-permissions@ieee.org.
Jiantao Jiao, Yanjun Han, and Tsachy Weissman are with the Department of
Electrical Engineering, Stanford University, CA, USA. Email: {jiantao,yjhan,
tsachy}@stanford.edu.
Kartik Venkat was with the Department of Electrical Engineering, Stanford University. He is currently with PDT Partners. Email:
kvenkat@alumni.stanford.edu.

Index Terms—entropy estimation, maximum likelihood estimator, Dirichlet prior smoothing, approximation theory, high dimensional statistics, Rényi entropy, approximation using positive
linear operators

I. I NTRODUCTION
Entropy and related information measures arise in information theory, statistics, machine learning, biology, neuroscience,
image processing, linguistics, secrecy, ecology, physics, and
finance, among other fields. Numerous inferential tasks rely
on data driven procedures to estimate these quantities (see,
e.g. [1]–[6]). We focus on two concrete and well-motivated
examples of information measures, namely the Shannon entropy [7]
S
X
−pi ln pi ,
(1)
H(P ) ,
i=1

and the power sum Fα (P ), α > 0:
Fα (P ) ,

S
X

pα
i , α > 0.

(2)

i=1

The power sum Fα (P ) functional often emerges in various
operational problems [8]. It also has connections to the Rényi
Fα (P )
entropy [9] Hα (P ) via the formula Hα (P ) = ln 1−α
.
Consider estimating the Shannon entropy H(P ) based on n
i.i.d. samples following unknown discrete distribution P with
unknown alphabet size S. This problem has a rich history
with extensive study in various fields ranging from information
theory, statistics, neuroscience, physics, psychology, medicine,
etc. We refer the reader to [10] for a review. One of the
most widely used estimators for this purpose is the Maximum
Likelihood Estimator (MLE), which is simply the empirical
entropy. The empirical entropy is an instantiation of the plugin principle in functional estimation, where a point estimate of
the parameter (distribution P in this case) is used to construct
an estimator for a functional of the parameter via the plug-in
approach. The idea of using the MLE for estimating information measures of interest (in this case entropy), is not only
intuitive, but has sound justification: asymptotic efficiency.
The beautiful theory of Hájek and Le Cam [11]–[13] shows
that, as the number of observed samples grows without bound
while the finite parameter dimension (e.g., alphabet size)
remains fixed, the MLE performs optimally in estimating any
differentiable functional when the statistical model complies
with the benign LAN (Local Asymptotic Normality) condition [13]. Thus, for finite dimensional problems, the problems

2

of parameter and functional estimation are well understood
in an asymptotic sense, and the MLE appears to be not only
natural but also theoretically justified. But does it make sense
to employ the MLE to estimate the entropy in most practical
applications?
As it turns out, while asymptotically optimal in entropy
estimation, the MLE is by no means sacrosanct in many
real applications, especially in regimes where the alphabet
size is comparable to, or even larger than the number of
observations. It was shown that the MLE for entropy is strictly
sub-optimal in the large alphabet regime [14], [15]. Therefore,
classical asymptotic theory does not satisfactorily address
high dimensional settings, which are becoming increasingly
important in the modern era of high dimensional statistics.
There has been a wave of recent research activities focusing
on analyzing existing approaches of functional estimation,
as well as proposing new estimators that are provably near
optimal in the large alphabet regime. Paninski [14] showed that
the MLE needs n ≫ S samples to consistently estimate the
Shannon entropy, and Paninski [15] established the existence
of a (non-explicit) estimator that only required n ≪ S
samples. It implies that the MLE is strictly sub-optimal in
terms of sample complexity. It was Valiant and Valiant [16]
who first explicitly constructed a linear programming based
estimator (later modified in [17]) that achieves consistency in
entropy estimation with n ≫ S/ ln S samples, which they also
proved to be necessary. Valiant and Valiant [18] constructed
another approximation based estimator that achieved better
theoretical properties than the linear programming ones, which
was not yet shown to be minimax rate-optimal for all ranges
of S and n. The authors [10] constructed the first minimax
rate-optimal estimators for H(P ) and Fα (P ), α > 0 based
on best polynomial approximation, which are agnostic to the
alphabet size S. Utilizing the released MATLAB and Python
packages of the estimators in [10], [19], [20] demonstrated that
these minimax rate-optimal estimators can lead to significant
performance boosts in various machine learning tasks. Wu and
Yang [21] independently applied the best polynomial approximation idea to entropy estimation and obtained the minimax
rates. However, their estimator requires the knowledge of the
alphabet size S. The approximation ideas proved to be very
fruitful in Acharya et al. [22], Wu and Yang [23], Han, Jiao,
and Weissman [24], Jiao, Han, and Weissman [25], Bu et
al. [26], Orlitsky, Suresh, and Wu [27], Wu and Yang [28].
The main contribution of this paper is an explicit characterization of the worst case squared error risk of estimating H(P )
and Fα (P ) using the MLE up to a universal multiplicative
constant for each specific functional, for all ranges of S and
n in which the risk may vanish. Understanding the benefits
and limitations of the MLE in a nonasymptotic setting serves
two key purposes. First, the approach is a natural benchmark
for comparing other more nuanced procedures for estimation
of functionals. Second, performance analysis for the MLE
reveals regimes where the problem is difficult, and motivates
the development of improvements, which have been validated
in [10], [14]–[18], [21], [22]. As a byproduct of the analysis,
we explicitly point out an equivalence between bias analysis
of functional estimators using plug-in rules and approximation

theory using positive linear operators. We believe these powerful tools introduced from approximation theory may have far
reaching impacts in various applications in the information
theory community.
We mention that there exist numerous other approaches
proposed in various disciplines to estimate entropy, many
among which are difficult to analyze theoretically. Among
them we mention the Miller–Madow bias-corrected estimator
and its variants [29]–[31], the jackknife estimator [32], the
shrinkage estimator [33], the coverage adjusted estimator [34],
the Best Upper Bound (BUB) estimator [14], the B-Splines
estimator [35], and [36], [37] etc. For a Bayesian statistician, a
natural approach is to first impose a prior on the unknown discrete distribution before considering estimating entropy. The
Dirichlet prior, being the conjugate prior to the multinomial
distribution, appears to be particularly popular in the Bayesian
approach to entropy estimation. Dirichlet smoothing may have
two connotations in the context of entropy estimation:
•

•

[38], [39] One first obtains a Bayes estimate for the
discrete distribution P , which we denote by P̂B , and then
plugs it in the entropy functional to obtain the entropy
estimate H(P̂B ).
[40] [41] One calculates the Bayes estimate for entropy
H(P ) under Dirichlet prior for squared error. The estimator is the conditional expectation E[H(P )|X], where
X represents the samples.

Nemenman, Shafee, and Bialek [42] argued in an intuitive
way why Dirichlet prior is bad for entropy estimation and
proposed to use mixtures of Dirichlet priors. Archer, Park,
and Pillow [43] have come up with priors that perform better
than the Dirichlet prior. Also see [44], [45].
Another contribution of this paper is an explicit characterization of the worst case squared error risk of estimating H(P )
using the Dirichlet prior plug-in approach up to a universal
multiplicative constant, for all ranges of S and n in which the
risk may vanish. We show rigorously that neither of the two
approaches utilizing the Dirichlet prior result in improvements
over the MLE in the large alphabet regime. Specifically, these
approaches require at least n ≫ S to be consistent, while the
minimax rate-optimal estimators such as the ones in [10] [21]
only need n ≫ lnSS to achieve consistency.
The rest of the paper is organized as follows. We present
the main results in Section III, discuss the fundamental ideas
behind the proofs in Section IV, and detail the proofs in
Section V and VI. Proofs of auxiliary lemmas are deferred
to the appendices.

II. P RELIMINARIES
The Dirichlet distribution with order S ≥ 2 with parameters
α1 , . . . , αS > 0 has a probability density function with respect
to Lebesgue measure on the Euclidean space RS−1 given by
S

f (x1 , · · · , xS ; α1 , · · · , αS ) =

1 Y αi −1
x
B(α) i=1 i

(3)

3

on the open S − 1-dimensional simplex defined by:
x1 , · · · , xS−1 > 0
x1 + · · · + xS−1 < 1

(4)
(5)

xS = 1 − x1 − · · · − xS−1

(6)

and zero elsewhere. The normalizing constant is the multinomial Beta function, which can be expressed in terms of the
Gamma function:
QS
Γ(αi )
,
α = (α1 , · · · , αS ).
(7)
B(α) = i=1
PS
Γ
α
i
i=1

Assuming the unknown discrete distribution P follows
prior distribution P ∼ Dir(α), and we observe a vector X = (X1 , X2 , . . . , XS ) with multinomial distribution
multi(n; p1 , p2 , . . . , pS ), then one can show that the posterior
distribution PP |X is also a Dirichlet distribution with parameters

estimator Ĥ Bayes the Bayes estimator under Dirichlet prior.
Throughout this paper, we observe n i.i.d. samples from
an unknown discrete distribution P = (p1 , p2 , . . . , pS ).
We denote the n samples as n i.i.d. random variables
{Zi }1≤i≤n taking values in Z = {1, 2, . . . , S} with probability (p1 , p2 , . . . , pS ). Defining
Xi ,

n
X
j=1

1(Zj = i), 1 ≤ i ≤ S,

(12)

we know that (X1 , X2 , . . . , XS ) follows a multinomial distribution with parameter (n; p1 , p2 , . . . , pS ). Denote hj ,
PS
0 ≤ j ≤ n. The Maximum Likelihood
i=1 1(Xi = j),
Estimator (MLE) for H(P ) and Fα (P ) are defined, respectively, as H(Pn ) and Fα (Pn ), with Pn being the empirical
distribution. We assume the functional F (P ) takes the form
F (P ) =

S
X

f (pi ).

(13)

i=1

α + X = (α1 + X1 , α2 + X2 , . . . , αS + XS ) .

(8)

Furthermore, the posterior mean (conditional expectation)
of pi given X is given by [46, Example 5.4.4]
δi (X) , E[pi |X] =

αi + Xi
.
P
n + Si=1 αi

(9)

The estimator δi (X) is widely used
in practice for various
√
n
choices of α. For example, if αi = S , then the corresponding
(δ1 (X), δ2 (X), . . . , δS (X)) is the minimax estimator for P
under squared loss [46, Example 5.4.5]. However, it is no
longer minimax under other loss functions such as ℓ1 loss,
which was investigated in [47].
Note that the estimator δi (X) subsumes the MLE p̂i = Xni
as a special case, since we can take the limit α → 0 for
δi (X) to obtain MLE. We denote the empirical distribution
by Pn = (p̂1 , p̂2 , . . . , p̂S ). The Dirichlet prior smoothed
distribution estimate is denoted as P̂B , where
PS
α
n
i=1 αi
Pn +
P̂B =
.
(10)
PS
PS
PS
n + i=1 αi
n + i=1 αi i=1 αi
Note that the smoothed distribution P̂B can be viewed as a
convex combination of the empirical distribution Pn and the
prior distribution PSα α . We call the estimator H(P̂B ) the
i=1 i
Dirichlet prior smoothed plug-in estimator.
Another way to apply Dirichlet prior in entropy estimation
is to compute the Bayes estimator for H(P ) under squared
error, given that P follows Dirichlet prior. It is well known
that the Bayes estimator under squared error is the conditional
expectation. It was shown in Wolpert and Wolf [40] that
!
S
X
(αi + Xi )
= ψ 1+
i=1

where ψ(z) ,

αi + Xi

PS

Γ′ (z)
Γ(z)

2
where
 (EP F̂ −
2F (P )) represents the squared bias, and
EP F̂ − EP F̂
represents the variance. The subscript P
means that the expectation is taken with respect to the distribution P that generates the i.i.d. observations. We omit the
subscript for the expectation operator E if the meaning of the
expectation is clear from the context.
Notation: a ∧ b denotes min{a, b}, a ∨ b denotes max{a, b}.
For two non-negative series {an }, {bn }, notation an . bn
means that there exists a positive universal constant C < ∞
such that abnn ≤ C, for all n. The notation an ≍ bn is equivalent
to an . bn and bn . an . Notation an ≫ bn means that
lim inf n→∞ abnn = ∞. Throughout this paper, the notations
., &, ≪, ≫ involve absolute constants that may only depend
on α but not S or n. We denote by MS the space of discrete
distributions with alphabet size S.

i=1 (αi

+ Xi )

RESULTS

A. Estimating Fα (P )
We split the upper bounds and the lower bounds into two
theorems, and present their succinct summaries in Corollary 1
and 2.

i=1

−

Recall that the risk function under squared error for any estimator F̂ in estimating functional F (P ) may be decomposed
as

2
EP (F (P ) − F̂ )2 = (EP F̂ − F (P ))2 + EP F̂ − EP F̂ ,
(15)

III. M AIN

Ĥ Bayes , E[H(P )|X]

S
X

Then it is evident that the MLE F (Pn ) for estimating functional F (P ) in (13) can be alternatively represented as the
following linear function of (h0 , h1 , . . . , hn ):
 
n
X
j
f
F (Pn ) =
hj .
(14)
n
j=0

!

ψ(αi + Xi + 1), (11)

is the digamma function. We call the

Theorem 1 (Upper bounds). We have the following upper
bounds on the worst case squared error risk of MLE in
estimating Fα (P ):

4

1) α ≥ 2:
2

sup EP (Fα (Pn ) − Fα (P )) ≤

P ∈MS



α(α − 1)
2n

2

2

+

α
.
4n
(16)

2) 1 < α < 2:
sup EP (Fα (Pn ) − Fα (P ))2

P ∈MS

≤



4
nα−1

∧

3S 1−α/2
5S
∧ Cα,n
2n
nα/2

2

+

α2
,
4n

sup EP (Fα (Pn ) − Fα (P ))
≤

2

5S
3S 1−α/2
∧ α
α/2
2n
2n



S
120
1
10S 2−2α
+ 2
∧
. (18)
+
n
α
n2α n2α−1

4) 0 < α < 1/2:
2

sup EP (Fα (Pn ) − Fα (P ))

2
5S
3S 1−α/2
∧
2nα
2nα/2



120
S
1
10S
.
+ 2
∧
+
n2α
α
n2α n2α−1


sup EP (Fα (Pn ) − Fα (P ))

(22)

2

2

1
α2 (1 − α)2
2
.
(S − 1) 1 −
≥
36n2α
n

(23)

There are several interesting implications of this result,
highlighted in the following corollaries.
Corollary 1. For any fixed α > 1, there exist universal
convergence rates for Fα (P ):

≍
(19)

Theorem 2 (Lower bounds). We have the following lower
bounds on the worst case squared error risk of MLE in
estimating Fα (P ):

1) α ≥ 3/2: there exists a constant Cα > 0 such that for
all n,
Cα
2
.
(20)
sup EP (Fα (Pn ) − Fα (P )) ≥
n
P ∈MS
2) 1 < α < 3/2: if S = cn, for any c > 0, then
lim inf n2(α−1) · sup EP (Fα (Pn ) − Fα (P ))2 > 0.
P ∈MS

4) 0 < α < 1/2: if n ≥ S, then

#2

sup EP (Fα (Pn ) − Fα (P ))2

S∈N+ P ∈MS

Moreover, in all the bounds presented above, the first term
bounds the square of the bias, and the second term bounds
the variance.

n→∞


1−α
−
(2(S − 1))1−α + 2−α
4n
!
1 −n/4 2(1−α)
− e
S
,
2

sup

P ∈MS

≤

2

1
α2 (1 − α)2
2
(S − 1) 1 −
≥
72n2α
n
"
α2
(2(S − 1))1−α − 2−α
+
64en

P ∈MS

2



2

sup EP (Fα (Pn ) − Fα (P ))

P ∈MS

(17)

where Cα,n , nωϕ2 (xα , n−1/2 ) > 0 satisfies
lim supn→∞ Cα,n < ∞ for 1 < α < 2, and ωϕ2 is
the second-order Ditzian–Totik modulus of smoothness
introduced in Section IV-B.
3) 1/2 ≤ α < 1:
P ∈MS

3) 1/2 ≤ α < 1: if n ≥ S, then

(21)

(

n−2(α−1)

1 < α < 3/2

n−1

α ≥ 3/2

(24)

Corollary 1 implies that, when α ≥ 3/2, estimation of
Fα (P ) is extremely simple in terms of convergence rate: plugin estimation achieves the best possible rate n−1 (as shown
in the theory of regular statistical experiments of classical
asymptotic theory, see [48, Chap. 1.7.]). Results of this form
have appeared in the literature, for example, Antos and Kontoyiannis [49] showed that it suffices to take n ≫ 1 samples
to consistently estimate Fα (P ), α ≥ 2, α ∈ Z. However,
when 1 < α < 3/2, the rate n−2(α−1) is considerably
slower. Interestingly, there exist estimators that demonstrate
better convergence rates for estimating Fα (P ), 1 < α < 3/2.
Jiao et al. [10] showed that the minimax rate in estimating Fα (P ), 1 < α < 3/2, is (n ln n)−2(α−1) as long as
S & n ln n, which is achieved using the general methodology developed therein for constructing minimax rate-optimal
estimators for nonsmooth functionals.
Let us now examine the case 0 < α < 1, another
interesting regime that has not been characterized before. In
this regime, we observe significant increase in the difficulty
of the estimation problem. In particular, the relative scaling
between the number of observations n and the alphabet size S
for consistent estimation of Fα (P ) exhibits a phase transition,
encapsulated in the following.
Corollary 2. Fix α ∈ (0, 1). The worst case squared error
risk of the MLE Fα (Pn ) in estimating Fα (P ) is characterized

5

as follows when n ≥ S:

B. Estimating H(P )
2

We not only consider H(Pn ), but also the so-called Miller–
Madow bias-corrected estimator [29] defined as

sup EP (Fα (Pn ) − Fα (P ))
( S2
S 2−2α
1/2 < α < 1
n2α +
n
≍
2
S
0 < α ≤ 1/2
n2α

P ∈MS

Corollary 2 follows directly from Theorem 1 and Theorem 2. In particular, it implies that it is necessary and
sufficient to take n ≫ S 1/α samples to consistently estimate
Fα (P ), 0 < α < 1 using MLE. Thus, as one might expect, the
scale of the number of measurements required for consistent
estimation increases as α decreases. When α → 0, the number
of samples required for the MLE grows super-polynomially in
S, which is consistent with the intuition that Fα (P ), α → 0
is essentially equivalent to the alphabet size of a distribution,
whose estimation is known to be very hard when there may
exist symbols with very small probabilities [50].
We exhibit some of our findings by plotting the value
required of ln n/ ln S for consistent estimation of Fα (P ) using
the MLE Fα (Pn ), as a function of α, in Figure 1.
ln n
ln S

S−1
.
2n

H MM (Pn ) = H(Pn ) +

(25)

(26)

Theorem 3. The worst case squared error risk of H(Pn )
admits the following upper bound for all S, n:
sup EP (H(Pn ) − H(P ))

P ∈MS

≤



2


2 

S−1
(ln n)2 2(ln S + 3)2
ln 1 +
.
+
∧
n
n
n
(27)

If n ≥ 15S, then

sup EP (H(Pn ) − H(P ))2

P ∈MS

≥

1
2



S−1
1
S2
−
+
2
2n
20n
12n2

2

+c

ln2 S
.
n

(28)

Moreover, if n ≥ 15S, the Miller–Madow bias-corrected
estimator satisfies
2
sup EP H MM (Pn ) − H(P )
P ∈MS

≥

1
2



S2
1
−
20n2 12n2

2

+c

ln2 S
,
n

(29)

where the positive constant c > 0 in both expressions does not
depend on S or n.
Theorem 3 implies the following corollary.
Corollary 3. The worst case squared error risk of the MLE
H(Pn ) in estimating H(P ) is characterized as follows when
n ≥ 15S:

achievable via MLE
(Theorem 1)
1

1/α

sup EP (H(Pn ) − H(P ))2 ≍

P ∈MS

1

(30)

Here the first term corresponds to the squared bias, and the
second term corresponds to the variance.

not achievable via MLE
(Theorem 2)
0

ln2 S
S2
+
.
2
n
n

2

α

Fig. 1: For any fixed point above the thick curve, consistent
estimation of Fα (P ) is achieved using MLE Fα (Pn ) as shown
in Theorem 1. For any fixed point below the thick curve in
the regime 0 < α < 1, Theorem 2 shows that the MLE does
not have vanishing maximum squared error risk.
It turns out that one can construct estimators that are better
than the MLE in terms of required sample complexity for
consistent estimation for the regime 0 < α < 1. Indeed, Jiao
et al. [10] showed that the minimax rate-optimal estimator
1
Sα
requires n ≫ ln
S samples to achieve consistency, which
attains a logarithmic improvement in the sample complexity
over the MLE.

Paninski [14] showed that if n = cS, where c > 0 is
a constant, the maximum squared error risk of H(Pn ), and
the Miller–Madow bias-corrected estimator H MM (Pn ), would
be bounded from zero. Paninski [14] also showed that when
n ≫ S, n → ∞, the MLE is consistent for estimating entropy.
Corollary 3 implies that it is necessary and sufficient to take
n ≫ S samples for the MLE to be consistent for estimating
entropy. Comparing the results for H(P ) with those for
Fα (P ), we see that the intuition that H(P ) being viewed close
to Fα (P ) when α → 1−1 is indeed approximately correct as
H(P ) coincides with α → 1− on the phase transition curve
shown in Figure 1.
Table I summarizes the minimax squared error rates and the
worst case squared error rates of the MLE in estimating H(P )
and Fα (P ), α > 0. It is clear that the MLE cannot achieve the
minimax rates for estimation of H(P ), and Fα (P ) when 0 <
α < 3/2. In these cases, there exist strictly better estimators
whose performance with n samples is roughly the same as

6

H(P )
Fα (P ), 0 < α ≤

1
2

Fα (P ), 21 < α < 1
Fα (P ), 1 < α < 23
Fα (P ), α ≥ 23

Minimax squared error rates
S2
ln2 S
(n & S/ ln S) ( [10], [16], [18], [21])
(n ln n)2 + n

S2
n & S 1/α / ln S, ln n . ln S ( [10])
(n ln n)2α

S2
S 2−2α
n & S 1/α / ln S ( [10])
(n ln n)2α +
n
(n ln n)−2(α−1) (S & n ln n) ( [10])
n−1 (Theorem 1)

Maximum squared error rates of MLE
S2
ln2 S
(n & S) (Corollary 3)
n2 + n

S2
n & S 1/α (Corollary 2)
n2α

S2
S 2−2α
n & S 1/α (Corollary 2)
n2α +
n
n−2(α−1) (S & n) (Corollary 1)
n−1

TABLE I: Summary of results in this paper and the companion [10]

that of the MLE with n ln n samples. This phenomenon was
termed effective sample size enlargement in [10].

L2 risk of H(P̂B ) in estimating H(P ) is lower bounded as

2
sup EP H(P̂B ) − H(P )
P ∈MS

C. Dirichlet prior techniques applying to entropy estimation

For symmetry, we restrict attention to the case where
the parameter α in the Dirichlet distribution takes the form
(a, a, . . . , a).
In comparison to MLE H(Pn ), where Pn is the empirical
distribution, the Dirichlet smoothing scheme H(P̂B ) has a
disadvantage: it requires the knowledge of the alphabet size S
in general. We define
p̂B,i =
and
pB,i

np̂i + a
,
n + Sa

npi + a
.
= E[p̂B,i ] =
n + Sa

(31)
(32)

It is clear that
n
Sa
P̂B =
Pn +
US
(33)
n + Sa
n + Sa
n
Sa
PB =
P+
US ,
(34)
n + Sa
n + Sa
where Pn stands for the empirical distribution, P is the true
distribution, and US denotes the uniform distribution on the
same alphabet with size S.
Theorem 4. If n ≥ max{Sa, 2ea}, then the maximum
squared error risk of H(P̂B ) in estimating H(P ) is upper
bounded as

2
sup EP H(P̂B ) − H(P )
P ∈MS

≤

 

2

S−1
2Sa
n + Sa
ln 1 +
∨
ln
n + Sa
n + Sa
2a


2
n + Sa
2n
3 + ln
∧S
.
(35)
+
(n + Sa)2
a+1

Here the first term bounds the squared bias, and the second
term bounds the variance.
Theorem 5. If n ≥ max{15S, Sa, 2ea}, then the maximum



2

S−1
1
S2
n + Sa
1 (S − 1)a
+
−
ln
+
≥
2 4(n + Sa)
a
8n
80n2 48n2
ln2 S
,
(36)
+c
n
where c > 0 is a universal constant that does not depend on
a, S, or n.
If n < Sa, then we have

2  S − 1 2
ln2 S.
sup EP H(P̂B ) − H(P ) ≥
2S
P ∈MS

(37)

If n < 2ea, then we have

2  S − 1 2
sup EP H(P̂B ) − H(P ) ≥
ln2 S. (38)
S + 2e
P ∈MS
If n < 15S, n ≥ 2ea, then we have

2
sup EP H(P̂B ) − H(P )

P ∈MS

≥

"

(S − 1)a
ln
4(n + Sa)



n + Sa
a



⌊n/15⌋
1
+
−
8n
16n

 #2

,

+

(39)

where ⌊x⌋ is the largest integer that does not exceed x, and
(x)+ = max{x, 0} represents the positive part of x.
The following corollary immediately follows from Theorem 4 and Theorem 5.
Corollary 4. If n ≫ S and a is upper bounded by a constant,
then the maximum squared error risk of H(P̂B ) vanishes.
Conversely, if n . S, then the maximum squared error risk of
H(P̂B ) is bounded away from zero.
The next theorem presents a lower bound on the maximum
risk of the Bayes estimator under Dirichlet prior. Since we
have assumed that all αi = a, 1 ≤ i ≤ S, the Bayes estimator
under Dirichlet prior is
Ĥ Bayes = ψ(Sa + n + 1) −

S
X
a + Xi
ψ(a + Xi + 1). (40)
Sa + n
i=1

7

Theorem 6. If S ≥ 2(n + 1), then

2  
sup EP Ĥ Bayes − H(P ) ≥ ln
P ∈MS

given that Z1 , Z2 , . . . , Zn are independent random variables.
Sa + S/2
Sa + n + e−γ

2

,

We refer the readers to Boucheron et al. [52] for a modern
exposition of the concentration inequality toolbox.

(41)

where γ ≈ 0.5772 is the Euler-Mascheroni constant.
Evident from Theorem 4, 5, and 6 is the fact that in
the best situation (i.e. a not too large), both the Dirichlet
prior smoothed plug-in estimator and the Bayes estimator
under Dirichlet prior still require at least n ≫ S samples
to be consistent, which is the same as MLE. In contrast, the
estimators in Valiant and Valiant [16]–[18], Jiao et al. [10], Wu
and Yang [21] are consistent if n ≫ lnSS , which is the optimal
sample complexity. Thus, we can conclude that the Dirichlet
smoothing technique does not solve the entropy estimation
problem.
IV. F UNDAMENTAL

IDEAS OF OUR ANALYSIS

In this section, we discuss the fundamental tools we employed to obtain the results in Section III, as well as general
recipes we suggest for analyzing performances of functional
estimators.
A. Variance
The variance characterizes the degree to which the random
variable F (P̂ ) is fluctuating around its expectation, and the
field of concentration inequalities perfectly fits our glove to
give the desired results. For all the functionals we consider,
it turns out that the Efron–Stein inequality [51] and the
bounded differences inequality give very tight bounds. For
completeness we state them below.
Lemma 1.
[52, Efron–Stein inequality, Theorem 3.1]
Let Z1 , . . . , Zn be independent random variables and let
f (Z1 , Z2 , . . . , Zn ) be a square integrable function. Moreover,
if Z1′ , Z2′ , . . . , Zn′ are independent copies of Z1 , Z2 , . . . , Zn
and if we define, for every i = 1, 2, . . . , n,

B. Bias
It turns out that the bias analysis in estimation, albeit
widely studied in statistics, seems to still largely bear an
asymptotic and expansion nature in the mainstream statistical literature [53], [54]. In particular, the bootstrap [55]
as a method for estimating functionals was essentially only
analyzed in an asymptotic setting [56]. Among asymptotic
analysis techniques, probably the most popular one is the
Taylor expansion. We will show that the Taylor expansion may
encounter great difficulties in analyzing the bias of MLE in
information measure estimation. Then, we will introduce the
field of approximation theory using positive linear operators
and demonstrate that it is essentially equivalent to nonasymptotic bias analysis for plug-in functional estimators. In doing
so, we present the readers with abundant handy tools from
approximation theory, which could be readily applicable to
many problems that may seem highly intractable with standard
expansion methods.
We start from entropy estimation. In the literature, considerable effort has been devoted to understanding the nonasymptotic performance of the MLE H(Pn ) in estimating
H(P ). One of the earliest investigations in this direction is
due to Miller [29] in 1955, who showed that, for any fixed
distribution P ,
 
1
S−1
.
(46)
+O
EH(Pn ) = H(P ) −
2n
n2

Equation (46) was later refined by Harris [57] using higher
order Taylor series expansions to yield
!
 
S
X
S
−
1
1
1
1
′
′
EH(P
)
=
H(P
)−
1
−
.
+O
+
n
fi = f (Z1 , Z2 , . . . , Zi−1 , Zi , Zi+1 , . . . , Zn ),
(42)
3
2n
12n2
p
n
i=1 i
(47)
then
n

1X 
Harris’s
result
reveals
an
undesirable
consequence
of
the
E (f − fi′ )2 .
(43)
Var(f ) ≤
Taylor expansion method: one cannot obtain P
uniform bounds
2 i=1
S
1
on the bias of the MLE. Indeed, the term
i=1 pi can be
The following inequality, which is called the bounded arbitrarily large for some distribution P . However,
it is evident
differences inequality, is a useful corollary of the Efron–Stein that both H(P ) and H(P ) are bounded above by ln S, since
n
inequality.
the maximum entropy of any distribution supported on S
S. Conceivably, for such a distribution P that
Lemma 2. [52, Bounded differences inequality, Corollary elements is lnP
S
1
n
would
make
3.2] If function f : Z → R has the bounded differences
i=1 pi very large, we need to compute even
higher order Taylor expansions to obtain more accuracy, but
property, i.e., for some nonnegative constants c1 , c2 , . . . , cn ,
even with such efforts we cannot obtain a uniform bias bound
sup
|f (z1 , . . . , zn ) − f (z1 , . . . , zi−1 , zi′ , zi+1 , . . . , zn )| for all P .
z1 ,...,zn ,zi′ ∈Z
We gain one of our key insights into the bias of the MLE by
≤ ci ,
(44)
relating it to the approximation error induced by the Bernstein
polynomial approximation of the function f , which was first
for every 1 ≤ i ≤ n, then
observed in Paninski [14]. To see this, we first compute the
n
1X 2
Var(f (Z1 , Z2 , . . . , Zn )) ≤
ci ,
(45) bias of F (Pn ) in estimating the functional F (P ) in (13).
4 i=1

8

Lemma 3. The bias of the estimator F (Pn ) is given by

where {µx } is a set of probability measures parametrized by
x, which may be viewed as a parameter. If we view the
Bias(F (Pn )) , EF (Pn ) − F (P )

 random variable Z as a summary statistics to plug-in the
  
S
n
functional f (·), the positive linear operator L(f )(x) is nothing
X
X
j
n j

f
=
pi (1 − pi )n−j − f (pi ) .but the expectation of the plug-in estimator f (Z). In this sense,
n
j
i=1
j=0
there exists a one-to-one correspondence between essentially
(48) the most general bias analysis problem in statistics, and the
most general positive linear operator approximation problem
The bias term in (48) can be equivalently expressed as1
in approximation theory.


 
n
S
After more than a century’s active research on approximaX
X
j

Bj,n (pi ) − f (pi ) (49) tion using positive linear operators, we now have highly nonf
Bias(F (Pn )) =
n
j=0
i=1
trivial tools for positive linear operators of functions on one
S
dimensional compact sets, but the general theory for vector
X
(Bn [f ](pi ) − f (pi )) ,
(50) valued multivariate functions on non-compact sets is still far
=
i=1
from complete [62]. In the next subsection, we present a

n j
n−j
where Bj,n (x) , j x (1−x)
is the well-known Bernstein sample of existing results in approximation using positive
polynomial basis, and Bn [f ](x) is the so-called Bernstein linear operators, corollaries of which will be used to analyze
polynomial for function f (x). Bernstein in 1912 [61] provided the bias of the MLE for two examples: Fα (P ) and H(P ).
2) Some general results in bias analysis: First, some elan insightful constructive proof of the Weierstrass theorem on
ementary
approximation theoretic concepts need to be introapproximation of continuous functions using polynomials, by
duced
in
order
to characterize the degree of smoothness of
showing that the Bernstein polynomial of any continuous funcfunctions.
For
I
⊂ R an interval, the first-order modulus of
tion converges uniformly to that function. From a functional
1
smoothness
ω
(f,
t), t ≥ 0 is defined as [62]
analytic viewpoint, the Bernstein polynomial is an operator
that maps a continuous function f ∈ C[0, 1] to another
continuous function Bn [f ] ∈ C[0, 1]. This operator is linear
in f , and is positive because Bn [f ] is also pointwise nonnegative if f is pointwise non-negative. Evidently, bounding
the approximation error incurred by the Bernstein polynomial
is equivalent to bounding the bias of the MLE f (X/n), where
X ∼ B(n, x). Fortunately, the theory of approximation using
positive linear operators [62] provides us with advanced tools
that are very effective for the bias analysis our problem calls
for. A century ago, probability theory served Bernstein in
breaking new ground in function approximation. It is therefore
very satisfying that advancements in the latter have come full
circle to help us better understand probability theory and statistics. We briefly review the general theory of approximation
using positive linear operators below.
1) Approximation theory using positive linear operators:
Generally speaking, for any estimator θ̂ of a parametric model
indexed by θ, the expectation f 7→ Eθ f (θ̂) is a positive
linear operator for f , and analyzing the bias Eθ f (θ̂) − f (θ)
is equivalent to analyzing the approximation properties of the
positive linear operator Eθ f (θ̂) in approximating f (θ). Hence,
analyzing the bias of any plug-in estimator for functionals
of parameters from any parametric families can be recast
as a problem of approximation theory using positive linear
operators [62].
Conversely, given a positive linear operator L(f )(x) that
operates on the space of continuous functions, the Riesz–
Markov–Kakutani theorem implies that under mild conditions
the operator may be written as
Z
(51)
L(f )(x) = f dµx = Eµx f (Z), Z ∼ µx ,
I

Pn

1 In the literature of combinatorics, the sum
j=0 aj,n Bj,n (x) is called
the Bernoulli sum, and various approaches have been proposed to evaluate its
asymptotics [58], [59], [60].

ω 1 (f, t) , sup{|f (u) − f (v)| : u, v ∈ I, |u − v| ≤ t}. (52)

The second-order modulus of smoothness ω 2 (f, t), t ≥ 0
[62] is defined as
(


u+v
2
+ f (v) :
ω (f, t) , sup f (u) − 2f
2
)
u, v ∈ I, |u − v| ≤ 2t .

(53)

Ditzian and Totik [63] introduced a class of moduli of
smoothness, which proves to be extremely useful in characterizing the incurred approximationp
errors. For simplicity, for
functions defined on [0, 1], ϕ(x) = x(1 − x), the first-order
Ditzian–Totik modulus of smoothness is defined as
(
ωϕ1 (f, t) , sup |f (u) − f (v)| :

u, v ∈ [0, 1], |u − v| ≤ tϕ



u+v
2

)

,

(54)

and the second-order Ditzian–Totik modulus of smoothness is
defined as
(


u+v
2
+ f (v) :
ωϕ (f, t) , sup f (u) − 2f
2
)

u+v
.
u, v ∈ [0, 1], |u − v| ≤ 2tϕ
2
(55)
Recall that we denote by ej , j ∈ N+ ∪ {0}, the monomial
functions ej (y) = y j , y ∈ I. The first estimate for general positive linear operators, using modulus ω 2 and with precise constants, was given by Gonska [64]. We rephrase Paltanea [62,

9

Cor. 2.2.1.] as follows. Note that notation e1 − xe0 denotes a
continuous function on I which is the difference of a linear
function y and a constant function with constant value x over
I. In other words, it is an abbreviation of e1 (y)−xe0 (y), y ∈ I,
which is a function of y rather than x.
For a positive linear functional F , we adopt the following
notation

BF (x) = |F (e1 ) − xF (e0 )| , VF = F (e1 − F (e1 )e0 )2 ,
(56)
which represent the “bias” and “variance” of a positive linear
functional F .
Lemma 4. [62, Cor. 2.2.1.] Let F : C(I) → R be a positive
linear functional, where I ⊂ R is an interval. Suppose that
F (e0 ) = 1, t > 0, length(I) ≥ 2t, s ≥ 2. Then,

ω 1 (f, t)
|F (f ) − f (x)| ≤ BF (x)
t


F (|e1 − xe0 |s )
+ 1+
ω 2 (f, t). (57)
2ts

We remark that Lemma 4 can be applied to bound the bias
of plug-in estimators in very general models. For example,
consider an arbitrary statistical experiment {Pθ , θ ∈ I}, from
which we obtain n i.i.d. samples X1 , X2 , . . . , Xn ∼ Pθ . For
any estimator θ̂n , we would like to analyze the bias of the
plug-in estimator f (θ̂n ) for functional f (θ).
Suppose length(I) ≥ 2t, s ≥ 2, then Lemma 4 implies that
ω 1 (f, t)
t
!
E|θ̂n − θ|s
1+
ω 2 (f, t). (58)
2ts

|Eθ f (θ̂n ) − f (θ)| ≤ |Eθ θ̂n − θ|
+

If we further assume that θ̂n is an unbiased estimator for θ,
i.e., Eθ θ̂n = θ holds for all θ ∈ I, then we have
!
E|θ̂n − θ|s
|Eθ f (θ̂n ) − f (θ)| ≤ 1 +
ω 2 (f, t).
(59)
2ts
Taking s = 2 and assuming Var(θ̂n ) ≤ length(I)/2, we
have
q
3
(60)
|Eθ f (θ̂n ) − f (θ)| ≤ ω 2 (f, Var(θ̂n )),
2
q
after we take t = E|θ̂n − θ|2 .
We remark that Lemma 4 is only one way to analyze the
bias, which is by no means always tight. For example, the following estimate using Ditzian–Totik modulus is significantly
better than Lemma 4 for certain functions such as the entropy.
Lemma 5. [62, Thm. 2.5.1.] If F : C[0, 1] → R is a linear
positive functional and F (e0 ) = 1, then we have
|F (f ) − f (x)| ≤

BF (x)
5
· ω 1 (f, 2h1 ) + ωϕ2 (f, h1 ), (61)
2h1 ϕ(x) ϕ
2

for all p
f ∈ C[0, 1] and 0p < h1 ≤ 12 , where
ϕ(x)
=
x(1 − x) and h1 =
F ((e1 − xe0 )2 )/ϕ(x) =
p
2
VF + (BF (x)) /ϕ(x). The “bias” BF (x) and “variance”
VF (x) are defined in (56).

Considering the same statistical experiment {Pθ , θ ∈ I},
and the plug-in estimator f (θ̂n ) for f (θ), if θ̂n is unbiased for
2
θ and Var(θ̂n ) ≤ ϕ(θ)
4 , then it follows from Lemma 5 that

 q
Var(θ̂n )
5 2
,
|Eθ f (θ̂n ) − f (θ)| ≤ ωϕ f,
(62)
2
ϕ(θ)
√
Var(θ̂ )
after we take t = ϕ(θ) n .
For certain functions f (θ) and statistical models Lemma 5
is stronger than Lemma 4. For example, if f (θ) = −θ ln θ, θ ∈
[0, 1], and we have n· θ̂n ∼ B(n, θ). We will show in Lemma 8
2
ln 4
2
that ωϕ2 (f, t) = t1+t
2 , and ω (f, t) = t ln 4. We also have
Var(θ̂n ) = θ(1−θ)
. Hence, Lemma 4 gives the upper bound
n
r
3 ln 4 θ(1 − θ)
|Eθ f (θ̂n ) − f (θ)| ≤
,
(63)
2
n
whereas Lemma 5 gives
|Eθ f (θ̂n ) − f (θ)| ≤

1
5 ln 4
·
,
2n 1 + 1/n

(64)

which is much stronger when n is large and θ not too close
to the endpoints of [0, 1].
There also exist various estimates for the bias when the
parameter lies in sets other than an interval in R. However,
the bounds we presented are in general not optimal for
specific functionals, thereby leaving ample room for future
development. For example, note that (63) is stronger than (64)
when θ ≤ 1/n, but Han, Jiao, and Weissman [65] showed that
when θ ≤ 1/n the pointwise bound in (63) is still strictly suboptimal for the entropy functional. Unsurprisingly, to obtain
the results in Section III, we need to go beyond the general
results in approximation theory, and incorporate the structure
of specific functions.
Note: In approximation theory literature, researchers have
explored the interactions between general positive linear operator approximation and its probabilistic counterpart decades
ago [66]–[68]. However, in statistics literature related to positive linear approximation, usually only specific operators are
used, such as the Bernstein operator [69], and the focus may
not be on obtaining the tightest bound on bias [70], [71].
C. Lower bounds
To lower bound the worst case performance of a specific
estimator, we have essentially two approaches: first, to analyze
the bias or the variance of the specific estimator carefully;
second, to prove a lower bound that is satisfied by all the
estimators, which naturally include the specific estimator we
need to analyze. These two approaches have different relative
advantages and disadvantages, so we utilize them together in
the lower bound construction.
We refer the readers to Tsybakov [72] for a nice collection
of techniques to prove minimax lower bounds. One specific
approach we use is the van Trees inequality, which we quote
below.
Let (X , F , Pθ ; θ ∈ Θ) be a dominated family of distributions on some sample space X ; denote the dominating measure

10

by µ. Assume Θ is a closed interval on the real line. Let
f (x|θ) denote the density of Pθ with respect to µ. Let π
be some probability distribution on Θ with a density λ(θ)
with respect to Lebesgue measure. Suppose that λ and f (x|·)
are both absolutely continuous (µ-almost surely), and that λ
converges to zero at the endpoints of the interval Θ. We define
2

∂ log f (X|θ)
(65)
I(θ) = Eθ
∂θ

2
d log λ(θ)
I(λ) = E
(66)
dθ
the Fisher information for θ and for a location parameter in
λ, respectively. We assume I(θ) is continuous in θ. We have
the following inequality.
Lemma 6 (van Trees inequality). [73] Under assumptions
above, the average risk of an arbitrary estimator ψ̂(X) in
estimating an absolutely continuous functional ψ(θ) under
squared error loss satisfies the following inequality:

2
(Eψ ′ (θ))2
E ψ̂(X) − ψ(θ) ≥
(67)
E[I(θ)] + I(λ)
V. P ROOFS

OF THE UPPER BOUNDS

In order to upper bound the maximum squared error risk
of any estimator, a natural approach would be to analyze the
squared bias term and the variance term separately. Then, it
suffices to find proper tools to give nonasymptotic analysis of
the bias and variance.

A. Bounding the bias
We first work to bound the bias. Lemma 3 shows that the
bias of F (Pn ) could be represented as
Bias(F (Pn )) =

S
X
i=1

(Bn [f ](pi ) − f (pi )) ,

(68)

where Bn [f ](x) is the Bernstein polynomial corresponding
to f (x). The following lemma summarizes some state-of-theart bounds for approximation error of Bernstein polynomials.
Lemma 7 can be derived easily from the general theory we
presented in Section IV-B2. We emphasize that one cannot
expect the bounds in Lemma 7 to be tight for any f ∈ C[0, 1],
since the Bernstein approximation error itself could be a
very complicated function in C[0, 1], and Lemma 7 is using
relatively simple functions to upper bound it.
Lemma 7. The following bounds are valid for function approximation error incurred by Bernstein polynomials:
1) Pointwise estimate: [62, Cor. 2.2.1] [74] for all continuous functions f on [0, 1],
!
r
x(1 − x)
3 2
, (69)
|f (x) − Bn [f ](x)| ≤ ω f,
2
n
and the constant 3/2 is shown by [74] to be the best
constant;

p
2) Norm estimate: [62, Cor. 4.1.10] for ϕ(x) = x(1 − x)
and all continuous functions f on [0, 1], we have

5 2
ω (f, n−1/2 );
(70)
2 ϕ
3) [75, Eqn. 10.3.4] for f ∈ C 2 [0, 1], i.e., twice continuously differentiable,
kBn [f ] − f k∞ ≤

x(1 − x)
;
(71)
2n
Proof. The pointwise estimate of Lemma 7 follows from
Lemma 4. The norm estimate of Lemma 7 follows from
Lemma 5. Regarding the third part, suppose random variable
X ∼ B(n, x). We have
|f (x) − Bn [f ](x)| ≤ kf ′′ k∞

|f (x) − Bn [f ](x)|

= |Ex f (X/n) − f (x)|

(72)

1
= |Ex [f ′ (x)(X/n − x) + f ′′ (ξX )(X/n − x)2 ]|
2
1
= |Ex f ′′ (ξX )(X/n − x)2 |
2
kf ′′ k∞
≤
|Ex (X/n − x)2 |
2
kf ′′ k∞ x(1 − x)
=
,
2
n
where we used Taylor expansion for f (X/n) at point x
the Lagrange remainder. The proof is complete.

(73)
(74)
(75)
(76)
with

Remark 1. Note that although (70) is in the form of an
upper bound, it has been shown to be a lower bound as well.
Totik [76] showed the following equivalence property on the
norm estimate of Bernstein approximation errors
kBn [f ](x) − f (x)k∞ ≍ ωϕ2 (f, n−1/2 ).2

(77)

It is easy to calculate the second-order modulus of smoothness and the Ditzian–Totik second-order modulus of smoothness for functions xα and −x ln x. The results are presented
in the following lemma.
Lemma 8. We have
2

ω (f, t)
ωϕ2 (f, t)

xα , 0 < α < 1
|2 − 2α |tα
t2α
|2 − 2α | (1+t
2 )α

xα , 1 < α < 2
|2 − 2α |tα
≍ t2

−x ln x
t ln 4
t2 ln 4
1+t2

where the second-order modulus results hold for 0 < t ≤ 1/2,
and the Ditizan–Totik second-order modulus results hold for
0 < t ≤ 1.
1) Bias of Fα (Pn ): We first bound the bias incurred by
Fα (Pn ).
1) α ≥ 2:
2 Note that it is a remarkable fact that (77) holds for any continuous function
f (x). The lower bound proof of (77) is considered one of the remarkable
results in approximation theory, and currently there are no “short” proofs of
this fact. Indeed, Ditzian [77, Section 8] mentioned that “I still would like to
see a new simple proof of (8.4) (Equation (77)) which I am sure will have
implications for other operators.”

11

In this case, f ∈ C 2 [0, 1], applying the third part of
Lemma 7,
|f (x) − Bn [f ](x)| ≤

α(α − 1)x(1 − x)
.
2n

(78)

Thus, we have
|Bias(Fα (Pn ))| ≤

S
X

α(α−1)

i=1

pi (1 − pi )
α(α − 1)
≤
.
2n
2n
(79)

2) 1 < α < 2
The following lemma presents a bound on the bias of
Fα (Pn ), which does not depend on the alphabet size
S. We note that the proof of Lemma 9 heavily utilizes
α
the
PS special properties of function x and the fact that
i=1 pi = 1.
Lemma 9. The bias of Fα (Pn ) for estimating
Fα (P ), 1 < α < 2, is upper bounded by the following:
4
.
(80)
nα−1
We also present two additional bounds involving the alphabet size S. Using the pointwise estimate in Lemma 7,
the bias term of the MLE is upper bounded as follows
for all 0 < α < 2, α 6= 1:
|Bias(Fα (Pn ))| ≤

S
X
3
i=1

2

≤

|2 − 2α |



pi (1 − pi )
n

α/2

S
3
1 X α/2
pi
|2 − 2α | α/2
2
n
i=1

(81)

3
1
1
|2 − 2α | α/2 S α/2
(82)
2
n
S
S 1−α/2
3
(83)
= |2 − 2α | α/2 .
2
n
Using the norm estimate in Lemma 7, when 1 < α < 2,
the bias would be upper bounded by Cα,n 5S
2n , where
Cα,n = nωϕ2 (xα , n−1/2 ) is a finite positive constant
such that lim supn→∞ Cα,n < ∞ for 1 < α < 2.
Combining Lemma 9, the pointwise estimate, and the
norm estimate in Lemma 7, we know that the bias of
Fα (Pn ) for 1 < α < 2 is upper bounded as
≤

|Bias(Fα (Pn ))| ≤

1−α/2
5S
3
α S
∧ Cα,n .
∧
|2
−
2
|
α−1
α/2
n
2
2n
n
(84)

4

3) 0 < α < 1:
The pointwise estimate from Lemma 7 is worked out
in (83). Using the norm estimate in Lemma 7, the bias
5S
would be upper bounded by |2−2α | 2n
α . Combining the
pointwise estimate and the norm estimate, we know that
the bias of Fα (Pn ) for 0 < α < 1 is upper bounded as
|Bias(Fα (Pn ))| ≤

5S
S 1−α/2
3
|2 − 2α | α/2 ∧ |2 − 2α | α .
2
2n
n
(85)

2) Bias of H(Pn ): We then bound the bias incurred by
H(Pn ). Using the norm estimate in Lemma 7, we know
5S ln 4
.
2n
Using the pointwise estimate in Lemma 7, we obtain
r
3 S
|Bias(H(Pn ))| ≤
ln 4.
2 n
|Bias(H(Pn ))| ≤

(86)

(87)

It was shown by Paninski [14, Prop. 1] that the squared bias
of MLE H(Pn ) is upper bounded as
 
2
S−1
2
(Bias(H(Pn ))) ≤ ln 1 +
,
(88)
n
which is better than the two bounds we obtained using
Bernstein polynomial results. However, we remark that (88) is
obtained using special properties of the entropy function and
connections between KL-divergence and χ2 -divergence [72],
which cannot be applied to general functions. Strukov and
Timan [66] also heavily exploited the structure of function xα
and −x ln x in order to analyze the Bernstein approximation
error for these functions, and obtained tight-in-order results.
3) Bias of H(P̂B ): We apply the general theory of positive
linear operator approximation. The following lemma is a
strengthened version of Lemma 5.
Lemma 10. If F : C[0, 1] → R is a linear positive functional
and F (e0 ) = 1, then
5
(89)
|F (f ) − f (x)| ≤ ω 1 (f, BF (x); x) + ωϕ2 (f, h2 )
2
p
for all f ∈√
C[0, 1] and 0 < h2 ≤ 21 , where ϕ(x) = x(1 − x)
and h2 = VF /ϕ(x), and
ω 1 (f, h; x) , sup {|f (u) − f (x)| : u ∈ [0, 1], |u − x| ≤ h} .
(90)
The “bias” BF (x) and “variance” VF (x) are defined in (56).
Proof. Applying Lemma 5 to x = F (e1 ) we have
5 2
ω (f, h2 )
(91)
2 ϕ
and then (89) is the direct result of the triangle inequality
|F (f ) − f (x)| ≤ |F (f ) − f (F (e1 ))| + |f (F (e1 )) − f (x)|.
|F (f ) − f (F (e1 ))| ≤

We show that Lemma 10 is indeed stronger than Lemma
5. Firstly, due to h1 ≥ h2 , we have ωϕ2 (f, h2 ) ≤ ωϕ2 (f, h1 ).
Second, for x ≤ 1/2, we have

BF (x)
BF (x)
· ω 1 (f, 2h1 ) ≈
· sup 2h1 ϕ(s)f ′ (s)
2h1 ϕ(x) ϕ
2h1 ϕ(x) 0≤s≤1
(92)
≥ BF (x) ·
≈

sup

f ′ (s)

x≤s≤1−x
sup ω 1 (f, BF (x); s)
x≤s≤1−x

(93)
(94)

which is almost the supremum of ω 1 (f, |F (e1 − xe0 )|; s)
over s ∈ [x, 1 − x] and is no less than the pointwise result
ω 1 (f, |F (e1 − xe0 )|; x), and here we have used the inequality
ϕ(s) ≥ ϕ(x) for x ≤ s ≤ 1−x. A similar argument also holds

12

for x > 1/2. Hence, Lemma 10 transforms the first order term
from the norm result in Lemma 5 to a pointwise result.
Applyingh Lemma
10 to the function f (p) = −p ln p and
i

np̂+a
, where n · p̂ ∼ B(n, p), we have the
F (f ) = E f n+Sa
following lemma.

Lemma 14. For 0 < α < 1/2, we have
sup Var(Fα (Pn ))

P ∈MS

≤

+

Lemma 11. If n ≥ max{Sa, 2ea, 4}, then
sup |EP H(P̂B ) − H(P )|

P ∈MS

5nS ln 2
2Sa
≤
+
ln
(n + Sa)2
n + Sa



n + Sa
2a

10S
n2α



3α · 23+2α + 1
8α2



8α
e

2α

+4

!


1
S
∧
n2α n2α−1
(102)

S
.
n2α
For 1/2 ≤ α < 1, we have
.

.

(95)

Note that Lemma 11 implies a slightly weaker bias bound
than Theorem 4, but it is only sub-optimal up to a multiplicative constant. The bias bound in Theorem 4 is obtained using
the following lemma, whose proof only applies to the entropy
function.
Lemma 12. If n ≥ max{2ea, Sa},
sup |EP H(P̂B ) − H(P )|




S−1
2Sa
n + Sa
≤ ln 1 +
∨
.
ln
n + Sa
n + Sa
2a

P ∈MS

(96)

(103)

sup Var(Fα (Pn ))

P ∈MS

10S 2−2α
n
!
 2α

1
S
3α · 23+2α + 1 8α
+4
∧
+
8α2
e
n2α n2α−1
(104)


2−2α
S
1
S
.
.
(105)
∧
+
n
n2α n2α−1
≤

Further, one can show that for all α ∈ (0, 1),
 2α
120
3α · 23+2α + 1 8α
+4≤ 2 ,
2
8α
e
α

(106)

which is used in Theorem 1.
Regarding the variance of H(Pn ), we have

B. Bounding the variance

Lemma 15.
The next lemma follows from an application of bounded
difference inequality presented in Lemma 2.

(ln n)2 2(ln S + 3)2
∧
n
n
2
2
(ln S) ∧ (ln n)
.
.
n

sup Var(H(Pn )) ≤

P ∈MS

Lemma 13. The variance of F (Pn ) satisfies the following
upper bound:
Var(F (Pn )) ≤ n · max (f ((j + 1)/n) − f (j/n))2 .
0≤j<n

(97)

If f is monotone, then we can strengthen the bound to be
n
Var(F (Pn )) ≤ · max (f ((j + 1)/n) − f (j/n))2 . (98)
4 0≤j<n
We first bound the variance for Fα (Pn ), α > 1. We have
α 2


1
α
α 2
max (((j + 1)/n) − (j/n) ) ≤ 1 − 1 −
0≤j<n
n
(99)
 α 2
≤
,
(100)
n
where in the last step we used Bernoulli’s inequality: (1 +
x)r ≥ 1 + rx, ∀r ≥ 1, x > −1, x ∈ R. Using Lemma 2, we
know the variance is upper bounded by
Var(Fα (Pn )) ≤

α2
.
4n

(101)

We bound the variance of Fα (Pn ), 0 < α < 1 in the
following lemma.

(107)
(108)

The variance of H(P̂B ) is upper bounded by the following
lemma.
Lemma 16. The variance of H(P̂B ) is upper bounded as
follows:


2


n + Sa
2n
3 + ln
∧S
.
Var H(P̂B ) ≤
(n + Sa)2
a+1
(109)

VI. P ROOFS

OF THE LOWER BOUNDS

A. Lower bounds for estimation of Fα (P ) when α ≥ 3/2
We apply the van Trees inequality as presented in Lemma 6.
It suffices to consider the restricted case of S = 2 and
prove the n−1 lower bound. Thus, the model is equivalent to
observing a Binomial random variable X ∼ B(n, p), and one
aims to estimate the functional ψα (p) = pα + (1 − p)α . We
have
ψα′ (p) = αpα−1 − α(1 − p)α−1 .

(110)

13

The Fisher information for parameter p under the Binomial
n
model is I(p) = p(1−p)
. Suppose we impose prior λ(p) on
parameter p. The van Trees inequality implies

all x ∈ (0, 1), we have
fα (x) − Bn [fα ](x)

2

sup EP (Fα (Pn ) − Fα (P ))

≥

P ∈MS


2
≥ inf sup EP Fˆα − Fα (P )

(111)

Fˆα P ∈MS

2
≥ E E[Fα (P )|X1S ] − Fα (P )
(Bayes risk)
R  α−1

α−1
( αp
− α(1 − p)
λ(p)dp)2
i
h
≥
n
+ I(λ)
Eλ p(1−p)

R  α−1
− α(1 − p)α−1 λ(p)dp)2
( αp
i
h
=
1
+ I(λ)
n · Eλ p(1−p)

(112)
(113)

Taking λ(p) to be the Dirichlet prior with parameter (a, b),
i.e.,
1
λ(p) =
pa−1 (1 − p)b−1 , a > 2, b > 2,
(115)
B(a, b)
we can explicitly evaluate the integrals above. Here B(a, b) is
the Beta function.
Taking a = 4, b = 3, we have
sup EP (Fα (Pn ) − Fα (P ))

2
2

(60α(B(α + 3, 3) − B(α + 2, 4)))
.
≥
5n + 45

(116)

Taking Cα = 72α2 (B(α + 3, 3) − B(α + 2, 4))2 , we have
2

sup EP (Fα (Pn ) − Fα (P )) ≥

P ∈MS

Cα
,
n

where
R1 (x) =

for all n ≥ 1.
(117)

Note that Cα > 0 for all α ≥ 3/2.

R2 (x) =

S
X
i=1

Lemma 18. Suppose fα (x) = −xα , 1 < α < 2 on [0, 1]. For

α(α − 1)(α − 2)(α − 3)(α − 4)
120
× xα−4 (1 − x)(1 − 2x)(1 − 12x(1 − x)). (121)

fα (1/S) − Bn [fα ](1/S) (Note that fα (x) = −xα )

α(α − 1)(α − 2)(α − 3)
(1 + 2(α − 4))
24S α−3 n3
!
α(α − 1)(α − 2)(α − 3)(α − 4)
−α
+ o(n )
+
120S α−4 n4


α(α − 1)
1
1 (2 − α)(5 − 3α)
=
+
nα−1
2cα−3 c
12
+

(α − 2)(α − 3)(1 + 2(α − 4))
24cα−4
!
(α − 2)(α − 3)(α − 4)
+
+ o(n−(α−1) )
120cα−5

+

=

α(α − 1)c2−α
nα−1

1 (2 − α)(5 − 3α)c
+
2
24

(α − 2)(α − 3)(1 + 2(α − 4))c2
24
!
(α − 2)(α − 3)(α − 4)c3
+ o(n−(α−1) )
+
120
+

(118)

Consider fα (x) = −xα , 1 < α < 2, x ∈ [0, 1]. Applying
Lemma 17 to fα , taking k = 6, we have the following result.

1 + 2(1 − x)((5 − 2α)x + α − 4) , (120)

= EFα (Pn ) − Fα (P )


α(α − 1) 1
(2 − α)(5 − 3α)
≥S·
+
2S α−2 n S
12n

The following lemma was proved in [69].

f (x) − Bn [f ](x) ≥ Qk−1 − Bn [Qk−1 ](x).

!

Note that we have assumed S = cn, c > 0. If c ≤
1, we take a uniform distribution on S elements P =
(1/S, 1/S, . . . , 1/S), otherwise we take distribution P =
nǫ
nǫ
, . . . , S−n
), where ǫ will
(n−1 − ǫ, n−1 − ǫ, . . . , n−1 − ǫ, S−n
be taken to be arbitrarily small. We first analyze the c ≤ 1
case. Applying Lemma 18, we have

B. Lower bounds for estimation of Fα (P ) when 1 < α < 3/2

Lemma 17. Let k ≥ 4 be an even number. Suppose that the
k-th derivative of f satisfies f (k) ≤ 0 in (0, 1), Qk−1 is the
Taylor polynomial of order k − 1 to f at some x1 in (0, 1).
Then for x ∈ [0, 1],

α(α − 1)(α − 2)(α − 3)xα−3 (1 − x)
24
×

(114)

where the second inequality follows from the fact that the
Bayes risk under any prior is upper bounded by the minimax
risk [78].

P ∈MS

(2 − α)(3α − 1)x
α(α − 1)xα−2 (1 − x)
x+
2n
12n
!
R1 (x) R2 (x)
(2 − α)(5 − 3α)
+
+
, (119)
+
12n
n3
n4

αc2−α (124 − 330α + 285α2 − 90α3 + 11α4 )
+ o(n−(α−1) ),
120nα−1
where the first inequality follows from Lemma 18, and in the
≥

14

last step we have taken c = 1 in the following expression
2

1 (2 − α)(5 − 3α)c (α − 2)(α − 3)(1 + 2(α − 4))c
+
+
2
24
24
(α − 2)(α − 3)(α − 4)c3
,
(122)
+
120
and considered the fact that it is a monotonically decreasing
function with respect to c on (0, 1] for any α ∈ (1, 3/2).

For cases when c > 1, since we take P = (n−1 − ǫ, n−1 −
nǫ
nǫ
, . . . , S−n
), by a continuity argument, the
ǫ, . . . , n−1 − ǫ, S−n
analysis is exactly the same as that above when we set c = 1
as we can take ǫ as small as possible. One can verify that
the function α(124 − 330α + 285α2 − 90α3 + 11α4 )/120 is
√
positive on interval (1, 3/2). Defining cα = αc2−α (124 −
2
3
4
330α + 285α − 90α + 11α )/120 > 0 when c ≤ 1, and
√
cα = α(124 − 330α + 285α2 − 90α3 + 11α4 )/120 > 0
when c > 1, the proof is completed.

1
2

≤ α < 1, we have

2
inf sup EP F̂ − Fα (P )
F̂ P ∈MS
"
α2
(2(S − 1))1−α − 2−α
≥
32en

Lemma 20. For


1−α
−
(2(S − 1))1−α + 2−α
4n

#2

− e−n/4 S 2(1−α)
S 2−2α
&
,
(128)
n
where the infimum is taken over all possible estimators.
Since this lower bound holds for all possible estimators, it
also holds for the MLE Fα (Pn ). Since max{a, b} ≥ 21 (a + b),
we have the desired lower bound.

D. Lower bounds for estimation of H(P )
C. Lower bounds for estimation of Fα (P ) when 0 < α < 1

Braess and Sauer [69] derived the following lower bound
for the approximation error of Bernstein polynomials for the
function g(x) = −x ln x:

Applying Lemma 17 to function fα (x) = xα , α ∈ (0, 1),
taking k = 4, we have the following result:

Lemma 21. Define g(x) = −x ln x on [0, 1]. For x ≥
[0, 1], we have

α

Lemma 19. For fα (x) = x on [0, 1], α ∈ (0, 1), x ∈ (0, 1),
we have


α(1 − α) α−2
2−α
fα (x) − Bn [fα ](x) ≥
.
x
(1 − x) x −
2n
3n
(123)
Suppose n
≥
S. Define
(w1 , w2 , . . . , wS ) ∈ MS such that

distribution

W

=

1
S−1
; wS = 1 −
.
(124)
n
n
Note that wi ≥ n−1 , 1 ≤ i ≤ S. It follows from Lemma 19
that

S−1
X α(1 − α)  1 α−2 
1
1
−
Fα (W ) − EW Fα (Pn ) ≥
6n2
n
n
i=1
(125)
α(1 − α)(S − 1) n − 1
.
(126)
=
6nα
n
1 ≤ i ≤ S − 1, wi =

Thus, we know for all 0 < α < 1,
sup EP (Fα (P ) − Fα (Pn ))

P ∈MS

α2 (1 − α)2 (S − 1)2
≥
36n2α

2

2

1
1−
.
n

(127)

It is shown in [10] that the following minimax lower bound
holds for estimation of Fα (P ), 1/2 ≤ α < 1.

g(x) − Bn [g](x) ≥

1
x
1−x
.
+
−
2
2n
20n x 12n2

15
n ,x

∈

(129)

Applying Lemma 21 to the estimation of H(P ), we know
that if ∀1 ≤ i ≤ S, pi ≥ 15
n,
!
S
X
S−1
1
1
1
H(P )−EH(Pn ) ≥
−
. (130)
+
2n
20n2 i=1 pi
12n2
Consider the uniform distribution P with n ≥ 15S, which
guarantees pi ≥ 15
n . Since

we have

S
X
1
≥ S2,
p
i
i=1

sup (H(P ) − EH(Pn )) ≥

P ∈MS

(131)

S−1
1
S2
−
. (132)
+
2n
20n2 12n2

Thus, when n ≥ 15S,

2
1
S2
S−1
−
+
.
2n
20n2 12n2
P ∈MS
(133)
It was shown in [21, Prop. 1] that the following minimax
lower bound holds.
2

sup EP (H(P ) − H(Pn )) ≥



Lemma 22. There exists a universal constant c > 0 such that

2
ln2 S
,
(134)
inf sup EP Ĥ − H(P ) ≥ c
n
Ĥ P ∈MS
where the infimum is taken over all possible estimators Ĥ.

15

Hence, we have

ACKNOWLEDGMENTS
2

sup EP (H(P ) − H(Pn ))
(
)
2
S−1
1
S2
ln2 S
≥ max
−
+
,c
2n
20n2 12n2
n

2
2
2
1
S
1 S−1
c ln S
−
+
.
≥
+
2
2
2
2n
20n
12n
2 n

P ∈MS

(135)
(136)

Similar arguments can be applied to the Miller–Madow
estimator.
E. Lower bounds for entropy estimation using H(P̂B )
Since H(P̂B ) is a specific estimator for entropy, the following lemma is proved via considering several specific distributions.
Lemma 23. If n ≥ max{15S, Sa, 2ea},
EP H(P̂B ) − H(P )
P ∈MS


S−1
(S − 1)a
1
S2
n + Sa
+
≥
−
ln
+
2
4(n + Sa)
a
8n
80n
48n2
(137)
sup

If n < Sa, then
sup
P ∈MS

EP H(P̂B ) − H(P ) ≥

S−1
ln S.
2S

(138)

P ∈MS

EP H(P̂B ) − H(P ) ≥

S−1
ln S.
2e + S

(139)

If n < 15S, n ≥ 2ea, then
EP H(P̂B ) − H(P )
P ∈MS


(S − 1)a
⌊n/15⌋
1
n + Sa
≥
+
ln
−
.
4(n + Sa)
a
8n
16n
sup

(140)

The corresponding results in Theorem 5 follow from
Lemma 23, Lemma 22, and the inequality max{a, b} ≥ a+b
2 .
Bayes

F. Lower bounds for entropy estimation using Ĥ
We prove Theorem 6 below. Applying Lemma 25, we have
Ĥ Bayes ≤ ψ(Sa + n + 1) −

S
X
a + Xi
ψ(a + 1)
Sa
+n
i=1

(141)

= ψ(Sa + n + 1) − ψ(a + 1)
(142)


−γ
Sa + n + e
≤ ln
.
(143)
a + 21


−γ
Since Ĥ Bayes is upper bounded by ln Sa+n+e
for any
1
a+ 2
empirical observations, the squared error it incurs in Shannon
entropy estimation when the true distribution is the uniform
distribution is at least
2
 
Sa + S/2
(144)
ln
Sa + n + e−γ
if S ≥ 2(n + 1).

A PPENDIX A
AUXILIARY LEMMAS
We begin with the definition of the negative association
property, which allows us to upper bound the variance by
treating each component of the empirical distribution Pn (i)
as “independent” random variables.
Definition 1.
[79, Def. 2.1] Random variables
X1 , X2 , · · · , XS are said to be negatively associated if
for any pair of disjoint subsets A1 , A2 of {1, 2, · · · , S}, and
any component-wise increasing functions f1 , f2 ,
Cov (f1 (Xi , i ∈ A1 ), f2 (Xj , j ∈ A2 )) ≤ 0.

If n < 2ea, then
sup

We thank Dany Leviatan, Gancho Tachev, and Radu Paltanea for very helpful discussions regarding the literature on
approximation theory using positive linear operators. We thank
Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, and
Himanshu Tyagi for communicating to us the independent
discovery that it suffices to take n ≫ 1 samples to consistently estimate Fα (P ), when α > 1. We thank Maya Gupta
for raising the question on the optimality of the Dirichlet
prior smoothing techniques applying to entropy estimation.
We thank the anonymous reviewers and the associate editor
for very helpful comments that significantly improved the
presentation of the paper.

(145)

To verify whether random variables X1 , X2 , · · · , XS are
negatively associated or not, the following lemma presents a
useful criterion.
Lemma 24. [79, Thm. 2.9] Let X1 , X2 , · · · , XS be S independent random variables with log-concave densities. Then
the joint conditional distribution of X1 , X2 , · · · , XS given
P
S
i=1 Xi is negatively associated.

In light of the preceding lemma, we can obtain the following
corollary.
Corollary 5. For any discrete probability distribution vector
P ∈ MS , the random variables X = (X1 , X2 , · · · , XS )
drawn from the multinomial distribution X ∼ multi(n; P ) are
negatively associated.
Proof. Consider the Poissonized model Yi ∼ Poi(npi ), 1 ≤
i ≤ S with all Yi independent, it is straightforward
to verify that each Yi possesses
PS a log-concave distribution. Then conditioning on
i=1 Yi = n, we know that
PS
(Y1 , Y2 , · · · , YS )|( i=1 Yi = n) ∼ multi(n; P ), hence
Lemma 24 yields the desired result.
The next
lemma gives bounds on the digamma functions
′
(z)
ψ(z) = ΓΓ(z)
.
Lemma 25. [80, Lemma 1.7] The digamma function ψ(z)
is the only solution of the functional equation F (x + 1) =
F (x)+ x1 that is monotone, strictly concave on R+ and satisfies
F (1) = −γ, where γ ≈ 0.5772 is the Euler–Mascheroni
constant.

16

The bias of F (Pn ) is

Let x be a positive real number. Then,
ln(x + 1/2) < ψ(x + 1) ≤ ln(x + e

−γ

).

(146)

If x ≥ 1, then

ln(x + 1/2) < ψ(x + 1) ≤ ln(x + e1−γ − 1).

(147)

The following lemma gives some tail bounds for Poisson or
Binomial random variables.
Lemma 26. [81, Exercise 4.7] If X ∼ Poi(λ) or X ∼
B(n, nλ ), then for any δ > 0, we have

λ
eδ
P(X ≥ (1 + δ)λ) ≤
,
(148)
(1 + δ)1+δ
λ

2
e−δ
P(X ≤ (1 − δ)λ) ≤
≤ e−δ λ/2 .
(149)
1−δ
(1 − δ)
To establish the upper bound of the variance obtained by
the plug-in estimator Fα (Pn ), we split p into two different
regimes p ≤ 1/n or p > 1/n, and the following lemmas give
the corresponding variance bounds.

Bias(F (Pn ))
= EF (Pn ) − F (P )
(158)






S
n
X
X
j
n j

f
=
pi (1 − pi )n−j − f (pi ) .
n
j
i=1
j=0
(159)

B. Proof of Lemma 8
We first compute the second-order modulus. Fix t, 0 < t ≤
1/2. Defining M , u+v
2 , then the computation of secondorder modulus is equivalent to maximization of |f (M − t) −
2f (M ) + f (M + t)| over interval M ∈ [t, 1 − t], since all
the functions we consider are strictly convex or concave over
[0, 1].
For f (x) = xα , 0 < α < 1, f (x) is strictly concave on
[0, 1]. It follows from Jensen’s inequality that
g(M ) = (M − t)α − 2M α + (M + t)α ≤ 0,

(160)

and it suffices to minimize this function of M in order to
obtain the modulus. Taking derivative of g(M ), we have
2p
2

(150)
Var(X α ) ≤ 2α ∧ 2α−1 0 < α < 1.
g ′ (M ) = α (M − t)α−1 − 2M α−1 + (M + t)α−1 ≥ 0,
n
n
(161)
Lemma 28. For nX ∼ B(n, p), p ≥ 1/n, 0 < α < 1, we have
since xα−1 is a convex function on [t, 1−t]. It implies that the

2α
 2α
function g(M ) is non-decreasing, and the minimum of g(M )
2
1
8α
10p2α−1
3 16α
+ 2α + 2
.over M ∈ [t, 1 − t] is attained at M = t, and the minimum
Var(X α ) ≤
+
n
2α en
n
8α
en
α
α
(151) value is g(t) = (2 − 2)t . Hence, the corresponding secondα α
order modulus is |2 − 2 |t .
Analogous procedures computes the second-order modulus
for xα , 1 < α < 2 and −x ln x.
A PPENDIX B
P ROOFS OF MAIN LEMMAS
Now we consider the computation of Ditzian–Totik secondorder modulus. Fix t, 0 < t ≤ 1. Again denote M , u+v
2 ∈
A. Proof of Lemma 3
[0, 1]. Then thepoptimization is over the regime |u − v| ≤
2tϕ(M p
) = 2t M (1 − M ).pEquivalently, it is the interval
We compute the first moment of F (Pn ).
[M − t M (1 − M ), M + t M (1 − M )] ∩ [0, 1].
 
n
X
Since the function f (x) = −x ln x is strictly convex on
j
EF (Pn ) =
f
Ehj ,
(152) [0, 1], the maximum of f (u) − 2f u+v  + f (v) is definitely
n
2
j=0
attained when up
and v take the boundary
p values of the feasible
and
interval [M − t qM (1 − M ), M + t M (1 − M )] ∩ [0, 1].
S
X
Define ∆ , t 1−M
M . The feasible interval can be equiva1(Xi = j)
(153)
Ehj = E
lently written as [M − ∆M, M + ∆M ] ∩ [0, 1]. We have
Lemma 27. For nX ∼ B(n, p), p ≤ 1/n, we have

=

i=1
S
X

P(Xi = j)

(154)

i=1

Thus, we have

S  
X
n j
pi (1 − pi )n−j .
=
j
i=1

 X
n
S  
X
j
n j
f
EF (Pn ) =
pi (1 − pi )n−j
j
n
j=0
i=1
  
n X
S
X
j
n j
f
=
pi (1 − pi )n−j .
n
j
j=0 i=1

M −t
as well as

(155)

(156)

(157)

p
M (1 − M ) ≥ 0 ⇔ M ≥

t2
,
1 + t2

(162)

1
.
(163)
1 + t2
Hence, it is equivalent to maximize over three regimes:
1) Regime A:
t2
u = 0, v = 2M, 0 ≤ M ≤ 1+t
2.
2) Regime B:
i
h 2
1
t
u = M − ∆M, v = M + ∆M, M ∈ 1+t
2 , 1+t2
3) Regime C:
1
u = 2M − 1, v = 1, 1 ≥ M ≥ 1+t
2.
M +t

p
M (1 − M ) ≤ 1 ⇔ M ≤

17

Over regime A, we have


u+v
+ f (v) = 2M ln 2.
f (u) − 2f
2

(164)

Hence, we have
X
B1 = E
Pnα (i) − pα
i
1
i:pi ≤ n

2

t
Maximizing over 0 ≤ M ≤ 1+t
2 , the maximum value is
2
2
t ln 4
t
1+t2 , attained at M = 1+t2 .
Over regime C, we have


u+v
+ f (v) = |2M ln M − (2M − 1) ln(2M − 1)| .
f (u) − 2f
2
(165)
1
Maximizing over 1+t
2 ≤ M ≤ 1, the maximum is attained at
t2 ln 4
1
M = 1+t
2 , and the maximum value is no more than 1+t2 .
h 2
i
t
1
Now we consider regime B. Since M ∈ 1+t
in
2 , 1+t2
q
2
regime B, we know ∆ = t 1−M
M ∈ [t , 1]. We have





u+v
+ f (v)
2
= M |(1 − ∆) ln(1 − ∆) + (1 + ∆) ln(1 + ∆)| . (166)
q
t2
implies M = t2 +∆
Since ∆ = t 1−M
2 , we can recast the
M
corresponding optimization problem as maximizing
f (u) − 2f

t2
|(1 − ∆) ln(1 − ∆) + (1 + ∆) ln(1 + ∆)|
2
∆ + t2

(167)

subject to constraint ∆ ∈ [t2 , 1]. One can show that the
maximum is always attained at ∆ = 1, with the maximum
2
ln 4
value t1+t
2 .
To sum up, we conclude that when 0 < t ≤ 1, the maximum
of the optimization problem defining ωϕ2 (−x ln x, t) is always
2t2
t2 ln 4
attained at u = 0, v = 1+t
2 , with the resulting modulus 1+t2 .
Analogous computation can also be done for function
xα , 0 < α < 1. For the function xα , 1 < α < 2, it is hard to
compute the modulus exactly, but it is easy to show that it is
of order t2 .

C. Proof of Lemma 9

=E

X

Pnα (i) −

(npi )α
nα

(173)

X

Pnα (i) −

(npi )2
nα

(174)

1
i:pi ≤ n

≤E
=E

(172)

1
i:pi ≤ n

X (nPn (i))α
(npi )2
−
nα
nα
1

(175)

i:pi ≤ n

≤E

X (nPn (i))2
(npi )2
−
α
n
nα
1

(176)

i:pi ≤ n

X E(nPn (i))2
(npi )2
=
−
nα
nα
1

(177)

=

(178)

i:pi ≤ n

≤

X (npi )2 + npi (1 − pi ) (npi )2
−
nα
nα
1
i:pi ≤ n
X npi
nα

1
i:pi ≤ n

(179)

1
,
(180)
nα−1
where we have used the fact that nPn (i) ≥ 1 for any Pn (i) 6=
0.
=

Regarding B2 , we have the following bounds:
B2 = E

X

Pnα (i) − pα
i

(181)

E|Pnα (i) − pα
i |

(182)

1
i:pi > n

≤

X

1
i:pi > n

α/2

X 3
pi (1 − pi )
α
≤
|2 − 2 |
2
n
1

(183)

≤

(184)

i:pi > n

The bias of Fα (Pn ), 1 < α < 2 can be expressed as follows:
|Bias(Fα (Pn ))| = |E
≤ E

S
X
i=1

Pnα (i) − pα
i |

X

1
i:pi ≤ n

+ E

(168)

i:pi > n

where the second inequality follows from the pointwise estimate in Lemma 7.

Pnα (i) − pα
i

X

1
i:pi > n

Pnα (i) − pα
i

, B1 + B2 .

(169)
(170)

Now we bound B1 and B2 separately. It follows from
Jensen’s inequality that for any i,
EPnα (i) ≥ pα
i ,

3|2 − 2α | X α/2
pi ,
2nα/2
1

1 ≤ i ≤ S.

(171)

Denoting |{i : pi > n1 }| = K ≤ n, we know
X α/2
pi ≤ K 1−α/2 ≤ n1−α/2 ,

(185)

1
i:pi > n

which implies that
B2 ≤

3|2 − 2α | 1−α/2
3|2 − 2α |
n
=
.
2nα−1
2nα/2

(186)

18

Therefore, we have

E. Proof of Lemma 12

|Bias(Fα (Pn ))| ≤ B1 + B2
3|2 − 2α |
1
≤ α−1 +
n
2nα−1
α
3|2 − 2 | + 2
≤
2nα−1
4
≤ α−1 .
n

(187)
(188)

We have
H(P̂B ) =

S
X
i=1

(189)

−p̂B,i ln p̂B,i

= H(PB ) +
(190)

(200)

S
S
X
X
p̂B,i
p̂B,i ln
.
(pB,i − p̂B,i ) ln pB,i −
pB,i
i=1
i=1
(201)

Taking expectations on both sides, we have

D. Proof of Lemma 11
√

n
. In order to
We apply Lemma 10. Note that h2 = n+Sa
ensure that h2 ≤ 1/2, it suffices to take n ≥ 4. Also, since
n ≥ Sa, for any i, 1 ≤ i ≤ S,

|1 − pi S|a
Sa
1
≤
≤ .
n + Sa
n + Sa
2

EH(P̂B ) − H(P ) = H(PB ) − H(P ) − ED(P̂B kPB ), (202)
PS
pi
where D(P kQ) =
is the KL diveri=1 pi ln qi
gence
between
distributions
P
and
Q.
Since H(PB ) =


Sa
n
H n+Sa P + n+Sa US , where US denotes the uniform distribution with alphabet size S, it follows from Jensen’s inequality and the concavity of the entropy function that
n
Sa
H(P ) +
H(US )
n + Sa
n + Sa
≥ H(P ).

H(PB ) ≥

(191)

(203)
(204)

Hence,
PS
i S|a
Meanwhile, since the function i=1 |1−p
is a convex
n+Sa
function of P = (p1 , p2 , . . . , pS ), it attains its maximum at
one of the corner points of the simplex. Hence,
S
X
|1 − pi S|a
i=1

n + Sa

≤

|1 − S|a
a
+ (S − 1) ·
n + Sa
n + Sa

(192)

=

2(S − 1)a
.
n + Sa

(193)

In light of Lemma 10, we have
|EP H(P̂B ) − H(P )|



S 
X
|1 − pi S|a
5n ln 2
1
ω f,
(194)
≤
; pi +
n + Sa
(n + Sa)2
i=1
!
!
S
S
X
(a)
|1 − pi S|a
1 X |1 − pi S|a
≤ −
ln
n + Sa
S i=1 n + Sa
i=1
5nS ln 2
(n + Sa)2


(b)
2Sa
5nS ln 2
n + Sa
≤
+
,
ln
n + Sa
2a
(n + Sa)2
+

2a
n
≤ e−1 ,

≤

In order to analyze the bias, it suffices to analyze the two
terms separately. We first analyze ED(P̂B kPB ).
It follows from Jensen’s inequality that
!
S
S
X
X
pi
p2i
pi ln
D(P kQ) =
,
(206)
≤ ln
qi
q
i=1
i=1 i
whose derivation here follows from Tsybakov [72, Lemma
2.7].
By Jensen’s inequality, we have
!
!
S
S
X
X
Ep̂2B,i
p̂2B,i
≤ ln
.
ED(P̂B kPB ) ≤ E ln
p
pB,i
i=1
i=1 B,i
(207)
We also have

(195)
(196)

where (a) follows from the fact that if |x − y| ≤ 1/2, x, y ∈
[0, 1], then |x ln x − y ln y| ≤ −|x − y| ln |x − y| [82, Thm.
17.3.3] and Jensen’s inequality. Step (b) follows from the fact
that the function −y ln y is monotonically increasing on the
interval [0, e−1 ], and
S
2a
1 X |1 − pi S|a
≤
S i=1 n + Sa
n + Sa

EH(P̂B ) − H(P ) ≤ max{H(PB ) − H(P ), ED(P̂B kPB )}.
(205)

(197)
(198)
(199)

where in the last step we used the assumption that n ≥ 2ea.

S
X
p2
i

i=1

and that

E(p̂B,i − pB,i )2 =

qi

=1+

S
X
(pi − qi )2
i=1

qi

,

(208)

n2
npi (1 − pi )
E(p̂i − pi )2 =
.
(n + Sa)2
(n + Sa)2
(209)

Hence,
ED(P̂B kPB ) ≤ ln 1 +

S
X

i=1
S
X

npi (1 − pi )
(n + Sa)(npi + a)

!

npi (1 − pi ) npi
= ln 1 +
(n
+ Sa)npi npi + a
i=1
!
S
X
1 − pi
,
≤ ln 1 +
(n + Sa)
i=1

(210)
!

(211)

(212)

19

which implies that

G. Proof of Lemma 14



S−1
.
ED(P̂B kPB ) ≤ ln 1 +
n + Sa

(213)

Now we consider the deterministic gap H(PB ) − H(P ). It
follows from a refinement result of Cover and Thomas [82,
Thm. 17.3.3] that when |pB,i − pi | ≤ 1/2 for all i, we have
kPB − P k1
|H(PB ) − H(P )| ≤ −kPB − P k1 ln

S
kPB − P k1
= S·f
,
S

(214)
(215)

where f (x) = −x ln x, x ∈ [0, 1]. Note that the condition
n ≥ Sa ensures that |pB,i − pi | ≤ 1/2.
We have
S
1 X Sa
1
kPB − P k1 =
|pi − 1/S|
S
S i=1 n + Sa

=

S
1 X |1 − pi S|a
S i=1 n + Sa

(216)

(217)

2a
,
(218)
n + Sa
where the last step follows from (192). Since we have assumed
2a
−1
n ≥ 2ea, we have n+Sa
≤ 2a
. Since the function
n ≤ e
f (x) = −x ln x is monotonically increasing on the interval
[0, e−1 ], we know
≤

2Sa
n + Sa
|H(PB ) − H(P )| ≤
ln
.
n + Sa
2a

(219)

In light of Lemma 27 and 28, we have
S
X

Var(Pn (i)α )

i=1

=

X

Var(Pn (i)α ) +

i:pi ≤1/n

≤

X

i:pi ≤1/n

X

Var(Pn (i)α )

(221)

i:pi >1/n

2
2pi
∧ 2α−1
2α
n
n


2α
10pi2α−1
3 16α
+
+
n
2α en
i:pi >1/n
 2α !
2
1
8α
+ 2α + 2
.
n
8α
en
X

(222)

We obtain the desired bounds after using the concavity of
x2α−1 when 1/2 ≤ α < 1.
Now we exploit the negative association property of all
random variables Pn (i), 1 ≤ i ≤ S. Corollary 5 and the
monotonically increasing property of xα yield
Var(Fα (Pn )) =

S
X

Var(Pn (i)α )

i=1

+2

X

Cov(Pn (i)α , Pn (j)α )

(223)

1≤i<j≤S

≤

S
X

Var(Pn (i)α ),

(224)

i=1

which finishes the proof of Lemma 14.

H. Proof of Lemma 15

F. Proof of Lemma 13

In our case, apparently F (Pn ) is a function of n independent random variables {Zi }1≤i≤n taking values in Z =
{1, 2, . . . , S}. Changing one location of the sample would
make some symbol with count j to have count j + 1, and
another symbol with count i to have count i − 1. Then the
total change in the functional estimator is

 
 



j
i
i−1
j+1
−f
−f
+f
.
(220)
f
n
n
n
n
If f is monotone, then the total change would be upper
bounded by max0≤j<n |f ((j + 1)/n) − f (j/n)|. If f is
not monotone, the total change can be upper bounded by
2 · max0≤j<n |f ((j + 1)/n) − f (j/n)|. Applying Lemma 2,
we have the desired bounds.

The upper bound (ln n)2 /n follows from Lemma 13. We
apply the Efron–Stein inequality (Lemma 1) to obtain the
other bound. Denote the n i.i.d. samples from distribution
P as Z1 , Z2 , . . . , Zn ∈ Z. Denoting the MLE H(Pn ) as
Ĥ(Z1 , Z2 , . . . , Zn ), since it is invariant to any permutation
of {Z1 , Z2 , . . . , Zn }, we know that the Efron–Stein inequality
implies
2
n 
Var(H(Pn )) ≤ E Ĥ(Z1 , Z2 , . . . , Zn ) − Ĥ(Z1′ , Z2 , . . . , Zn ) ,
2
(225)
where Z1′ is an i.i.d. copy of Z1 .
Recall that
n
X
1(Zj = i), 1 ≤ i ≤ S.
(226)
Xi =
j=1

For notional brevity, we denote the S-tuple
(X1 , X2 , . . . , XS ) as X1S , and the n-tuple (Z1 , Z2 , . . . , Zn )
as Z1n . A specific realization of (X1 , X2 , . . . , XS ) is denoted
by xS1 = (x1 , x2 , . . . , xS ), and a specific realization of
(Z1 , Z2 , . . . , Zn ) is denoted by z1n = (z1 , z2 , . . . , zn ).

20

In order to upper bound the right hand side of (225), we and
first condition on {X1 , X2 , . . . , XS }. In other words, we use
2
E[D+
|X1S ]

2
  

2
X
E Ĥ(Z1 , Z2 , . . . , Zn ) − Ĥ(Z1′ , Z2 , . . . , Zn )
(227)
Xi
Xi
Xi − 1
=
p
r
−
r
i
" "
##
n
n
n

2
1≤i≤S
′
S




 2

= E E Ĥ(Z1 , Z2 , . . . , Zn ) − Ĥ(Z1 , Z2 , . . . , Zn )
X1
.
X
Xi
Xi + 1
Xi
r
−r
+
.
pi 1 −
n
n
n
(228)
1≤i≤S

(240)

The following lemma calculates the conditional distribution
of Z1 conditioned on (X1 , X2 , . . . , XS ).

Lemma 29. The conditional distribution of Z1 conditioned on
(X1 , X2 , . . . , XS ) is given by the following discrete distribution:
(X1 /n, X2 /n, . . . , XS /n).
(229)
Proof. By definition of conditional distribution, for any k, 1 ≤
k ≤ S, we have
P(Z1 = k|X1S = xS1 )

P(Z1 = k, X1S = xS1 )
=
P(X1S = xS1 )
P(Z1 = k)P(X1S = xS1 |Z1 = k)
=
P(X1S = xS1 )
 xk −1 Q
xi
n−1
pk
pk x1 ,x2 ,...,x
i6=k pi
k −1,...,xS

Q
=
xi
n
1≤i≤S pi
x1 ,x2 ,...,xS

n−1
=

=

x1 ,x2 ,...,xk −1,...,xS

n
x1 ,x2 ,...,xS
xk

n

,

(230)
(231)

1≤i≤S 1≤j≤n

× P(B(n, pi ) = j)

2
E[D+
]

 

 2
j−1
j
j
r
−r
=
n
n
n
1≤i≤S 0≤j≤n
  

2 !

j
j+1
j
r
−r
+ 1−
n
n
n
X

(233)

Denoting r(p) = −p ln p, we have r(j/n) ,
rewrite

−j
n

ln nj . We

Ĥ(Z1′ , Z2 , . . . , Zn )− Ĥ(Z1 , Z2 , . . . , Zn ) = D− +D+ , (236)
where



XZ1
XZ1 − 1
−r
D− = r
n
n
 X ′ 
X ′ 
Z +1
Z
1
r
− r n1
Z1 =
6 Z1′
n




D+ =
r XZ1′ − r XZ1′ −1
Z1 = Z1′
n
n

(237)

X

× pi P(B(n, pi ) = j).

(234)

where the multinomial coefficient x1 ,x2n,...,xS is defined as


n
n!
= QS
.
(235)
x1 , x2 , . . . , xS
i=1 xi !

(241)

and

(232)






2
as 0 when
Note that we interpret Xni r Xni − r Xin−1
2
2
Xi = 0. Taking expectations of E[D−
|X1S ] and E[D+
|X1S ]
S
with respect to X1 , we have
 2
X X j  j − 1
j
2
r
−r
E[D−
]=
n
n
n

(242)

2
2
]. It
After some algebra, one can show that E[D+
] = E[D−
then follows from (225) that

Var(H(Pn ))

2
n
≤ · E Ĥ(Z1 , Z2 , . . . , Zn ) − Ĥ(Z1′ , Z2 , . . . , Zn )
2
(243)
n
2
(244)
= · E (D− + D+ )
2
2
2
≤ n · E(D−
+ D+
)
(245)

2
≤ 2nED−
(246)

2
X
1
= 2n ·
EPn (i) r(Pn (i)) − r(Pn (i) − )
n
1≤i≤S

(238)

Here, D− is the change in Ĥ that occurs when Z1 is
removed according to the distribution specified in Lemma 29,
and D+ is the change in Ĥ that occurs when Z1′ is added
back according to the true distribution P .
2
2
Now we compute E[D−
|X1S ] and E[D+
|X1S ]. We have
 2
X Xi   Xi − 1 
Xi
2
r
−r
,
E[D−
|X1S ] =
n
n
n
1≤i≤S

(239)

(247)

The proof above is an elaborate version of that in [14, App.
B.3]. Now we proceed to obtain non-asymptotic upper bounds
of (247). For x ≥ 1/n, it follows from Taylor expansion with
integral form residue that
(x −

1
1
1
) ln(x − ) = x ln x + (ln x + 1)(− )
n
n
n
Z x− n1
1
1
+
(x − − u) du.
n
u
x

(248)

21

Then, we have

so



1
r(Pn (i)) − r Pn (i) −
n
Z Pn (i)− n1
Pn (i) −
| ln Pn (i) + 1|
+
≤
n
u
Pn (i)

1
n

du +

| ln Pn (i) + 1| + 2
.
≤
n

1
n
(249)
(250)

|(x − t) ln(x − t) − x ln x| ≤ t| ln x + 1|
Z x−t
x−t
du + t (259)
+
u
x
≤ t| ln x + 1| + 2t
(260)
≤ t(3 − ln x).

As a result,

Hence, we have
Var(H(Pn )) ≤ 2n ·

1≤i≤S

EPn (i)



| ln Pn (i) + 1| + 2
n

2

.

(251)
Noting that ln Pn (i) ≤ 0, hence 0 ≤ | ln Pn (i) + 1| ≤ 1 −
ln Pn (i). We have
2 X
2
EPn (i) (ln Pn (i) − 3)
(252)
Var(H(Pn )) ≤ ·
n
1≤i≤S
2 X
≤
pi (ln pi − 3)2
(253)
n
1≤i≤S

1
2
S · (− ln S − 3)2
(254)
n
S
2
2(ln S + 3)
=
,
(255)
n
where we have used the fact that x(ln x − 3)2 is a concave
function on [0, 1].
≤

I. Proof of Lemma 16






k+a
k−1+a
−f
1≤k≤n
n + Sa
n + Sa



k+a
1
3 − ln
≤ max
1≤k≤n n + Sa
n + Sa



1
n + Sa
≤
3 + ln
.
n + Sa
a+1
max f

X

(261)

Hence, the bounded differences inequality shows that


Var H(P̂B )


2
 
k−1+a
k+a
−f
≤ n max f
2≤k≤n
n + Sa
n + Sa
2


n
n + Sa
≤
3 + ln
,
(n + Sa)2
a+1

(262)
(263)

(264)
(265)

which completes the proof of the first part.
To prove the second part, we use the Efron–Stein inequality (Lemma 1). Since H(P̂B ) = ĤB (Z1 , · · · , Zn ) is invariant
to any permutation of (Z1 , Z2 , · · · , Zn ), we know that the
Efron–Stein inequality implies


Var H(P̂B )
2
n 
≤ E ĤB (Z1′ , Z2 , · · · , Zn ) − ĤB (Z1 , Z2 , · · · , Zn ) ,
2
(266)
where Z1′ is an i.i.d. copy of Z1 .

We apply the bounded differences inequality (Lemma 2).
In our case, F (P̂B ) is a function of n independent random
variables {Zi }1≤i≤n taking values in Z = {1, 2, · · · , S}.
Changing one location of the sample would make some
symbol with count j to have count j + 1, and another symbol
with count i to have count i − 1. Then the absolute value of
the total change in the functional estimator is




j+a
j+1+a
−f
f
n + Sa
n + Sa




i−1+a
i+a
+f
(256)
−f
n + Sa
n + Sa




k−1+a
k+a
−f
. (257)
≤ 2 max f
1≤k≤n
n + Sa
n + Sa
In light of the Taylor expansion with integral form residue,
we have that for 1 ≥ x ≥ t > 0,
Z x−t
x−t−u
(x − t) ln(x − t) = x ln x − t(ln x + 1) +
du
u
x
(258)

Recall that
Xi =

n
X
j=1

1(Zj = i),

1 ≤ i ≤ S.

(267)

For brevity, we denote the S-tuple (X1 , · · · , XS ) as X1S ,
and the n-tuple (Z1 , · · · , Zn ) as Z1n . A specific realization
of (X1 , · · · , XS ) is denoted by xS1 = (x1 , · · · , xS ), and
a specific realization of (Z1 , · · · , Zn ) is denoted by z1n =
(z1 , · · · , zn ). Then we have
2

(268)
E ĤB (Z1′ , Z2 , · · · , Zn ) − ĤB (Z1 , Z2 , · · · , Zn )
X
=
P(X1S = xS1 )
xS
1

×E




2
ĤB (Z1′ , Z2 , · · · , Zn ) − ĤB (Z1 , Z2 , · · · , Zn )
X1S = xS1 .
(269)

In light of Lemma 29, we know that the conditional distribution of Z1 conditioned on (X1 , · · · , XS ) is the discrete distrinp+a
),
bution (X1 /n, X2 /n, · · · , XS /n). Denoting r(p) = f ( n+Sa

22

we can rewrite
ĤB (Z1′ , Z2 , · · ·

, Zn ) − ĤB (Z1 , Z2 , · · · , Zn ) = D− + D+
(270)

where



XZ1
XZ1 − 1
−r
D− = r
n
n
  X ′ +1 
X ′ 
Z
Z
1
r
− r n1
Z1 =
6 Z1′
n
X ′ 
 X ′ −1 
D+ =
.
Z
Z
r
′
1
1
−
r
Z
=
Z
1
1
n
n


(271)

(272)

Hence, we have


Var H(P̂B )

n
2
2
2
2
= 2nED−
(277)
+ D+
≤ E (D− + D+ ) ≤ nE D−
2


S
2
X
1
EPn (i) r(Pn (i) − ) − r(Pn (i))
= 2n
(278)
n
i=1


2

S
X
nPn (i) + a
1
3 − ln
EPn (i)
≤ 2n
n + Sa
n + Sa
i=1
(279)



S
2
X
2n
nPn (i) + a
=
EP
(i)
3
−
ln
n
(n + Sa)2 i=1
n + Sa
(280)



S
2
X
npi + a
2n
pi 3 − ln
(281)
≤
2
(n + Sa) i=1
n + Sa


2
2n
n/S + a
1
≤
3
−
ln
(282)
S
·
(n + Sa)2
S
n + Sa
2n(3 + ln S)2
(283)
=
(n + Sa)2

Here, D− is the change in ĤB that occurs
when Z1 is removed according to the distribution
(X1 /n, X2 /n, · · · , XS /n), and D+ is the change in Ĥ
that occurs when Z1′ is added back according to the true where we have used the inequality (261) and Jensen’s inequaldistribution P . Now we have
ity due to
 

 2
S
"  
X

2 #
X
−
1
X
X
i
i
i
2
nx + a
d2
r
−r
(273)
E[D−
|X1S ] =
−3
x ln
n
n
n
i=1
dx2
n + Sa
  

2
S
"  
X


Xi
Xi − 1
Xi
2
nx + a
n
r
−r
pi
E[D+
|X1S ] =
3
ln
−
3
=
n
n
n
nx + a
n + Sa
i=1





 2
S


 #
X
Xi
Xi + 1
Xi
nx
+
a
nx
+
pi 1 −
r
−r
4 − ln
(284)
+
n
n
n
nx + a
n + Sa
i=1
(274)
< 0.
(285)
where we define r(x) = 0 when x ∈
/ [0, 1]. Then, by the law
J. Proof of Lemma 18
of iterated expectation, we know that
 

 2
It is well known (see, e.g. [75, Cor. 10.4.2]) that if f is
S X
n
X
j
j−1
j
2
concave in (0, 1), then
r
−r
E[D−
]=
n
n
n
i=1 j=0
f (x) − Bn [f ](x) ≥ 0, 0 ≤ x ≤ 1.
(286)
× P(B(n, pi ) = j)
(275)
Hence we focus on deriving the other bound. For concave
 

 2
S X
n
X
j
j−1
j
2
function
fα (x) = −xα , α ∈ (1, 2), Taylor’s polynomial of
r
−r
E[D+ ] =
n
n
n
degree 5 at x = x0 takes the form
i=1 j=0
 

 2 !

α(α − 1) α−2
j+1
j
j
x0 (x − x0 )2
Q5 (x) = −
r
−r
+ 1−
2
n
n
n
α(α − 1)(α − 2) α−3
x0 (x − x0 )3
−
× pi P(B(n, pi ) = j).
(276)
6
α(α − 1)(α − 2)(α − 3) α−4
x0 (x − x0 )4
−
24
α(α − 1)(α − 2)(α − 3)(α − 4) α−5
x0 (x − x0 )5
−
120
+ affine terms of x

2
2
After some algebra we can show that E[D−
] = E[D+
].

We know that the Bernstein polynomial of any affine
function on [0, 1] is the affine function itself, hence it suffices
to consider the non-affine part of Q5 (x). [69, Prop. 4] showed
the following results for Bernstein polynomials:

23

Lemma 30. Let 0 ≤ x0 ≤ 1. Then we have

L. Proof of Lemma 23

x0 (1 − x0 )
(287)
n
x0 (1 − x0 )
(1 − 2x0 )
(288)
Bn [(x − x0 )3 ](x0 ) =
n2
x2 (1 − x0 )2
Bn [(x − x0 )4 ](x0 ) = 3 0
n2
x0 (1 − x0 )
+
[1 − 6x0 (1 − x0 )] (289)
n3
x2 (1 − x0 )2
Bn [(x − x0 )5 ](x0 ) = 10 0
n3
!
x0 (1 − x0 )
+
[1 − 12x0 (1 − x0 )]
n4

Bn [(x − x0 )2 ](x0 ) =

× (1 − 2x0 )

(290)

Applying Lemma 17 and Lemma 30, taking x0 = x, we
have the desired bound.

By setting P = (1, 0, 0, · · · , 0), we have H(P ) = 0 and




(S − 1)a
n+a
a
n+a
H(P̂B ) = −
−
ln
ln
n + Sa
n + Sa
n + Sa
n + Sa
(298)


n + Sa
(S − 1)a
,
(299)
ln
≥
n + Sa
a
hence we have obtained the first lower bound


(S − 1)a
n + Sa
sup EP H(P̂B ) − H(P ) ≥
.
ln
n + Sa
a
P ∈MS
(300)
If n < Sa, then
sup
P ∈MS

(S − 1)a
ln S
2Sa
S−1
ln S.
≥
2S

EP H(P̂B ) − H(P ) ≥

(301)
(302)

If n > 2ea, then
sup
P ∈MS

K. Proof of Lemma 19
It is well known (see, e.g. [75, Cor. 10.4.2]) that if f is
concave in (0, 1), then
f (x) − Bn [f ](x) ≥ 0,

0 ≤ x ≤ 1.

(291)

Hence we focus on deriving the other bound. For function
fα (x) = xα , Taylor’s polynomial of degree 3 at x = x0 takes
the form
α(α − 1) α−2
Q3 (x) =
x0 (x − x0 )2
2
α(α − 1)(α − 2) α−3
x0 (x − x0 )3
+
6
+ affine terms of x.
(292)
Applying Lemma 17 and Lemma 30, taking x0 = x, we
have
Q3 (x) − Bn [Q3 ](x)
α(α − 1) α−2 x(1 − x)
x
=−
2
n
α(α − 1)(α − 2) α−3 x(1 − x)
(1 − 2x)
(293)
x
−
2
6
 n

α(1 − α) α−2
2−α
=
x
(1 − x) x −
(1 − 2x)
(294)
2n
3n


2−α
α(1 − α) α−2
.
(295)
x
(1 − x) x −
≥
2n
3n
Hence, we have
fα (x) − Bn [fα ](x) ≥ Q3 (x) − Bn [Q3 ](x)
(296)


α(1 − α) α−2
2−α
≥
.
x
(1 − x) x −
2n
3n
(297)

(S − 1)a
ln S
Sa + 2ea
S −1
ln S.
=
S + 2e

EP H(P̂B ) − H(P ) ≥

(303)
(304)

From now on we assume n ≥ Sa, n ≥ 2ea. For n ≥ 15S,
it follows from applying Lemma 21 that
sup
P ∈MS

EP H(P̂ ) − H(P ) ≥

S−1
1
S2
−
.
+
2n
20n2 12n2
(305)

If n < 15S, then it follows from applying Lemma 21 that one
can essentially take S = ⌊n/15⌋ in (305), and obtain
sup
P ∈MS

EP H(P̂ ) − H(P ) ≥

1
⌊n/15⌋
−
.
2n
4n

(306)

It follows from a refinement result of Cover and
Thomas [82, Thm. 17.3.3] that when |p̂B,i − p̂i | ≤ 1/2 for
all i (which is ensured by condition n ≥ Sa), we have
!
kP̂B − P̂ k1
,
(307)
|H(P̂B ) − H(P̂ )| ≤ Sf
S
where f (x) = −x ln x, x ∈ [0, 1]. We have
S
1
1 X |S p̂i − 1|a
kP̂B − P̂ k1 =
S
S i=1 n + Sa

≤

2(S − 1)a
,
S(n + Sa)

(308)
(309)

where the last step follows from (192). Since we have assumed
2a
−1
n ≥ 2ea, we have n+Sa
≤ 2a
. Since the function
n ≤ e
f (x) = −x ln x, x ∈ [0, 1] is monotonically increasing when
x ∈ [0, e−1 ], we have


n + Sa
2(S − 1)a
.
(310)
ln
|H(P̂B ) − H(P̂ )| ≤
n + Sa
a
A combination of these two inequalities yield the second

24

where ηX ∈ [min{X, p}, max{X, p}].
Similarly, we have

lower bound
EP H(P̂B ) − H(P )

sup
P ∈MS

S−1
1
2(S − 1)a
S2
≥
−
−
+
ln
2n
20n2
12n2
n + Sa




n + Sa
a
(311)

when n ≥ 15S, and the second lower bound
sup
P ∈MS

EP H(P̂B ) − H(P )

⌊n/15⌋
1
2(S − 1)a
≥
−
−
ln
2n
4n
n + Sa



n + Sa
a



(312)

when n < 15S.
Hence we are done by using these two lower bounds and
the inequality max{a, b} ≥ 3a+b
4 .
A PPENDIX C
P ROOFS

f (X) = f (p) + f ′ (p)(X − p) + R2 (X; p)
(325)
Z X
1
(X − u)f ′′ (u)du = f ′′ (νX )(X − p)2 ,
R2 (X; p) =
2
p
(326)
where νX ∈ [min{X, p}, max{X, p}].
Taking expectation on both sides with respect to X, where
nX ∼ B(n, p), we have
|Ef 2 (X) − f 2 (p)| = |ER1 (X; p)|.

Similarly, we have
|Ef (X) − f (p)| = |ER2 (X; p)|.
|r′′ (x)| = 2α(2α − 1)x2α−2 ≤ 2x2α−2 ,
1
|f ′′ (x)| = α(1 − α)xα−2 ≤ xα−2 .
4

A. Proof of Lemma 27

Var(X α ) ≤ EX 2α
E(nX)2α
=
n2α
E(nX)2
≤
n2α
(np)2 + np(1 − p)
=
n2α
2p
2
≤ 2α ∧ 2α−1 ,
n
n
which completes the proof.

(313)
(314)
(315)
(316)
(317)

Denoting f (p) = pα , 0 < α < 1, we have
Var(f (X))
= Ef 2 (X) − (Ef (X))2
2

2

(318)
2

2

= Ef (X) − f (p) + f (p) − (Ef (X))
2

2

2

(319)

2

2

2

= |Ef (X) − f (p)| + |(Ef (X) − f (p))
+ 2f (p)(Ef (X) − f (p))|

(321)

+ 2f (p)|Ef (X) − f (p)|.

(322)

≤ |Ef 2 (X) − f 2 (p)| + |Ef (X) − f (p)|2

Hence, it suffices to obtain bounds on |Ef 2 (X) − f 2 (p)|
and |Ef (X) − f (p)|. Denoting r(x) = f 2 (x), it follows
from Taylor’s formula and the integral representation of the
remainder term that
2

|ER1 (X; p)|
≤ E|R1 (X; p)|

′

r(X) = f (p) + r (p)(X − p) + R1 (X; p)
(323)
Z X
1
R1 (X; p) =
(X − u)r′′ (u)du = r′′ (ηX )(X − p)2
2
p
(324)

(330)

(331)

= E[|R1 (X; p)1(X ≥ p/2)|] + E[R1 (X; p)1(X < p/2)]
(332)


2α−2
2
≤ E 2(p/2)
(X − p) + E[R1 (X; p)1(X < p/2)]
(333)
p2α−1
+ sup |R1 (x; p)|P(nX < np/2)
(334)
≤8
n
x≤p/2
p2α−1
+ sup |R1 (x; p)|e−np/8 ,
n
x≤p/2

(335)

where in the last step we have used Lemma 26. Regarding
supx≤p/2 |R1 (x; p)|, for any x ≤ p/2, we have
Z p
Z p
(u − x)2u2α−2 du
(u − x)r′′ (u)du ≤
R1 (x; p) =
x

x

2

≤ |Ef (X) − f (p)| + |f (p) − (Ef (X) − f (p) + f (p)) |
(320)

(329)

Now we are in the position to bound |ER1 (X; p)| and
|ER2 (X; p)|. For |ER1 (X; p)|, we have

≤8

B. Proof of Lemma 28

(328)

It is straightforward to show that

OF AUXILIARY LEMMAS

Since nX is an integer, we have (nX)2 ≥ (nX)2α , 0 <
α < 1. Hence, for p ≤ 1/n,

(327)

≤2
≤2

p

Z

Zxp

(336)

u2α−1 du

(337)

u2α−1 du

(338)

0
2α

p
.
α
Hence, we have
=

(339)

1
8p2α−1
+ p2α e−np/8 .
(340)
n
α
obtain the following bound for

|ER1 (X; p)| ≤
Analogously,
|ER2 (X; p)|:

we

|ER2 (X; p)| ≤

1 α −np/8
pα−1
+
p e
.
n
4α

(341)

Plugging these estimates of |ER1 (X; p)| and |ER2 (X; p)|

25

into (322), we have for p ≥ 1/n,

[14] L. Paninski, “Estimation of entropy and mutual information,” Neural
Computation, vol. 15, no. 6, pp. 1191–1253, 2003.
1 2α −np/8
8p
[15] ——, “Estimating entropy on m bins given fewer than m samples,”
α
+ p e
Var(X ) ≤
Information Theory, IEEE Transactions on, vol. 50, no. 9, pp. 2200–
n
α
2203, 2004.
 α−1
2
p
1 α −np/8
[16] G. Valiant and P. Valiant, “Estimating the unseen: an n/ log n-sample
+
+
p e
estimator for entropy and support size, shown optimal via new CLTs,”
n
4α
in Proceedings of the 43rd annual ACM symposium on Theory of

 α−1
1 α −np/8
p
computing. ACM, 2011, pp. 685–694.
(342) [17] P. Valiant and G. Valiant, “Estimating the unseen: improved estimators
+
p e
+ 2f (p)
n
4α
for entropy and other properties,” in Advances in Neural Information
Processing Systems, 2013, pp. 2157–2165.
1 2α −np/8 2p2(α−1)
8p2α−1
+ p e
+
≤
[18] G. Valiant and P. Valiant, “The power of linear estimators,” in Founda2
n
α
n
tions of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium
 α−1

1 2α −np/4
p
1 α −np/8
on. IEEE, 2011, pp. 403–412.
α
+ 2p e
+ 2p
+
p e
[19] J. Jiao, K. Venkat, Y. Han, and T. Weissman, “Beyond maximum
8α
n
4α
likelihood: from theory to practice,” arXiv preprint arXiv:1409.7458,
(343)
2014.
[20] J. Jiao, Y. Han, and T. Weissman, “Beyond maximum likelihood:
10p2α−1
1
3 2α −np/8
2
≤
+
p e
+ 2α + 2 p2α e−np/4
Boosting the Chow-Liu algorithm for large alphabets,” in Signals,
n
2α
n
8α
Systems and Computers, 2016 50th Asilomar Conference on. IEEE,
(344)
2016, pp. 321–325.

2α
 2α [21] Y. Wu and P. Yang, “Minimax rates of entropy estimation on large
2
1
8α
10p2α−1
3 16α
alphabets via best polynomial approximation,” IEEE Transactions on
+ 2α + 2
.
≤
+
Information Theory, vol. 62, no. 6, pp. 3702–3720, 2016.
n
2α en
n
8α
en
(345) [22] J. Acharya, A. Orlitsky, A. T. Suresh, and H. Tyagi, “Estimating Rényi
entropy of discrete distributions,” IEEE Transactions on Information
Theory, vol. 63, no. 1, pp. 38–56, 2017.
where we have used the following inequality in the last step:
[23] Y. Wu and P. Yang, “Chebyshev polynomials, moment matching, and
for x ∈ (0, 1) and any c > 0,
optimal estimation of the unseen,” arXiv preprint arXiv:1504.01227,
2α

2015.
2α
.
(346) [24] Y. Han, J. Jiao, and T. Weissman, “Minimax rate-optimal estimax2α e−cnx ≤
tion of divergences between discrete distributions,” arXiv preprint
cen
arXiv:1605.09124, 2016.
2α−1
by [25] J. Jiao, Y. Han, and T. Weissman, “Minimax estimation of the L1
Note that if 0 < α < 1/2, we can upper bound 10pn
distance,” in Information Theory (ISIT), 2016 IEEE International Sym1
10
posium on. IEEE, 2016, pp. 750–754.
n2α , since we have constrained p ≥ n .
[26] Y. Bu, S. Zou, Y. Liang, and V. V. Veeravalli, “Estimation of KL
divergence: Optimal minimax rate,” arXiv preprint arXiv:1607.02653,
R EFERENCES
2016.
[27] A. Orlitsky, A. T. Suresh, and Y. Wu, “Optimal prediction of the number
[1] C. Olsen, P. E. Meyer, and G. Bontempi, “On the impact of entropy
of unseen species,” Proceedings of the National Academy of Sciences,
estimation on transcriptional regulatory network inference based on
p. 201607774, 2016.
mutual information,” EURASIP Journal on Bioinformatics and Systems
[28] Y. Wu and P. Yang, “Sample complexity of the distinct elements
Biology, vol. 2009, no. 1, p. 308959, 2009.
problem,” arXiv preprint arXiv:1612.03375, 2016.
[2] J. P. Pluim, J. A. Maintz, and M. A. Viergever, “Mutual-information[29] G. A. Miller, “Note on the bias of information estimates,” Information
based registration of medical images: a survey,” Medical Imaging, IEEE
Theory in Psychology: Problems and Methods, vol. 2, pp. 95–100, 1955.
Transactions on, vol. 22, no. 8, pp. 986–1004, 2003.
[30] A. Carlton, “On the bias of information estimates.” Psychological
[3] P. Viola and W. M. Wells III, “Alignment by maximization of mutual
Bulletin, vol. 71, no. 2, p. 108, 1969.
information,” International journal of computer vision, vol. 24, no. 2,
[31] P. Grassberger, “Finite sample corrections to entropy and dimension
pp. 137–154, 1997.
estimates,” Physics Letters A, vol. 128, no. 6, pp. 369–373, 1988.
[4] L. Batina, B. Gierlichs, E. Prouff, M. Rivain, F.-X. Standaert, and
[32] S. Zahl, “Jackknifing an index of diversity,” Ecology, vol. 58, no. 4, pp.
N. Veyrat-Charvillon, “Mutual information analysis: a comprehensive
907–913, 1977.
study,” Journal of Cryptology, vol. 24, no. 2, pp. 269–291, 2011.
[33] J. Hausser and K. Strimmer, “Entropy inference and the James-Stein
[5] M. O. Hill, “Diversity and evenness: a unifying notation and its
estimator, with application to nonlinear gene association networks,” The
consequences,” Ecology, vol. 54, no. 2, pp. 427–432, 1973.
Journal of Machine Learning Research, vol. 10, pp. 1469–1484, 2009.
[6] F. Franchini, A. Its, and V. Korepin, “Rényi entropy of the XY spin
[34] A. Chao and T.-J. Shen, “Nonparametric estimation of Shannon’s index
chain,” Journal of Physics A: Mathematical and Theoretical, vol. 41,
of diversity when there are unseen species in sample,” Environmental
no. 2, p. 025302, 2008.
and ecological statistics, vol. 10, no. 4, pp. 429–443, 2003.
[7] C. E. Shannon, “A mathematical theory of communication,” The Bell
[35] C. O. Daub, R. Steuer, J. Selbig, and S. Kloska, “Estimating mutual
System Technical Journal, vol. 27, pp. 379–423, 623–656, 1948.
information using B-spline functions–an improved similarity measure
[8] L. Breiman, J. Friedman, C. J. Stone, and R. A. Olshen, Classification
for analysing gene expression data,” BMC bioinformatics, vol. 5, no. 1,
and regression trees. CRC press, 1984.
p. 118, 2004.
[9] A. Rényi, “On measures of entropy and information,” in Fourth Berkeley
[36] P. Grassberger, “Entropy estimates from insufficient samplings,” arXiv
Symposium on Mathematical Statistics and Probability, 1961, pp. 547–
preprint physics/0307138, 2008.
561.
[37] M. Vinck, F. P. Battaglia, V. B. Balakirsky, A. H. Vinck, and C. M.
[10] J. Jiao, K. Venkat, Y. Han, and T. Weissman, “Minimax estimation
Pennartz, “Estimation of the entropy based on its polynomial represenof functionals of discrete distributions,” Information Theory, IEEE
tation,” Physical Review E, vol. 85, no. 5, p. 051139, 2012.
Transactions on, vol. 61, no. 5, pp. 2835–2885, 2015.
[38] T. Schürmann and P. Grassberger, “Entropy estimation of symbol
[11] J. Hájek, “A characterization of limiting distributions of regular estisequences,” Chaos: An Interdisciplinary Journal of Nonlinear Science,
mates,” Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebivol. 6, no. 3, pp. 414–427, 1996.
ete, vol. 14, no. 4, pp. 323–330, 1970.
[39] S. Schober, “Some worst-case bounds for Bayesian estimators of discrete
[12] ——, “Local asymptotic minimax and admissibility in estimation,” in
distributions,” in Information Theory Proceedings (ISIT), 2013 IEEE
Proceedings of the sixth Berkeley symposium on mathematical statistics
International Symposium on. IEEE, 2013, pp. 2194–2198.
and probability, vol. 1, 1972, pp. 175–194.
[40] D. H. Wolpert and D. R. Wolf, “Estimating functions of probability
[13] L. Le Cam, Asymptotic methods in statistical decision theory. Springer,
distributions from a finite set of samples,” Physical Review E, vol. 52,
1986.
no. 6, p. 6841, 1995.
2α−1

26

[41] D. Holste, I. Grosse, and H. Herzel, “Bayes’ estimators of generalized
entropies,” Journal of Physics A: Mathematical and General, vol. 31,
no. 11, p. 2551, 1998.
[42] I. Nemenman, F. Shafee, and W. Bialek, “Entropy and inference,
revisited,” Advances in neural information processing systems, vol. 1,
pp. 471–478, 2002.
[43] E. Archer, I. M. Park, and J. W. Pillow, “Bayesian estimation of discrete
entropy with mixtures of stick-breaking priors,” in Advances in Neural
Information Processing Systems, 2012, pp. 2015–2023.
[44] I. Nemenman, W. Bialek, and R. d. R. van Steveninck, “Entropy and
information in neural spike trains: Progress on the sampling problem,”
Physical Review E, vol. 69, no. 5, p. 056111, 2004.
[45] I. Nemenman, “Coincidences and estimation of entropies of random
variables with large cardinalities,” Entropy, vol. 13, no. 12, pp. 2013–
2023, 2011.
[46] E. L. Lehmann and G. Casella, Theory of point estimation. Springer,
1998, vol. 31.
[47] Y. Han, J. Jiao, and T. Weissman, “Minimax estimation of discrete
distributions under ℓ1 loss,” IEEE Transactions on Information Theory,
vol. 61, no. 11, pp. 6343–6354, 2015.
[48] I. A. Ibragimov and R. Z. Has’ minskii, Statistical estimation: asymptotic
theory. Springer-Verlag New York, 1981, vol. 2.
[49] A. Antos and I. Kontoyiannis, “Convergence properties of functional
estimates for discrete distributions,” Random Structures & Algorithms,
vol. 19, no. 3-4, pp. 163–193, 2001.
[50] B. Efron and R. Thisted, “Estimating the number of unsen species: How
many words did Shakespeare know?” Biometrika, vol. 63, no. 3, pp. pp.
435–447, 1976. [Online]. Available: http://www.jstor.org/stable/2335721
[51] B. Efron and C. Stein, “The jackknife estimate of variance,” The Annals
of Statistics, pp. 586–596, 1981.
[52] S. Boucheron, G. Lugosi, and P. Massart, Concentration inequalities: A
nonasymptotic theory of independence. Oxford University Press, 2013.
[53] O. E. Barndorff-Nielsen and D. R. Cox, Asymptotic techniques for use
in statistics. Chapman & Hall, 1989.
[54] C. G. Small, Expansions and asymptotics for statistics. CRC Press,
2010.
[55] B. Efron, “Bootstrap methods: another look at the Jackknife,” The Annals
of Statistics, pp. 1–26, 1979.
[56] P. Hall, The bootstrap and Edgeworth expansion. Springer Science &
Business Media, 1992.
[57] B. Harris, “The statistical estimation of entropy in the non-parametric
case,” DTIC Document, Tech. Rep., 1975.
[58] P. Jacquet and W. Szpankowski, “Entropy computations via analytic
depoissonization,” Information Theory, IEEE Transactions on, vol. 45,
no. 4, pp. 1072–1081, 1999.
[59] P. Flajolet, “Singularity analysis and asymptotics of Bernoulli sums,”
Theoretical Computer Science, vol. 215, no. 1, pp. 371–381, 1999.
[60] J. Cichoń, Z. Golkebiewski, M. Kardas, and M. Klonowski, “On deltamethod of moments and probabilistic sums,” 2013.
[61] S. Bernstein, “Collected works: Vol 1. constructive theory of functions
(1905-1930), English translation,” Atomic Energy Commission, Springfield, Va, 1958.
[62] R. Paltanea, Approximation theory using positive linear operators.
Springer, 2004.
[63] Z. Ditzian and V. Totik, Moduli of smoothness. Springer, 1987.
[64] H. H. Gonska, Quantitative Aussagen zur Approximation durch positive
lineare Operatoren. Gesamthochschule Duisburg, 1979.
[65] Y. Han, J. Jiao, and T. Weissman, “Adaptive estimation of Shannon
entropy,” in Information Theory (ISIT), 2015 IEEE International Symposium on. IEEE, 2015, pp. 1372–1376.
[66] L. Strukov and A. Timan, “Mathematical expectation of continuous
functions of random variables. smoothness and variance,” Siberian
Mathematical Journal, vol. 18, no. 3, pp. 469–474, 1977.
[67] H. Walk, “Probabilistic methods in the approximation by linear positive
operators,” in Indagationes Mathematicae (Proceedings), vol. 83, no. 4.
Elsevier, 1980, pp. 445–455.
[68] L. Hahn et al., “A note on stochastic methods in connection with
approximation theorems for positive linear operators,” Pacific J. Math,
vol. 101, pp. 307–319, 1981.
[69] D. Braess and T. Sauer, “Bernstein polynomials and learning theory,”
Journal of Approximation Theory, vol. 128, no. 2, pp. 187–206, 2004.
[70] P. Diaconis and S. Zabell, “Closed form summation for classical
distributions: variations on a theme of de moivre,” Statistical Science,
pp. 284–302, 1991.
[71] W. Feller, An introduction to probability theory and its applications.
John Wiley & Sons, 2008, vol. 2.

[72] A. Tsybakov, Introduction to Nonparametric Estimation.
SpringerVerlag, 2008.
[73] R. D. Gill and B. Y. Levit, “Applications of the van Trees inequality: a
Bayesian Cramér-Rao bound,” Bernoulli, pp. 59–79, 1995.
[74] R. Paltanea, “On some constants in approximation by Bernstein operators,” General Mathematics, vol. 16, no. 4, p. 137148, 2008.
[75] R. A. DeVore and G. G. Lorentz, Constructive approximation. Springer,
1993, vol. 303.
[76] V. Totik, “Approximation by Bernstein polynomials,” American Journal
of Mathematics, pp. 995–1018, 1994.
r (f, t) twenty years later,”
[77] Z. Ditzian, “Polynomial approximation and ωϕ
Surveys in Approximation Theory, vol. 3, pp. 106–151, 2007.
[78] A. Wald, Statistical decision functions. Wiley, 1950.
[79] K. Joag-Dev and F. Proschan, “Negative association of random variables
with applications,” The Annals of Statistics, vol. 11, no. 1, pp. 286–295,
March 1983.
[80] N. Batir, “Inequalities for the gamma function,” Archiv der Mathematik,
vol. 91, no. 6, pp. 554–563, 2008.
[81] M. Mitzenmacher and E. Upfal, Probability and computing: Randomized
algorithms and probabilistic analysis. Cambridge University Press,
2005.
[82] T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed.
New York: Wiley, 2006.

Jiantao Jiao (S’13) received the B.Eng. degree with the highest honor in
Electronic Engineering from Tsinghua University, Beijing, China in 2012,
and a Master’s degree in Electrical Engineering from Stanford University in
2014. He is currently working towards the Ph.D. degree in the Department of
Electrical Engineering at Stanford University. He is a recipient of the Stanford
Graduate Fellowship (SGF). His research interests include information theory
and statistical signal processing, with applications in communication, control,
computation, networking, data compression, and learning.

Kartik Venkat (S’12) is currently a Research Associate in New York at
PDT Partners, a quantitative investment manager. Kartik’s research interests
include statistical inference, information theory, machine learning and their
inter-connections. Kartik received his Ph.D. in Electrical Engineering from
Stanford University in 2015. Kartik also received a Masters Degree from the
same university in 2012, and a Bachelors degree from the Indian Institute
of Technology Kanpur in 2010, both in Electrical Engineering. Kartik was
the recipient of the Thomas M. Cover Dissertation Award in 2016 awarded
by the IEEE. Kartik was named the 2015 Marconi Society Paul Baran
Young Scholar. His other honors include the Jack Keil Wolf Student Best
Paper Award at the 2012 International Symposium on Information Theory, a
Stanford Graduate Fellowship for Engineering and Sciences, the Numerical
Technologies Founders Graduate Prize, and the National Talent Scholarship
awarded by the Government of India.

Yanjun Han (S’14) received his B.Eng. degree with the highest honor in
Electronic Engineering from Tsinghua University, Beijing, China in 2015,
and a Master’s degree in Electrical Engineering from Stanford University in
2017. He is currently working towards the Ph.D. degree in the Department of
Electrical Engineering at Stanford University. His research interests include
information theory and statistics, with applications in communications, data
compression, and learning.

Tsachy Weissman (S’99-M’02-SM’07-F’13) graduated summa cum laude
with a B.Sc. in electrical engineering from the Technion in 1997, and earned
his Ph.D. at the same place in 2001. He then worked at Hewlett-Packard
Laboratories with the information theory group until 2003, when he joined
Stanford University, where he is Professor of Electrical Engineering and
incumbent of the STMicroelectronics chair in the School of Engineering. He
has spent leaves at the Technion, and at ETH Zurich.

27

Tsachy’s research is focused on information theory, statistical signal
processing, the interplay between them, and their applications.
He is recipient of several best paper awards, and prizes for excellence in
research.
He served on the editorial board of the IEEE T RANSACTIONS ON
I NFORMATION T HEORY from Sept. 2010 to Aug. 2013, and currently serves
on the editorial board of Foundations and Trends in Communications and
Information Theory.

