Bias Correction with Jackknife, Bootstrap, and Taylor Series
Jiantao Jiao,

Yanjun Han,

and Tsachy Weissman∗

arXiv:1709.06183v1 [math.ST] 18 Sep 2017

September 20, 2017

Abstract
We analyze the bias correction methods using jackknife, bootstrap, and Taylor series. We
focus on the binomial model, and consider the problem of bias correction for estimating f (p),
where f ∈ C[0, 1] is arbitrary. We characterize the supremum norm of the bias of general
jackknife and bootstrap estimators for any continuous functions, and demonstrate the in deleted jackknife, different values of d may lead to drastically different behavior in jackknife. We
show that in the binomial model, iterating the bootstrap bias correction infinitely many times
may lead to divergence of bias and variance, and demonstrate that the bias properties of the
bootstrap bias corrected estimator after r−1 rounds is exactly the same as that of the r-jackknife
estimator if a bounded coefficients condition is satisfied.

1

Introduction

One of the classic problems in statistics is to design procedures to reduce the bias of estimators.
General bias correction methods such as the bootstrap, the jackknife, and the Taylor series have
been widely employed and well studied in the literature. See [Que56, AGW71, Mil74, Efr79, Efr82,
RS02, Wit87, HM88, Hal92, ET94, PRW99, ZI04, ST12, CCN14] and the references therein.
A close inspection of the literature on those general bias correction methods show that they
usually rely on certain expansion (differentiability) properties of the expectation of the estimator
one would like to correct the bias for, and the analysis is pointwise asymptotics [Wit87,Hal92,ST12].
One motivation for this work is that the methods based on series expansions and differentiability
assumptions may not suffice in the analysis of bootstrap and jackknife even in the simplest statistical models, and the practical implementations of bootstrap and jackknife do not require those
differentiability conditions. The Taylor series itself, by definition, is a series expansion method
which we include here for comparison with bootstrap and jackknife.
To illustrate our point, consider one of the simplest statistical models, the binomial model,
where n · p̂n ∼ B(n, p). For any function f : [0, 1] 7→ R, we would like to correct the bias of f (p̂n )
as an estimator of f (p). Let e1,n (p) = f (p) − Ep f (p̂n ) be the bias term. The expectation of the
jackknife bias corrected estimator fˆ2 satisfies
E[fˆ2 ] = E [nf (p̂n ) − (n − 1)f (p̂n−1 )] ,

(1)

∗
Jiantao Jiao, Yanjun Han, and Tsachy Weissman are with the Department of Electrical Engineering, Stanford
University. Email: {jiantao, yjhan, tsachy}@stanford.edu

1

where (n − 1) · p̂n−1 ∼ B(n − 1, p). The textbook argument of the bias reduction property of the
jackknife is the following [ST12]. Suppose that
a(p) b(p)
1
e1,n (p) =
+ 2 + Op
,
n
n
n3




(2)

where a(p), b(p) are unknown functions of p which do no depend on n, and Op (an ) is a sequence
that is elementwise upper bounded by an up to a multiplicative constant for fixed p. We also have
1
b(p)
a(p)
+ Op
.
+
e1,n−1 (p) =
2
n − 1 (n − 1)
(n − 1)3




(3)

Hence, the overall bias of fˆ2 is:
f (p) − Ep fˆ2 = ne1,n (p) − (n − 1)e1,n−1 (p)
 
b(p)
b(p)
1
=
−
+ Op
n
n−1
n2
 
1
b(p)
+ Op
,
=−
n(n − 1)
n2

(4)
(5)
(6)

which seems to suggest that the bias has been reduced to order n12 instead of order n1 . However, if
we particularize (2) to f (p) = p ln(1/p), which relates to the Shannon entropy [Sha48], we have
1
1 − p 1 − 3p + 2p2
−
+ Op
.
e1,n (p) =
2
2n
6pn
n3




(7)

One immediately sees that it may not be reasonable to claim that the jackknife has reduced the
bias upon looking at (7) and (6). Indeed, the bias of the jackknife estimator is uniformly upper
bounded by O(n), but the right hand side of (7) and (6) explodes to infinity as p → 0. It shows
that one cannot ignore the dependence on p in the Op (·) notation, but even doing higher order of
Taylor expansion does not help. In fact, it was shown first in [Pan03] that for f (p) = p ln(1/p),
there exist universal constants C1 > 0, C2 > 0 such that
sup |e1,n (p)| ≤
p∈[0,1]

C1
n

C2
.
sup |f (p) − Ep [fˆ2 ]| ≥
n
p∈[0,1]

(8)
(9)

In other words, the jackknife does not change the bias order at all. There exist other estimators that
achieve a smaller order of bias. Indeed, the estimators [VV11, VV13, WY16, JVHW15] that achieve
the optimal minimax sample complexity for Shannon entropy estimation used best approximation
1
polynomials to reduce the bias of of each symbol from n1 to n ln
n.
In this paper, we connect the jackknife and bootstrap to the theory of approximation, and
provide a systematic treatment of the problem of correcting the bias for f (p̂n ) as an estimator of
f (p) for f ∈ C[0, 1] and n · p̂n ∼ B(n, p). Compared with existing literature, we choose to simplify
the statistical model to the extreme, but consider arbitrary functions f . We believe it is an angle
worth investigating due to the following reasons. First of all, it directly leads to analysis of the
bias correction properties of jackknife and bootstrap for important statistical questions such as the
2

Shannon entropy estimation, which existing theory proves insufficient of handling. Second, even in
this simplest statistical model the analysis of jackknife and bootstrap is far non-trivial, and there
still exist abundant open problems as we discuss in this paper. One message we would like to convey
in this work is that the analysis of jackknife and bootstrap in simple statistical models but general
functions could lead to interesting and deep mathematical phenomena that remain fertile ground
for research. Moreover, we emphasize that the insights obtained through analyzing the binomial
model could generalize to other statistical models. 1
We introduce some notations below. The r-th symmetric difference of a function f : [0, 1] 7→ R
is given by
∆rh f (x)

=

r
X

!

k

(−1)

k=0

r
f (x + r(h/2) − kh),
k

(10)

where ∆rh f (x) = 0 if x + rh/2 or x − rh/2 is not in [0, 1]. We introduce the r-th Ditzian–Totik
modulus of smoothness of a function f : [0, 1] 7→ R as
ωϕr (f, t) = sup

0<h≤t

∆rhϕ(x) f ,

(11)

p

where ϕ(x) = x(1 − x), and the norm is the supremum norm.
The ωϕr (f, t) modulus satisfies the following properties.
Lemma 1. [DT87, Chap. 4] The Ditzian–Totik modulus of smoothness ωϕr (f, t) in (11) satisfies
the following:
1. ωϕr (f, t) is a nondecreasing function of t.
2. There exist universal constants K > 0, t0 > 0 such that ωϕr (f, λt) ≤ Kλr ωϕr (f, t) for λ ≥ 1,
and λt ≤ t0 .
3. There exist universal constants K > 0, t0 > 0 such that ωϕr+1 (f, t) ≤ Kωϕr (f, t) for 0 < t ≤ t0 .
4. There exists a universal constant K > 0 such that ωϕr (f, t) ≤ K supx∈[0,1] |f (r) (x)|tr .
ω r (f,t)

5. limt→0+ ϕtr
= 0 ⇒ f is a polynomial with degree r − 1. (f is a polynomial of degree
r
r − 1 ⇒ ωϕ (f, t) = 0).
6. ωϕr (f, t) = O(tr ) for fixed f, r if and only if f (r−1) ∈ A.C.loc and kϕr f (r) k < ∞,
where f (r−1) ∈ A.C.loc means that f is r − 1 times differentiable and f (r−1) is absolutely continuous
in every closed finite interval [c, d] ⊂ (0, 1).
1

We mention that most of the results in this paper could be generalized to the case of natural exponential family of
quadratic variance functions [Mor82, Mor83], which comprises of six families: Gaussian, Poisson, binomial, negative
binomial, gamma, and generalized hyperbolic secant. Coincidentally, these distribution families were also identified as
special in approximation theory literature, where they were named operators of the exponential-type [May76, IM78].

3

We emphasize that Ditzian–Totik modulus of smoothness is easy to compute for various functions. For example, for f (x) = xδ | ln x/2|γ , x ∈ (0, 1). Then for r ≥ 2δ, we have [DT87, Section
3.4]:
ωϕr (f, t) r,δ,γ


t2δ | ln t|γ

δ∈
/ Z, δ ≥ 0, γ ≥ 0

t2δ | ln t|γ−1

δ ∈ Z, δ ≥ 0, γ ≥ 1

.

(12)

An intuitive understanding of ωϕr (f, t) is the following. If the function f is “smoother”, the
modulus is smaller. However, a non-zero ωϕr (f, t) cannot vanish faster than the order tr for any
fixed f .
Notation: All the norms in this paper refer to the supremum norm. Concretely kf k =
supx |f (x)|. For non-negative sequences aγ , bγ , we use the notation aγ .α bγ to denote that there
a
exists a universal constant C that only depends on α such that supγ bγγ ≤ C, and aγ &α bγ is
equivalent to bγ .α aγ . Notation aγ α bγ is equivalent to aγ .α bγ and bγ .α aγ . We write
aγ . bγ if the constant is universal and does not depend on any parameters. Notation aγ  bγ
a
means that lim inf γ bγγ = ∞, and aγ  bγ is equivalent to bγ  aγ . We write a ∧ b = min{a, b} and
a ∨ b = max{a, b}. Moreover, polydn denotes the set of all d-variate polynomials of degree of each
variable no more than n, and En [f ; I] denotes the distance of the function f to the space polydn
in the uniform norm k · k∞,I on I ⊂ Rd . The space poly1n is also abbreviated as polyn . All logarithms are in the natural base. The notation Eθ [X] denotes the mathematical expectation of the
random variable X whose distribution is indexed by the parameter θ. The s-backward difference
of a function defined over integers Gn is
s

∆ Gn ,

s
X

!

k

(−1)

k=0

s
Gn−k .
k

(13)

Remark 1 (Operator view of bias reduction). It was elaborated in [JVHW17] that for any statistical model, the quantity Eθ F (θ̂) could be viewed as an operator that maps the function F (·) to
another function of θ. The operator is obviously linear in F , and is also positive in the sense that
if F ≥ 0 everywhere it is also everywhere non-negative. If we view Eθ F (θ̂) as an approximation of
F (θ), then analyzing the bias of the estimator F (θ̂) is equivalent to analyzing the approximation
error of Eθ F (θ̂).
Casting the bias analysis problem as an approximation problem, a key observation of this work
is that the bootstrap bias correction could be viewed as the iterated Boolean sum approximation,
and the jackknife bias correction could be viewed as a linear combination approximation, and the
Taylor series bias correction corresponds to the Taylor series approximation. The main tool we
use to handle these approximation theoretic questions is the K-functional, which we introduce in
Section A.
We now summarize our main results for jackknife, bootstrap, and Taylor series bias correction.

1.1

Jackknife bias correction

The jackknife is a subsampling technique [ST12] that aims at making the biases of estimators with
different sample sizes cancel each other.

4

Definition 1 (r-jackknife estimator). Fix r ≥ 1, r ∈ Z. Fix K > 0 such that K does not scale
with n. For a collection of sample sizes n1 < n2 < n3 < . . . < nr ≤ Kn1 = n, under the binomial
model the general r-jackknife estimator is defined as
r
X

fˆr =

Ci Un [f (p̂ni )],

(14)

i=1

P
β

f (Xβ1 ,Xβ2 ,...,Xβq )

is the U -statistic with kernel f , and the sum is over all distinct
(nq)
combinations of q elements from total n samples from the Bernoulli distribution Bern(p). Each
ni · p̂ni ∼ B(ni , p). The coefficients {Ci } are given by

where Un [f ] =

Ci =

ni
, 1 ≤ i ≤ r.
n − nj
j6=i i
Y

(15)

If nr = n, ni − ni−1 = d, then it is called the delete-d r-jackknife estimator.
Note that the standard jackknife in (1) corresponds to n1 = n − 1, n2 = n, whose corresponding
coefficients are C1 = −(n − 1), C2 = n. As shown in Lemma 13 in Section B, the coefficients
{Ci }1≤i≤r in (15) satisfy the following:
r
X
i=1
r
X
i=1

Ci = 1
Ci
= 0,
nρi

1 ≤ ρ ≤ r − 1, ρ ∈ Z.

(16)

The intuition behind this condition is clear: only through these equations can one completely
cancel any bias terms of order 1/nρ , ρ ≤ r − 1. It is also clear that (16) corresponds to solving
a linear system with the Vandermonde matrix, for which the solution given in (15) is the unique
solution due to the fact that all the ni ’s are distinct. The rationale above also appeared in [SGO71],
and the corresponding coefficients Ci were given in the form of determinants. Equation (15) shows
that in this special case the coefficients admit a simple expression.
1.1.1

Jackknife with the bounded coefficients condition

We introduce the following condition on {Ci }1≤i≤r which turns out to be crucial for the bias and
variance properties of the general r-jackknife.
Condition 1 (Bounded coefficients condition). We say that the jackknife coefficients Ci in (15)
satisfy the bounded coefficients condition with parameter C if there exists a constant C that only
depends on r such that
r
X

|Ci | ≤ C.

(17)

i=1

One motivation for Condition 1 is the following. Observe that
Ep fˆr =

r
X

Ci Ep [f (p̂ni )].

i=1

5

(18)

Viewing Ep [f (p̂ni )] as an operator that maps f to a polynomial, it is an approximation to f (p),
which, by the Bernstein theorem [AS04, Chap. 7] in fact limn→∞ kEp f (p̂n ) − f (p)k∞ = 0 for any
continuous function f on [0, 1]. Then, one can view the r-jackknife as a linear combination of
operators. In this sense, Condition 1 assures that the linear combination as a new operator has
bounded norm that is independent of n.
The following theorem quantifies the performance of the general r-jackknife under the bounded
coefficients condition in Condition 1.
Theorem 1. Suppose {Ci }1≤i≤r satisfies Condition 1 with parameter C. Suppose r ≥ 1 is a fixed
integer. Let fˆr denote the general r-jackknife in (14). Then, for any f ∈ C[0, 1], the following is
true.
1.
√
kf (p) − Ep fˆr k .r,C ωϕ2r (f, 1/ n) + n−r kf k

(19)

kf (p) − Ep fˆr k .α,r,C n−α/2 ⇔ ωϕ2r (f, t) .α,r,C tα .

(20)

2. Fixing 0 < α < 2r,

3. Suppose there is a constant D < 22r for which
ωϕ2r (f, 2t) ≤ Dωϕ2r (f, t) for t ≤ t0 .

(21)

√
kf (p) − Ep fˆr k r,C,D ωϕ2r (f, 1/ n).

(22)

√
kf (p) − Ep fˆr k  ωϕ2r (f, 1/ n).

(23)

Then,

4. For r = 1,

The following corollary of Theorem 1 is immediate given (12).
Corollary 1. Under the conditions in Theorem 1, if f = −p ln p, then
1
kf (p) − Ep fˆr k r,C .
n

(24)

1
.
nα

(25)

If f (p) = pα , 0 < α < 1, then,
kf (p) − Ep fˆr k r,C

Corollary 1 implies that the r-jackknife estimator for fixed r does not improve the bias of f (p̂n )
for f (p) = p ln(1/p), which makes it incapable of achieving the minimax rates of Shannon entropy
estimation [WY16, JVHW15].

6

1.1.2

Jackknife without the bounded coefficients condition

Theorem 1 has excluded the case that n1 = n − 1, n2 = n. Clearly, to satisfy the assumptions of
Theorem 1, we need to require |ni − ni−1 | & n1 , which puts a minimum gap between the different
sample sizes we can use. This begs the question: is this condition necessary to Theorem 1 to hold?
If not, what bad consequences it will lead to?
From a computational perspective, taking d small in the delete-d jackknife may reduce the
computational burden. However, as we now show, the usual delete-1 jackknife does not satisfy
Theorem 1 in general and exhibits drastically different bias and variance properties. 2
We now show that the delete-1 jackknife may have bias and variance both diverging to infinity
in the worst case.
Theorem 2. Let fˆr denote the delete-1 r-jackknife estimator. There exists a fixed function f ∈
C(0, 1] that satisfies kf k∞ ≤ 1 such that
kEp fˆr − f (p)k∞ & nr−1 .

