Introduction to the U-statistic

Notes for A Class of Statistics with Asymptotically Normal Distribution by Wassily Hoeffding.

Author: Jiang Wenxin

Date: 2024 Mar 28

Link to summary of notation and formulas.

Basic Concepts and Motivating Examples

Functional, Kernel and Degree

Suppose that Φ(x1,...,xm)\Phi(x_1,...,x_m) is a function of mm random variables and X1,...,XnX_1,...,X_n are i.i.d. observations from c.d.f. F(x)F(x). Assume n>mn>m.

Make inference about
θ=θ(F)=EF[Φ(X1,...,Xm)]\theta = \theta(F)=E_{F}[\Phi(X_1,...,X_m)]

Note: θ\theta is a functional of the distribution FF. Functional is a function of a function which maps a function to a real (or complex) number.

To use all the samples, we can use the U-statistic
U=(mn)−1Σ′Φ(Xi1,...,Xim)=1n(n−1)...(n−m+1)∑1≤i1<...<im≤nΦ(Xi1,...,Xim)\begin{align*} U &= \left(^n_m\right)^{-1}\Sigma^ \prime \Phi(X_{i_1},...,X_{i_m})\\ &= \frac{1}{n(n-1)...(n-m+1)}\sum_{1\leq i_1<...<i_m\leq n}\Phi(X_{i_1},...,X_{i_m}) \end{align*}
where Σ′\Sigma^\prime stands for summation over all permutations of mm integers i1,...,imi_1,...,i_m such that 1≤i1<...<im≤n1\leq i_1<...<i_m\leq n.

Here, UU is a function of the sample X1,...,XnX_1,...,X_n called a U-statistic. The Φ\Phi function is called the kernel and mm is the degree of the functional θ(F)\theta(F).

Symmetry of Kernel

For convenience, we assume that Φ\Phi is symmetric in its arguments, which means
Φ(...,xi,...,xj,...)=Φ(...,xj,...,xi,...)\Phi(...,x_{i},...,x_{j},...)=\Phi(...,x_{j},...,x_{i},...)

But it is not necessary to assume the symmetry of the kernel. Because we can always convert a non-symmetric kernel to a symmetric one.

If Φ(x1,...,xm)\Phi(x_1,...,x_m) is not symmetric, there exist a symmetric Φ0(x1,...,xm)\Phi_0(x_1,...,x_m) such that
Φ0(x1,...,xm)=1m!∑Φ(xα1,...,xαm)\Phi_0(x_1,...,x_m)=\frac{1}{m!}\sum \Phi(x_{\alpha_1},...,x_{\alpha_m})
where the sum is over all permutations of mm integers 1,...,m1,...,m.

Motivating Examples

Example 1: Let m=1m=1 and Φ(x)=x\Phi(x)=x. Then, U=∑i=1nXi/nU=\sum_{i=1}^nX_i/n is the sample mean.

Example 2: Let m=2m=2 and Φ(x1,x2)=x12−x1x2\Phi(x_1,x_2)=x_1^2-x_1x_2. Then, U=∑1≤i<j≤n(Xi2−XiXj)/(n(n−1))U=\sum_{1\leq i<j\leq n}(X_i^2-X_iX_j)/(n(n-1)) is the sample variance. A symmetric kernel can be Φ0(x1,x2)=(x1−x2)2/2\Phi_0(x_1,x_2)=(x_1-x_2)^2/2.

Example 3: Let m=2m=2 and Φ(x1,x2)=I(x1+x2>0)\Phi(x_1, x_2)=I(x_1+x_2>0). Then, U=∑1≤i<j≤nI(xi+xj>0)/(n(n−1))U=\sum_{1\leq i<j\leq n} I(x_i+x_j>0)/(n(n-1)) is related to one sample Wilcoxon statistics.

Asymptotic Normality of U-statistic: A Simple Version

Define ζ1=σ2(Φ1(X1))\zeta_1=\sigma^2(\Phi_1(X_1)). X1,...,XnX_1,...,X_n are i.i.d. observations from c.d.f. F(x)F(x). Suppose that the kernel Φ\Phi satisfies EΦ2(X1,...,Xm)<∞E\Phi^2(X_1,...,X_m)<\infty. Assume that 0<ζ1<∞0<\zeta_1<\infty. Then,
U−θσ2(U)→dN(0,1)\frac{U-\theta}{\sqrt{\sigma^2(U)}}\xrightarrow{d}N(0,1)
where σ2(U)=m2nζ1+O(n−2)\sigma^2(U)=\frac{m^2}{n}\zeta_1+O(n^{-2}) .

U-statistic

Notations

Definition: U-statistic

Consider the function of the sample,

U(x1,⋯ ,xn)=(nm)−1Σ′Φ(xα1,⋯ ,xαm)(4.4)U\left(x_{1}, \cdots, x_{n}\right)=\left(\begin{array}{c} n \tag{4.4}\\ m \end{array}\right)^{-1} \Sigma^{\prime} \Phi\left(x_{\alpha_{1}}, \cdots, x_{\alpha_{m}}\right)

where the kernel Φ\Phi is symmetric in its mm vector arguments and the sum Σ′\Sigma^{\prime} is extended over all subscripts α\alpha such that

1≤α1<α2<⋯<αm≤n1 \leq \alpha_{1}<\alpha_{2}<\cdots<\alpha_{m} \leq n

Asymptotic Normality of U-statistic

The Variance of a U-statistic

The Unbiased Estimator and Its Variance

If θ=θ(F)\theta=\theta(F), we have
E{U}=E{Φ(X1,⋯ ,Xm)}=θE\{U\}=E\left\{\Phi\left(X_{1}, \cdots, X_{m}\right)\right\}=\theta

Let
Φc(x1,⋯ ,xc)=E{Φ(x1,⋯ ,xc,Xc+1,⋯ ,Xm)},(c=1,⋯ ,m),\begin{align*} \Phi_{c}\left(x_{1}, \cdots, x_{c}\right)&=E\left\{\Phi\left(x_{1}, \cdots, x_{c}, X_{c+1}, \cdots, X_{m}\right)\right\}, \tag{5.2}\\(c&=1, \cdots, m), \end{align*}

where x1,⋯ ,xcx_{1}, \cdots, x_{c} are arbitrary fixed vectors and the expected value is taken with respect to the random vectors Xc+1,⋯ ,XmX_{c+1}, \cdots, X_{m}.

We can rewrite (5.2) in a more familiar form, which is called Hoeffding's projection:

Φc(X1,⋯ ,Xc)=E{Φ(X1,⋯ ,Xm)∣X1,⋯ ,Xc}\begin{equation*} \Phi_{c}\left(X_{1}, \cdots, X_{c}\right)=E\left\{\Phi\left(X_{1}, \cdots, X_{m}\right)|X_{1}, \cdots, X_{c}\right\} \end{equation*}

Then

Φc−1(x1,⋯ ,xc−1)=E{Φc(x1,⋯ ,xc−1,Xc)}\begin{equation*} \Phi_{c-1}\left(x_{1}, \cdots, x_{c-1}\right)=E\left\{\Phi_{c}\left(x_{1}, \cdots, x_{c-1}, X_{c}\right)\right\} \tag{5.3} \end{equation*}

and

E{Φc(X1,⋯ ,Xc)}=θ,(c=1,⋯ ,m).\begin{equation*} E\left\{\Phi_{c}\left(X_{1}, \cdots, X_{c}\right)\right\}=\theta, \quad(c=1, \cdots, m) . \tag{5.4} \end{equation*}

Define

Ψ(x1,⋯ ,xm)=Φ(x1,⋯ ,xm)−θΨc(x1,⋯ ,xc)=Φc(x1,⋯ ,xc)−θ,(c=1,⋯ ,m).\begin{align*} & \Psi\left(x_{1}, \cdots, x_{m}\right)=\Phi\left(x_{1}, \cdots, x_{m}\right)-\theta \tag{5.5}\\ & \Psi_{c}\left(x_{1}, \cdots, x_{c}\right)=\Phi_{c}\left(x_{1}, \cdots, x_{c}\right)-\theta, \quad(c=1, \cdots, m) . \tag{5.6} \end{align*}

