betaFeedback

WorksMathematics

Sharp upper and lower bounds on the variance of U-statistics

Abstract

For a U-statistic with a symmetric kernel of any rank, we offer new upper and lower bounds on its variance, which are uniformly sharper than those established in the classical paper by Hoeffding (1948, Theorem 5.2). Our new bounds have strong optimality properties and can tightly describe how the variance scales with the degree of the kernel. As an application, we leverage our new upper bound to improve an existing Berry-Esseen theorem for the normal approximation of incomplete U-statistics based on Bernoulli sampling, in a computationally frugal regime where the computational budget is much smaller than the available sample size.

Introduction

Let X1,…,XnX_1,\ldots,X_n be independent and identically distributed sample points taking values in a measurable space (M,M)(M,\mathcal{M}), and h:Mm→Rh:M^m \to\mathbb{R} be a measurable real-valued function symmetric in its mm arguments, i.e. h(x1,…,xm)=h(xπ1,…,xπm)h(x_1,\ldots,x_m)=h(x_{\pi_1},\ldots,x_{\pi_m}) for any permutation (π1,…,πm)(\pi_1,\ldots,\pi_m) of the indices (1,…,m)(1,\ldots,m). For m≤nm \le n, in his seminal paper, Hoeffding [2] introduced the U-statistic

Un≡(nm)−1∑1≤i1<⋯<im≤nh(Xi1,…,Xim)(1)U_n \equiv\binom{n}{m}^{-1}\sum_{1\le i_1<\cdots<i_m\le n}h(X_{i_1},\ldots,X_{i_m}) \tag*{(1)}

that averages the evaluations of the kernel function hh over all possible (nm)\binom{n}{m} subsets of mm distinct sample points. Throughout, for any natural number k≤nk \le n, we will adopt the shorthand [k]≡{1,…,k}[k]\equiv\{1,\ldots,k\}; moreover, given a function t:Mk→Rt:M^k\to\mathbb{R} in kk arguments in MM and another natural number ℓ\ell, we will use E[t]\mathbb{E}[t], var⁡[t]\operatorname{var}[t], and E[tℓ]\mathbb{E}[t^\ell] as respective shorthands for E[t(X1,…,Xk)]\mathbb{E}[t(X_1,\ldots,X_k)], var⁡[t(X1,…,Xk)]\operatorname{var}[t(X_1,\ldots,X_k)] and E[(t(X1,…,Xk))ℓ]\mathbb{E}[(t(X_1,\ldots,X_k))^\ell]. We will assume that 0<var⁡[h]<∞0<\operatorname{var}[h]<\infty, so that UnU_n is not always trivially equal to its expectation θ≡E[h]\theta\equiv\mathbb{E}[h].

The structure of the variance of UnU_n is well understood. For any c∈[m]c\in[m], let

Ψc(x1,…,xc)≡E[h(x1,…,xc,Xc+1,…,Xm)]−θ(2)\Psi_c(x_1,\ldots,x_c)\equiv\mathbb{E}[h(x_1,\ldots,x_c,X_{c+1},\ldots,X_m)]-\theta \tag*{(2)}

be the centered conditional expectation of hh by fixing cc of its mm arguments, and

gc(x1,…,xc)≡Ψc(x1,…,xc)−∑j=1c−1∑1≤i1<⋯<ij≤cgj(xi1,…,xij)(3)g_c(x_1,\ldots,x_c)\equiv\Psi_c(x_1,\ldots,x_c)-\sum_{j=1}^{c-1}\sum_{1\le i_1<\cdots<i_j\le c}g_j(x_{i_1},\ldots,x_{i_j}) \tag*{(3)}

be the recursively defined canonical projection function of hh. Define the second moment quantities

ζc≡E[Ψc2]andδc≡E[gc2](4)\zeta_c \equiv\mathbb{E}[\Psi_c^2] \quad\text{and} \quad\delta_c \equiv\mathbb{E}[g_c^2] \tag*{(4)}

for every c∈[m]c \in[m]. The two exact variance formulas

var⁡[Un]=(nm)−1∑c=1m(mc)(n−mm−c)ζc(5)\operatorname{var}[U_n] = \binom{n}{m}^{-1}\sum_{c=1}^{m}\binom{m}{c}\binom{n-m}{m-c}\zeta_c \tag*{(5)}
=∑c=1m(mc)2(nc)−1δc(6)= \sum_{c=1}^{m}\binom{m}{c}^{2}\binom{n}{c}^{-1}\delta_c \tag*{(6)}