(26)

If we allow the function f to depend on n, then one can have f ∈ C[0, 1]. 3
Meanwhile, for any n ≥ 4, there exists a function f ∈ C[0, 1] depending on n such that
n2
kVarp (fˆ2 )k∞ ≥
.
e

(30)

Theorem 2 shows that in the worst case, the delete-1 r-jackknife may have bad performances
compared to that satisfying Condition 1. Before we delve into the refined analysis of delete-1 rjackknife, we illustrate the connection between various types of r-jackknife estimators. It turns out
that the jackknife is intimately related to the divided differences of functions.
Definition 2 (Divided difference). The divided difference f [x1 , x2 , . . . , xn ] of a function f over n
distinct points {x1 , x2 , . . . , xn } is defined as
f [x1 , x2 , . . . , xn ] =

n
X

f (xi )
.
j6=i (xi − xj )

Q
i=1

(31)

2

It has been observed in the literature [SW89] that in jackknife variance estimation, which is a different area of
application of the jackknife methodology, sometimes it is also necessary to take d large to guarantee consistency.
3
We emphasize that if we restrict f ∈ C[0,
kf k∞ ≤ 1, and do not allow f to depend on n, then one cannot
P1],
r
achieve the bound (26). Indeed, noting that
C = 1, the error term can be written as
i=1 i
r
X

Ci Ep f (p̂n+i−r ) − f (p) =

i=1

r
X

Ci (Ep f (p̂n+i−r ) − f (p))

(27)

i=1
r

≤

X

|Ci |kEp f (p̂n+i−r ) − f (p)k∞ ,

(28)

i=1

It follows from the Bernstein theorem [AS04, Chap. 7] that limn→∞ kEp f (p̂n ) − f (p)k∞ = 0 for any continuous
function f on [0, 1]. Hence, for any f ∈ C[0, 1] one has
kEp fˆr − f (p)k∞ = o(nr−1 ),
since max1≤i≤r |Ci | . nr−1 for the delete-1 r-jackknife.

7

(29)

It follows from (18), (15) and Lemma 13 in Section B that the bias of a general r-jackknife
estimator fˆr can be written as
Ep [fˆr ] − f (p) =
=

r Y
X

ni
(Ep [f (p̂ni )] − f (p))
n − nj
i=1 j6=i i

(32)

r
X
nr−1
(Ep [f (p̂ni )] − f (p))
i
Q
.

(33)

j6=i (ni

i=1

− nj )

Define Gn,f,p = nr−1 (Ep [f (p̂n )] − f (p)). Then, the bias of fˆr can be written as the divided
difference of function G·,f,p :
Ep [fˆr ] − f (p) = G·,f,p [n1 , n2 , . . . , nr ].

(34)

It follows from the mean value theorem of divided differences defined over integers in Lemma 11
of Section B that for every p, f ,
|Ep [fˆr ] − f (p)| ≤

max |G·,f,p [n − r + 1, n − r + 2, . . . , n − 1, n]|,

n1 ≤n≤nr

(35)

and the right hand side of (35) is nothing but the maximum of the bias of the delete-1 r-jackknife
with varying sample sizes.
Equation (35) shows that in terms of the bias, the delete-1 jackknife might be the “worst” among
all r-jackknife estimators. However, what is the precise performance of the delete-1 r-jackknife when
the function f is “smooth”? Does the performance improve compared to Theorem 2? We answer
this question below.
Condition 2 (Condition Ds ). A function f : [0, 1] 7→ R is said to satisfy the condition Ds , s ≥
0, s ∈ Z with parameter L > 0 if the following is true:
1. s = 0: f is Lebesgue integrable on [0, 1] and supx∈[0,1] |f (x)| ≤ L.
2. s ≥ 1:
(a) f (s−1) is absolutely continuous on [0, 1];
(b) supx∈[0,1] |f (i) (x)| ≤ L, 0 ≤ i ≤ s.
Remark 2. We mention that if a function f satisfies condition Ds , it does not necessarily belong
to the space C s [0, 1], where C s [0, 1] denotes the space of continuously differentiable functions on
[0, 1]. Indeed, the function f (x) = x2 sin(1/x)1(x ∈ (0, 1]) satisfies condition D1 as a function
mapping from [0, 1] to R, but it does not belong to C 1 [0, 1].
The performance of the delete-1 r-jackknife in estimating f (p) satisfying condition Ds is summarized in the following theorem.
Theorem 3. For any r ≥ 1, s ≥ 0 and f satisfying condition Ds with parameter L, let fˆr be the
delete-1 r-jackknife. Then,

kEp fˆr − f (p)k .r,s,L



nr−s−1



1

n

−(r− 2 )




n−r

8

if 0 ≤ s ≤ 2r − 2;
if s = 2r − 1;
if s ≥ 2r.

(36)

Theorem 4. For 1 ≤ s ≤ 2r − 3, there exists some universal constant c > 0 such that for any
n ∈ N, there exists some function f ∈ C s [0, 1] such that kf k∞ ≤ 1, kf 0 k∞ ≤ 1, · · · , kf (s) k∞ ≤ 1,
and for delete-1 r-jackknife fˆr :
kEp fˆr (p̂n ) − f (p)k∞ ≥ cnr−1−s .

(37)

Theorem 5. For integer 2r − 2 ≤ s ≤ 2r − 1, there exists some function f ∈ C s [0, 1] such that
kf k∞ ≤ 1, kf 0 k∞ ≤ 1, · · · , kf (s) k∞ ≤ 1, and for delete-1 r-jackknife fˆr ,
lim inf
n→∞

kEp fˆr (p̂n ) − f (p)k∞
> 0.
n−s/2

(38)

Moreover, if s ≥ 2r, then
1
kEp fˆr (p̂n ) − f (p)k∞ & r .
n

(39)

Proof. The first part follows from (35) and Theorem 1. The second part follows from taking f (p)
to be a polynomial of order 2r with leading coefficient one.
Now we compare the performance of the r-jackknife estimator fˆr with and without Condition 1.
Under Condition 1, we know from Theorem 1 that
s

|Ep fˆr (p̂n ) − f (p)| .r,s,L,C n− min{r, 2 }

(40)

for f satisfying condition Ds with parameter L 4 , where the exponent is better than that of Theorem
3. A pictorial illustration is shown in Figure 1.
Remark 3. For general delete-d r-jackknife, the cases of d  n and d = 1 exhibit drastically
different behavior. It remains fertile ground for research to analyze what is the minimum d needed
for the delete-d r-jackknife to achieve the bias performance that is of the same order as those
satisfying Condition 1 for a specific function f .
1.1.3

Specific functions

The last part of results pertaining to the jackknife investigates some specific functions f (p). Here we
take f (p) = −p ln p or pα , 0 < α < 1. Those functions even do not belong to D1 under Condition 2.
However, we show that the jackknife applied to these functions exhibits far better convergence rates
than the worst case analysis in Theorem 4 predicted.
We show that for the r-jackknife when r = 2, no matter whether Condition 1 is satisfied or not,
the bias of the jackknife estimator can be universally controlled.
Theorem 6. Let fˆ2 denote a general 2-jackknife in Definition 1. Then,
1. if f (p) = −p ln p,
kEp fˆ2 − f (p)k .
4

1
.
n

(41)

It follows from the proof of Theorem 1 that the first part of Theorem 1 also applies to functions f satisfying
condition Ds .

9

3
r=1,
r=2,
r=3,
r=4,
r=1,
r=2,
r=3,
r=4,

2

error exponent

1

Good
Good
Good
Good
Bad
Bad
Bad
Bad

0

-1

-2

-3

-4
0

1

2

3

4

5

6

7

8

9

10

smoothness of function

Figure 1: Error exponents of “Good" and “Bad" jackknife estimators. Here “Good” refers to the
r-jackknife satisfying Condition 1, and “Bad” refers to the delete-1 r-jackknife.
2. if f (p) = pα , 0 < α < 1,
1
kEp fˆ2 − f (p)k . α .
n

(42)

Meanwhile, let fˆ2 be either the delete-1 2-jackknife, or a 2-jackknife that satisfies Condition 1.
Then,
1. if f (p) = −p ln p,
1
kEp fˆ2 − f (p)k & .
n

(43)

1
kEp fˆ2 − f (p)k & α .
n

(44)

2. if f (p) = pα , 0 < α < 1,

Remark 4. We conjecture that Theorem 6 holds for any fixed r instead of only r = 2.

1.2

Bootstrap bias correction

The rationale behind bootstrap bias correction is to use the plug-in rule to estimate the bias and
then iterate the process [Hal92]. Concretely, suppose we would like to estimate a function f (θ), and

10

we have an estimator for θ, denoted as θ̂. The estimator θ̂(X1n ) is a function of the observations
i.i.d.
(X1 , X2 , . . . , Xn ), and Xi ∼ Pθ . The bias of the plug-in rule fˆ1 = f (θ̂) is defined as
e1 (θ) = f (θ) − Eθ f (θ̂).

(45)

We would like to correct this bias. The additive bootstrap bias correction does this by using
the plug-in rule e1 (θ̂) to estimate e1 (θ), and then use f (θ̂) + e1 (θ̂) to estimate f (θ), hoping that
this bias corrected estimator has a smaller bias.
It is the place that the Monte Carlo approximation principle takes effect: it allows us to compute
the plug-in estimator e1 (θ̂) without knowing the concrete form of the bias function e1 (θ). Indeed,
we have
e1 (θ̂) = f (θ̂) − Eθ̂ f (θ̂∗ ),

(46)

i.i.d.

where θ̂∗ = θ̂(X1∗ , X2∗ , . . . , Xn∗ ), and the samples Xi∗ ∼ Pθ̂ . To compute Eθ̂ f (θ̂∗ ), it suffices to
draw the n-tuple sample (X1∗ , X2∗ , . . . , Xn∗ ) in total B times under Pθ̂ , and use the empirical average
to replace the expectation, hoping that the law of large number would make the empirical average
close to the expectation Eθ̂ f (θ̂∗ ). This argument also shows that it takes B rounds of sampling to
evaluate e1 (·) at one point.
After doing bootstrap bias correction as introduced above once, we obtain fˆ2 = f (θ̂) + e1 (θ̂).
What about its bias? The bias of this new estimator, denoted as e2 (θ), is


e2 (θ) = f (θ) − Eθ f (θ̂) + Eθ e1 (θ̂)



= e1 (θ) − Eθ e1 (θ̂).

(47)
(48)

Clearly, in order to compute e2 (θ̂), we need to evaluate e1 (·) in total B times, which amounts
to a total computation complexity B 2 .
It motivates the general formula: the bias of the bootstrap bias corrected estimator after m − 1
rounds of correction is related to that after m − 2 rounds via
em (θ) = em−1 (θ) − Eθ em−1 (θ̂).

(49)

Indeed, denoting the estimator after m − 2 rounds of bias correction as fˆm−1 , by definition we know
em−1 (θ) = f (θ)−Eθ fˆm−1 . The bias corrected estimator after m−1 rounds is fˆm = fˆm−1 +em−1 (θ̂),
whose bias is


em (θ) = f (θ) − Eθ fˆm−1 + em−1 (θ̂)



= em−1 (θ) − Eθ em−1 (θ̂).

(50)
(51)

The bias corrected estimator after m − 1 rounds of correction is
fˆm = f (θ̂) +

m−1
X

ei (θ̂).

(52)

i=1

It takes B m−1 order computations to compute fˆm if we view the computation of fˆ2 = f (θ̂)+e1 (θ̂)
takes computational time B. We introduce an linear operator An that maps the function f to the
same function space such that
An [f ](θ) = Eθ f (θ̂).
11

(53)

With the help of the operator An , one may view the bias of fˆm in the following succinct way.
Indeed, since
em (θ) = em−1 (θ) − An [em−1 ](θ)
= (I − An )[em−1 ](θ),

(54)
(55)

we have
m−1
X

Eθ fˆm = An I +

!
i

(I − An )

[f ]

(56)

i=1

= An

m−1
X

!
i

(I − An )

[f ]

(57)

i=0

= (I − (I − An )m )[f ].

(58)

The operator I − (I − An )m is known as the iterated Boolean sum in the approximation theory
literature [Nat83, Sev91]. Indeed, defining the Boolean sum as P ⊕ Q = P + Q − P Q, we have
I − (I − An )m = An ⊕ An ⊕ . . . ⊕ An = ⊕m An ,

(59)

where there are m terms on the right hand side.
Let the bias of the bootstrap bias corrected estimator after m − 1 rounds be denoted as em (p),
where
em (p) = em−1 (p) − Ep em−1 (p̂n ),

(60)

and e1 (p) = f (p) − Ep [f (p̂n )]. Here f ∈ C[0, 1], and n · p̂n ∼ B(n, p). Our first result on bootstrap
bias correction is about the limiting behavior of em (p) as m → ∞. In other words, what happens
when we conduct the bootstrap bias correction infinitely many times?
Theorem 7. Denote the unique polynomial of order n that interpolates the function f (p) at n + 1
points {i/n : 0 ≤ i ≤ n} by Ln [f ]. Then, for any f : [0, 1] 7→ R,
lim

sup |em (p) − (f − Ln [f ])| = 0,

m→∞ p∈[0,1]

(61)

where em (p) is defined in (60).
In other words, the bias function converges uniformly to the approximation error of the Lagrange
interpolation polynomial that interpolates the function f at equidistant points on [0, 1]. This
interpolating polynomial is in general known to exhibit bad approximation properties unless the
function is very smooth. The Bernstein example below shows an extreme case.
Lemma 2. [Nat64, Chap. 2, Sec. 2] [Bernstein’s example] Suppose f (p) = |p − 1/2|, and Ln [f ]
denotes the unique polynomial that interpolates the function f (p) at n + 1 points {i/n : 0 ≤ i ≤ n}.
Then,
lim inf |Ln [f ](p)| = ∞
n→∞

for all p ∈ [0, 1] except for p = 0, 1/2, and 1.

(62)

5

This phenomenon has been generalized to other functions such as |p − 21 |α , α > 0 when α is not an even integer.
See [Gan03] for more details.
5

12

For more discussions on the convergence/divergence behavior of Ln [f ], we refer the readers
to [MM08] for more details. We emphasize that it is a highly challenging question. For example, it
was shown in [LS94] that for any p ∈ [0, 1], we have
lim |Ln [f ](p) − f (p)| = 0,

n→∞

(63)

where f (p) = −p ln p or pα , α > 0, α ∈
/ Z, and Ln [f ] is the Lagrange interpolation polynomial at
equi-distant points. However, to our knowledge it is unknown that whether supp∈[0,1] |Ln [f ](p) −
f (p)| converges to zero as n → ∞ for those specific functions, and if so, what the convergence rate
is.
As Theorem 7 and Lemma 2 show, it may not be a wise idea to iterate the bootstrap bias
correction too many times. It is both computationally prohibitive, and even may deteriorate
statistically along the process. In practice, one usually conducts the bootstrap bias correction
a few times. The next theorem provides performance guarantees for the first few iterations of
bootstrap bias correction.
Theorem 8. Fix the number of iterations m ≥ 0, and 0 < α ≤ 2m. Then the following statements
are true for any f ∈ C[0, 1]. Here em (p) is defined in (60).
1.
√
kem (p)k .m ωϕ2m (f, 1/ n) + kf kn−m .

(64)

kem (p)k .α,m n−α/2 if and only if ωϕ2m (f, t) .α,m tα .

(65)

kem (p)k m n−m if and only if f is an affine function

(66)

2.

3.

4. Suppose there is a constant D < 22m for which
ωϕ2m (f, 2t) ≤ Dωϕ2m (f, t) for t ≤ t0 .

(67)

√
kem (p)k m,D ωϕ2m (f, 1/ n).

(68)

√
kem (p)k  ωϕ2m (f, 1/ n).

(69)

Then,

5. For m = 1,