We have

Ψc−1(x1,⋯ ,xc−1)=E{Ψc(x1,⋯ ,xc−1,Xc)}E{Ψc(X1,⋯ ,Xc)}=E{Ψ(X1,⋯ ,Xm)}=0,(c=1,⋯ ,m).\begin{gather*} \Psi_{c-1}\left(x_{1}, \cdots, x_{c-1}\right)=E\left\{\Psi_{c}\left(x_{1}, \cdots, x_{c-1}, X_{c}\right)\right\} \tag{5.7}\\ E\left\{\Psi_{c}\left(X_{1}, \cdots, X_{c}\right)\right\}=E\left\{\Psi\left(X_{1}, \cdots, X_{m}\right)\right\}=0, \quad(c=1, \cdots, m) . \tag{5.8} \end{gather*}

Suppose that the variance of Ψc(X1,⋯ ,Xc)\Psi_{c}\left(X_{1}, \cdots, X_{c}\right) exists, and let

ζ0=0,ζc=E{Ψc2(X1,⋯ ,Xc)},(c=1,⋯ ,m)\begin{equation*} \zeta_{0}=0, \quad \zeta_{c}=E\left\{\Psi_{c}^{2}\left(X_{1}, \cdots, X_{c}\right)\right\}, \quad(c=1, \cdots, m) \tag{5.9} \end{equation*}

We have

ζc=E{Φc2(X1,⋯ ,Xc)}−θ2\begin{equation*} \zeta_{c}=E\left\{\Phi_{c}^{2}\left(X_{1}, \cdots, X_{c}\right)\right\}-\theta^{2} \tag{5.10} \end{equation*}

Stationary Order of a Functional

If, for some parent distribution F=F0F=F_{0} and some integer dd, we have ζd(F0)=0\zeta_{d}\left(F_{0}\right)=0, this means that Ψd(X1,⋯ ,Xd)=0\Psi_{d}\left(X_{1}, \cdots, X_{d}\right)=0 with probability 1. By (5.7) and (5.9), ζd=0\zeta_{d}=0 implies ζ1=⋯=ζd−1=0\zeta_{1}=\cdots=\zeta_{d-1}=0.

If ζ1(F0)=0\zeta_{1}\left(F_{0}\right)=0, we shall say that the regular functional θ(F)\theta(F) is stationary for F=F0F=F_{0}. If

ζ1(F0)=⋯=ζd(F0)=0,ζd+1(F0)>0,(1≤d≤m)\begin{equation*} \zeta_{1}\left(F_{0}\right)=\cdots=\zeta_{d}\left(F_{0}\right)=0, \quad \zeta_{d+1}\left(F_{0}\right)>0, \quad(1 \leq d \leq m) \tag{5.11} \end{equation*}

θ(F)\theta(F) will be called stationary of order dd for F=F0F=F_{0}.

The Variance of a U-statistic: i.i.d. Case

If (α1,⋯ ,αm)\left(\alpha_{1}, \cdots, \alpha_{m}\right) and (β1,⋯ ,βm)\left(\beta_{1}, \cdots, \beta_{m}\right) are two sets of mm different integers, 1≤αi1 \leq \alpha_{i}, βi≤n\beta_{i} \leq n, and cc is the number of integers common to the two sets, we have, by the symmetry of Ψ\Psi,

E{Ψ(Xα1,⋯ ,Xαm)Ψ(Xβ1,⋯ ,Xβm)}=ζc\begin{equation*} E\left\{\Psi\left(X_{\alpha_{1}}, \cdots, X_{\alpha_{m}}\right) \Psi\left(X_{\beta_{1}}, \cdots, X_{\beta_{m}}\right)\right\}=\zeta_{c} \tag{5.12} \end{equation*}

If the variance of UU exists, it is equal to

σ2(U)=(nm)−2E{Σ′Ψ(Xα1,⋯ ,Xαm)}2=(nm)−2∑c=0mΣ(c)E{Ψ(Xα1,⋯ ,Xαm)Ψ(Xβ1,⋯ ,Xβm)}\begin{aligned} \sigma^{2}(U) & =\left(\begin{array}{c}n \\m\end{array}\right)^{-2} E\left\{\Sigma^{\prime} \Psi\left(X_{\alpha_{1}}, \cdots, X_{\alpha_{m}}\right)\right\}^{2} \\& =\left(\begin{array}{c}n \\m\end{array}\right)^{-2} \sum_{c=0}^{m} \Sigma^{(c)} E\left\{\Psi\left(X_{\alpha_{1}}, \cdots, X_{\alpha_{m}}\right) \Psi\left(X_{\beta_{1}}, \cdots, X_{\beta_{m}}\right)\right\} \end{aligned}

where Σ(c)\Sigma^{(c)} stands for summation over all subscripts such that

1≤α1<α2<⋯<αm≤n,1≤β1<β2<⋯<βm≤n1 \leq \alpha_{1}<\alpha_{2}<\cdots<\alpha_{m} \leq n, \quad 1 \leq \beta_{1}<\beta_{2}<\cdots<\beta_{m} \leq n

and exactly cc equations αi=βj\alpha_{i}=\beta_{j} are satisfied. By (5.12), each term in Σ(c)\Sigma^{(c)} is equal to ζc\zeta_{c}. The number of terms in Σ(c)\Sigma^{(c)} is easily seen to be

n(n−1)⋯(n−2m+c+1)c!(m−c)!(m−c)!=(mc)(n−mm−c)(nm)\frac{n(n-1) \cdots(n-2 m+c+1)}{c !(m-c) !(m-c) !}=\left(\begin{array}{l}m \\c\end{array}\right)\left(\begin{array}{l} n-m \\m-c\end{array}\right)\left(\begin{array}{l} n \\m\end{array}\right)

and hence, since ζ0=0\zeta_{0}=0,

σ2(U)=(nm)−1∑c=1m(mc)(n−mm−c)ζc(5.13)\sigma^{2}(U)=\left(\begin{array}{l} n \tag{5.13}\\m\end{array}\right)^{-1} \sum_{c=1}^{m}\left(\begin{array}{l}m \\c\end{array}\right)\left(\begin{array}{l}n-m \\ m-c\end{array}\right) \zeta_{c}

The Variance of a U-statistic: General Case

When the distributions of X1,⋯ ,XnX_{1}, \cdots, X_{n} are different, Fν(x)F_{\nu}(x) being the d.f. of XνX_{\nu}, let

θα1,⋯ ,αm=E{Φ(Xα1,⋯ ,Xαm)}\begin{equation*} \theta_{\alpha_{1}, \cdots, \alpha_{m}}=E\left\{\Phi\left(X_{\alpha_{1}}, \cdots, X_{\alpha_{m}}\right)\right\} \tag{5.14} \end{equation*}

Ψc(α1,⋯ ,αc)β1,⋯ ,βm−c(x1,⋯ ,xc)=E{Φ(x1,⋯ ,xc,Xβ1…,Xβm−c)}−θα1,⋯ ,αc,β1,⋯ ,βm−c,(c=1,⋯ ,m),\begin{align*} &\Psi_{c\left(\alpha_{1}, \cdots, \alpha_{c}\right) \beta_{1}, \cdots, \beta_{m-c}}\left(x_{1}, \cdots, x_{c}\right) \\ =&E\left\{\Phi\left(x_{1}, \cdots, x_{c}, X_{\beta_{1}} \ldots, X_{\beta_{m-c}}\right)\right\}-\theta_{\alpha_{1}, \cdots, \alpha_{c}, \beta_{1}, \cdots, \beta_{m-c}}, \tag{5.15}\\ &\qquad(c=1, \cdots, m), \end{align*}