are standard results in the U-statistic literature ([4 Chapter 1]. We also remark that ζm=var⁡[h]\zeta_m = \operatorname{var}[h] by definition.

Nevertheless, instead of the exact forms in (5) and (6), it is sometimes more instructive to work with bounds on var⁡[Un]\operatorname{var}[U_n], particularly when one demands a more transparent understanding of how var⁡[Un]\operatorname{var}[U_n] scales with the kernel degree mm. In this article, we will contribute new bounds on var⁡[Un]\operatorname{var}[U_n] that are sharp, which we believe will be useful for future research on the theory of U-statistics, an area that has proven to be fertile even after nearly 8 decades since the work by Hoeffding [2].

Main results

Hoeffding [2] (Theorem 5.2) established that, if the kernel hh is of rank at least dd, then

mdKn,m(d)ζd≤var⁡[Un]≤Kn,m(d)ζm(7)\frac{m}{d}K_{n,m}(d)\zeta_d \leq\operatorname{var}[U_n] \leq K_{n,m}(d)\zeta_m \tag*{(7)}

for the constant

Kn,m(d)≡(nm)−1∑c=dm(m−1c−1)(n−mm−c).(8)K_{n,m}(d) \equiv\binom{n}{m}^{-1}\sum_{c=d}^{m}\binom{m-1}{c-1}\binom{n-m}{m-c}. \tag*{(8)}

The rank of a kernel hh (or of the corresponding U-statistic) is defined to be the smallest integer r∈[m]r \in[m] such that ζ1=⋯=ζr−1=0\zeta_1 = \cdots= \zeta_{r-1} = 0 and ζr>0\zeta_r > 0; it is well-defined, because it must be true that 0≤ζ1≤⋯≤ζm0 \leq\zeta_1 \leq\cdots\leq\zeta_m as an easy consequence of Jensen’s inequality. Alternatively, for any c∈[m]c \in[m], using the well-known identities that

ζc=∑j=1c(cj)δj(9)\zeta_c = \sum_{j=1}^{c}\binom{c}{j}\delta_j \tag*{(9)}

and

δc=∑j=1c(−1)c−j(cj)ζj(10)\delta_c = \sum_{j=1}^{c}(-1)^{c-j}\binom{c}{j}\zeta_j \tag*{(10)}

the rank can be equivalently defined as the smallest r∈[m]r \in[m] such that δ1=⋯=δr−1=0\delta_1 = \cdots= \delta_{r-1} = 0 and δr>0\delta_r > 0.2 In the literature, a kernel of rank 1 is said to be non-degenerate, and a kernel of rank mm is said to be completely degenerate.

Rather surprisingly, in this article we illustrate that the classical inequalities in (7) are actually suboptimal. Our main contributions are the following upper and lower bounds on var⁡[Un]\operatorname{var}[U_n] that are uniformly sharper than (7), which are proven in Appendix A.

Theorem 1 (Sharper variance bounds on U-statistics). Suppose UnU_n is a UU-statistic defined as in (1) of rank at least d∈[m]d \in[m] and m<nm < n. Then

(md)Bn,m(d)ζd≤var⁡[Un]≤Bn,m(d)ζm,(11)\binom{m}{d} B_{n,m}(d)\zeta_d \le\operatorname{var}[U_n] \le B_{n,m}(d)\zeta_m, \tag*{(11)}

for the constant

Bn,m(d)=(nd)−1(md).(12)B_{n,m}(d) = \binom{n}{d}^{-1}\binom{m}{d}. \tag*{(12)}

Moreover, these two properties hold:

(i) It is true that

mdKn,m(d)≤(md)Bn,m(d)andBn,m(d)≤Kn,m(d),(13)\frac{m}{d}K_{n,m}(d) \le\binom{m}{d}B_{n,m}(d) \quad\text{and}\quad B_{n,m}(d) \le K_{n,m}(d), \tag*{(13)}

and each inequality in (13) becomes an equality if and only if d∈{1,m}d \in\{1,m\}.

(ii) Each inequality in (11) is an equality if and only if δd+1=⋯=δm=0\delta_{d+1}=\cdots=\delta_m=0.

We assume m<nm<n in Theorem 1 to exclude the mathematically uninteresting case m=nm=n, in which the variance upper bounds in both (7) and (11) trivially become equalities as Bm,m(d)=Km,m(d)=1B_{m,m}(d)=K_{m,m}(d)=1 and var⁡[Un]=ζm\operatorname{var}[U_n]=\zeta_m. Property (i) in Theorem 1 says that our bounds in (11) are strictly sharper than those in (7) by having better constants, except when the kernel is non-degenerate or completely degenerate; it is established through a neat argument that expresses both Bn,m(d)B_{n,m}(d) and Kn,m(d)K_{n,m}(d) in terms of the same hypergeometric random variable and exploits its binomial moments; see (A.11) and (A.12).

To further illustrate the optimality of our result, property (ii) in Theorem 1 says that both inequalities in (11) can be attained when δd\delta_d is the only non-vanishing quantity among all of δ1,…,δm\delta_1,\ldots,\delta_m, that is, when UnU_n is entirely comprised of the dd-th component in its canonical decomposition [4 p.24] and therefore, upon centering by its mean θ\theta, has the form

Un−θ=(md)(nd)−1∑1≤i1<⋯<id≤ngd(Xi1,…,Xid).(14)U_n-\theta=\binom{m}{d}\binom{n}{d}^{-1}\sum_{1\le i_1<\cdots<i_d\le n}g_d(X_{i_1},\ldots,X_{i_d}). \tag*{(14)}

An example of a kernel that can give rise to (14) is as follows. Let ψ:M→R\psi:M\to\mathbb{R} be a (measurable) function such that E[ψ]=0\mathbb{E}[\psi]=0 and 0<E[ψ2]<∞0<\mathbb{E}[\psi^2]<\infty, and define the mean-zero kernel

hψ(x1,…,xm)≡∑1≤i1<⋯<id≤mψ(xi1)⋯ψ(xid).(15)h_\psi(x_1,\ldots,x_m)\equiv\sum_{1\le i_1<\cdots<i_d\le m}\psi(x_{i_1})\cdots\psi(x_{i_d}). \tag*{(15)}

For instance, if A∈MA\in\mathcal{M} is a set such that 0<P(X1∈A)<10<\mathbb{P}(X_1\in A)<1 and ψ(x)≡1{x∈A}−P(X1∈A)\psi(x)\equiv\mathbf{1}\{x\in A\}-\mathbb{P}(X_1\in A), then E[ψ]=0\mathbb{E}[\psi]=0 and E[ψ2]=P(X1∈A)P(X1∉A)∈(0,∞)\mathbb{E}[\psi^2]=\mathbb{P}(X_1\in A)\mathbb{P}(X_1\notin A)\in(0,\infty). In Appendix § 7, we will show that a U-statistic based on the kernel hψh_\psi above satisfies (14).

To the best of our knowledge, Theorem 1 is new. That being said, a prototype of our upper bound on var⁡[Un]\operatorname{var}[U_n] in (11) has been hinted by Peng et al. [6], who set out to improve upon the Berry-Esseen theorem for a non-degenerate UnU_n stated in Chen et al. [1]. In this latter line of work, a key step is to bound the variance of the Hájek projection remainder of UnU_n

Uhˉm≡(nm)−1∑1≤i1<⋯<im≤nhˉm(Xi1,…,Xim),U_{\bar h_m}\equiv\binom{n}{m}^{-1}\sum_{1\le i_1<\cdots<i_m\le n}\bar h_m(X_{i_1},\ldots,X_{i_m}),

which is itself a U-statistic constructed with the kernel hˉm(x1,…,xm)≡h(x1,…,xm)−θ−∑i=1mΨ1(xi)\bar h_m(x_1,\ldots,x_m)\equiv h(x_1,\ldots,x_m)-\theta-\sum_{i=1}^{m}\Psi_1(x_i) and is of rank at least 2. Peng et al. [6] applied a bound qualitatively comparable to our upper bound in (11) to get

var⁡[Uhˉm]≤m2n2E[hˉm2].(16)\operatorname{var}[U_{\bar h_m}]\le\frac{m^2}{n^2}\mathbb{E}[\bar h_m^2]. \tag*{(16)}

On the contrary, Chen et al. [1] have effectively applied Hoeffding [2]’s upper bound in (7) at d=2d=2 on var⁡[Uˉhm]\operatorname{var}[\bar{U}_{h_m}], and their subsequent arguments [1 p.284-286], which show the inequality

Kn,m(2)≤m(m−1)2n(n−m+1)(17)K_{n,m}(2) \le\frac{m(m-1)^2}{n(n-m+1)} \tag*{(17)}

will further lead to the bound var⁡[Uˉhm]≤m(m−1)2n(n−m+1)E[hˉm2]\operatorname{var}[\bar{U}_{h_m}] \le\frac{m(m-1)^2}{n(n-m+1)}\mathbb{E}[\bar{h}_m^2], which is fundamentally looser than (16) with respect to order in mm. As a result, among other things, the Berry-Esseen bound for UnU_n in Peng et al. [6] is superior to the one in Chen et al. [1] by exhibiting a tighter dependence on the degree mm. The proof of our upper bound in (11) essentially sharpens Peng et al. [6]’s arguments and generalizes them for a U-statistic of any arbitrary rank. In § 3, we will further leverage this new upper bound to improve an existing Berry-Esseen theorem for incomplete U-statistics with Bernoulli sampling.

We have also developed the proposition below (proven in Appendix § 8) to illustrate some properties of the constant Bn,m(d)B_{n,m}(d), particularly how it scales with the kernel degree mm:

Proposition 1 (Further properties of the constant Bn,m(d)B_{n,m}(d)). The following inequalities are true:

(i) For any d∈[m]d \in[m],

(m−d+1n)d≤Bn,m(d)≤(mn)d.(18)\left(\frac{m-d+1}{n}\right)^d \le B_{n,m}(d) \le\left(\frac{m}{n}\right)^d. \tag*{(18)}

(ii) Suppose n>2mn>2m. For any 1<d<m1<d<m,

(n−m)m−d(n−d)m−dm−1d−1Bn,m(d)≤Kn,m(d),(19)\frac{(n-m)_{m-d}}{(n-d)_{m-d}}\frac{m-1}{d-1}B_{n,m}(d) \le K_{n,m}(d), \tag*{(19)}

where (a)b(a)_b denotes the falling factorial a(a−1)⋯(a−b+1)a(a-1)\cdots(a-b+1).

Proposition 1(i) should intuitively make sense to the reader once we rewrite the constant as

Bn,m(d)=∏j=0d−1m−jn−j;(20)B_{n,m}(d)=\prod_{j=0}^{d-1}\frac{m-j}{n-j}; \tag*{(20)}

it suggests that for a fixed dd, Bn,m(d)B_{n,m}(d) is of the order O(md/nd)O(m^d/n^d). To understand Proposition 1(ii), first note that it is always true that Kn,m(d)≤(m−1d−1)Bn,m(d)K_{n,m}(d) \le\binom{m-1}{d-1}B_{n,m}(d), which simply rephrases the first inequality in (13). Therefore, (19) can be understood as a “reverse” of the latter inequality via adjustment by the factor (n−m)m−d(n−d)m−d<1\frac{(n-m)_{m-d}}{(n-d)_{m-d}}<1. However, when dd is held fixed and m2/n→0m^2/n \to0, the factor (n−m)m−d(n−d)m−d\frac{(n-m)_{m-d}}{(n-d)_{m-d}} is very close to 1, which suggests that Kn,m(d)K_{n,m}(d) is approximately larger than Bn,m(d)B_{n,m}(d) by a factor of m−1d−1=O(md−1)\frac{m-1}{d-1}=O(m^{d-1}). Indeed, it is no coincidence that only an upper bound of the order O(m3/n2)O(m^3/n^2) can be established for Kn,m(2)K_{n,m}(2) as in (17) by Chen et al. [1], which is looser than the tighter bound of the order O(m2/n2)O(m^2/n^2) suggested by (18) at d=2d=2.

Application to Berry-Esseen theorems for incomplete U-statistics with a small Bernoulli sampling budget

Let In,m≡{(i1,…,im):1≤i1<⋯<im≤n}I_{n,m}\equiv\{(i_1,\ldots,i_m):1\le i_1<\cdots<i_m\le n\}, and for a positive integer N<(nm)N<\binom{n}{m}, define p≡N(nm)−1p\equiv N\binom{n}{m}^{-1}. Suppose (Zi)i∈In,m(Z_i)_{i\in I_{n,m}} are (nm)\binom{n}{m} independent and identically distributed Bernoulli random variables such that P(Zi=1)=p\mathbb{P}(Z_i=1)=p, and that they are also independent of all the sample points X1,…,XnX_1,\ldots,X_n. Let N^≡∑i∈In,mZi\hat{N}\equiv\sum_{i\in I_{n,m}}Z_i be the count of how many of these Bernoulli random variables realize as a “1”. For a kernel with a large degree mm, instead of UnU_n in (1) which sums over all (nm)\binom{n}{m} kernel evaluations, to achieve computational savings one can construct the incomplete U-statistic with Bernoulli sampling

Un,N′=1N^∑i∈In,mZih(Xi),(21)U'_{n,N}=\frac{1}{\hat{N}}\sum_{i\in I_{n,m}}Z_i h(X_i), \tag*{(21)}

where we have used the shorthand h(Xi)≡h(Xi1,…,Xim)h(X_i) \equiv h(X_{i_1},\ldots,X_{i_m}) for any i≡(i1,…,im)∈In,m\mathbf{i} \equiv(i_1,\ldots,i_m) \in I_{n,m}; by convention, Un,N′U'_{n,N} is set to be zero when N^=0\widehat{N}=0. Because only approximately a fraction pp of all the Bernoulli samplers ZiZ_{\mathbf{i}} in (21) will be “switched on”, Un,N′U'_{n,N} sums over many fewer kernel evaluations than UnU_n, particularly when the computational budget NN is small.

The normal convergence behavior of Un,N′U'_{n,N} has been well-studied. In particular, if rr is the rank of the kernel hh, it has been established that, for a fixed mm,

N(Un,N′−θ)ζm1/2\frac{\sqrt{N}(U'_{n,N}-\theta)}{\zeta_m^{1/2}}

converges in distribution to the standard normal as n,N→∞n,N \to\infty with nr/N→∞n^r/N \to\infty; (22)

see Leung [5] which has its roots in Janson [3]. Note that the asymptotic regime here suggests a computationally frugal situation where NN could be much less than nrn^r. Leung [5] also developed a Berry-Esseen theorem to gauge the normal approximating accuracy in terms of Kolmogorov distance for the weak convergence in (22). Turns out, the said Berry-Esseen theorem can be further improved with our new upper bound on var⁡[Un]\operatorname{var}[U_n] in (11). Below, we will first state the improved theorem, and then explain how it has improved upon its predecessor Leung [5]; we will use Φ(⋅)\Phi(\cdot) to denote the standard normal distribution function.

Corollary 1 (Improved Berry-Esseen theorem for the normal convergence in (22)). Let Un,N′U'_{n,N} be constructed as in (21) with a symmetric kernel hh of rank rr on Mm\mathcal{M}^m. Suppose that

E[h]=0,(22)\mathbb{E}[h] = 0, \tag*{(22)}

0<E[∣h∣4]<∞0 < \mathbb{E}[|h|^4] < \infty and 2≤m<n/22 \le m < n/2 hold. Then, there exists an absolute constant C>0C > 0 such that

sup⁡z∈R∣P(NUn,N′ζm1/2≤z)−Φ(z)∣≤C{E[∣h∣3](1−2p+2p2)N(1−p)ζm3/2+exp⁡(−nζm324m(E[∣h∣3])2)+NBn,m(r)1−p+mE[(h2−ζm)2]nζm}.(23)\sup_{z \in\mathbb{R}} \left| \mathbb{P}\left(\frac{\sqrt{N}U'_{n,N}}{\zeta_m^{1/2}} \le z\right)-\Phi(z)\right| \le C\left\{ \frac{\mathbb{E}[|h|^3](1-2p+2p^2)}{\sqrt{N}(1-p)\zeta_m^{3/2}} +\exp\left(\frac{-n\zeta_m^3}{24m(\mathbb{E}[|h|^3])^2}\right) +\frac{\sqrt{NB_{n,m}(r)}}{\sqrt{1-p}} +\frac{\sqrt{m\mathbb{E}[(h^2-\zeta_m)^2]}}{\sqrt{n\zeta_m}} \right\}. \tag*{(23)}

As is customary in the literature on Berry-Esseen theorems for U-statistics, we have made the mean zero assumption in (22) only to avoid cluttering the notation in our bound (23); obviously, one could present the theorem in terms of the centered kernel h(⋅)−θh(\cdot)-\theta without making this assumption. Moreover, similarly to Leung [5], a version of the result with the milder finite third moment assumption E[∣h∣3]<∞\mathbb{E}[|h|^3] < \infty can also be stated, but we have opted to only present the notationally cleaner result (23) under the finite fourth moment assumption E[∣h∣4]<∞\mathbb{E}[|h|^4] < \infty for the purpose of illustration.

The original Berry-Esseen bound in Leung [5] is essentially the same as (23) except that the quantity Kn,m(r)K_{n,m}(r) was in the place of Bn,m(r)B_{n,m}(r); indeed, as explained in Appendix § 9, the proof of Corollary 1 is only a minor modification of that of Leung [5] by making use of the new upper bound in (11). As such, when 1<r<m1 < r < m, our Berry-Esseen bound (23) is now tighter, not only because Bn,m(r)B_{n,m}(r) is smaller than Kn,m(r)K_{n,m}(r) as per property (i) in Theorem 1, but also because it is smaller than it by approximately a factor of order O((m−1)1−r)O((m-1)^{1-r}) for a fixed rr as m2/n→0m^2/n \to0, as per (19). The latter is an important attribute for modern applications of incomplete U-statistics such as uncertainty inference in random forests, where the degree mm corresponds to the subsample size for growing each tree, which is typically quite large; we refer the readers to Leung [5] which contains more related discussion.

Acknowledgments

This research is partially funded by the Manchester-Melbourne-Toronto Research Fund. Dennis Leung would also like to thank Dr. Yuta Koike for some helpful discussion during the early stage of this project.

Declaration of generative AI and AI-assisted technologies in the manuscript preparation process.

During the preparation of this work, the first author (K.N.) used Claude (Anthropic) to assist in refining and verifying certain mathematical arguments and calculations, while the last author (D.L.) used Codex (OpenAI) to assist with some final edits. The authors independently verified all mathematical statements and proofs, and take full responsibility for the content of the published article.

Proof of Theorem 1

From (6), we can first write the variance of UnU_n as

var⁡[Un]=∑j=dmBn,m(j)(mj)δj(24)\operatorname{var}[U_n] = \sum_{j=d}^{m} B_{n,m}(j) \binom{m}{j} \delta_j \tag*{(24)}
=∑j=d+1mBn,m(j)(mj)δj+Bn,m(d)(md)ζd,(25)= \sum_{j=d+1}^{m} B_{n,m}(j) \binom{m}{j} \delta_j + B_{n,m}(d) \binom{m}{d} \zeta_d, \tag*{(25)}

where (A.1) is true because

δ1=⋯=δd−1=0,(26)\delta_1 = \cdots= \delta_{d-1} = 0, \tag*{(26)}

as the rank of hh is at least dd, and (A.2) is true because

ζd=δd,(27)\zeta_d = \delta_d, \tag*{(27)}

which can be seen by taking c=dc=d in (9) and using (A.3).

Under m<nm<n, Bn,m(r)/Bn,m(r+1)=n−rm−r>1B_{n,m}(r)/B_{n,m}(r+1) = \frac{n-r}{m-r} > 1 for any r∈[m−1]r \in[m-1], which implies

Bn,m(r) is strictly decreasing in r∈[m].(28)B_{n,m}(r) \text{ is strictly decreasing in } r \in[m]. \tag*{(28)}

In light of (A.5), one can deduce from (A.1) that

var⁡[Un]=∑j=dmBn,m(j)(mj)δj≤Bn,m(d)∑j=dm(mj)δj=Bn,m(d)ζm,(29)\operatorname{var}[U_n] = \sum_{j=d}^{m} B_{n,m}(j) \binom{m}{j} \delta_j \le B_{n,m}(d) \sum_{j=d}^{m} \binom{m}{j} \delta_j = B_{n,m}(d)\zeta_m, \tag*{(29)}

where the last equality in (A.6) comes from (9), (A.3) and (A.4). On the other hand, from (A.2), one can immediately see that

(md)Bn,m(d)ζd≤∑j=d+1mBn,m(j)(mj)δj+Bn,m(d)(md)ζd=var⁡[Un].(30)\binom{m}{d} B_{n,m}(d)\zeta_d \le\sum_{j=d+1}^{m} B_{n,m}(j) \binom{m}{j} \delta_j + B_{n,m}(d) \binom{m}{d} \zeta_d = \operatorname{var}[U_n]. \tag*{(30)}

Not only do the inequalities (A.6) and (A.7) together imply (11), but it is also easy to see that each of them precisely becomes an equality if and only if δd+1=⋯=δm=0\delta_{d+1} = \cdots= \delta_m = 0, which proves the property (ii).

It remains to show property (i). To that end, we will exploit expressions of Bn,m(d)B_{n,m}(d) and Kn,m(d)K_{n,m}(d) in terms of hypergeometric random variables, as well as an elementary result on the binomial moments of hypergeometric distributions [8 Eq. (93]: If HT,S,tH_{T,S,t} is a Hypergeometric(T,S,t)(T,S,t) random variable, i.e. it is the number of successes in tt draws without replacement, out of a finite population of size TT containing SS successes, then

E[(HT,S,tr)1{HT,S,t≥r}]=(Sr)(tr)(Tr)for r=1,…,S.(31)\mathbb{E}\left[\binom{H_{T,S,t}}{r}\mathbf{1}\{H_{T,S,t}\ge r\}\right] = \frac{\binom{S}{r}\binom{t}{r}}{\binom{T}{r}} \quad\text{for } r=1,\ldots,S. \tag*{(31)}

We will first prove

Bn,m(d)≤Kn,m(d),(32)B_{n,m}(d) \le K_{n,m}(d), \tag*{(32)}

as well as the fact that

{xref}`(A.9)` is an exact inequality if and only if $d \in\{1,m\}$. \tag*{(33)}

From the definition of Kn,m(d)K_{n,m}(d) in (8) and (m−1c−1)=cm(mc)\binom{m-1}{c-1} = \frac{c}{m}\binom{m}{c}, we can first write

Kn,m(d)=∑c=dmcm(mc)(n−mm−c)(nm)=∑c=dmcmP(Hn,m,m=c)=1mE[Hn,m,m1{Hn,m,m≥d}].(34)K_{n,m}(d)=\sum_{c=d}^{m}\frac{c}{m}\frac{\binom{m}{c}\binom{n-m}{m-c}}{\binom{n}{m}}=\sum_{c=d}^{m}\frac{c}{m}\mathbb{P}(H_{n,m,m}=c)=\frac{1}{m}\mathbb{E}\left[H_{n,m,m}1\{H_{n,m,m}\ge d\}\right]. \tag*{(34)}

On the other hand, using the definition of Bn,m(d)B_{n,m}(d) in (12) and formula (A.8), we have

Bn,m(d)=(md)−1E[(Hn,m,md)1{Hn,m,m≥d}]=1mE[(Hn,m,m−1d−1)(m−1d−1)Hn,m,m1{Hn,m,m≥d}].B_{n,m}(d)=\binom{m}{d}^{-1}\mathbb{E}\left[\binom{H_{n,m,m}}{d}1\{H_{n,m,m}\ge d\}\right]=\frac{1}{m}\mathbb{E}\left[\frac{\binom{H_{n,m,m}-1}{d-1}}{\binom{m-1}{d-1}}H_{n,m,m}1\{H_{n,m,m}\ge d\}\right].
{#eq:A.12}[^4]

Since Hn,m,m≤mH_{n,m,m}\le m by definition, it is always true that (Hn,m,m−1d−1)(m−1d−1)≤1\frac{\binom{H_{n,m,m}-1}{d-1}}{\binom{m-1}{d-1}}\le1; therefore, it is always true that

(Hn,m,m−1d−1)(m−1d−1)Hn,m,m1{Hn,m,m≥d}≤Hn,m,m1{Hn,m,m≥d},(35)\frac{\binom{H_{n,m,m}-1}{d-1}}{\binom{m-1}{d-1}}H_{n,m,m}1\{H_{n,m,m}\ge d\}\le H_{n,m,m}1\{H_{n,m,m}\ge d\}, \tag*{(35)}

which proves (A.9) by comparing the rightmost expectations in (A.11) and (A.12). Moreover, it is easy to see that (A.13) becomes an equality when d∈{1,m}d\in\{1,m\}, so the “if” part of (A.10) is proved. When 1<d<m1<d<m, on the event {Hn,m,m=m−1}\{H_{n,m,m}=m-1\} which has a strictly positive probability, (A.13) becomes a strict inequality because (Hn,m,m−1d−1)(m−1d−1)=(m−2d−1)(m−1d−1)<1\frac{\binom{H_{n,m,m}-1}{d-1}}{\binom{m-1}{d-1}}=\frac{\binom{m-2}{d-1}}{\binom{m-1}{d-1}}<1, which proves the “only if” part of (A.10) by comparing (A.11) and (A.12) again.

Next, we will prove mdKn,m(d)≤(md)Bn,m(d)\frac{m}{d}K_{n,m}(d)\le\binom{m}{d}B_{n,m}(d), which is equivalent to

Kn,m(d)≤(m−1d−1)Bn,m(d),(36)K_{n,m}(d)\le\binom{m-1}{d-1}B_{n,m}(d), \tag*{(36)}

as well as the fact that

{xref}`(A.14)` is an exact equality if and only if \(d \in\{1,m\}\). \tag*{(37)}

in an analogous manner. The rightmost expression of Bn,m(d)B_{n,m}(d) in (A.12) readily gives

(m−1d−1)Bn,m(d)=1mE[(Hn,m,m−1d−1)Hn,m,m1{Hn,m,m≥d}].(38)\binom{m-1}{d-1}B_{n,m}(d)=\frac{1}{m}\mathbb{E}\left[\binom{H_{n,m,m}-1}{d-1}H_{n,m,m}1\{H_{n,m,m}\ge d\}\right]. \tag*{(38)}

Since it is always true that (Hn,m,m−1d−1)≥1\binom{H_{n,m,m}-1}{d-1}\ge1 on the event {Hn,m,m≥d}\{H_{n,m,m}\ge d\}, we have

Hn,m,m1{Hn,m,m≥d}≤(Hn,m,m−1d−1)Hn,m,m1{Hn,m,m≥d},(39)H_{n,m,m}1\{H_{n,m,m}\ge d\}\le\binom{H_{n,m,m}-1}{d-1}H_{n,m,m}1\{H_{n,m,m}\ge d\}, \tag*{(39)}

which proves (A.14) by comparing the expectations in (A.11) and (A.16). Moreover, it is easy to see that (A.17) becomes an equality when d∈{1,m}d\in\{1,m\}, so the “if” part of (A.15) is proved. When 1<d<m1<d<m, on the event {Hn,m,m=m}\{H_{n,m,m}=m\} which has a strictly positive probability, we have (Hn,m,m−1d−1)=(m−1d−1)>1\binom{H_{n,m,m}-1}{d-1}=\binom{m-1}{d-1}>1, so (A.17) becomes a strict inequality, which proves the “only if” part of (A.15) by comparing (A.11) and (A.16) again.

Collecting (A.9), (A.10), (A.14) and (A.15) proves the property (i), and we are done.

Proof that the kernel hψh_{\psi} in (15) satisfies (14)

In this section, all the special functions in (2) and (3) and moment quantities in (4) mentioned are defined with respect to the specific kernel hψh_{\psi}. Note that δ1=⋯=δd−1=0\delta_1=\cdots=\delta_{d-1}=0 because

g1=⋯=gd−1=0(40)g_1=\cdots=g_{d-1}=0 \tag*{(40)}

as per their recursive definitions in (3), because it is easy to see that Ψc(x1,…,xc)=0\Psi_c(x_1,\ldots,x_c)=0 for the kernel hψh_{\psi} and any c≤d−1c\le d-1. To show that δd+1=⋯=δm=0\delta_{d+1}=\cdots=\delta_m=0, because of (B.1), one first notes that Ψd(x1,…,xd)=gd(x1,…,xd)=ψ(x1)⋯ψ(xd)\Psi_d(x_1,\ldots,x_d)=g_d(x_1,\ldots,x_d)=\psi(x_1)\cdots\psi(x_d), and so δd=(E[ψ2])d\delta_d=(\mathbb{E}[\psi^2])^d. Further, by exploiting independence, via direct calculations it must be true that

ζm=E[hψ2]=∑1≤i1<⋯<id≤mE[ψ2(Xi1)]⋯E[ψ2(Xid)]=(md)(E[ψ2])d=(md)δd.\zeta_m=\mathbb{E}[h_{\psi}^2]=\sum_{1\le i_1<\cdots<i_d\le m}\mathbb{E}[\psi^2(X_{i_1})]\cdots\mathbb{E}[\psi^2(X_{i_d})]=\binom{m}{d}\bigl(\mathbb{E}[\psi^2]\bigr)^d=\binom{m}{d}\delta_d.

In light of the generic formula for ζm\zeta_m in (9), the above display is only true when all the δd+1,…,δm\delta_{d+1},\ldots,\delta_m vanish.

Proof of Proposition 1

We first prove (i). The upper bound in (18) follows from (20) since m−jn−j≤mn\frac{m-j}{n-j}\le\frac{m}{n} when m≤nm\le n. Moreover, since any jj is at most d−1d-1 in (20), we have m−d+1n≤m−jn−j\frac{m-d+1}{n}\le\frac{m-j}{n-j}, and the lower bound in (18) follows. Now we prove (ii). It suffices to show

(n−m)m−d(n−d)m−d(m−1d−1)Bn,m(d)=(m−1d−1)(n−mm−d)/(nm),(41)\frac{(n-m)^{m-d}}{(n-d)^{m-d}}\binom{m-1}{d-1}B_{n,m}(d)=\binom{m-1}{d-1}\binom{n-m}{m-d}\big/\binom{n}{m}, \tag*{(41)}

because the term on the right hand side of (C.1) is the term at c=dc=d of the sum defining Kn,m(d)K_{n,m}(d) in (8). Since (nm)(md)=(nd)(n−dm−d)\binom{n}{m}\binom{m}{d}=\binom{n}{d}\binom{n-d}{m-d}, we have

(m−1d−1)(n−mm−d)/(nm)=(m−1d−1)Bn,m(d)(nd)(n−mm−d)(nd)(md)=(m−1d−1)Bn,m(d)(n−mm−d)(n−dm−d)=(m−1d−1)Bn,m(d)(n−m)⋯((n−m)−(m−d)+1)(n−d)⋯((n−d)−(m−d)+1),\begin{aligned} \binom{m-1}{d-1}\binom{n-m}{m-d}\big/\binom{n}{m} =\binom{m-1}{d-1}B_{n,m}(d)\frac{\binom{n}{d}\binom{n-m}{m-d}}{\binom{n}{d}\binom{m}{d}} \\ &=\binom{m-1}{d-1}B_{n,m}(d)\frac{\binom{n-m}{m-d}}{\binom{n-d}{m-d}} \\ &=\binom{m-1}{d-1}B_{n,m}(d)\frac{(n-m)\cdots((n-m)-(m-d)+1)}{(n-d)\cdots((n-d)-(m-d)+1)}, \end{aligned}

and our proof of (C.1) is done.

Proof of Corollary 1

The proof is almost word for word the same as the proof of Leung [5]; one simply has to replace all the occurrences of Kn,m(r)K_{n,m}(r) in the proof of Leung [5] with Bn,m(r)B_{n,m}(r). For the interested reader who will explore the fine details in Leung [5], we briefly explain why such simple replacements suffice below.

The proof of Leung [5] relies on a technical result stated in Leung [5], whose proof in Leung [5] in turn uses that E[Un2]≤Kn,m(r)ζm\mathbb{E}[U_n^2]\le K_{n,m}(r)\zeta_m, which is simply Hoeffding [2]’s upper bound in (7) under (22). Obviously, by our new upper bound in (11), it is also true that E[Un2]≤Bn,m(r)ζm\mathbb{E}[U_n^2]\le B_{n,m}(r)\zeta_m, so Kn,m(r)K_{n,m}(r) can be supplanted. Another place where Kn,m(r)K_{n,m}(r) shows up in the original proof of Leung [5] is at Leung [5], where the inequality (nm)−1≤Kn,m(r)\binom{n}{m}^{-1}\le K_{n,m}(r) is employed. However, it is certainly also true that (nm)−1=m⋯1n⋯(n−m+1)≤Bn,m(r)=m⋯(m−r+1)n⋯(n−r+1)\binom{n}{m}^{-1}=\frac{m\cdots1}{n\cdots(n-m+1)}\le B_{n,m}(r)=\frac{m\cdots(m-r+1)}{n\cdots(n-r+1)}, so Kn,m(r)K_{n,m}(r) can be supplanted there as well.

References

  1. [1]Chen, L.H.Y., Goldstein, L., Shao, Q.M., 2011. Normal Approximation by Stein’s Method. Probability and its Applications, Springer, Heidelberg. doi:10.1007/978-3-642-15007-4.DOI
  2. [2]Hoeffding, W., 1948. A class of statistics with asymptotically normal distribution. The Annals of Mathematical Statistics 19, 293–325. doi:10.1214/aoms/1177730196.
  3. [3]Janson, S., 1984. The asymptotic distributions of incomplete u-statistics. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 66, 495–505.DOI
  4. [4]Koroljuk, V.S., Borovskich, Y.V., 1994. Theory of U-statistics. volume 273 of Mathematics and its Applications. Kluwer Academic Publishers Group, Dordrecht. Translated from the 1989 Russian original by P. V. Malyshev and D. V. Malyshev and revised by the authors.
  5. [5]Leung, D., 2026. Berry–Esseen theorems for the asymptotic normality of incomplete U-statistics with Bernoulli sampling. Electronic Journal of Probability 31, Article no. 17, 1–52. doi:10.1214/26-EJP1473.DOI
  6. [6]Peng, W., Coleman, T., Mentch, L., 2022. Rates of convergence for random forests via generalized U-statistics. Electronic Journal of Statistics 16, 232–292. doi:10.1214/21-EJS1958.DOI
  7. [7]Pitman, J., 1993. Probability. Springer Texts in Statistics, Springer-Verlag, New York. doi:10.1007/978-1-4612-4374-8.DOI
  8. [8]Pitman, J., 2001. Random mappings, forests, and subsets associated with abel-cayley-hurwitz multinomial expansions. Séminaire Lotharingien de Combinatoire [electronic only] 46, B46h–45.

Paper details

vlnc:W_26k7jdk3
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude (Anthropic), Codex

View statement
Looking for related papers…
Contents