Theorem 8 has several interesting implications. First of all, it shows that for a few iterations
of the bootstrap bias correction, we have a decent bound on the bias kem (p)k, which is intimately
√
connected with the 2m-th order Ditzian–Totik modulus of smoothness evaluated at 1/ n. This
bound is tight in various senses. The second statement shows that it captures the bias kem (p)k at
least up to the granularity of the exponent in n, and the third statement shows that it is impossible
13

for the bootstrap bias corrected estimator to achieve bias of order lower than n−m except for the
trivial case of affine functions, which have bias zero. The fourth statement shows that as long as
the modulus ωϕ2m (f, t) is not too close to t2m , the DT modulus bound is tight. The fifth statement
shows that when we do not do any bias correction, the DT modulus bound is tight for any function
in C[0, 1].
The following corollary is immediate given (12).
Corollary 2. If f (p) = −p ln p, then,
kem (p)k m

1
m ke1 (p)k,
n

(70)

If f (p) = pα , 0 < α < 1, then
1
m ke1 (p)k,
(71)
nα
which means that the bootstrap bias correction for the first few rounds does not change the order
of bias at all.
We have shown that the bias of fˆm converges to the approximation error of the Lagrange
kem (p)k m

interpolation polynomial at equi-distant points when m → ∞ (Theorem 7). However, we also know
that for the first few iterations of the bootstrap, the bias of fˆm can be well controlled (Theorem 8).
It begs the question: how does kem (p)k evolve as m → ∞?
We study this problem through the example of f (p) = |p − 1/2|, with the sample size n = 20.
Thanks to the special structure of the Binomial functions, we are able to numerically compute
kem (p)k up to m ≈ 8.5 × 105 . It follows from Theorem 7 that
lim kem (p)k = kf − Ln [f ]k,

m→∞

and for n = 20, we numerically evaluated kf − Ln [f ]k to be 47.5945.

14

(72)

Figure 2: The evolution of kem (p)k as a function of m for 1 ≤ m ≤ 8.5 × 105 .

Figure 3: The evolution of kem (p)k as a function of m for 1 ≤ m ≤ 2 × 104 .

15

Figure 4: The Lagrange interpolation points and the Lagrange interpolation polynomial of the
function |p − 1/2| with equi-distant n + 1 points, where n = 20.

Figure 2, 3, and 4 show that the behavior of kem (p)k could be highly irregular: in fact, for the
specific function f (p) = |p − 1/2|, it continues to decrease until m grows slightly above 2 × 103 , and
then keeps on increasing until m exceeds about 1.2 × 104 , then it continues to drop until it hits
about 3 × 104 , then it keeps on increasing again within the range of computations we conduct. It is
also clear that after about 8.5 × 105 bootstrap iterations, which is by no means practical, kem (p)k
is still far from its limit kf − Ln [f ]k, which is about 47.5945 as shown in Figure 4.
Remark 5 (Connections between bootstrap and jackknife). The interested reader must have observed that the bias properties of the bootstrap bias corrected estimator after r − 1 rounds is
exactly the same as that of the r-jackknife estimator satisfying Condition 1. Concretely, their bi√
ases are both dictated by the modulus ωϕ2r (f, 1/ n). It would be interesting to compare the rate
√
ωϕ2r (f, 1/ n) with that of the best polynomial approximation, upon noting that in the binomial
model, the biases of both the jackknife and bootstrap estimators are polynomial approximation
errors of the function f (p) with degree at most n. It follows [DT87, Thm. 7.2.1.] that for best
polynomial approximation with degree n, the approximation error inf P ∈polyn supp∈[0,1] |f (p) − P (p)|
is upper bounded by ωϕk (f, 1/n) for any k < n. We first observe that one achieves a smaller argu√
ment (1/n compared to 1/ n) in this case, but more importantly, there is essentially no restriction
on the modulus order when n is large. It indicates the best polynomial approximation induces a
much better approximation (smaller bias) for estimating f (p), which, unfortunately has been shown
in [Pan03] to fail to achieve the minimax rates in entropy estimation, since the variance explodes
while the bias is very small. The estimators in [VV11, WY16, JVHW17] only choose to conduct
16

best polynomial approximation in certain regimes of f , which reduces the bias by a logarithmic
factor without increasing too much the variance.

1.3

Taylor series bias correction

The Taylor series can only be applied to functions with certain global differentiablity conditions,
which makes it a less versatile method compared to the bootstrap and jackknife. The Taylor series
bias correction method exhibits various forms in the literature, and we discuss two of them in
this section. We call one approach the iterative first order correction, and the other approach
the sample splitting correction. To illustrate the main ideas behind the methods, we still use the
binomial model n · p̂n ∼ B(n, p).
1.3.1

Iterative first order correction

As shown in [LC98, Chapter 6, Section 1, Pg. 436], suppose for certain f , we have
1
Bn (p)
,
Ep f (p̂n ) − f (p) =
+O
n
n2




(73)

where Bn (p) = 12 f 00 (p)nEp (p̂n − p)2 . Then, the Taylor series bias corrected estimator is defined as
Bn (p̂n )
fˆ2 = f (p̂n ) −
.
n

(74)

We can generalize the approach above to conduct bias correction for multiple rounds [Wit87].
However, the correction formula becomes increasingly more complicated as the correction order
becomes higher. We start with the following lemma.
Lemma 3. Suppose function f : [0, 1] 7→ R satisfies condition Ds with parameter L as in Condition 2, where s = 2k is a positive even integer. Then, if n · p̂n ∼ B(n, p), there exist k − 1 linear
operators denoted as Tj [f ](p), 1 ≤ j ≤ k − 1, independent of n, such that
Ep f (p̂n ) − f (p) −

k−1
X
j=1

1
1
Tj [f ](p) .k,L k .
j
n
n

(75)

Here supp∈[0,1] |Tj [f ](p)| .k,L 1. Concretely, Tj [f ](p) is a linear combination of the derivatives of f
of order from j + 1 to 2j where the combination coefficients are polynomials of p with degree no
more than 2j.
Now we describe the Taylor series bias correction algorithm below [Wit87].
Construction 1 (Taylor series bias correction). [Wit87] Define ti (p) iteratively. Set t0 (p) = f (p),
and for i ≥ 1 define
ti (p) = −

i
X

Tj [ti−j ](p).

(76)

j=1

The final bias corrected estimator is
fˆk =

k−1
X
i=0

1
ti (p̂n ).
ni

17

(77)

Construction 1 may be intuitively understood as the iterative generalization of the order one
Taylor series bias correction (74). Indeed, after we conduct the first order bias correction and
obtain
T1 [f ](p̂)
fˆ2 = f (p̂n ) −
n
t1 (p̂n )
= t0 (p̂n ) +
,
n
we apply Lemma 3 to the function t0 +
t0 (p) +

t1
n

and obtain the expansion up to order

(78)
(79)
1
n2

as

t1 (p) T1 [t0 ](p) T2 [t0 ](p) T1 [t1 ](p)
T2 [t0 ](p) T1 [t1 ](p)
+
+
+
= t0 (p) +
+
,
2
2
n
n
n
n
n2
n2

(80)

where we used the definition of t1 = −T1 [t0 ]. It naturally leads to the further correction
t2 (p) = −T2 [t0 ](p) − T1 [t1 ](p).

(81)

One can repeat this process to obtain the formula in Construction 1.
Now we prove that the estimator fˆk in Construction 1 achieves bias of order O(n−k ) if the
original function f satisfies condition Ds with s = 2k. It can be viewed as one concrete example
of [Wit87].
Theorem 9. Suppose f : [0, 1] 7→ R satisfies condition Ds with parameter L, and s = 2k, k ≥
1, k ∈ Z. Then, the estimator in Construction 1 satisfies
1
kEp [fˆk ] − f (p)k .k,L k .
n
1.3.2

(82)

Sample splitting correction

This method was proposed in [HJW16]. It aims at solving one disadvantage of Construction 1,
which is that the bias correction formula for higher orders may not be easy to manipulate since it is
defined through a recursive formula. The sampling splitting correction method provides an explicit
bias correction formula which is easy to analyze with transparent proofs, but the disadvantage it
has is that it only applies to certain statistical models.
The intuition of the sample splitting correction method is the following, which is taken from [HJW16].
Suppose f satisfies condition D2k with parameter L. Instead of doing Taylor expansion of f (p̂n )
near p, we employ Taylor expansion of f (p) near p̂n :
f (p) ≈

2k−1
X
i=0

f (i) (p̂n )
(p − p̂n )i .
i!

(83)

Now, f (i) (p̂n ) is by definition an unbiased estimator for Ep [f (i) (p̂n )]. However, the unknown
p in the right hand side still prevents us from using this estimator explicitly. Fortunately, this
difficulty can be overcome by the standard sample splitting approach: we split samples to obtain
(1)
(2)
independent p̂n and p̂n , both of which follow the same class of distribution (with possibly different

18

parameters) as p̂n . We remark that sample splitting can be employed for divisible distributions,
including multinomial, Poisson and Gaussian models [Nem00]. Now our bias-corrected estimator is
fˆk =

2k−1
X
i=0

(1)

i
f (i) (p̂n ) X
i
(1) i−j
Sj (p̂(2)
n )(−p̂n )
i!
j
j=0

!

(84)

(2)

where Sj (p̂n ) is an unbiased estimator of pj (which usually exists when sample splitting is doable).
Now it is straightforward to show that
E[fˆk ] − f (p) = Ep

"2k−1
X f (i) (p̂(1)
n )
i=0
kf (2k) k

. Ep
.k,L

(2k)!

#

(p −

i!

i
p̂(1)
n )

− f (p)

(85)

2k
(p̂(1)
n − p)

(86)

1
,
nk

(87)

where in the last step we used the property of the binomial distribution in Lemma 15.
The rest of the paper is organized as follows. Section 2 discusses the key proof ingredients of
the results pertaining to jackknife bias correction. The proofs of main results on bootstrap bias
correction are provided in Section 3. Section A reviews the K-functional approach for bias analysis.
Section B collects auxiliary lemmas used throughout this paper. Proofs of the rest of the theorems
and lemmas in the main text are provided in Section C, and the proofs of the auxiliary lemmas are
presented in Section B.

2
2.1

Jackknife bias correction
Theorem 3

We first present the proof of Theorem 3. We explain the roadmap below, and the key lemmas used
in roadmap are proved in Section C.
The first step to analyze the general r-jackknife for functions f satisfying the Condition Ds in
Condition 2 is to use Taylor expansions. It is reflected in Lemma 4.
Lemma 4. Suppose f satisfies Condition 2 for fixed s ≥ 1 with parameter L. Then, for the general
r-jackknife estimator with fixed r ≥ 1 in Definition 1,
|Ep fˆr − f (p)| .r,s,L n−r +
+

Z 1 X
r
p

Z p X
r
0

Ci Ep (p̂ni − t)s−1
dt
+

i=1

Ci Ep (p̂ni − t)s−1
dt.
−

(88)

i=1

Here the coefficients {Ci }1≤i≤r are given in Definition 1.
Lemma 4 shows that it suffices to analyze the behavior of the quantities ri=1 Ci Ep (p̂ni − t)s−1
+
P
s−1
and ri=1 Ci Ep (p̂ni − t)−
. These quantities can be viewed as divided differences (see (34)), and
to analyze the worst case we analyze the following backward difference sequences.
P

19

For t ≥ p, u ≥ 0, s ≥ 0, define
An,u (t) = Ep (p̂n − t)u+

(89)

and consider its s-backward difference defined as
s

∆ An,u (t) ,

s
X

!

k

(−1)

k=0

s
An−k,u (t).
k

(90)

We have
Lemma 5. For s, u ≥ 0, t ≥ p and n ≥ 2s, we have

|∆s An,u (t)| ≤ c1 ·



−(u+s−1) p + n−u pu∧1 ( √1 ∧ 1) · exp(−c nt)

n
2


nt


 −( u +s) u
c2 n(t−p)2
−u u∧1 1

n

2

p2 + n

p

∧ 1) · exp(−

(√

nt



u
u


 n−( 2 +s) (1 − p) 2 + n−u (1 − p)u∧1 ( √ 1

n(1−t)

if p ≤ n1 ,
if

1
n

< p ≤ 21 ,

∧ 1) · exp(− c2 n(t−p)
) if
1−p

1
2

< p ≤ 1 − n1 .

t

)



2

(91)
where the universal constants c1 , c2 > 0 only depend on u, s (not on n or p). Moreover, if t > 1 − n1 ,
we have
|∆s An,u (t)| ≤ c1 (1 − t)u (1 − p)s pn−s .

(92)

Note that in Lemma 5, the case where p > 1− n1 has already been included in the case t > 1− n1 ,
for t ≥ p. Hence, Lemma 5 has completely characterized an upper bound on the dependence of
|∆s An,u (t)| on all n, p and t. By symmetry, we have the following corollary regarding
u
A−
n,u (t) , Ep (p̂n − t)− .

(93)

Corollary 3. For s, u ≥ 0, t ≤ p and n ≥ 2s, we have

|∆s A−
n,u (t)| ≤ c1 ·




1
−(u+s−1)
−u
u∧1

n
(1 − p) + n (1 − p) ( √
∧ 1) · exp(−c2 n(1 − t))


n(1−t)



u

u

n−( 2 +s) (1 − p) 2 + n−u (1 − p)u∧1 ( √ 1
∧ 1) · exp(−

n(1−t)





u
u

c2 n(t−p)2
−u u∧1 √1
 −( 2 +s) 2
n

p +n

p

(

nt

∧ 1) · exp(−

p

)

c2 n(t−p)2
)
1−t

if p ≥ 1 − n1 ,
if

1
2

≤ p ≤ 1 − n1 ,

if

1
n

≤ p < 12 .
(94)

where the universal constants c1 , c2 > 0 only depend on u, s (not on n or p). Moreover, if t <
we have
|∆s An,u (t)| ≤ c1 tu ps (1 − p)n−s .

1
n,

(95)

Furthermore, in most cases we do not need the dependence on p, and Lemma 5 implies the
following corollary.

20

Corollary 4. For s, u ≥ 0, t ≥ p ≥ t0 and n ≥ 2s, we have
s

−( u
+s)
2

exp(−c2 n(t − p) ) + n

0
A−
n,u (t )|

−( u
+s)
2

0

|∆ An,u (t)| ≤ c1 n
s

|∆

≤ c1 n

2

!

c2 n(t − p)2
1
exp(−
·√
)
t
t + n−1

−(u+ 21 )

2

exp(−c2 n(t − p) ) + n

−(u+ 21 )

(96)
!

1
c2 n(t0 − p)2
·√
exp(−
)
1−t
1 − t0 + n−1
(97)

where the universal constants c1 , c2 > 0 only depend on u, s (not on n or p).
Now we can start the proof of Theorem 3.
Proof of Theorem 3. We split into three cases. When s = 0, we use the triangle inequality to
conclude that
|Ep fˆr (p̂n ) − f (p)| =

r
X

Ci Ep f (p̂ni ) − f (p)

(98)

|Ci | + 1)kf k∞

(99)

i=1
r
X

≤(

i=1
r−1

.L n

.

(100)

For 1 ≤ s ≤ 2r, it follows from Lemma 4 that
|Ep fˆr (p̂n ) − f (p)| .r,s,L n−r +
+

Z 1 X
r

Z p X
r
0

p

Ci Ep (p̂ni − t)s−1
dt
+

i=1

Ci Ep (p̂ni − t)s−1
dt.
−

(101)

i=1

For t ≥ p, it follows from Corollary 4 that there exist universal constants c1 , c2 depending on
r, s only such that
c2 n(t−p)2
1
2
t
e−
+ e−c2 n(t−p) )
−1
t+n