ζc(α1,⋯ ,αc)β1,⋯ ,βm−c;γ1,⋯ ,γm−c=E{Ψc(α1,⋯ ,αc)β1,⋯ ,βm−c(Xα1,⋯ ,Xαc)Ψc(α1,⋯ ,αc)γ1,⋯ ,γm−c(Xα1,⋯ ,Xαc)}ζc,n=c!(m−c)!(m−c)!n(n−1)⋯(n−2m+c+1)Σc(α1,⋯ ,αc)β1,⋯ ,βm−c;γ1,⋯ ,γm−c\begin{align*} & \zeta_{c\left(\alpha_{1}, \cdots, \alpha_{c}\right) \beta_{1}, \cdots, \beta_{m-c} ; \gamma_{1}, \cdots, \gamma_{m-c}} \\ =&E\left\{\Psi_{c\left(\alpha_{1}, \cdots, \alpha_{c}\right) \beta_{1}, \cdots, \beta_{m-c}}\left(X_{\alpha_{1}}, \cdots, X_{\alpha_{c}}\right) \Psi_{c\left(\alpha_{1}, \cdots, \alpha_{c}\right) \gamma_{1}, \cdots, \gamma_{m-c}}\left(X_{\alpha_{1}}, \cdots, X_{\alpha_{c}}\right)\right\} \tag{5.16}\\ \zeta_{c, n}=&\frac{c !(m-c) !(m-c) !}{n(n-1) \cdots(n-2 m+c+1)} \Sigma_{c\left(\alpha_{1}, \cdots, \alpha_{c}\right) \beta_{1}, \cdots, \beta_{m-c} ; \gamma_{1}, \cdots, \gamma_{m-c}} \tag{5.17} \end{align*}

where the sum is extended over all subscripts α,β,γ\alpha, \beta, \gamma such that

1≤α1<⋯<αc≤n,1≤β1<⋯<βm−c≤n,1≤γ1<⋯γm−c≤nαi≠βj,αi≠γj,βi≠γj\begin{gathered} 1 \leq \alpha_{1}<\cdots<\alpha_{c} \leq n, \quad 1 \leq \beta_{1}<\cdots<\beta_{m-c} \leq n, \quad 1 \leq \gamma_{1}<\cdots \gamma_{m-c} \leq n \\ \alpha_{i} \neq \beta_{j}, \quad \alpha_{i} \neq \gamma_{j}, \quad \beta_{i} \neq \gamma_{j} \end{gathered}

Then the variance of UU is equal to

σ2(U)=(nm)−1∑c=1m(mc)(n−mm−c)ζc,n(5.18)\sigma^{2}(U)=\left(\begin{array}{l}n \tag{5.18}\\m \end{array}\right)^{-1} \sum_{c=1}^{m}\left(\begin{array}{l} m \\c\end{array}\right)\left(\begin{array}{l} n-m \\m-c \end{array}\right) \zeta_{c, n}

Properties of the Moments and the Variance

Returning to the case of identically distributed XX 's, we shall now prove some inequalities satisfied by ζ1,⋯ ,ζm\zeta_{1}, \cdots, \zeta_{m} and σ2(U)\sigma^{2}(U) which are contained in the following theorems:

Theorem 5.1 The quantities ζ1,⋯ ,ζm\zeta_{1}, \cdots, \zeta_{m} as defined by (5.9) satisfy the inequalities

0≤ζcc≤ζdd if 1≤c<d≤m\begin{equation*} 0 \leq \frac{\zeta_{c}}{c} \leq \frac{\zeta_{d}}{d} \quad \text { if } 1 \leq c<d \leq m \tag{5.19} \end{equation*}

Theorem 5.2 The variance σ2(Un)\sigma^{2}\left(U_{n}\right) of a UU-statistic Un=U(X1,⋯ ,Xn)U_{n}=U\left(X_{1}, \cdots, X_{n}\right), where X1,⋯ ,XnX_{1}, \cdots, X_{n} are independent and identically distributed, satisfies the inequalities

m2nζ1≤σ2(Un)≤mnζm\begin{equation*} \frac{m^{2}}{n} \zeta_{1} \leq \sigma^{2}\left(U_{n}\right) \leq \frac{m}{n} \zeta_{m} \tag{5.20} \end{equation*}

nσ2(Un)n \sigma^{2}\left(U_{n}\right) is a decreasing function of nn,

(n+1)σ2(Un+1)≤nσ2(Un),\begin{equation*} (n+1) \sigma^{2}\left(U_{n+1}\right) \leq n \sigma^{2}\left(U_{n}\right), \tag{5.21} \end{equation*}

which takes on its upper bound mζmm \zeta_{m} for n=mn=m and tends to its lower bound m2ζ1m^{2} \zeta_{1} as nn increases:

σ2(Um)=ζmlim⁡n→∞nσ2(Un)=m2ζ1\begin{gather*} \sigma^{2}\left(U_{m}\right)=\zeta_{m} \tag{5.22}\\ \lim _{n \rightarrow \infty} n \sigma^{2}\left(U_{n}\right)=m^{2} \zeta_{1} \tag{5.23} \end{gather*}

If E{Ln}=θ(F)E\left\{L_{n}\right\}=\theta(F) is stationary of order ≥d−1\geq d-1 for the d.f. of Xα,(5.20)X_{\alpha},(5.20) may be replaced by

mdKn(m,d)ζd≤σ2(Un)≤Kn(m,d)ζm\begin{equation*} \frac{m}{d} K_{n}(m, d) \zeta_{d} \leq \sigma^{2}\left(U_{n}\right) \leq K_{n}(m, d) \zeta_{m} \tag{5.24} \end{equation*}

where

Kn(m,d)=(nm)−1∑c=dm(m−1c−1)(n−mm−c)(5.25)K_{n}(m, d)=\left(\begin{array}{l} n \tag{5.25}\\m \end{array}\right)^{-1} \sum_{c=d}^{m}\left(\begin{array}{l} m-1 \\c-1 \end{array}\right)\left(\begin{array}{l} n-m \\m-c \end{array}\right)

A Necessary and Sufficient Condition for the Existence of the Variance

(5.13) and (5.19) imply that a necessary and sufficient condition for the existence of σ2(U)\sigma^{2}(U) is the existence of

ζm=E{Φ2(X1,⋯ ,Xm)}−θ2\begin{equation*} \zeta_{m}=E\left\{\Phi^{2}\left(X_{1}, \cdots, X_{m}\right)\right\}-\theta^{2} \tag{5.26} \end{equation*}

or that of E{Φ2(X1,⋯ ,Xm)}E\left\{\Phi^{2}\left(X_{1}, \cdots, X_{m}\right)\right\}.

If ζ1>0,σ2(U)\zeta_{1}>0, \sigma^{2}(U) is of order n−1n^{-1}.

If θ(F)\theta(F) is stationary of order dd for F=F0F=F_{0}, that is, if (5.11) is satisfied, σ2(U)\sigma^{2}(U) is of order n−d−1n^{-d-1}. Only if, for some F=F0,θ(F)F=F_{0}, \theta(F) is stationary of order mm, where mm is the degree of θ(F)\theta(F), we have σ2(U)=0\sigma^{2}(U)=0, and UU is equal to a constant with probability 1.

Lemma 5.1

For proving Theorem 5.1 we shall require the following:

Lemma 5.1. If

δd=ζd−(d1)ζd−1+(d2)ζd−2⋯+(−1)d−1(dd−1)ζ1(5.27)\delta_{d}=\zeta_{d}-\left(\begin{array}{l} d \tag{5.27}\\1 \end{array}\right) \zeta_{d-1}+\left(\begin{array}{l} d \\2 \end{array}\right) \zeta_{d-2} \cdots+(-1)^{d-1}\left(\begin{array}{c} d \\d-1 \end{array}\right) \zeta_{1}

we have

δd≥0,(d=1,⋯ ,m)6\begin{equation*} \delta_{d} \geq 0, \quad(d=1, \cdots, m)^{6} \tag{5.28} \end{equation*}

and

ζd=δd+(d1)δd−1+⋯+(dd−1)δ1(5.29)\zeta_{d}=\delta_{d}+\left(\begin{array}{l} d \tag{5.29}\\1 \end{array}\right) \delta_{d-1}+\cdots+\left(\begin{array}{c} d \\d-1 \end{array}\right) \delta_{1}

Proof. (5.29) follows from (5.27) by induction.

For proving (5.28) let

η0=θ2,ηc=E{Φc2(X1,⋯ ,Xc)},(c=1,⋯ ,m)\eta_{0}=\theta^{2}, \quad \eta_{c}=E\left\{\Phi_{c}^{2}\left(X_{1}, \cdots, X_{c}\right)\right\}, \quad(c=1, \cdots, m)

Then, by (5.10),

ζc=ηc−η0\zeta_{c}=\eta_{c}-\eta_{0}

and on substituting this in (5.27) we have

δd=∑c=0d(−1)d−c(dc)ηc\delta_{d}=\sum_{c=0}^{d}(-1)^{d-c}\left(\begin{array}{l} d \\c \end{array}\right) \eta_{c}

From (5.9) it is seen that (5.28) is true for d=1d=1. Suppose that (5.28) holds for 1,⋯ ,d−11, \cdots, d-1. Then (5.28) will be shown to hold for dd.

Let

Φˉ0(x1)=Φ1(x1)−θ,Φˉc(x1,x2,⋯ ,xc+1),(c=1,⋯ ,d−1)=Φc+1(x1,⋯ ,xc+1)−Φc(x2,⋯ ,xc+1).\begin{aligned} &\bar{\Phi}_{0}\left(x_{1}\right)=\Phi_{1}\left(x_{1}\right)-\theta, \\ &\bar{\Phi}_{c}\left(x_{1}, x_{2}, \cdots, x_{c+1}\right), \quad(c=1, \cdots, d-1) \\ =&\Phi_{c+1}\left(x_{1}, \cdots, x_{c+1}\right)-\Phi_{c}\left(x_{2}, \cdots, x_{c+1}\right). \end{aligned}

For an arbitrary fixed x1x_{1}, let

ηˉc(x1)=E{Φˉc2(x1,X2,⋯ ,Xc+1)},(c=0,⋯ ,d−1)\bar{\eta}_{c}\left(x_{1}\right)=E\left\{\bar{\Phi}_{c}^{2}\left(x_{1}, X_{2}, \cdots, X_{c+1}\right)\right\}, \quad(c=0, \cdots, d-1)

Then, by induction hypothesis,

δˉd−1(x1)=∑c=0d−1(−1)d−1−c(d−1c)ηˉc(x1)≥0\bar{\delta}_{d-1}\left(x_{1}\right)=\sum_{c=0}^{d-1}(-1)^{d-1-c}\left(\begin{array}{c} d-1 \\c \end{array}\right) \bar{\eta}_{c}\left(x_{1}\right) \geq 0

for any fixed x1x_{1}.

Now,

E{ηˉc(X1)}=ηc+1−ηcE\left\{\bar{\eta}_{c}\left(X_{1}\right)\right\}=\eta_{c+1}-\eta_{c}

and hence

E{δˉd−1(X1)}=∑c=0d−1(−1)d−1−c(d−1c)(ηc+1−ηc)=∑c=0d(−1)d−c(dc)ηc=δd\begin{align*} E\left\{\bar{\delta}_{d-1}\left(X_{1}\right)\right\}&=\sum_{c=0}^{d-1}(-1)^{d-1-c}\left(\begin{array}{c} d-1 \\c \end{array}\right)\left(\eta_{c+1}-\eta_{c}\right)\\ &=\sum_{c=0}^{d}(-1)^{d-c}\left(\begin{array}{l} d \\c \end{array}\right) \eta_{c}=\delta_{d} \end{align*}

The proof of Lemma 5.1 is complete.

Proof of Theorem 5.1

By (5.29) we have for c<dc<d

cζd−dζc=c∑a=1d(da)δa−d∑a=1c(ca)δa=∑a=1c[c(da)−d(ca)]δa+c∑a=c+1d(da)δa\begin{align*} c \zeta_{d}-d \zeta_{c} & =c \sum_{a=1}^{d}\left(\begin{array}{l}d \\a \end{array}\right) \delta_{a}-d \sum_{a=1}^{c}\left(\begin{array}{l}c \\a \end{array}\right) \delta_{a} \\ & =\sum_{a=1}^{c}\left[c\left(\begin{array}{l}d \\a \end{array}\right)-d\left(\begin{array}{l}c \\a \end{array}\right)\right] \delta_{a}+c \sum_{a=c+1}^{d}\left(\begin{array}{l}d \\a \end{array}\right) \delta_{a} \tag{5.30} \end{align*}

From (5.28), and since c(da)−d(ca)≥0c\left(\begin{array}{l}d \\ a\end{array}\right)-d\left(\begin{array}{l}c \\ a\end{array}\right) \geq 0 if 1≤a≤c≤d1 \leq a \leq c \leq d, it follows that each term in the two sums of (5.30) is not negative. This, in connection with (5.9) proves Theorem 5.1.

Proof of Theorem 5.2.

From (5.19) we have

cζ1≤ζc≤cmζm,(c=1,⋯ ,m)c \zeta_{1} \leq \zeta_{c} \leq \frac{c}{m} \zeta_{m}, \quad(c=1, \cdots, m)

Applying these inequalities to each term in (5.13) and using the identity

(nm)−1∑c=1mc(mc)(n−mm−c)=m2n(5.31)\left(\begin{array}{l} n \tag{5.31}\\m \end{array}\right)^{-1} \sum_{c=1}^{m} c\left(\begin{array}{l} m \\c \end{array}\right)\left(\begin{array}{l} n-m \\m-c \end{array}\right)=\frac{m^{2}}{n}

we obtain (5.20).

(5.22) and (5.23) follow immediately from (5.13).

For (5.21) we may write

Dn≥0\begin{equation*} D_{n} \geq 0 \tag{5.32} \end{equation*}

where

Dn=nσ2(Un)−(n+1)σ2(Un+1)D_{n}=n \sigma^{2}\left(U_{n}\right)-(n+1) \sigma^{2}\left(U_{n+1}\right)

Let

Dn=∑c=1mdn,cζcD_{n}=\sum_{c=1}^{m} d_{n, c} \zeta_{c}

Then we have from (5.13)

dn,c=n(mc)(n−mm−c)(nm)−1−(n+1)(mc)(n+1−mm−c)(n+1m)−1,\begin{align*} & d_{n, c}=n\left(\begin{array}{c} m \\c\end{array}\right)\left(\begin{array}{l} n-m \\m-c\end{array}\right)\left(\begin{array}{l}n \\m \end{array}\right)^{-1}-(n+1)\left(\begin{array}{c} m \\c\end{array}\right) \tag{5.33}\\ &\left(\begin{array}{c} n+1-m \\m-c\end{array}\right)\left(\begin{array}{c} n+1 \\m\end{array}\right)^{-1}, \end{align*}

or

dn,c=(mc)(n−m+1m−c)(n−m+1)−1(nm)−1{(c−1)n−(m−1)2},(1≤c≤m≤n).\begin{aligned} & d_{n, c}=\left(\begin{array}{c} m \\c \end{array}\right)\left(\begin{array}{c} n-m+1 \\m-c \end{array}\right)(n-m+1)^{-1}\left(\begin{array}{l} n \\m \end{array}\right)^{-1}\left\{(c-1) n-(m-1)^{2}\right\}, \\ &(1 \leq c \leq m \leq n). \end{aligned}

Putting

c0=1+[(m−1)2n]c_{0}=1+\left[\frac{(m-1)^{2}}{n}\right]

where [u][u] denotes the largest integer ≤u\leq u, we have

dn,c≤0 if c≤c0dn,c>0 if c>c0.\begin{array}{ll} d_{n, c} \leq 0 & \text { if } c \leq c_{0} \\ d_{n, c}>0 & \text { if } c>c_{0} . \end{array}

Hence, by (5.19),

dn,cζc≥1c0ζc0cdn,c,(c=1,⋯ ,m)d_{n, c} \zeta_{c} \geq \frac{1}{c_{0}} \zeta_{c_{0}} c d_{n, c}, \quad(c=1, \cdots, m)

and

Dn≥1c0ζc0∑c=1mcdn,cD_{n} \geq \frac{1}{c_{0}} \zeta_{c_{0}} \sum_{c=1}^{m} c d_{n, c}

By (5.33) and (5.31), the latter sum vanishes. This proves (5.32).