|∆u An,s−1 (t)| ≤ c1 ( √
·

n−(

s−1
+u)
2

n−(s− 12 )

if 0 ≤ u ≤ b 2s c,

(102)

if u ≥ d 2s e.

Now define
Bn,r,s (t) = nr−1 An,s (t).

(103)

By the product rule of backward difference we obtain
X

|∆r−1 Bn,r,s (t)| .r,s

|∆i nr−1 | · |∆j An,s (t)|

(104)

0≤i,j≤r−1,i+j≥r−1

X

.r,s

nr−1−i · ( √

0≤i,j≤r−1,i+j≥r−1

c2 n(t−p)2
s−1
1
1
2
t
+ e−c2 n(t−p) )n− min{ 2 +j,s− 2 }
e−
t + n−1

(105)
.r,s ( √

1
e
t + n−1

c n(t−p)2
− 2 t

2

+ e−c2 n(t−p) )n− min{

21

s−1
,s−r+ 21 }
2

.

(106)

As a result of Lemma 11,
r
X

r
X

s−1
=
Ci Ep (p̂ni − t)+

Ci Ani ,s−1 (t)

(107)

i=1

i=1

= |B·,r,s [n1 , · · · , nr ](t)|
1
≤
max |∆r Bm,r,s (t)|
(r − 1)! m∈[n1 ,nr ]
c2 n(t−p)2
s−1
1
1
2
t
e−
.r,s ( √
+ e−c2 n(t−p) )n− min{ 2 ,s−r+ 2 } .
−1
t+n

(108)
(109)
(110)

Using this inequality, finally we arrive at
Z 1 X
r
p

s−1
dt
Ci Ep (p̂ni − t)+

i=1
Z 1

c2 n(t−p)2
s−1
1
1
2
t
e−
+ e−c2 n(t−p) )n− min{ 2 ,s−r+ 2 } dt
−1
t+n
p
!
Z ∞
Z ∞
c nu2
1
1
2
− 2u+p
− min{ s−1
−c
nu
,s−r+
}
2
2
p
e 2 du
du +
e
≤n
u + p + n−1
0
0

.r,s

≤n

(√

− min{ s−1
,s−r+ 12 }
2

Z p
1
0

≤n

− min{ s−1
,s−r+ 12 }
2

1
√
p

√ e
p
Z ∞

−

c2 nu2
2p

du +

Z ∞
√

ne

−

c2 nu
2

Z ∞

−

e

c2 nu2
2p

(112)
!

du

(113)

0

√ Z
du + n

∞

e

−

c2 nu
2

Z ∞

−c2 nu2

e

du +

0

0

e

du +

p

−c2 nu2

(111)

!

du

(114)

0

s

.r,s n− min{ 2 ,s−r+1}

(115)

as desired. The remaining part can be dealt with analogously.
When s ≥ 2r, the desired result follows from applying Lemma 4 with s = 2r.

2.2

Theorem 4

We consider the case where s > 0 and s ≤ 2r − 3. To come up with an example which matches the
upper bound in Theorem 3, we first need to prove a “converse" of Lemma 5. Recall that for t ≥ p,
An,u (t) = Ep (p̂n − t)u+ .

(116)

1
}
Lemma 6. For any 0 ≤ u ≤ 2(s−1), there exists some p0 > 0 such that for any 0 < p < min{p0 , 4s
1
1
and any n ≥ p2 , whenever t ∈ [p, p + √n ] satisfies

1.

k
n−s+1

2.

k
n−s

<t<

<t<

k−p
n−s

k+p
n−s

for some k ∈ N if u < s;

for some k ∈ N if u ≥ s,

we have
1

|∆s An,u (t)| ≥ cn−(u+ 2 )
where c > 0 is a universal constant which only depends on u, s and p.
22

(117)

Now we start the proof of Theorem 4. The basic idea of the proof is to construct functions f
such that Lemma 4 is nearly tight.
Proof of Theorem 4. Pick an arbitrary p > 0 which satisfies Lemma 6, and we define
g(t) = sign

r
X

!

t)s−1
+

Ci Ep (p̂ni −

· 1(t ≥ p).

(118)

i=1

Note that g is not continuous, but we can find some h ∈ C[0, 1] such that kg − hk1 ≤ n−2r . Now
choose any f with f (s) = h , we know that f ∈ C s [0, 1], and the norm conditions are satisfied under
proper scaling.
It follows from Lemma 4 that
|Ep fˆr (p̂n ) − f (p)|  O(n

−r

r
X

Z 1

h(t)

)+
p

r
X

h(t)
0

!

Ci Ep (p̂ni −
r
X

Z 1

g(t)
0

= O(n−r ) +

Z 1 X
r

= o(nr−1−s ) +

dt

(119)

r−1−s

!

Ci Ep (p̂ni − t)s−1
dt + O(kg − hk1 ) ·
+

r
X

|Ci |

(120)

i=1

Ci Ep (p̂ni − t)s−1
dt
+

(121)

i=1

Z 1 X
r
p

Z

)+

i=1
r
X

G i=1
√1 ]
n

t)s−1
−

i=1

p