For the stationary case ζ1=⋯=ζd−1=0\zeta_{1}=\cdots=\zeta_{d-1}=0, (5.24) is a direct consequence of (5.13) and (5.19). The proof of Theorem 5.2 is complete.

Properties of the Covariance

Let's talk about the covariance of two U-statistics. Consider a set of gg U-statistics,

U(γ)=(nm(γ))−1Σ′Φ(γ)(Xα1,⋯ ,Xαm(γ)),(γ=1,⋯ ,g)U^{(\gamma)}=\left(\begin{array}{c} n \\m(\gamma) \end{array}\right)^{-1} \Sigma^{\prime} \Phi^{(\gamma)}\left(X_{\alpha_{1}}, \cdots, X_{\alpha_{m}(\gamma)}\right), \quad(\gamma=1, \cdots, g)

each U(γ)U^{(\gamma)} being a function of the same nn independent, identically distributed random vectors X1,⋯ ,XnX_{1}, \cdots, X_{n}. The function Φ(γ)\Phi^{(\gamma)} is assumed to be symmetric in its m(γ)m(\gamma) arguments (γ=1,⋯ ,g)(\gamma=1, \cdots, g).

Let

E{U(γ)}=E{Φ(γ)(X1,⋯ ,Xm(γ))}=θ(γ),(γ=1,⋯ ,g);Ψ(γ)(x1,⋯ ,xm(γ))=Φ(γ)(x1,⋯ ,xm(γ))−θ(γ),(γ=1,⋯ ,g);Ψc(γ)(x1,⋯ ,xc)=E{Ψ(γ)(x1,⋯ ,xc,Xc+1,⋯ ,Xm(γ))},(c=1,⋯ ,m(γ);γ=1,⋯ ,g);ζc(γ,δ)=E{Ψc(γ)(X1,⋯ ,Xc)Ψc(δ)(X1,⋯ ,Xc)},\begin{gather*} E\left\{U^{(\gamma)}\right\}=E\left\{\Phi^{(\gamma)}\left(X_{1}, \cdots, X_{m(\gamma)}\right)\right\}=\theta^{(\gamma)}, \quad(\gamma=1, \cdots, g) ; \\ \Psi^{(\gamma)}\left(x_{1}, \cdots, x_{m(\gamma)}\right)=\Phi^{(\gamma)}\left(x_{1}, \cdots, x_{m(\gamma)}\right)-\theta^{(\gamma)}, \quad(\gamma=1, \cdots, g) ; \tag{6.1}\\ \Psi_{c}^{(\gamma)}\left(x_{1}, \cdots, x_{c}\right)=E\left\{\Psi^{(\gamma)}\left(x_{1}, \cdots, x_{c}, X_{c+1}, \cdots, X_{m(\gamma)}\right)\right\}, \tag{6.2}\\ (c=1, \cdots, m(\gamma) ; \gamma=1, \cdots, g) ; \\ \zeta_{c}^{(\gamma, \delta)}=E\left\{\Psi_{c}^{(\gamma)}\left(X_{1}, \cdots, X_{c}\right) \Psi_{c}^{(\delta)}\left(X_{1}, \cdots, X_{c}\right)\right\}, \tag{6.3} \end{gather*}

(γ,δ=1,⋯ ,g)(\gamma, \delta=1, \cdots, g)

If, in particular, γ=δ\gamma=\delta, we shall write

ζc(γ)=ζc(γ,γ)=E{Ψc(γ)(X1,⋯ ,Xc)}2\begin{equation*} \zeta_{c}^{(\gamma)}=\zeta_{c}^{(\gamma, \gamma)}=E\left\{\Psi_{c}^{(\gamma)}\left(X_{1}, \cdots, X_{c}\right)\right\}^{2} \tag{6.4} \end{equation*}

Let

σ(U(γ),U(δ))=E{(U(γ)−θ(γ))(U(δ)−θ(δ))}\sigma\left(U^{(\gamma)}, U^{(\delta)}\right)=E\left\{\left(U^{(\gamma)}-\theta^{(\gamma)}\right)\left(U^{(\delta)}-\theta^{(\delta)}\right)\right\}

be the covariance of U(γ)U^{(\gamma)} and U(δ)U^{(\delta)}.

In a similar way as for the variance, we find, if m(γ)≤m(δ)m(\gamma) \leq m(\delta),

σ(U(γ),U(δ))=(nm(γ))−1∑c=1m(γ)(m(δ)c)(n−m(δ)m(γ)−c)ζc(γ,δ).(6.5)\sigma\left(U^{(\gamma)}, U^{(\delta)}\right)=\left(\begin{array}{c} n \tag{6.5}\\m(\gamma) \end{array}\right)^{-1} \sum_{c=1}^{m(\gamma)}\left(\begin{array}{c}m(\delta) \\c \end{array}\right)\left(\begin{array}{c} n-m(\delta) \\m(\gamma)-c \end{array}\right) \zeta_{c}^{(\gamma, \delta)} .

The right hand side is easily seen to be symmetric in γ,δ\gamma, \delta.

For γ=δ,(6.5)\gamma=\delta,(6.5) is the variance of U(γ)U^{(\gamma)} (cf. (5.13)).

We have from (5.23) and (6.5)

lim⁡n→∞nσ2(U(γ))=m2(γ)ξ1(γ)lim⁡n→∞nσ(U(γ),U(δ))=m(γ)m(δ)ξ1(γ,δ).\begin{aligned} \lim _{n \rightarrow \infty} n \sigma^{2}\left(U^{(\gamma)}\right) & =m^{2}(\gamma) \xi_{1}^{(\gamma)} \\ \lim _{n \rightarrow \infty} n \sigma\left(U^{(\gamma)}, U^{(\delta)}\right) & =m(\gamma) m(\delta) \xi_{1}^{(\gamma, \delta)} . \end{aligned}

Hence, if ζ1(γ)≠0\zeta_{1}^{(\gamma)} \neq 0 and ζ1(δ)≠0\zeta_{1}^{(\delta)} \neq 0, the product moment correlation ρ(U(γ),U(δ))\rho\left(U^{(\gamma)}, U^{(\delta)}\right) between U(γ)U^{(\gamma)} and U(δ)U^{(\delta)} tends to the limit

lim⁡n→∞ρ(U(γ),U(δ))=ζ1(γ,δ)ζ1(γ)ζ1(δ)\begin{equation*} \lim _{n \rightarrow \infty} \rho\left(U^{(\gamma)}, U^{(\delta)}\right)=\frac{\zeta_{1}^{(\gamma, \delta)}}{\sqrt{\zeta_{1}^{(\gamma)} \zeta_{1}^{(\delta)}}} \tag{6.6} \end{equation*}

The Limit Theorems: i.i.d. Case

In this section the vectors XαX_{\alpha} will be assumed to be identically distributed.

Notes:
Converge of the Distribution Function:
A sequence of d.f.'s F1(x)F_{1}(x), F2(x),⋯F_{2}(x), \cdots converges to a d.f. F(x)F(x) if lim⁡Fn(x)=F(x)\lim F_{n}(x)=F(x) in every point at which the one-dimensional marginal limiting d.f.'s are continuous.

Singularity of the Distribution:
A gg-variate normal distribution is called non-singular if the rank rr of its covariance matrix is equal to gg, and singular if r<gr<g.

LEMMA 7.1. Let V1,V2,⋯V_{1}, V_{2}, \cdots be an infinite sequence of random vectors Vn=V_{n}= (Vn(1),⋯ ,Vn(g))\left(V_{n}^{(1)}, \cdots, V_{n}^{(g)}\right), and suppose that the d.f. Fn(v)F_{n}(v) of VnV_{n} tends to a d.f. F(v)F(v) as n→∞n \rightarrow \infty. Let Vn(γ)′=Vn(γ)+dn(γ)V_{n}^{(\gamma)^{\prime}}=V_{n}^{(\gamma)}+d_{n}^{(\gamma)}, where

lim⁡n→∞E{dn(γ)}2=0,(γ=1,⋯ ,g)\begin{equation*} \lim _{n \rightarrow \infty} E\left\{d_{n}^{(\gamma)}\right\}^{2}=0, \quad(\gamma=1, \cdots, g) \tag{7.1} \end{equation*}

Then the d.f. of Vn′=(Vn(1),⋯ ,Vn(g))V_{n}^{\prime}=\left(V_{n}^{(1)}, \cdots, V_{n}^{(g)}\right) tends to F(v)F(v).

The Limit Theorem 7.1 and 7.2

Theorem 7.1. Let X1,⋯ ,XnX_{1}, \cdots, X_{n} be nn independent, identically distributed random vectors,

Xα=(Xα(1),⋯ ,Xα(r)),(α=1,⋯ ,n)X_{\alpha}=\left(X_{\alpha}^{(1)}, \cdots, X_{\alpha}^{(r)}\right), \quad(\alpha=1, \cdots, n)

Let

Φ(γ)(x1,⋯ ,xm(γ)),(γ=1,⋯ ,g),\Phi^{(\gamma)}\left(x_{1}, \cdots, x_{m(\gamma)}\right), \quad(\gamma=1, \cdots, g),

be gg real-valued functions not involving n,Φ(γ)n, \Phi^{(\gamma)} being symmetric in its m(γ)(≤n)m(\gamma)(\leq n) vector arguments xα=(xα(1),⋯ ,xα(r)),(α=1,⋯ ,m(γ);γ=1,⋯ ,g)x_{\alpha}=\left(x_{\boldsymbol{\alpha}}^{(1)}, \cdots, x_{\alpha}^{(r)}\right),(\alpha=1, \cdots, m(\gamma) ; \gamma=1, \cdots, g). Define

U(γ)=(nm(γ))−1Σ′Φ(γ)(Xα1,⋯ ,Xαm(γ)),(γ=1,⋯ ,g)(7.2)U^{(\gamma)}=\left(\begin{array}{c} n \tag{7.2}\\m(\gamma) \end{array}\right)^{-1} \Sigma^{\prime} \Phi^{(\gamma)}\left(X_{\alpha_{1}}, \cdots, X_{\alpha_{m}(\gamma)}\right), \quad(\gamma=1, \cdots, g)

where the summation is over all subscripts such that 1≤α1<⋯<αm(γ)≤n1 \leq \alpha_{1}<\cdots<\alpha_{m(\gamma)} \leq n. Then, if the expected values

θ(γ)=E{Φ(γ)(X1,⋯ ,Xm(γ))},(γ=1,⋯ ;g)\begin{equation*} \theta^{(\gamma)}=E\left\{\Phi^{(\gamma)}\left(X_{1}, \cdots, X_{m(\gamma)}\right)\right\}, \quad(\gamma=1, \cdots ; g) \tag{7.3} \end{equation*}

and

E{Φ(γ)(X1,⋯ ,Xm(γ))}2,(γ=1,⋯ ,g)\begin{equation*} E\left\{\Phi^{(\gamma)}\left(X_{1}, \cdots, X_{m(\gamma)}\right)\right\}^{2}, \quad(\gamma=1, \cdots, g) \tag{7.4} \end{equation*}

exist, the joint d.f. of

n(U(1)−θ(1)),⋯ ,n(U(g)−θ(g))\sqrt{n}\left(U^{(1)}-\theta^{(1)}\right), \cdots, \sqrt{n}\left(U^{(g)}-\theta^{(g)}\right)

tends, as n→∞n \rightarrow \infty, to the g-variate normal d.f. with zero means and covariance matrix (m(γ)m(δ)ζ1(γ,δ))\left(m(\gamma) m(\delta) \zeta_{1}^{(\gamma, \delta)}\right), where ζ1(γ,δ)\zeta_{1}^{(\gamma, \delta)} is defined by (6.3). The limiting distribution is non-singular if the determinant ∣ζ1(γ,δ)∣\left|\zeta_{1}^{(\gamma, \delta)}\right| is positive.

According to Theorem 5.2, σ2(U)\sigma^{2}(U) exceeds its asymptotic value m2ζ1/nm^{2} \zeta_{1} / n for any finite nn. Hence, when nn is large but finite, Theorem 7.1 underestimate the variance of UU. And for such cases the following theorem, which is an immediate consequence of Theorem 7.1, will be more useful.

Theorem 7.2. Under the conditions of Theorem 7.1, and if

ζ1(γ)>0,(γ=1,⋯ ,g)\zeta_{1}^{(\gamma)}>0, \quad(\gamma=1, \cdots, g)

the joint d.f. of

(U(1)−θ(1))/σ(U(1)),⋯ ,(U(g)−θ(g))/σ(U(g))\left(U^{(1)}-\theta^{(1)}\right) / \sigma\left(U^{(1)}\right), \cdots,\left(U^{(g)}-\theta^{(g)}\right) / \sigma\left(U^{(g)}\right)

tends, as n→∞n \rightarrow \infty, to the gg-variate normal d.f. with zero means and covariance matrix (ρ(γ,δ))\left(\rho^{(\gamma, \delta)}\right), where

ρ(γ,δ)=lim⁡n→∞σ(U(γ),U(δ))σ(U(γ))σ(U(δ))=ζ1(γ,δ)ζ1(γ)ζ1(δ),(γ,δ=1,⋯ ,g).\rho^{(\gamma, \delta)}=\lim _{n \rightarrow \infty} \frac{\sigma\left(U^{(\gamma)}, U^{(\delta)}\right)}{\sigma\left(U^{(\gamma)}\right) \sigma\left(U^{(\delta)}\right)}=\frac{\zeta_{1}^{(\gamma, \delta)}}{\sqrt{\zeta_{1}^{(\gamma)} \zeta_{1}^{(\delta)}}}, \quad(\gamma, \delta=1, \cdots, g).

Proof of Theorem 7.1. The existence of (7.4) entails that of

ζm(γ)=E{Φ(γ)(X1,⋯ ,Xm(γ))}2−(θ(γ))2\zeta_{m}^{(\gamma)}=E\left\{\Phi^{(\gamma)}\left(X_{1}, \cdots, X_{m(\gamma)}\right)\right\}^{2}-\left(\theta^{(\gamma)}\right)^{2}

which, by (5.19), (5.20) and (6.6), is sufficient for the existence of

ζ1(γ),⋯ ,ζm−1(γ), of σ2(U(γ)), and of ζ1(γ,δ)≤ζ1(γ)ζ1(δ)\zeta_{1}^{(\gamma)}, \cdots, \zeta_{m-1}^{(\gamma)} \text {, of } \sigma^{2}\left(U^{(\gamma)}\right) \text {, and of } \zeta_{1}^{(\gamma, \delta)} \leq \sqrt{\zeta_{1}^{(\gamma)} \zeta_{1}^{(\delta)}}

Now, consider the gg quantities

Y(γ)=m(γ)n∑α=1nΨ1(γ)(Xα),(γ=1,⋯ ,g)Y^{(\gamma)}=\frac{m(\gamma)}{\sqrt{n}} \sum_{\alpha=1}^{n} \Psi_{1}^{(\gamma)}\left(X_{\alpha}\right), \quad(\gamma=1, \cdots, g)

where Ψ1(γ)(x)\Psi_{1}^{(\gamma)}(x) is defined by (6.2). Y(1),⋯ ,Y(g)\quad Y^{(1)}, \cdots, Y^{(g)} are sums of nn independent, random variables with zero means, whose covariance matrix, by virtue of (6.3), is

{σ(Y(γ),Y(δ))}={m(γ)m(δ)ξ1(γ,δ)}\begin{equation*} \left\{\sigma\left(Y^{(\gamma)}, Y^{(\delta)}\right)\right\}=\left\{m(\gamma) m(\delta) \xi_{1}^{(\gamma, \delta)}\right\} \tag{7.5} \end{equation*}

By the Central Limit Theorem for vectors (cf. Cramer [1, p. 112]), the joint d.f. of (Y(1),⋯ ,Y(ρ))\left(Y^{(1)}, \cdots, Y^{(\rho)}\right) tends to the normal gg-variate d.f. with the same means and covariances.

Theorem 7.1 will be proved by showing that the gg random variables