where G ⊂ [p, p +
to see

dt

i=1

= O(n−r ) +

≥ o(n

Ci Ep (p̂ni −

i=1

Z p

+

!

t)s−1
+

Ci Ani ,s−1 (t) dt

(122)

Ci Ani ,s−1 (t) dt

(123)

is the set of all “good" t’s which satisfy the condition of Lemma 6. It’s easy
1

m(G)  n− 2

(124)

where m(·) denotes the Lebesgue measure. Moreover, by our choice of delete-1 jackknife, for t ∈ G
we have
r
X

Ci Ani ,s−1 (t) = ∆r−1 (nr−1 An,s−1 (t))

(125)

i=1

& nr−1 |∆r−1 An,s−1 (t)|
X

−

|∆i nr−1 | · |∆j An,s−1 (t)|

(126)

1≤i≤r−1,0≤j≤r−1,i+j≥r−1
1

X

& nr−1−(s− 2 ) −

nr−1−i−min{

s−1
+j,s− 12 }
2

(127)

1≤i≤r−1,0≤j≤r−1,i+j≥r−1
1

& nr−s− 2

(128)

23

where we have used Lemma 5, Lemma 6 and the assumption that 0 ≤ s − 1 ≤ 2(r − 2). As a result,
we conclude that
|Ep fˆr (p̂n ) − f (p)| & o(nr−1−s ) +

Z

r
X

G i=1

Ci Ani ,s−1 (t) dt
1

& o(nr−1−s ) + m(G) · nr−s− 2
&n

r−s−1

(129)
(130)
(131)

as desired.

2.3

Theorem 6

The following lemma characterizes the difference Ep f (p̂n ) − Ep f (p̂n−1 ) for certain functions.
Lemma 7. [ST77] Suppose f (p) = −p ln p, p ∈ [0, 1]. Then,
1 − pn − (1 − p)n
.
n(n − 1)

(132)

(1 − α)(1 − pn − (1 − p)n )
.
n(n − 1)α

(133)

0 ≤ Ep f (p̂n ) − Ep f (p̂n−1 ) ≤
Suppose f (p) = pα , p ∈ [0, 1], 0 < α < 1. Then,
0 ≤ Ep f (p̂n ) − Ep f (p̂n−1 ) ≤

The next lemma characterizes the lower bound for the bias of the jackknife estimate fˆ2 .
Lemma 8. Suppose fˆ2 is the delete-1 2-jackknife. Then,
1. for f (p) = −p ln p,
1
kEp fˆ2 − f (p)k & .
n

(134)

1
kEp fˆ2 − f (p)k & α .
n

(135)

2. for f (p) = pα , 0 < α < 1,

Suppose fˆ2 is a 2-jackknife that satisfies Condition 1. Then,
1. for f (p) = −p ln p,
1
kEp fˆ2 − f (p)k & .
n

(136)

1
.
nα

(137)

2. for f (p) = pα , 0 < α < 1,
kEp fˆ2 − f (p)k &
Now we can start the proof of Theorem 6.
24

Proof of Theorem 6. The lower bounds follow from Lemma 8. Now we prove the upper bounds.
For a general 2-jackknife and general function f , we have
Ep [fˆ2 ] − f (p) =

n2
n1
(Ep [f (p̂n1 )] − f (p)) +
(Ep [f (p̂n2 )] − f (p)) .
n1 − n2
n2 − n1

(138)

Define Hn = Ep [f (p̂n )] − f (p). Then,
n2 Hn2 − n1 Hn1
Ep [fˆ2 ] − f (p) =
n2 − n1
n1
(Hn2 − Hn1 ) .
= Hn2 +
n2 − n1

(139)
(140)

For any f ∈ C[0, 1], we have limn→∞ Hn = 0, which implies
Hn2 = Hn2 − H∞
=

∞
X

(141)

(Hj − Hj+1 )

(142)

j=n2

and
Hn2 − Hn1 =

n2
X

(Hj − Hj−1 )

(143)

j=n1 +1

It follows from Lemma 8 that for f (p) = −p ln p, 0 ≤ Hj − Hj−1 .
kEp [fˆ2 ] − f (p)k .



∞
X
1
j=n2

1
.
j2

n

Hence,


2
X
n1
1

+
·
2
j
n2 − n1
j2
j=n +1

(144)

1

1
n1
.
+
n2 n2 − n1
1
.
n2
1
. ,
n



1
1
−
n1 n2



(145)
(146)
(147)

where in the last step we used Definition 1.
The case of f (p) = pα , 0 < α < 1 can be proved analogously.

3
3.1

Bootstrap bias correction
Theorem 7

Define the Bernstein operator Bn : C[0, 1] 7→ C[0, 1] as
Bn [f ](p) =

n
X
i=0

i
n

 

f

25

!

n i
p (1 − p)n−i .
i

(148)

Theorem 7 can be proved using the eigenstructure of the Bernstein operator [Sev95]. We give
a concrete proof as follows.
It was shown in [CW00] that the Bernstein operator Bn [f ] admits a clean eigenstructure. Con(n)
cretely, it has n + 1 linearly independent eigenfunctions pk , 0 ≤ k ≤ n, which are polynomials
(n)
n!
with order k, with k simple zeros on [0, 1]. The corresponding eigenvalues are λk = n1k (n−k)!
.
The Bernstein operator is also degree reducing in the sense that it maps a k-degree polynomial to
another polynomial with degree no more than k.
Decomposing f (p) as f (p) = Ln [f ](p) + g(p). It follows the definition of Ln [f ] that g(i/n) =
0, 0 ≤ i ≤ n. Hence, Bn [g] ≡ 0.
Since Ln [f ](p) is a polynomial with degree no more than n, it admits a unique expansion
Ln [f ](p) =

n
X

(n)

ak p k .

(149)

k=0

Applying I − Bn on the decomposition of f , we have
(I − Bn )[f ] = f − Bn [f ]
n
X

=
=

k=0
n
X

(150)

(n)

ak pk + g −

n
X

(n) (n)

ak λk pk

(151)

k=0
(n)

(n)

ak (1 − λk )pk + g

(152)

(n)

(153)

k=0

It follows by induction that
em (p) =

n
X

(n)

ak (1 − λk )m pk + g

k=0

We have
sup |em (p) − g| ≤
p

n
X

(n)

smallest

(n)
λk ,



= 1· 1−

(n)

1
n





... 1 −

k−1
n



(154)

p

k=0

→0
Note that λk

(n)

(1 − λk )m |ak | sup |pk |
as m → ∞.

(155)
(n)

, k ≥ 2, and λk

= 1 when k = 0, 1. Hence, the

which is the slowest to vanish corresponds to k = n. Since
√
n!
2πn
(n)
,
λn = n ≈
n
en
n

(156)

(n)

e
rounds of iteration to make (1 − λn )m vanish, which is a prohibitively large
it takes m & √
n
number in practice.

4

Acknowledgment

We are grateful to Yihong Wu for pointing out the the connection of Theorem 10 with f -divergence
inequalities [SV16].
26

A

The K-functional approach to bias analysis

We introduce the r-th modulus of smoothness of a function f : [0, 1] 7→ R as
ω r (f, t) = sup k∆rh f k,

(157)

0<h≤t

where ∆rh f is defined in (10). The r-th Ditzian–Totik modulus of smoothness of a function f :
[0, 1] 7→ R is defined in (11).
Intuitively, the smoother the function is, the smaller is its moduli of smoothness. For f ∈ C[0, 1],
we define the K-functional Kr (f, tr ) as follows:
Kr (f, tr ) = inf {kf − gk + tr kg (r) k : g (r−1) ∈ A.C.loc },
g

(158)

and the K-functional Kr,ϕ (f, tr ) as
Kr,ϕ (f, tr ) = inf {kf − gk + tr kϕr g (r) k : g (r−1) ∈ A.C.loc },
g

(159)

where g (r−1) ∈ A.C.loc means that g is r − 1 times differentiable and g (r−1) is absolutely continuous
in every closed finite interval [c, d] ⊂ (0, 1).
The remarkable fact is, the K-functionals are equivalent to the corresponding moduli of smoothness for any function f ∈ C[0, 1]. Concretely, we have the following lemma:
Lemma 9. [DL93, Chap. 6, Thm. 2.4, Thm. 6.2] [DT87, Thm. 2.1.1.] There exist constants
c1 > 0, c2 > 0 which depend only on r such that for all f ∈ C[0, 1],
c1 ω r (f, t) ≤ Kr (f, tr ) ≤ c2 ω r (f, t)
c1 ωϕr (f, t)

r

≤ Kr,ϕ (f, t ) ≤

c2 ωϕr (f, t)

for all t > 0
for all t ≤ t0 ,

(160)
(161)

where t0 > 0 is a constant that only depends on r.
We emphasize that the K-functionals and moduli of smoothness introduced here are tailored for
the interval [0, 1] and the supremum norm, which can be generalized to general finite intervals and
infinite intervals, and Lp norms. The corresponding equivalence results also hold in those settings.
We refer the interested readers to [DL93, Chap. 6] and [DT87, Chap. 2] for details. For other
use of K-functionals in statistics and machine learning, we refer the readers to the theory of Besov
spaces as interpolation spaces [HKPT12] and distribution testing [BCG16].
Now we illustrate the K-functional approach to bias analysis, which is well known in the approximation theory literature, see, e.g. [Tot88]. Suppose X is a random variable taking values in
[0, 1], and we would like to bound the quantity |E[f (X)] − f (E[X])| for any f ∈ C[0, 1]. Clearly,
f may not be differentiable, so we introduce another function g ∈ C[0, 1] such that g (1) ∈ A.C.loc .
We proceed as follows:
|E[f (X)] − f (E[X])| = |E [f (X) − g(X) + g(X) − g(EX) + g(EX) − f (EX)] |
≤ 2kf − gk + |E[g(X) − g(EX)]|
1
≤ 2kf − gk + kg 00 kVar(X)
2


= 2 kf − gk + t2 kg 00 k ,
27

(162)
(163)
(164)
(165)

where t2 =

Var(X)
.
4

Since g (1) ∈ A.C.loc is arbitrary, we know
n

|E[f (X)] − f (E[X])| ≤ 2 inf kf − gk + t2 kg 00 k

o

(166)

g

= 2K2 (f, t2 )


Var(X)
= 2K2 f,
4
!
p
Var(X)
≤ 2c2 ω 2 f,
,
2

(167)
(168)
(169)

where the constant c2 is introduced in Lemma 9.
It was shown in [DL93, Chap. 2, Sec. 9, Example 1] that if f (x) = x ln x, x ∈ [0, 1], then
2
ω (f, t) ≤ 2(ln 2)t. Hence, we have shown that for any random variable X ∈ [0, 1],
|E[X ln X] − E[X] ln(E[X])| .

q

Var(X).

(170)

Specializing to the case where X = p̂n , where n · p̂n ∼ B(n, p), we have proved that for f (p) =
−p ln p, we have
s

|E[f (p̂n )] − p ln p| .

p(1 − p)
.
n

(171)

q

The upper bound p(1−p)
is a pointwise bound that becomes smaller when p is close to 0 or
n
1. When p lies in the middle of the interval [0, 1], say p ≈ 21 , the bound is of scale √1n . We now
show that using the K-functional Kr,ϕ instead of Kr results in a better uniform bound in this case,
which is of order n1 . 6
For any f ∈ C[0, 1], n · p̂n ∼ B(n, p), and any g ∈ C[0, 1] such that g (1) ∈ A.C.loc , we have
|Ep [f (p̂n )] − f (p)| ≤ |Ep [f (p̂n ) − g(p̂n ) + g(p̂n ) − g(p) + g(p) − f (p)|

(172)

= 2kf − gk + |Ep g(p̂n ) − g(p)|

(173)

"

= 2kf − gk + Ep g 0 (p)(p̂n − p) +
= 2kf − gk + Ep
≤ 2kf − gk + Ep
= 2kf − gk + Ep

"Z

Z p̂n

#

(p̂n − t)g 00 (t)dt

(174)

p

#

p̂n

00

(p̂n − t)g (t)dt

(175)

p̂n − t
· t(1 − t)g 00 (t) dt
t(1 − t)

(176)

p

Z p̂n
p

Z p̂n
|p̂n − p|
p

p(1 − p)

≤ 2kf − gk + kϕ2 g 00 kEp
1
≤ 2kf − gk + kϕ2 g 00 k ,
n
6

|t(1 − t)g 00 (t)|dt

(p̂n − p)2
p(1 − p)

(177)
(178)
(179)

One remarkable fact is that, the K-functional approach with Kr,ϕ in bias analysis provides the tight norm bound
for any f ∈ C[0, 1] under the binomial model [Tot94].

28

p

where ϕ(t) = t(1 − t), and we used the elementary inequality that
between p and p̂n . Taking the infimum over all g, we have

|p̂n −t|
t(1−t)

≤

|p̂n −p|
p(1−p)

for any t

1
)
2n

(180)

1
. ωϕ2 (f, √ ).
2n

(181)

|Ep [f (p̂n )] − f (p)| ≤ 2Kr,ϕ (f,

It follows from [JVHW17] that for f (p) = −p ln p, ωϕ2 (f, t)  t2 , which implies that
|Ep [p̂n ln p̂n ] − p ln p| .

1
.
n

(182)

The functional Ent(X) , E[X ln X]−E[X] ln(E[X]), which is also called entropy, plays a crucial
role in the theory of concentration inequalities. Concretely, the Herbst argument [BLM13] shows
2
that if Ent(eλf (X) ) ≤ λ2 E[eλf (X) ], we have sub-Gaussian type concentration P (f (X) − E[f (X)] ≥ t) ≤
2
e−t /2 . Due to the significance of the functional Ent(X), we now present a theorem providing upper and lower bounds of Ent(X). The key idea in the following proof is to relate the Ent(X)
functional to the KL divergence, whose functional inequalities have been well studied in the literature. Conceivably, they are stronger bounds than those obtained using the general K-functional
approach (Lemma 17 in Section B).
Theorem 10. Suppose X is a non-negative random variable. Denote Ent(X) = E[X ln X] −
E[X] ln(E[X]). Then,
q
Var(X)
Ent(X) ≤ E[X] ln 1 +
≤
Var(X)
(E[X])2

q
√ 
√
Ent(X) ≥ 2 E[X] − E[X]E[ X] ≥ Var( X)




1
X
Ent(X) ≥ E[X] E
−1
2
E[X]


(183)
(184)

2

.

(185)

√
Remark 6. It was shown in [LO00] that Ent(X) ≥ Var( X). Theorem 10 strengthens [LO00].
Proof. Without loss of generality we assume E[X] > 0. Then, we have
X
Ent(X) = E X ln
E[X]


X
X
= E[X] · E
ln
E[X] E[X]




(186)
(187)
(188)

Denote the distribution of X as Q, and introduce a new probability measure P via the Radon–
Nikodym derivative
dP
X
=
,
dQ
E[X]

29

(189)

we have
dP
dP
ln
dQ dQ
= EQ [X] · D(P, Q),




(190)

Ent(X) = EQ [X]EQ

(191)

where D(P, Q) is the KL divergence between P and Q.
Applying Lemma 18 in Section B, we have


Ent(X) ≤ EQ [X] · ln EQ

X
EQ [X]

!2 

(192)



Var(X)
= E[X] · ln 1 +
,
(E[X])2




(193)

where in the last step we used the fact that Var(X) = E[X 2 ] − (E[X])2 . Using the fact that
√
< 1, we have
supx≥0 ln(1+x)
x
Ent(X) ≤

q

Var(X).

(194)

Now we prove the lower bounds. Applying the Hellinger distance part of Lemma 18 in Section B,
we have
Ent(X) ≥ EQ [X] · H 2 (P, Q)
s

(195)
!2

X
−1
EQ [X]

q
√ 
≥ 2 EQ [X] − EQ [X]EQ [ X]
√
≥ EQ [X] − (EQ [ X])2
√
= Var( X).
√
√
p
Here in the last inequality we used the fact that E[X] + (E[ X])2 − 2 E[X]E[ X] ≥ 0.
Applying the total variation distance part of Lemma 18 in Section B, we have
= EQ [X] · EQ

Ent(X) ≥ EQ [X] · 2V 2 (P, Q)
X
1
= EQ [X] · EQ
−1
2
EQ [X]

B

(196)
(197)
(198)
(199)

(200)
!2

.

(201)

Auxiliary lemmas

Lemma 10 (Mean value theorem for divided difference). Suppose the function f is n − 1 times
differentiable in the interval determined by the smallest and the largest of the xi ’s, we have
f [x1 , x2 , . . . , xn ] =

30

f (n−1) (ξ)
,
(n − 1)!

(202)

where ξ is in the open interval (mini xi , maxi xi ), and f [x1 , x2 , . . . , xn ] is the divided difference in
Definition 2.
The following lemma which is closely related to the mean value theorem for divided differences
in the continuous case.
Lemma 11. For integers x0 < x1 < · · · < xr and any function f defined on Z, the following holds:
|f [x0 , · · · , xr ]| ≤

1
max |∆r f (x)|.
r! x∈[x0 ,xr ]

(203)

Here ∆r f (x) denotes the r-th order backward difference of f , which is defined as
r
X

r

∆ f (x) ,

!

k

(−1)

k=0

r
f (x − k).
k

(204)

Lemma 12. Suppose one observes X ∼ B(n, p). Then, the r-jackknife estimator with n1 =
n − 1, n2 = n, r = 2 in estimating f (p) in (14) can be represented as
fˆ2 = nf



X
n



n−1
(n − X)f
n


−



X
n−1





+ Xf

X −1
n−1



,

(205)

where one conveniently sets f (x) = 0 if x < 0.
Lemma 13. Let r ≥ 2. Then, for the coefficients given in (15), we have the following.
1. If ρ = 0, then
r
X
Ci
i=1

nρi

= 1.

(206)

= 0.

(207)

2. If 1 ≤ ρ ≤ r − 1, then
r
X
Ci
i=1

nρi

3. If ρ ≥ r, then
r
X
Ci

nρ
i=1 i

≤

r−2
Y

(r − 1 − ρ − s)

s=0

≤

1
1
(r − 1)! nρ1

(ρ − 1)r−1 1
.
(r − 1)! nρ1

(208)
(209)

Define Tn,s (p) = ns Ep (p̂n − p)s , n = 1, 2, . . . , s = 0, 1, . . .. We have Tn,0 = 1, Tn,1 = 0. Upon
observing the recurrence relation




0
Tn,s+1 (x) = x(1 − x) Tn,s
(x) + nsTn,s−1 (x) ,

one obtains the following result.
31

(210)

Lemma 14. [DL93, Chapter 10, Theorem 1.1.] For a fixed s = 0, 1, . . ., Tn,s (p) is a polynomial in
p of degree ≤ s, and in n of degree bs/2c. Moreover, for ϕ2 = p(1 − p), we have
Tn,2s (p) =

s
X

aj,s (ϕ2 )nj ϕ2j

(211)

j=1

Tn,2s+1 (p) = (1 − 2p)

s
X

bj,s (ϕ2 )nj ϕ2j ,

(212)

j=1

where aj,s , bj,s are polynomials of degree ≤ s − j, with coefficients independent of n.
Lemma 15. The central moments of p̂n where n · p̂n ∼ B(n, p) satisfy the following:
bs/2c

ns Ep (p̂n − p)s =

X

hj,s (p)nj ,

(213)

j=1

where
(4es)s
.
j!

khj,s (p)k∞ ≤

(214)

Lemma 16 (Chernoff bound). [AV79] Let X1 , X2 , . . . , Xn be independent {0, 1} valued random
P
variables with P(Xi = 1) = pi . Denote X = ni=1 Xi , µ = E[X]. Then,
P(X ≤ (1 − β)µ) ≤ e−β

2 µ/2

0<β≤1


β2 µ

e− 2+β ≤ e− βµ
3
P(X ≥ (1 + β)µ) ≤
2

 −β µ

e

(215)

β>1

(216)

0<β≤1

3

Lemma 17. [ST77] For any continuous function f : R 7→ R and any random variable X taking
values in R, we have
p

|E[f (X)] − f (E[X])| ≤ 3 · ω

2

f,

!

Var(X)
.
2

(217)

If f is only defined on an interval [a, b] that is a strict subset of R, the result holdswith the constant 3
P
replaced by 15. Here ω r (f, t) , sup0<h≤t k∆rh f k, where ∆rh f (x) = rk=0 (−1)k kr f (x+r(h/2)−kh),
and ∆rh f (x) = 0 if x + rh/2 or x − rh/2 is not inside the domain of f .
Lemma 18. [Tsy08, Section 2.4] Suppose P, Q are both probability measures, and P  Q.
Introduce the following divergence functionals:
1. Total variation distance:
1
dP
V (P, Q) = EQ
−1 ;
2
dQ

(218)

2. Hellinger distance:


s

H(P, Q) = EQ

32

dP
−1
dQ

!2 1/2


;

(219)

3. Kullback–Leibler (KL) divergence:


D(P, Q) = EQ

dP
dP
;
ln
dQ dQ


(220)

4. χ2 divergence:
2
dP
χ (P, Q) = EQ
−1
dQ


dP 2
= EQ
− 1.
dQ



2



(221)
(222)

Then, we have the following upper and lower bounds on the KL divergence:


D(P, Q) ≤ ln 1 + χ2 (P, Q)



(223)

D(P, Q) ≥ 2V 2 (P, Q)

(224)

2

D(P, Q) ≥ H (P, Q).

C
C.1

(225)

Proofs of main theorems and lemmas
Proof of Theorem 1

Recognizing Ep fˆr as linear combination of operators, the first and second parts of Theorem 1 follow
from [DT87, Theorem 9.3.2.], the third part follows from [DT87, Corollary 9.3.8.], and the last part
follows from [Tot94].

C.2

Proof of Theorem 2
n

m



o

Define f ∈ C(0, 1] to be the piecewise linear interpolation function at nodes m−1 , 1+(−1)
, m ∈ N+ .
2
Clearly f (m−1 ) = 1 when m is even, f (m−1 ) = 0 when m is odd, and kf k∞ ≤ 1. We set f (0) = 0.
We have
|Ep fˆr − f (p)| =

r
X

Ci Ep f (p̂n+i−r ) − f (p)

(226)

i=1

≥

X

X

Ci Ep f (p̂n+i−r ) −

n+i−r is even

≥

X

Ci Ep f (p̂n+i−r ) − |f (p)|

(227)

n+i−r is odd

X

|Ci |Ep f (p̂n+i−r ) −

n+i−r is even

|Ci |Ep f (p̂n+i−r ) − 1

(228)

n+i−r is odd

where in the last step we have used the fact that C1 , · · · , Cr have alternating signs, and f ≥ 0.
When n + i − r is even and p = n−1 ,
1
Ep f (p̂n+i−r ) ≥ f
· P(B(n + i − r, p) = 1)
n+i−r
= (n + i − r)p (1 − p)n+i−r−1
1
≥ (1 − o(1)).
e




33

(229)
(230)
(231)

When n + i − r is odd and p = n−1 , noting that f (0) = f



1
n+i−r



= 0, we have

Ep f (p̂n+i−r ) ≤ kf k∞ · P(B(n + i − r, p) ≥ 2)


2
(1 + o(1)).
≤ 1−
e
Since ri=1 Ci = 1, we have
these together, we arrive at
P

n+i−r is odd |Ci |

P

|Ep fˆr − f (p)| &

= (1+o(1))

P

(233)

n+i−r is even |Ci |

2
1
− 1−
|Ci |
e
e
n+i−r is even


X

(232)





 nr−1 . Combining



− o(1)

(234)

& nr−1 .

(235)

which completes the proof of the first claim.
As for the second claim, it suffices to replace the function f on interval [0, 1/n] by the linear
n
interpolation function interpolating f (0) = 0 and f (1/n) = 1+(−1)
and keep other parts of the
2
function intact. Consequently, after this modification f ∈ C[0, 1].
Now we prove the variance part.
Construct
interpolation function at the following nodes:
 f ∈ C[0,
 1] to be a piecewise

linear

1
2
1
2
f (0) = 0, f n = f n−1 = 1, f n−1 = f n = −1, f (1) = 0.
It follows from straightforward algebra and Lemma 12 that

fˆ2 =



0




X=0

2n − 2 + n−1




−2n + 5 − 4

n

X=1.

(236)

X=2

It follows from the definition of variance that


Varp (fˆ2 ) = Ep fˆ2 − Ep fˆ2


= inf Ep fˆ2 − a

2

(237)

2

(238)

a



≥ inf P(B(n, p) = 1)(2n − 2 + n−1 − a)2 + P(B(n, p) = 2)(−2n + 5 − 4/n − a)2
a



= inf np(1 − p)n−1 (2n − 2 + n−1 − a)2 +
a



(239)

n(n − 1) 2
p (1 − p)n−2 (−2n + 5 − 4/n − a)2
2
(240)


Setting p = 1/n, we have
1
1
Varp (fˆ2 ) ≥
1−
2
n


n−1





inf (2n − 2 + n−1 − a)2 + (−2n + 5 − 4/n − a)2 .
a

(241)

The infimum is achieved when
(2n − 2 + n−1 ) + (−2n + 5 − 4/n)
2


3
1
=
1−
.
2
n

a=

34

(242)
(243)

Hence,
1 n−1
1 3
1
1
1−
· 2 · 2n − 2 + −
1−
kVarp (fˆ2 )k ≥
2
n
n 2
n

n−1
1
≥ 1−
n2
n
n2
≥
.
e






where we have used n ≥ 4 and 1 −

C.3

1
n

n−1





2

(244)
(245)
(246)

≥ e−1 .

Proof of Lemma 4

Since f satisfies condition Ds , it admits the Taylor expansion:
f (x) = f (p) +

s−1
X

f (u) (p)
(x − p)u + Rs (x; p)
u!
u=1

(247)

Applying the r-jackknife estimator on it, we have
Ep fˆr = f (p) +
= f (p) +

r
r
X
f (u) (p) X
Ci Ep Rs (p̂ni ; p)
Ci Ep (p̂ni − p)u +
u! i=1
u=1
i=1
s−1
X

(248)

s−1
X

r
r
X
f (u) (p) X
Ci Ep Rs (p̂ni ; p),
Ci Ep (p̂ni − p)u +
u! i=1
u=r+1
i=1

Pb

where in the last step we have used Lemma 13 and Lemma 14. By convention
P
Denote Eu = ri=1 Ci Ep (p̂ni − p)u , u ≥ r + 1, it follows from Lemma 15 that
Eu =

r
X

bu/2c

Ci

i=1

X

hj,u (p)

j=1

1
nu−j
i

bu/2c

X

=

hj,u (p)

r
X
Ci
i=1

j=1

nu−j
i

.

a

(249)

= 0 if a > b.

(250)

Note that
r
X
Ci
i=1

nu−j
i

6= 0

(251)

if and only if u − j ≥ r, and when that is the case, we have
r
X
Ci
i=1

nu−j

≤ (u − j − 1)r−1

1
nu−j
1

≤

ur−1
nu−j
1

≤

ur−1
nr1

(252)

Since r is fixed, it follows from (252), Lemma 15 and condition Ds with parameter L that
s−1
X

f (u) (p)
1
Eu .r,s,L r .
u!
n
u=r+1
35

(253)

It follows from the integral form of Taylor remainder that
Rs (x; p) =
=

1
(s − 1)!

Z x

(x − t)s−1 f (s) (t)dt

p

R1
 1
(s−1)! 0 |x
 1 R 1 |x
(s−1)! 0

(254)

− t|s−1 f (s) (t)1t∈[min{x,p},max{x,p}] (−1)1x<p dt

s is odd

− t|s−1 f (s) (t)1t∈[min{x,p},max{x,p}] dt

s is even

(255)

When s is even, we have
Ep |p̂ni − t|s−1 1t∈[min{p̂ni ,p},max{p̂ni ,p}] =


Ep (p̂n − t)s−1
+
i

t≥p

t)s−1
−

t<p

E (p̂ −
p ni

(256)

where (x)+ = max{x, 0}, (x)− = max{−x, 0}.
When s is odd,
Ep |p̂ni − t|s−1 1t∈[min{p̂ni ,p},max{p̂ni ,p}] (−1)1p̂ni <p =


Ep (p̂n − t)s−1
+
i

t≥p

−E (p̂ − t)s−1
p ni
−

t<p

(257)

Hence,


r
X

1 
Ci Ep Rs (p̂ni ; p) =
(s − 1)!
i=1
Z 1

+

Z p

f
0

f (s) (t)

p

.r,s,L

(s)

(t)

r
X

!

Ci Ep (p̂ni −

s
t)s−1
− (−1)

dt

i=1
r
X

!



Ci Ep (p̂ni − t)s−1
dt
+

(258)

i=1

Z p X
r
0

Ci Ep (p̂ni − t)s−1
dt +
−

Z 1 X
r

i=1

p

Ci Ep (p̂ni − t)s−1
dt,
+

(259)

i=1

where we have used the assumption that kf (s) k ≤ L.

C.4

Proof of Lemma 5

First we recall the following additive Chernoff bound: for np̂n ∼ B(n, p) and t ≥ p, we have
P(p̂n > t) ≤ exp(−nD(tkp))

(260)

where D(tkp) denotes the KL divergence between the binary distributions (t, 1 − t) and (p, 1 − p).
Note that
D(tkp) ≥

1
d2 D(ukp)
min
2 ξ∈[p,t]
du2

(t − p)2
ξ∈[p,t] 2ξ(1 − ξ)
(t − p)2
≥ min
2ξ
ξ∈[p,t]
2
(t − p)
=
2t
= min

36

· (t − p)2

(261)

u=ξ

(262)
(263)
(264)

we arrive at the following inequality:
P(p̂n > t) ≤ exp(−nD(tkp)) ≤ exp(−

n(t − p)2
).
2t

(265)

Now we prove the lemma. Let X1 , · · · , Xn be i.i.d Bern(p) random variables, and consider the
following coupling between p̂n−s , · · · , p̂n : for k = 0, · · · , s, define
p̂n−k =

X
1 n−k
Xi .
n − k i=1

(266)

In other words, we have
p̂n−k = p̂n−s +

X
1 s−1
(Xn−i − p̂n−s ).
n − k i=k

(267)

Now define gu,t (x) = (x − t)u+ , by Taylor expansion we have
s

∆ An,u (t) = Ep

s
X

!

s
gu,t (p̂n−k )
k

k

(−1)

k=0

= Ep

s
X

!

(268)

(j)

X gu,t (p̂n−s )
s u−1
(p̂n−k − p̂n−s )j
j!
k
j=0

k

(−1)

k=0



(u)

gu,t (ξk )
+
(p̂n−k − p̂n−s )u 
u!
= Ep

s
X

!

(269)

(j)

u
gu,t (p̂n−s )
s X
(p̂n−k − p̂n−s )j
j!
k
j=0

k

(−1)

k=0
(u)



(u)

gu,t (ξk ) − gu,t (p̂n−s )
+
(p̂n−k − p̂n−s )u 
u!
= Ep

(j)
u
s
X
gu,t (p̂n−s ) X
j=0

j!
+ Ep

s
X

(j)
u
X
gu,t (p̂n−s )
j=0

j!

(−1)

k

! (u)

k=0

≡ Ep

X
s
1 s−1
Ep [(
(Xn−i − p̂n−s ))j |X n−s ]
k
n − k i=k
!

k=0
k

(−1)

(270)

(u)

s gu,t (ξk ) − gu,t (p̂n−s )
(p̂n−k − p̂n−s )u
k
u!

Aj + Ep Bu .

(271)

(272)
(u)

Note that gu,t (x) is in fact not u-times differentiable at x = t, but with the convention that gu,t (t)
can stand for any number in [0, u!], the previous formula remains valid.
C.4.1

Non-remainder term Aj

Further define
aj (t) , Ep (Xn − t)j = p(1 − t)j + (1 − p)(−t)j
37

(273)

we have a0 (t) = 1, a1 (t) = p − t, and
Aj =

s−1
X

!

s
1
k (n − k)j

(−1)k

k=0

j
i1 · · · is−k

X
i1 +···+is−k =j

! s−k
Y

Denote by Ij the set of all multi-indices i = (i1 , · · · , it(i) ) with t(i) ≤ s,
for any i ∈ Ij , the coefficient of

Qt(i)

l=1 ail (p̂n−s )

ail (p̂n−s ).

Pt(i)

l=1 il

= j and il ≥ 1, then

in Aj is

s−1
X
j
s
s−k
1
P0
(−1)k
j
i1 · · · it(i) k=0
k (n − k) d1 · · · dt0 s − k − tl0 =1 dl0

!

bi =
=

=
=

j
i1 · · · it(i)

!

j
i1 · · · it(i)

!

j
i1 · · · it(i)

!

!

t(i)
d1 · · · dt0

! s−1
X

t(i)
d1 · · · dt0

!

t(i)
d1 · · · dt0

!

!

s−k
s
1
j
t(i)
k (n − k)

k

(−1)

k=0

! s−t(i)
X

s
t(i)

max

!

(275)

!

(276)

!

k

(−1)

k=0

s − t(i)
1
(n − k)j
k

(277)

!

s
· ∆s−t(i) n−j
t(i)

(278)

where d1 , · · · , dt0 is the nonzero histograms of i = (i1 , · · · , it(i) ) with
value theorem of backward differences, we have
|∆s−t(i) n−j | ≤

(274)

l=1

x∈[n−s+t(i),n]

Pt0

l0 =1 dl0

= t(i). By the mean

ds−t(i) −j
(x ) .s n−(j+s−t(i))
dxs−t(i)

(279)

and thus
|bi | ≤ c(i)n−(j+s−t(i))

(280)

where the constant c(i) does not depend on n or p.
Now for any j = 0, 1, · · · , u, we have




(j)
t(i)
X Y
gu,t (p̂n−s )
b
·
ail (p̂n−s )
Ep
Aj  Ep (p̂n−s − t)u−j
i
+
j!
i∈I
l=1

(281)

j



≤

X

t(i)
Y
u−j

c(i)n−(j+s−t(i)) · Ep (p̂n−s − t)+

i∈Ij



|ail (p̂n−s )| .

(282)

l=1

For any i ∈ Ij , denote by v(i) the number of ones in i = (i1 , · · · , it ), using a1 (t) = p − t and
|aj (t)| ≤ p + t yields


t(i)
Y
u−j

Ep (p̂n−s − t)+


h

i

v(i)
|ail (p̂n−s )| ≤ Ep (p̂n−s − t)u−j
|p̂n−s + p|t(i)−v(i) .
+ |p̂n−s − p|

l=1

38

(283)

We distinguish into two cases. If np ≥ 1, by Holder’s inequality E[XY Z]3 ≤ E[|X|3 ]E[|Y |3 ]E[|Z|3 ]
we obtain


Ep (p̂n−s −

t)u−j
+

t(i)
Y


h

v(i)
|p̂n−s + p|t(i)−v(i)
|ail (p̂n−s )| ≤ Ep (p̂n−s − t)u−j
+ |p̂n−s − p|

i

(284)

l=1

≤ Ep |p̂n−s − p|u−j+v(i) 1(p̂n−s ≥ t) · |p̂n−s + p|t(i)−v(i)
h



≤ Ep |p̂n−s − p|3(u−j+v(i))

1 
3

Ep |p̂n−s + p|3(t(i)−v(i))

i

(285)

1 q
3

· 3 P(p̂n−s > t)
(286)

p)2

p u−j+v(i) t(i)−v(i)
c2 n(t −
.u,s ( ) 2
)
·p
· exp(−
n
t
u−j+v(i) u−j+2t(i)−v(i)
c2 n(t − p)2
2
= n− 2 p
· exp(−
)
t

(287)
(288)

where in the last step we have used (265), and the fact that when np ≥ 1, we have [HJW16]
p k
Ep |p̂n − p|k .k ( ) 2
n
Ep |p̂n + p|k .k pk .

(289)
(290)

As a result, in this case we conclude that

Ep

(j)
X
u−j+v(i) u−j+2t(i)−v(i)
gu,t (p̂n−s )
c2 n(t − p)2
2
Aj .u,s
c(i)n−(j+s−t(i)) · n− 2 p
exp(−
)
j!
t
i∈I

(291)

j

=

X

u

u

c(i)n−( 2 +s) p 2 · (np)−

j+v(i)−2t(i)
2

exp(−

i∈Ij

Note that j =

Pt(i)

k=1 ik

c2 n(t − p)2
).
t

(292)

≥ v(i) + 2(t(i) − v(i)), we have j + v(i) ≥ 2t(i), and thus by np ≥ 1,

(j)
X
gu,t (p̂n−s )
u
u
c2 n(t − p)2
Ep
Aj .u,s
)
c(i)n−( 2 +s) p 2 · exp(−
j!
t
i∈I

(293)

j

u

u

.u,s n−( 2 +s) p 2 · exp(−

c2 n(t − p)2
)
t

(294)

where we have used that both |Ij | and c(i) do not depend on n or p in the last step.
If np < 1, we first show that
Ep [p̂kn 1(p̂n > t)] .k

p
nk−1

exp(−

c2 n(t − p)2
).
t

(295)

In fact, the MGF of p̂n gives
λ

Ep [eλp̂n ] = (pe n + 1 − p)n .
Differentiating w.r.t λ for k times, for λ > 0 we arrive at
39

(296)

Ep [p̂kn eλp̂n ] =

i
dk h λ
(pe n + 1 − p)n
k
dλ

≤ Ck

k
X

λ

(297)

λ

(pe n )j nj−k (pe n + 1 − p)n−j

(298)

j=1



λ

λ

pe n (pe n + 1 − p)n−1 
1+
.k
nk−1

!k−1 

λ

npe n

(299)



λ
n

pe + 1 − p

λ

kλ

pe n (pe n + 1 − p)n
.k
,
nk−1

(300)

where Ck is a universal constant depending on k only, and in the last step we have used np < 1.
As a result, by Markov’s inequality we have for any λ > 0,
λ

kλ

Ep [p̂kn
Specifically, when t >

1(p̂n > t)] ≤

2k
n,

Ep [p̂kn eλ(p̂n −t) ]

.k e

−λt

pe n (pe n + 1 − p)n
.
·
nk−1

(301)

choosing λ = n ln (1−p)t
(2−t)p yields

Ep [p̂kn

1(p̂n > t)] .k

p



nk−1
p



(2 − t)p
(1 − p)t

(2 − t)p
(1 − p)t

nt−k

1−p
1 − 2t

·

 nt

1−p
1 − 2t

2

!n

(302)

!n

·
nk−1
t
p
≤ k−1 exp(−nD( kp))
n
2
p
c2 n(t − p)2
≤ k−1 exp(−
)
n
t
≤

as desired. When p < t ≤

2k
n,

we have

c2 n(t−p)2
t

(303)
(304)
(305)

= O(1), and (295) follows from

Ep [p̂kn 1(p̂n < t)] ≤ Ep p̂kn .k

p
nk−1

.

(306)

Now based on (295), we have


Ep (p̂n−s −

t)u−j
+

t(i)
Y


h

v(i)
|ail (p̂n−s )| ≤ Ep (p̂n−s − t)u−j
|p̂n−s + p|t(i)−v(i)
+ |p̂n−s − p|

i

(307)

l=1

≤ Ep |p̂n−s − p|u−j+v(i) 1(p̂n−s ≥ t) · |p̂n−s + p|t(i)−v(i)
h

h

u−j+t(i)

.u,s Ep (p̂n−s


.u,s
.u,s

p

+ pu−j+t(i) )1(p̂n > t)

i



+ pu−j+t(i) · exp(−

nu−j+t(i)−1
p
c2 n(t − p)2
exp(−
).
t
nu−j+t(i)−1
40

c2 n(t − p)2
)
t

i

(308)
(309)
(310)
(311)

As a result, in this case we have
(j)
X
gu,t (p̂n−s )
p
c2 n(t − p)2
c(i)n−(j+s−t(i)) · u−j+t(i)−1 exp(−
Ep
Aj .u,s
)
j!
t
n
i∈I

(312)

j

=

X

c(i)n−(u+s−1) p · exp(−

i∈Ij

.u,s n−(u+s−1) p · exp(−

c2 n(t − p)2
)
t

c2 n(t − p)2
).
t

(313)
(314)

Moreover, when 21 < p ≤ 1 − n1 , we can use the symmetry n(1 − p̂n ) ∼ B(n, 1 − p) and |aj (t)| ≤
(1 − p) + (1 − t), and then adapt the proof of the first case to conclude that
(j)

Ep

gu,t (p̂n−s )
u
u
c2 n(t − p)2
Aj .u,s n−( 2 +s) (1 − p) 2 · exp(−
).
j!
1−p

(315)

In summary, for the non-remainder terms we have

2

n−(u+s−1) p · exp(− c2 n(t−p)
)

t


2
u
u

if p < n1
(j)
gu,t (p̂n−s )
Ep
Aj .u,s n−( 2 +s) p 2 · exp(− c2 n(t−p)
)
if n1 ≤ p ≤ 12
t

j!


2
u
 −( u2 +s)
) if 21 < p ≤ 1 − n1 .
n
(1 − p) 2 · exp(− c2 n(t−p)
1−p
C.4.2

(316)

The remainder term Bu
(u)

(u)

(u)

By our convention on gu,t (·) we observe that gu,t (ξk ) − gu,t (p̂n−s ) is non-zero only if
(ξk − t)(p̂n−s − t) ≤ 0.

(317)

However, since min{p̂n−k , p̂n−s } ≤ ξk ≤ max{p̂n−k , p̂n−s }, the previous inequality implies that the
“path" consisting of p̂n−s , · · · , p̂n under our coupling “walks across" t. Let’s call it “good path".
Moreover, note that
|p̂n−k − p̂n−s | ≤

s
,
n−s

k = 0, · · · , s

(318)

under our coupling, for a good path we must have
|p̂n−s − t| ≤

s
.
n−s

(319)

1
Since p̂n−s must be an integral multiple of n−s
, we conclude that the number of good paths is O(1).
Let’s call p̂n−k → p̂n−k+1 a “right step" if p̂n−k < p̂n−k+1 or p̂n−k = p̂n−k+1 = 1, and a “left step"
if p̂n−k > p̂n−k+1 or p̂n−k = p̂n−k+1 = 0.
First we consider the case where p ≤ 12 , and consider any good path L. The idea is that, each
good path L gives rise to a realization of Bu , and Ep Bu is the expectation averages over all good
paths. Hence, to evaluate Ep Bu , it suffices to compute the value of Bu given L, and the probability

41

of the path L. Denote by r, l the number of right and left steps in L, and by q the starting point
of L, it is easy to see that the probability of this path is
P(L) = pr (1 − p)l · P(B(n − s, p) = (n − s)q).

(320)

We first take a look at the quantity P(B(n, p) = nq) for any q with |q − t| = O(n−1 ). By
Stirling’s approximation
n! =

√

2πn

 n
n

e

(1 + o(1)),

(321)

we have
!

P(B(n, p) = nq) =
.
.
≤

n nq
p (1 − p)n−nq
nq
√
2πn( ne )n
nq
n−nq
√
nq nq p
n−nq n−nq p (1 − p)
2πnq( e ) · 2π(n − nq)( e )
1
p
· e−nD(qkp)
nq(1 − q)
n(q − p)2+
1
p
· exp(−
)
2q
nq(1 − q)

(322)
(323)
(324)
(325)

where the last step is given by (265). Moreover, for q > 1 − n1 , (265) gives a better bound
P(B(n, p) = nq) ≤ exp(−

n(q − p)2
).
2q

(326)

Combining them together, we conclude that
n(q − p)2+
1
)
P(B(n, p) = nq) . √ exp(−
nq
4q

(327)

Now we show that if q = t+O(n−1 ), we can replace q by t without loss in the previous inequality.
In fact, if nq ≥ 1, it is easy to verify that
n(q − p)2+
1
1
n(t − p)2
P(B(n, p) = nq) . √ exp(−
) . ( √ ∧ 1) exp(−
)
nq
4q
4t
nt

(328)

and if nq < 1, we use the trivial bound
1
n(t − p)2
).
P(B(n, p) = nq) ≤ 1 . ( √ ∧ 1) exp(−
4t
nt

(329)

As a result, for all good paths with starting point q we conclude that
1
n(t − p)2
P(B(n, p) = nq) . ( √ ∧ 1) exp(−
)
4t
nt

42

(330)

Now we evaluate the quantity Bu (L) given L. In fact, it is easy to see
|Bu (L)| .u


n−u

if r > 0

( p )u

if r = 0.

n

(331)

As a result,
p
|Bu (L)| · P(L) .u n−u · p + ( )u · P(B(n, p) = nq)
n
1
c2 n(t − p)2
.u n−u pu∧1 · ( √ ∧ 1) exp(−
)
t
nt




Finally, there are only O(1) good paths, and for p ≤
|Ep Bu | ≤

X
L

1
2

c2 n(t − p)2
1
).
|Bu (L)| · P(L) .u n−u pu∧1 · ( √ ∧ 1) exp(−
t
nt
1
2


n−u (1 −

(√

1
n(1−t)

(334)

< p ≤ 1 − n1 , and we conclude


2

n−u pu∧1 · ( √1 ∧ 1) exp(− c2 n(t−p)
)
t
nt
u∧1
p)
·

(333)

we arrive at

The previous approach can also be applied to the case where
that
|Ep Bu | .u

(332)

if p ≤
2

) if
∧ 1) exp(− c2 n(t−p)
1−p

1
2

1
2

< p ≤ 1 − n1 .

(335)

Finally, when t > 1 − n1 , it’s easy to see
An,u (t) = (1 − t)u · P(p̂n = 1) = (1 − t)u pn

(336)

|∆s An,u (t)| = (1 − t)u |∆s pn | .u,s (1 − t)u pn−s (1 − p)s .

(337)

and

Now the combination of (316), (335) and (337) completes the proof of Lemma 5.

C.5

Proof of Lemma 6

First note that by assumption we have
k+1
1 + O(p)
−t=
n−j
n−j

(338)

for any j = 0, · · · , s in both cases, and when u < s we have
k
p
−t& .
n−s
n

(339)

Adopt the same coupling as in the proof of Lemma 5, and write
|∆s An,u (t)| = |Ep ∆s (p̂n − t)u+ (1(p̂n−s ∈ A) + 1(p̂n−s ∈
/ A)|
s

≥ |Ep ∆ (p̂n −

t)u+

1(p̂n−s ∈ A)| − |Ep ∆ (p̂n −
s

43

t)u+

(340)

1(p̂n−s ∈/ A)|.

(341)

where
k−s
k
.
A,
,
n−s n−s




(342)
u

By the proof of Lemma 5, the non-remainder terms in the Taylor expansion is at most O(n−( 2 +s) ) =
1
o(n−(u+ 2 ) ), and by our coupling the remainder term is non-zero only if p̂n−s ∈ A, we conclude that
|Ep ∆s (p̂n − t)u+ 1(p̂n−s ∈
/ A)| = o(n−(u+ 2 ) ).
1

(343)

Now we deal with the first term. It’s easy to verify that for any x ∈ A, we have
1
1
1
|x − p| = |t − p| + O( ) ≤ √ + O( ).
n
n
n

(344)

As a result, by the Stirling approximation formula in the proof of Lemma 5, we conclude that for
m
any n−s
∈ A with m ∈ N,
q , P(p̂n−s =

m
1
k
) = (1 + o(1)) · P(p̂n−s =
)& √ .
n−s
n−s
n

(345)

In other words, p̂n−s is almost uniformly distributed restricted to A with mass at least Θ( √1n ) on
each point. Moreover, for j = 0, 1, · · · , s and i = 1, · · · , s − j, it follows from the coupling that
k+i
, p̂n−s ∈ A)
n−j
s
X
k+i
k−m
k−m
P(p̂n−j =
=
|p̂n−s =
)P(p̂n−s =
)
n
−
j
n
−
s
n−s
m=0

P(p̂n−j =

=

s
X
m=0

(346)

!

s − j m+i
p
(1 − p)s−j−m−i · q(1 + o(1))
m+i

44

(347)

As a result, when u < s, we have
|Ep ∆s (p̂n − t)u+ 1(p̂n−s ∈ A)|
= Ep

s
X

!

s
(p̂n−j − t)u+ 1(p̂n−s ∈ A)
j

j

(−1)

j=0

s−j

(348)

s
XX
p
k+i
s k+i
= (−1) ( )u +
− t)u+ · P(p̂n−j =
, p̂n−s ∈ A)
(−1)j
(
n
n
−
j
n
−j
j
i=1 j=0

!

s

s−j X
s s−i−j
X
X
p
s
= q(1 + o(1)) (−1) ( )u +
(−1)j
n
j
i=1 j=0 m=0

!

s

(349)

!

s − j m+i
k+i
− t)u
p
(1 − p)s−j−m−i (
n−j
m+i
(350)

s X
s−i
X

!

p
s
= q(1 + o(1)) (−1)s ( )u +
pm+i
n
m
+
i
i=1 m=0
·

s−i−m
X

!

(−1)

j

j=0

s−m−i
k+i
− t)u
(1 − p)s−m−i−j (
n−j
j

(351)

s−i
s X
p u X
s
= q(1 + o(1)) (−1) ( ) +
pm+i (i + O(p))u
m
+
i
n
i=1 m=0

!

s

·

s−i−m
X

!

(−1)

j=0

j

s−m−i
1 u
(1 − p)s−m−i−j (
)
j
n−j

(352)

s X
s−i
s
(1 − p)s−m−i−x
p u X
pm+i (i + O(p))u ∆s−i−m
= q(1 + o(1)) (−1) ( ) +
.
m+i
n
(n − x)u
i=1 m=0

!

s

(353)

By the product rule of differentiation we know that
∆s−i−m

(−p)s−i−m (1 + O(p))
(1 − p)s−m−i−x
=
· (1 + o(1)).
(n − x)u
nu

(354)

Plugging into the previous expression, we arrive at
|Ep ∆s (p̂n − t)u+ 1(p̂n−s ∈ A)|
s X
s−i
X
q(1 + o(1))(1 + O(p))
s
s
u
=
(−1)
Θ(p
)
+
pm+i iu (−p)s−i−m
nu
m
+
i
i=1 m=0

!

s X
s−i
X
q(1 + o(1))(1 + O(p))
s
s
u
s
=
(−1)
Θ(p
)
+
p
(−1)m+i iu
nu
m
+
i
i=1 m=0
q
u
& u · p (1 + O(p))
n
1
 n−(u+ 2 ) · pu (1 + O(p))

(355)

!

(356)
(357)
(358)

where we have used u < s. Hence, in this case by choosing p0 small enough we arrive at the desired
result.
45

When u ≥ s, similarly we have
|Ep ∆s (p̂n − t)u+ 1(p̂n−s ∈ A)|
s X
s−i
s
q(1 + o(1))(1 + O(p)) s X
p
(−1)m+i iu
=
nu
m
+
i
i=1 m=0

!

ps (1 + O(p))



1

nu+ 2
n

u+ 21

r
s X
iu
r i=1

!

r

(−1)

r=0

ps (1 + O(p))

=

·

s
X

· ∆s

(359)

r
X

(360)

iu .

(361)

i=1

Since ri=1 iu is a polynomial of r with degree u + 1 > s, its s-backward difference is not zero, and
thus the desired result also follows by choosing p0 small enough.
P

C.6

Proof of Lemma 8

We first prove the lower bound for the delete-1 jackknife. It suffices to fix p = nc , where c > 0 is a
positive constant, and prove




(362)





(363)

lim n Ep fˆ2 − f (p) 6= 0

n→∞

when f (p) = −p ln p, and
lim nα Ep fˆ2 − f (p) 6= 0

n→∞

for f (p) = pα , 0 < α < 1.
It follows from Lemma 12 that it suffices to analyze the expectation of the following quantity:


gn (X) = nf

X
n



n−1
(n − X)f
n


−



X
n−1





+ Xf

X −1
n−1



c
.
n

 

−f

(364)

As n → ∞, the measure µn = B(n, p) converges weakly to µ = Poi(c).
We will show that limn→∞ nEµn gn (X) 6= 0 when f (p) = −p ln p and limn→∞ nα Eµn gn (X) 6= 0
when f (p) = pα .
For f (p) = −p ln p,
X
n
n − 1 (n − X)X n − 1 n − 1 X(X − 1)
n−1
c n
ln
−
ln
−
ln
− ln
n
X
n
n−1
X
n
n−1
X −1 n c
(365)


n
X(n − X) n − 1 X(X − 1)
n−1
c n
= Eµn n · X ln
−
ln
−
ln
− ln
(366)
X
n
X
n
X −1 n c


X(n − X)
X(X − 1)
c n
= Eµn n · X ln n −
ln(n − 1) −
ln(n − 1) − ln
(367)
n
n
n c


1
X(n − X)
1
X(X − 1)
1
+ Eµn n · X ln
−
ln
−
ln
(368)
X
n
X
n
X −1






1
1
1
= (c − cn) ln 1 −
+ c ln c + Eµn X 2 ln
− X(X − 1) ln
(369)
n
X
X −1
= An + Bn .
(370)


Eµn n · gn (X) = Eµn n · n

46





1
Since limn→∞ An = c + c ln c, limc→0+ c−2 (c + c ln c) = ∞, and c−2 Eµ X 2 ln X1 − X(X − 1) ln X−1
has a finite limit at c = 0+ , we know there exists some c > 0 such that

lim Eµn n · gn (X) 6= 0.



(371)

n→∞

For f (p) = pα , 0 < α < 1, we have
α
n−1
n−1
c α
X
X −1 α
Eµn n · gn (X) = n
−
−
−
(372)
(n − X)
X
n
n−1
n
n−1
n


α

n−1
= Eµn nX α −
(X α (n − X) + X(X − 1)α ) − cα
(373)
n



 
 



1 α
n − 1 1−α
= Eµn nX α 1 − 1 −
− cα +
Eµn X α+1 − X(X − 1)α .
n
n
(374)
α

X
n
n

 

α

α









  

Hence,




lim Eµn nα · gn (X) = Eµ αX α + X α+1 − X(X − 1)α − cα .

(375)

n→∞

Noting that c−1 Eµ αX α + X α+1 − X(X − 1)α has a finite limit at c = 0 but cα−1 does not, we
know there exists some c > 0 such that


lim Eµn nα · gn (X) 6= 0

(376)

n→∞

when f (p) = pα , 0 < α < 1.
For a 2-jackknife that satisfies Condition 1, the lower bound is given by Theorem 1 and (12).

C.7

Proof of Theorem 8

The first three statements follow from [GZ94]. The last statement follows from [Tot94]. Now we
work to prove the fourth statement.
It follows from [DT87, Inequality 9.3.5., 9.3.7.] that for f ∈ C[0, 1], we have kϕ2m (Bk [f ])(2m) k ≤
m
(2m) ∈ C[0, 1], we have kϕ2m (B [f ])(2m) k ≤ Ckϕ2m f (2m) k. Here
Ck kf k,
k
p and for f such that f
ϕ(x) = x(1 − x).
It follows from the definition of the K-functional K2m,ϕ (f, 1/nm ) that
K2m,ϕ (f, 1/nm ) ≤ kf − ⊕m Bk [f ]k + n−m kϕ2m (⊕m Bk [f ])(2m) k

(377)

Noting that ⊕m Bk [f ] is nothing but linear combinations of the powers of Bk up to degree m,
we can apply the estimates on kϕ2m (Bk [f ])(2m) k to kϕ2m (⊕m Bk [f ])(2m) k. For any g ∈ A.C.loc , we
have
kϕ2m (⊕m Bk [f ])(2m) k ≤ kϕ2m (⊕m Bk [f − g])(2m) k + kϕ2m (⊕m Bk [g])(2m) k
m

2m (2m)

≤ Ck kf − gk + Ckϕ

g

k.

(378)
(379)

Hence,
n

−m

2m

kϕ

m

(2m)

(⊕ Bk [f ])

 m 
k

k ≤ C inf

n

g

 m

=C

k
n

47



kf − gk + k −m kϕ2m g (2m) k

K2m,ϕ (f, k −m ).

(380)
(381)

We have showed that
m

m

K2m,ϕ (f, 1/n ) ≤ kf − ⊕ Bk [f ]k + C

 m
k

n

K2m,ϕ (f, k −m ).

(382)

Now we utilize the assumption that ωϕ2m (f, 2t) ≤ Dωϕ2m (f, t). We have
√
D−q ωϕ2m (f, 1/ k) ≤ ωϕ2m (f, 2−q k −1/2 )

(383)

= ωϕ2m (f, (22q k)−1/2 )

(384)

≤ M1 K2m,ϕ (f, 1/(22q(m) k m )),

(385)

where in the last step we have used the equivalence between K-functional and the Ditzian–Totik
modulus.
Setting n = 22q k and applying (382), we have
√
√
D−q ωϕ2m (f, 1/ k) ≤ M1 kf − ⊕m Bk [f ]k + M1 2−2qm ωϕ2m (f, 1/ k).
(386)
We now choose q so that D−q > 2M1 2−2qm , which is possible since D−1 > 2−2m , and obtain
√
kf − ⊕m Bk [f ]k ≥ 2−2qm ωϕ2m (f, 1/ k).
(387)
The proof is complete.

C.8

Proof of Lemma 3

It follows from [Hur76, Theorem 1] that
Ep f (p̂n ) − f (p) −

2k−1
X
j=1

f (j) (p)
1
Ep (p̂n − p)j .k,L k .
j!
n

(388)

It follows from Lemma 14 and 15 that for any j ≥ 1 integer there exist polynomials hm,j (p) with
degree no more than j, and coefficients independent of n such that
bj/2c

Ep (p̂n − p)j =

X
m=1

hm,j (p)

1
nj−m

.

(389)

Define
Tj [f ](p) =

2k−1
X
i=1

f (i) (p)
hi−j,i (p)1 (i − bi/2c ≤ j ≤ i − 1) .
i!

(390)

It is clear that Tj [f ](p) depends on f only through the derivatives of f of order from j + 1 to 2j.
Concretely, Tj [f ](p) is a linear combination of the derivatives of f of order from j + 1 to 2j where
the combination coefficients are polynomials of p with degree no more than 2j.

48

C.9

Proof of Theorem 9

Proof. We first show, through induction, that each ti , 0 ≤ i ≤ k − 1 satisfies condition D2(k−i) with
parameter .k L. Indeed, it is true for i = 0. Assuming that it is true for i = m, 1 ≤ m ≤ k − 2, we
now show that it is true for i = m + 1. We have
tm+1 (p) = −

m+1
X

Tj [tm+1−j ](p).

(391)

j=1

Since Tj [f ] involves the derivatives of f up to order 2j (Lemma 3), for each j-th term Tj [tm+1−j ](p),
1 ≤ j ≤ m + 1, it involves the derivatives of f up to order
2(m + 1 − j) + 2j = 2(m + 1),

(392)

which implies that tm+1 satisfies the condition D2k−2(m+1) with parameter .k L.
Now we apply Lemma 3 to each term in the formula of fˆk . For the i-th term, 0 ≤ i ≤ k − 1, we
have


Ep

k−i−1
X
1
1
1
1
t
(p̂
)
=
t
(p)
+
Tj [ti ](p) + O
i n
i
i
i
j+i
n
n
n
nk
j=1







k−1
X 1
1
1
= i ti (p) +
Tm−i [ti ](p) + O
m
n
n
nk
m=i+1



(393)


.

(394)

.

(395)

Sum over 0 ≤ i ≤ k − 1, we have
k−1
X





k−1
X 1
1
1
ˆ

Ep [fk ] =
t
(p)
+
Tm−i [ti ](p) + O
i
i
m
n
n
nk
i=0
m=i+1





It suffices to show that
k−1
X





k−1
X 1
1
 ti (p) +
Tm−i [ti ](p) = f (p).
i
n
nm
i=0
m=i+1

(396)

We have
k−1
X
i=0

k−1
X 1
1
t
(p)
=
f
(p)
+
ti (p),
i
ni
ni
i=1



(397)

and
k−1
X 1 m−1
X
1
T
[t
](p)
=
Tm−i [ti ](p)
m−i
i
m
m
n
n
m=1
i=0 m=i+1
i=0

k−1
X

k−1
X

=−

k−1
X

1
tm (p),
nm
m=1

where in the last step we used the definition of ti (p). The proof is now complete.
49

(398)

(399)

D

Proofs of auxiliary lemmas

D.1

Proof of Lemma 11

Let p(x) be the Lagrangian interpolating polynomial of f at points x0 , · · · , xr , and define g(x) =
f (x) − p(x). It is easy to see that g(x) has at least (r + 1) zeros x0 , · · · , xr . Since
x1
X

0 = g(x1 ) − g(x0 ) =

∆g(x)

(400)

x=x0 +1

there must be some y0 ∈ (x0 , x1 ] such that ∆g(y0 ) ≤ 0. Similarly, there exists some y1 ∈ (x1 , x2 ]
such that ∆g(y1 ) ≥ 0, and y2 ∈ (x2 , x3 ] such that ∆g(y2 ) ≤ 0, so on and so forth. Next observe
that
y1
X

0 ≤ ∆g(y1 ) − ∆g(y0 ) =

∆2 g(y)

(401)

y=y0 +1

there must exist some z0 ∈ (y0 , y1 ] such that ∆2 g(z0 ) ≥ 0. Similarly, there exists some z1 ∈ (y1 , y2 ]
such that ∆2 g(z1 ) ≤ 0, and z2 ∈ (y2 , y3 ] such that ∆2 g(z2 ) ≥ 0, so on and so forth. Repeating this
process, there must be some x ∈ [x0 , xr ] such that (−1)r ∆r g(x) ≥ 0. Note that p(x) is a degree-r
polynomial with leading coefficient f [x0 , · · · , xr ], we conclude that
0 ≤ (−1)r ∆r g(x)
r

(402)

r

= (−1) ∆ (f (x) − p(x))
r

r

= (−1) (∆ f (x) − r!f [x0 , · · · , xr ]).

(403)
(404)

Similarly, we can also show that there exists x0 ∈ [x0 , xr ] such that
0 ≤ (−1)r+1 (∆r f (x0 ) − r!f [x0 , · · · , xr ]).

(405)

Combining these two inequalities completes the proof.

D.2

Proof of Lemma 13

The key idea is to connect the problem of solving the matrix equations (16) to the notion of divided
difference in approximation theory.
For ρ ≥ 0, ρ ∈ Z,
r
X
Ci
i=1

nρi

=
=

r
X
1 Y
i=1
r
X

nρi

ni
n
− nj
j6=i i

nr−1−ρ
i

i=1
r−1−ρ

=x

1
n − nj
j6=i i
Y

[n1 , n2 , . . . , nr ],

(406)
(407)
(408)

where f [x1 , x2 , . . . , xr ] denotes the divided difference in Definition 2. The lemma is proved using
the mean value theorem (Lemma 10) of the divided difference for function xr−1−ρ .
50

D.3

Proof of Lemma 15

The first part follows from Lemma 14. Regarding the second part, the moment generating function
of p̂n − p is given by
n



E[exp(z(p̂n − p))] = e−zp 1 + p(ez/n − 1)

.

(409)

Written as formal power series of z, the previous identity becomes
∞
X
E(p̂n − p)s s
z =

∞
X
(−p)i i
z

s=0

i=0

s!

i!

! n
X

k=0

!

n k
p
k

!k 
∞
X
1 z l 
.
( )
l=1

l! n

(410)

Hence, by comparing the coefficient of nj−s z s at both sides, we obtain


j

s−i
tk,j−i k
hj,s (p) X (−p)i  X
=
p
s!
i!
k!
i=0
a
k=j−i

k
Y
1

X

1 +···+ak =s−i,a1 ,··· ,ak ≥1 l=1

al !




(411)

where tk,r is the coefficient of xr in x(x − 1) · · · (x − k + 1). It’s easy to see
|tk,r | ≤ k

k
r

k−r

!

≤

kk
.
r!

(412)

Moreover, it’s easy to see when k ≤ s − i, we have
k
Y
1

X

a1 +···+ak =s−i,a1 ,··· ,ak ≥1 l=1

al !

X

≤

k
Y
1

a1 +···+ak =s−i l=1

X

≤

k+i
Y

a1 +···+ak+i =s l=1

al !
1
(k + i)s
=
al !
s!

(413)

(414)

and this quantity is zero when k > s − i.
Then, applying k! ≥

 k
k
e

yields

|hj,s (p)| ≤

j
s−i
X
1 X
ek (k + i)s
i=0

≤

j
X
i=0

i! k=j−i (j − i)!
ses ss
i!(j − i)!

2j
j!
s(2es)s
≤
j!
(4es)s
≤
j!
= s(es)s

51

(415)

(416)
(417)
(418)
(419)

D.4

Proof of Lemma 17

We first prove the statement when the domain of f is the whole real line. We introduce the first
and second Stekolv functions fh (x), fhh (x) as follows:
fh (x) = f ∗ Kh

(420)

fh (x) = fh ∗ Kh = f ∗ Kh ∗ Kh ,

(421)

where Kh = h1 1(x ∈ [−h/2, h/2]) is the box kernel, and the operation ∗ denotes convolution.
The Steklov functions have the following nice properties [Akh56, Chap. V, Sec. 83]:
1 h/2
(f (x) − f (x + t))dt
(422)
h −h/2
 



1
h
h
0
fh (x) =
f x+
−f x−
(423)
h
2
2
Z
Z
1 h/2 h/2
f (x) − fhh (x) = 2
[4f (x) − f (x + s + t) − f (x + s − t) − f (x − s + t) − f (x − s − t)]dsdt
h 0
0
(424)
1
00
fhh
(x) = 2 (f (x + h) + f (x − h) − 2f (x)) .
(425)
h
f (x) − fh (x) =

Z

Hence, we have
|f (x) − fhh (x)| ≤

1
h2

Z h/2 Z h/2
0

[|2f (x) − f (x + s + t) − f (x − s − t)| + |2f (x) − f (x + s − t) − f (x − s + t)|]dsdt

0

(426)
≤

Z
Z
1 h/2 h/2

h2 0
0
1 2
= ω (f, h),
2

[2ω 2 (f, h)]dsdt

(427)
(428)

and
00
kfhh
(x)k ≤

1 2
ω (f, h).
h2

(429)

We use
|E[f (X)] − f (E[X])| ≤ |E[f (X) − fhh (X) + fhh (X) − fhh (E[X]) + fhh (E[X]) − f (E[X])]| (430)
≤ 2kf − fhh k + |E[fhh (X)] − fhh (E[X])|
1 00
≤ 2kf − fhh k + kfhh
kVar(X)
2
1
≤ ω 2 (f, h) + 2 ω 2 (f, h)Var(X)
2h
= 3 · ω 2 (f, h),

(431)
(432)
(433)
(434)

√
Var(X)
where h =
.
2
Now we argue that when the domain of f is an interval [a, b] that is a strict subset of R, we can
replace the constant 3 by 15. Indeed, as argued in [Tim14, Sec. 3.5.71, pg. 121], for any continuous
52

(a)
function f ∈ [a, b], one can extend φ(x) = f (x) − f (b)−f
(x − a) − f (a) to the whole real line while
b−a
ensuring the second order modulus of the extension is upper bounded by five times the ω 2 (f, t) of
the original function f . Indeed, one achieves this by extending φ so as to be odd with respect to
the ends of the [a, b] and then periodically with period 2(b − a) on the whole real line.

References
[AGW71]

JE Adams, HL Gray, and TA Watkins. An asymptotic characterization of bias reduction
by jackknifing. The Annals of Mathematical Statistics, pages 1606–1612, 1971.

[Akh56]

Naum Il’ich Akhiezer. Theory of approximation. New York, 1956.

[AS04]

Noga Alon and Joel H Spencer. The probabilistic method. John Wiley & Sons, 2004.

[AV79]

Dana Angluin and Leslie G Valiant. Fast probabilistic algorithms for Hamiltonian
circuits and matchings. Journal of Computer and system Sciences, 18(2):155–193, 1979.

[BCG16]

Eric Blais, Clément L Canonne, and Tom Gur. Alice and bob show distribution testing
lower bounds. 2016.

[BLM13]

Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities:
A nonasymptotic theory of independence. Oxford university press, 2013.

[CCN14]

Gauss M Cordeiro and Francisco Cribari-Neto. An introduction to Bartlett correction
and bias reduction. Springer, 2014.

[CW00]

Shaun Cooper and Shayne Waldron. The eigenstructure of the Bernstein operator.
Journal of Approximation Theory, 105(1):133–165, 2000.

[DL93]

Ronald A DeVore and George G Lorentz. Constructive approximation, volume 303.
Springer Science & Business Media, 1993.

[DT87]

Zeev Ditzian and Vilmos Totik. Moduli of smoothness. Springer, 1987.

[Efr79]

Bradley Efron. Bootstrap methods: another look at the Jackknife. The Annals of
Statistics, pages 1–26, 1979.

[Efr82]

Bradley Efron. The jackknife, the bootstrap and other resampling plans. SIAM, 1982.

[ET94]

Bradley Efron and Robert J Tibshirani. An introduction to the bootstrap, volume 57.
CRC press, 1994.

[Gan03]

Michael I Ganzburg. Strong asymptotics in lagrange interpolation with equidistant
nodes. Journal of approximation theory, 122(2):224–240, 2003.

[GZ94]

Heinz H Gonska and Xin-long Zhou. Approximation theorems for the iterated Boolean
sums of Bernstein operators. Journal of Computational and applied mathematics,
53(1):21–31, 1994.

[Hal92]

Peter Hall. The bootstrap and Edgeworth expansion. Springer Science & Business Media,
1992.
53

[HJW16]

Yanjun Han, Jiantao Jiao, and Tsachy Weissman. Minimax rate-optimal estimation of
divergences between discrete distributions. arXiv preprint arXiv:1605.09124, 2016.

[HKPT12] Wolfgang Härdle, Gerard Kerkyacharian, Dominique Picard, and Alexander Tsybakov.
Wavelets, approximation, and statistical applications, volume 129. Springer Science &
Business Media, 2012.
[HM88]

Peter Hall and Michael A Martin. On bootstrap resampling and iteration. Biometrika,
75(4):661–671, 1988.

[Hur76]

Jan Hurt. Asymptotic expansions of functions of statistics. Aplikace matematiky,
21(6):444–456, 1976.

[IM78]

Mourad EH Ismail and C Ping May. On a family of approximation operators. Journal
of Mathematical Analysis and Applications, 63(2):446–462, 1978.

[JVHW15] Jiantao Jiao, Kartik Venkat, Yanjun Han, and Tsachy Weissman. Minimax estimation
of functionals of discrete distributions. IEEE Transactions on Information Theory,
61(5):2835–2885, 2015.
[JVHW17] Jiantao Jiao, Kartik Venkat, Yanjun Han, and Tsachy Weissman. Maximum likelihood
estimation of functionals of discrete distributions. IEEE Transactions on Information
Theory, 63(10):6774–6798, Oct 2017.
[LC98]

Erich Leo Lehmann and George Casella.
Springer, 1998.

[LO00]

Rafał Latała and Krzysztof Oleszkiewicz. Between Sobolev and Poincaré. In Geometric
aspects of functional analysis, pages 147–168. Springer, 2000.

[LS94]

Xin Li and EB Saff. Local convergence of Lagrange interpolation associated with
equidistant nodes. Journal of Approximation Theory, 78(2):213–225, 1994.

[May76]

CP May. Saturation and inverse theorems for combinations of a class of exponential
type operators. Canad. J. Math, 28(6):1224–1250, 1976.

[Mil74]

Rupert G Miller. The jackknife-a review. Biometrika, 61(1):1–15, 1974.

[MM08]

Giuseppe Mastroianni and Gradimir Milovanovic. Interpolation processes: Basic theory
and applications. Springer Science & Business Media, 2008.

[Mor82]

Carl N Morris. Natural exponential families with quadratic variance functions. The
Annals of Statistics, pages 65–80, 1982.

[Mor83]

Carl N Morris. Natural exponential families with quadratic variance functions: statistical theory. The Annals of Statistics, pages 515–529, 1983.

[Nat64]

Isidor Pavlovich Natanson. Constructive function theory: interpolation and approximation quadratures, volume 3. Ungar, 1964.

[Nat83]

GI Natanson. Application of the method of IP Natanson and I. Yu. Kharrik in the
algebraic case. Operator Theory and Function Theory, (1):166–170, 1983.
54

Theory of point estimation, volume 31.

[Nem00]

A Nemirovski. Topics in non-parametric statistics. lectures on probability theory and
statistics, saint flour 1998, 1738, 2000.

[Pan03]

Liam Paninski. Estimation of entropy and mutual information. Neural Computation,
15(6):1191–1253, 2003.

[PRW99]

Dimitris N Politis, Joseph P Romano, and Michael Wolf. Subsampling. Springer Series
in Statistics, 1999.

[Que56]

Maurice H Quenouille. Notes on bias in estimation. Biometrika, 43(3/4):353–360, 1956.

[RS02]

C Rose and MD Smith. h-statistics: Unbiased estimators of central moments. Mathematical Statistics with Mathematica, pages 253–256, 2002.

[Sev91]

Joathan Carl Sevy. Acceleration of convergence of sequences of simultaneous approximants. 1991.

[Sev95]

JC Sevy. Lagrange and least-squares polynomials as limits of linear combinations of
iterates of Bernstein and Durrmeyer polynomials. Journal of Approximation Theory,
80(2):267–271, 1995.

[SGO71]

WR Schucany, HL Gray, and DB Owen. On bias reduction in estimation. Journal of
the American Statistical Association, 66(335):524–533, 1971.

[Sha48]

Claude Elwood Shannon. A mathematical theory of communication. The Bell System
Technical Journal, 27:379–423, 623–656, 1948.

[ST77]

LI Strukov and AF Timan. Mathematical expectation of continuous functions of random
variables. smoothness and variance. Siberian Mathematical Journal, 18(3):469–474,
1977.

[ST12]

Jun Shao and Dongsheng Tu. The jackknife and bootstrap. Springer Science & Business
Media, 2012.

[SV16]

Igal Sason and Sergio Verdú. f -divergence inequalities. IEEE Transactions on Information Theory, 62(11):5973–6006, 2016.

[SW89]

Jun Shao and CF Jeff Wu. A general theory for jackknife variance estimation. The
Annals of Statistics, pages 1176–1197, 1989.

[Tim14]

Aleksandr Filippovich Timan. Theory of approximation of functions of a real variable,
volume 34. Elsevier, 2014.

[Tot88]

V Totik. Uniform approximation by exponential-type operators. Journal of mathematical analysis and applications, 132(1):238–246, 1988.

[Tot94]

Vilmos Totik. Approximation by Bernstein polynomials. American Journal of Mathematics, 116(4):995–1018, 1994.

[Tsy08]

A. Tsybakov. Introduction to Nonparametric Estimation. Springer-Verlag, 2008.

55

[VV11]

Gregory Valiant and Paul Valiant. The power of linear estimators. In Foundations of
Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, pages 403–412.
IEEE, 2011.

[VV13]

Paul Valiant and Gregory Valiant. Estimating the unseen: improved estimators for
entropy and other properties. In Advances in Neural Information Processing Systems,
pages 2157–2165, 2013.

[Wit87]

Christopher Stroude Withers. Bias reduction by Taylor series. Communications in
Statistics-Theory and Methods, 16(8):2369–2383, 1987.

[WY16]

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

[ZI04]

Abdelhak M Zoubir and D Robert Iskander. Bootstrap techniques for signal processing.
Cambridge University Press, 2004.

56