Z(γ)=n(U(γ)−θ(γ)),(γ=1,⋯ ,g),\begin{equation*} Z^{(\gamma)}=\sqrt{n}\left(U^{(\gamma)}-\theta^{(\gamma)}\right), \quad(\gamma=1, \cdots, g), \tag{7.6} \end{equation*}

have the same joint limiting distribution as Y(1),⋯ ,Y(g)Y^{(1)}, \cdots, Y^{(g)}.

According to Lemma 7.1 it is sufficient to show that

lim⁡n→∞E(Z(γ)−Y(γ))2=0,(γ=1,⋯ ,n)\begin{equation*} \lim _{n \rightarrow \infty} E\left(Z^{(\gamma)}-Y^{(\gamma)}\right)^{2}=0, \quad(\gamma=1, \cdots, n) \tag{7.7} \end{equation*}

For proving (7.7), write

E{Z(γ)−Y(γ)}2=E{Z(γ)}2+E{Y(γ)}2−2E{Z(γ)Y(γ)}\begin{equation*} E\left\{Z^{(\gamma)}-Y^{(\gamma)}\right\}^{2}=E\left\{Z^{(\gamma)}\right\}^{2}+E\left\{Y^{(\gamma)}\right\}^{2}-2 E\left\{Z^{(\gamma)} Y^{(\gamma)}\right\} \tag{7.8} \end{equation*}

By (5.13) we have

E{Z(γ)}2=nσ2(U(γ))=m2(γ)ζ1(γ)+O(n−1)\begin{equation*} E\left\{Z^{(\gamma)}\right\}^{2}=n \sigma^{2}\left(U^{(\gamma)}\right)=m^{2}(\gamma) \zeta_{1}^{(\gamma)}+O\left(n^{-1}\right) \tag{7.9} \end{equation*}

and from (7.5),

E{Y(γ)}2=m2(γ)ζ1(γ)\begin{equation*} E\left\{Y^{(\gamma)}\right\}^{2}=m^{2}(\gamma) \zeta_{1}^{(\gamma)} \tag{7.10} \end{equation*}

By (7.2) and (6.1) we may write for (7.6)

Z(γ)=n(nm(γ))−1Σ′Ψ(γ)(Xα1,⋯ ,Xαm(γ))Z^{(\gamma)}=\sqrt{n}\left(\begin{array}{c} n \\m(\gamma) \end{array}\right)^{-1} \Sigma^{\prime} \Psi^{(\gamma)}\left(X_{\alpha_{1}}, \cdots, X_{\alpha_{m}(\gamma)}\right)

and hence

E{Z(γ)Y(γ)}=m(γ)(nm(γ))−1∑α=1nΣ′E{Ψ1(γ)(Xα)Ψ(γ)(Xα1,⋯ ,Xαm(γ))}.E\left\{Z^{(\gamma)} Y^{(\gamma)}\right\}=m(\gamma)\left(\begin{array}{c} n \\m(\gamma) \end{array}\right)^{-1} \sum_{\alpha=1}^{n} \Sigma^{\prime} E\left\{\Psi_{1}^{(\gamma)}\left(X_{\alpha}\right) \Psi^{(\gamma)}\left(X_{\alpha_{1}}, \cdots, X_{\alpha_{m}(\gamma)}\right)\right\}.

The term

E{Ψ1(γ)(Xα)Ψ(γ)(Xα1,⋯ ,Xαm(γ))}E\left\{\Psi_{1}^{(\gamma)}\left(X_{\alpha}\right) \Psi^{(\gamma)}\left(X_{\alpha_{1}}, \cdots, X_{\alpha_{m}(\gamma)}\right)\right\}

is =ζ1(γ)=\zeta_{1}^{(\gamma)} if

α1=α or α2=α⋯ or αm(γ)=α\begin{equation*} \alpha_{1}=\alpha \quad \text { or } \quad \alpha_{2}=\alpha \cdots \quad \text { or } \quad \alpha_{m(\gamma)}=\alpha \tag{7.11} \end{equation*}

and 0 otherwise. For a fixed α\alpha, the number of sets⁡{α1,⋯ ,αm(γ)}\operatorname{sets}\left\{\alpha_{1}, \cdots, \alpha_{m(\gamma)}\right\} such that 1≤α1<⋯<αm(γ)≤n1 \leq \alpha_{1}<\cdots<\alpha_{m(\gamma)} \leq n and (7.11) is satisfied, is (n−1m(γ)−1)\left(\begin{array}{c}n-1 \\ m(\gamma)-1\end{array}\right). Thus,

E{Z(γ)Y(γ)}=m(γ)(nm(γ))−1n(n−1m(γ)−1)ζ1(γ)=m2(γ)ζ1(γ)(7.12)E\left\{Z^{(\gamma)} Y^{(\gamma)}\right\}=m(\gamma)\left(\begin{array}{c} n \tag{7.12}\\m(\gamma) \end{array}\right)^{-1} n\left(\begin{array}{c} n-1 \\m(\gamma)-1 \end{array}\right) \zeta_{1}^{(\gamma)}=m^{2}(\gamma) \zeta_{1}^{(\gamma)}

On inserting (7.9), (7.10), and (7.12) in (7.8), we see that (7.7) is true.

The proof of Theorem 7.1 is complete.

The Limit Theorem 7.3: Extension Theorem 7.1 to a Larger Class of Statistics

The application of Lemma 7.1 leads immediately to the following extension of Theorem 7.1 to a larger class of statistics.

Theorem 7.3. Let

U(g)′=U(g)+bn(γ)n,(γ=1,⋯ ,g)\begin{equation*} U^{(g)^{\prime}}=U^{(g)}+\frac{b_{n}^{(\gamma)}}{\sqrt{n}}, \quad(\gamma=1, \cdots, g) \tag{7.13} \end{equation*}

where U(γ)U^{(\gamma)} is defined by (7.2) and bn(γ)b_{n}^{(\gamma)} is a random variable. If the conditions of Theorem 7.1 are satisfied, and lim⁡E{bn(γ)}2=0,(γ=1,⋯ ,g)\lim E\left\{b_{n}^{(\gamma)}\right\}^{2}=0,(\gamma=1, \cdots, g), then the joint distribution of

n(U(1)′−θ(1)),⋯ ,n(U(g)′−θ(g))\sqrt{n}\left(U^{(1) \prime}-\theta^{(1)}\right), \cdots, \sqrt{n}\left(U^{(g) \prime}-\theta^{(g)}\right)

tends to the normal distribution with zero means and covariance matrix

{m(γ)m(δ)ζ1(γ,δ)}\left\{m(\gamma) m(\delta) \zeta_{1}^{(\gamma, \delta)}\right\}

The Limit Theorem 7.4: Extension to Sample Functionals

The theorem 7.3 applies, in particular, to the regular functionals θ(S)\theta(S) of the sample d.f.,

θ(S)=1nm∑α1=1n…∑αm=1nΦ(Xα1,⋯ ,Xαm)\theta(S)=\frac{1}{n^{m}} \sum_{\alpha_{1}=1}^{n} \ldots \sum_{\alpha_{m}=1}^{n} \Phi\left(X_{\alpha_{1}}, \cdots, X_{\alpha_{m}}\right)

in the case that the variance of θ(S)\theta(S) exists. For we may write

nmθ(S)=(nm)U+Σ∗Φ(Xα1,⋯ ,Xαm)n^{m} \theta(S)=\left(\begin{array}{l} n \\m \end{array}\right) U+\Sigma^{*} \Phi\left(X_{\alpha_{1}}, \cdots, X_{\alpha_{m}}\right)

where the sum Σ∗\Sigma^{*} is extended over all mm-tuples (α1,⋯ ,αm)\left(\alpha_{1}, \cdots, \alpha_{m}\right) in which at least one equality αi=αj(i≠j)\alpha i=\alpha_{j}(i \neq j) is satisfied. The number of terms in Σ∗\Sigma^{*} is of order nm−1n^{m-1}. Hence

θ(S)−U=1nD\theta(S)-U=\frac{1}{n} D

where the expected value E{D2}E\left\{D^{2}\right\}, whose existence follows from that of σ2{θ(S)}\sigma^{2}\{\theta(S)\}, is bounded for n→∞n \rightarrow \infty. Thus, if we put U(γ)′=θ(γ)(S)U^{(\gamma)^{\prime}}=\theta^{(\gamma)}(S), the conditions of Theorem 7.3 are fulfilled. We may summarize this result as follows:

Theorem 7.4. Let X1,⋯ ,XnX_{1}, \cdots, X_{n} be a random sample from an r-variate population with d.f. F(x)=F(x(1),⋯ ,x(r))F(x)=F\left(x^{(1)}, \cdots, x^{(r)}\right), and let

θ(γ)(F)=∫⋯∫Φ(γ)(x1,⋯ ,xm(γ))dF(x1)⋯dF(xm(γ)),(γ=1,⋯ ,g)\theta^{(\gamma)}(F)=\int \cdots \int \Phi^{(\gamma)}\left(x_{1}, \cdots, x_{m(\gamma)}\right) d F\left(x_{1}\right) \cdots d F\left(x_{m}{ }^{(\gamma)}\right), \quad(\gamma=1, \cdots, g),

be gg regular functionals of FF, where Φ(γ)(x1,⋯ ,xm(γ))\Phi^{(\gamma)}\left(x_{1}, \cdots, x_{m(\gamma)}\right) is symmetric in the vectors x1,⋯ ,xm(γ)x_{1}, \cdots, x_{m(\gamma)} and does not involve nn. If S(x)S(x) is the d.f. of the random sample, and if the variance of

θ(γ)(S)=1nm∑α1=1n⋯∑αm(γ)=1nΦ(γ)(Xα1,⋯ ,Xαm(γ))\theta^{(\gamma)}(S)=\frac{1}{n^{m}} \sum_{\alpha_{1}=1}^{n} \cdots \sum_{\alpha_{m}(\gamma)=1}^{n} \Phi^{(\gamma)}\left(X_{\alpha_{1}}, \cdots, X_{\alpha_{m}(\gamma)}\right)

exists, the joint d.f. of

n{θ(1)(S)−θ(1)(F)},⋯ ,n{θ(θ)(S)−θ(g)(F)}\sqrt{n}\left\{\theta^{(1)}(S)-\theta^{(1)}(F)\right\}, \cdots, \sqrt{n}\left\{\theta^{(\theta)}(S)-\theta^{(g)}(F)\right\}

tends to the g-variate normal d.f. with zero means and covariance matrix

{m(γ)m(δ)ζ1(γ,δ)}\left\{m(\gamma) m(\delta) \zeta_{1}^{(\gamma, \delta)}\right\}

The Limit Theorem 7.5: Extension to Functions of Statistics

The following theorem is concerned with the asymptotic distribution of a function of statistics of the form UU or U′U^{\prime}.

Theorem 7.5. Let U′=(U(1)′,⋯ ,U(g)′)U^{\prime}=\left(U^{(1)^{\prime}}, \cdots, U^{(g) \prime}\right) be a random vector, where U(γ)U^{(\gamma)} is defined by (7.13), and suppose that the conditions of Theorem 7.3 are satisfied. If the function h(y)=h(y(1),⋯ ,y(g))h(y)=h\left(y^{(1)}, \cdots, y^{(g)}\right) does not involve nn and is continuous together with its second order partial derivatives in some neighborhood of the point (y)=(θ)=(y)=(\theta)= (θ(1),⋯ ,θ(g))\left(\theta^{(1)}, \cdots, \theta^{(g)}\right), then the distribution of the random variable n{h(U′)−h(θ)}\sqrt{n}\left\{h\left(U^{\prime}\right)-h(\theta)\right\} tends to the normal distribution with mean zero and variance

∑γ=1g∑δ=1gm(γ)m(δ)(∂h(y)∂y(γ))y=θ(∂h(y)∂y(δ))y=θζ1(γ,δ)\sum_{\gamma=1}^{g} \sum_{\delta=1}^{g} m(\gamma) m(\delta)\left(\frac{\partial h(y)}{\partial y^{(\gamma)}}\right)_{y=\theta}\left(\frac{\partial h(y)}{\partial y^{(\delta)}}\right)_{y=\theta} \zeta_{1}^{(\gamma, \delta)}

Applications to particular statistics

Example: Mean different and Coefficient of Concentration

If Y1,⋯ ,YnY_{1}, \cdots, Y_{n} are nn independent real-valued random variables, Gini's mean difference (without repetition) is defined by

d=1n(n−1)∑α≠β∣Yα−Yβ∣d=\frac{1}{n(n-1)} \sum_{\alpha \neq \beta}\left|Y_{\alpha}-Y_{\beta}\right|

If the YαY_{\alpha} 's have the same distribution FF, the mean of dd is

δ=∬∣y1−y2∣dF(y1)dF(y2)\delta=\iint\left|y_{1}-y_{2}\right| d F\left(y_{1}\right) d F\left(y_{2}\right)

and the variance, by (5.13) is

σ2(d)=2n(n−1){2ζ1(δ)(n−2)+ζ2(δ)}\sigma^{2}(d)=\frac{2}{n(n-1)}\left\{2 \zeta_{1}(\delta)(n-2)+\zeta_{2}(\delta)\right\}

where

ζ1(δ)=∫{∫∣y1−y2∣dF(y2)}2dF(y1)−δ2ζ2(δ)=∬(y1−y2)2dF(y1)dF(y2)−δ2=2σ2(Y)−δ2\begin{gather*} \zeta_{1}(\delta)=\int\left\{\int\left|y_{1}-y_{2}\right| d F\left(y_{2}\right)\right\}^{2} d F\left(y_{1}\right)-\delta^{2} \tag{9.1}\\ \zeta_{2}(\delta)=\iint\left(y_{1}-y_{2}\right)^{2} d F\left(y_{1}\right) d F\left(y_{2}\right)-\delta^{2}=2 \sigma^{2}(Y)-\delta^{2} \tag{9.2} \end{gather*}

By Theorem 7.1, n(d−δ)\sqrt{n}(d-\delta) is asymptotically normal if ζ2(δ)\zeta_{2}(\delta) exists.

If Y1,⋯ ,YnY_{1}, \cdots, Y_{n} do not assume negative values, the coefficient of concentration is defined by

G=d2YˉG=\frac{d}{2 \bar{Y}}

where Yˉ=ΣYα/n.G\bar{Y}=\Sigma Y_{\alpha} / n . \quad G is a function of two UU-statistics. If the YαY_{\alpha} 's are identically distributed, if E{Y2}E\left\{Y^{2}\right\} exists, and if μ=E{Y}>0\mu=E\{Y\}>0, then, by Theorem 7.5, n(G−δ/2μ)\sqrt{n}(G-\delta / 2 \mu) tends to be normally distributed with mean 0 and variance

δ24μ4ζ1(μ)−δμ3ζ1(μ,δ)+1μ2ζ1(δ)\frac{\delta^{2}}{4 \mu^{4}} \zeta_{1}(\mu)-\frac{\delta}{\mu^{3}} \zeta_{1}(\mu, \delta)+\frac{1}{\mu^{2}} \zeta_{1}(\delta)

where

ζ1(μ)=∫y2dF(y)−μ2=σ2(Y)ζ1(μ,δ)=∬y1∣y1−y2∣dF(y1)dF(y2)−μδ\begin{gathered} \zeta_{1}(\mu)=\int y^{2} d F(y)-\mu^{2}=\sigma^{2}(Y) \\ \zeta_{1}(\mu, \delta)=\iint y_{1}\left|y_{1}-y_{2}\right| d F\left(y_{1}\right) d F\left(y_{2}\right)-\mu \delta \end{gathered}

and ζ1(δ)\zeta_{1}(\delta) is given by (9.1).

References

[1]. W. Hoeffding, ‘A Class of Statistics with Asymptotically Normal Distribution’, Ann. Math. Statist., vol. 19, no. 3, pp. 293–325, Sep. 1948, doi: 10.1214/aoms/1177730196.

[2]. Shao J. Mathematical statistics[M]. Springer Science & Business Media, 2003.

[3]. Van der Vaart A. Asymptotic statistics[M]. Cambridge university press, 2000.

[1]. Hajek Projection

END