Notes on U Statistic

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

You can view the lecture notes on U-statistics.

• Basic Concepts and Motivating Examples
  • Functional, Kernel and Order
  • Symmetry of Kernel
  • Motivating Examples
  • Asymptotic Normality of U-statistic: A Simple Version
• U-statistic
  • Notations
  • Definition: U-statistic
• Asymptotic Normality of U-statistic
  • The Variance of a U-statistic
    • The Unbiased Estimator and Its Variance
    • Stationary Order of a Functional
    • The Variance of a U-statistic: i.i.d. Case
    • The Variance of a U-statistic: General Case
  • Properties of the Moments and the Variance
    • A Necessary and Sufficient Condition for the Existence of the Variance
    • Lemma 5.1
    • Proof of Theorems 5.1
    • Proof of Theorem 5.2.
  • Properties of the Covariance
  • The Limit Theorems: i.i.d. Case
    • The Limit Theorem 7.1 and 7.2
    • The Limit Theorem 7.3: Extension Theorem 7.1 to a Larger Class of Statistics
    • The Limit Theorem 7.4: Application to Sample Functionals
    • The Limit Theorem 7.5: Application to Functions of Statistics
• Applications to particular statistics
• References

Basic Concepts and Motivating Examples

Functional, Kernel and Order

Suppose that $\mathrm{\Phi }(x_1,\dots ,x_m)$ is a function of $m$ random variables and $X_1,\dots ,X_n$ are i.i.d. observations from c.d.f. $F(x)$. Assume $n>m$.

Make inference about
$$\theta =\theta (F)=E_F[\mathrm{\Phi }(X_1,\dots ,X_m)]$$

Note: $\theta$ is a functional of the distribution $F$. 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
$$\begin{array}{rl}U& ={\left({}_m^n\right)}^{-1}{\mathrm{\Sigma }}^{\prime }\mathrm{\Phi }(X_{i_1},\dots ,X_{i_m})\\ & =\frac{1}{n(n-1)\dots (n-m+1)}\sum _{1\le i_1<\dots <i_m\le n}\mathrm{\Phi }(X_{i_1},\dots ,X_{i_m})\end{array}$$
where ${\mathrm{\Sigma }}^{\prime }$ stands for summation over all permutations of $m$ integers $i_1,\dots ,i_m$ such that $1\le i_1<\dots <i_m\le n$.

Here, $U$ is a function of the sample $X_1,\dots ,X_n$ called a U-statistic. The $\mathrm{\Phi }$ function is called the kernel and $m$ is its order.

Symmetry of Kernel

For convenience, we assume that $\mathrm{\Phi }$ is symmetric in its arguments, which means
$$\mathrm{\Phi }(\dots ,x_i,\dots ,x_j,\dots )=\mathrm{\Phi }(\dots ,x_j,\dots ,x_i,\dots )$$

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 $\mathrm{\Phi }(x_1,\dots ,x_m)$ is not symmetric, there exist a symmetric ${\mathrm{\Phi }}_0(x_1,\dots ,x_m)$ such that
$${\mathrm{\Phi }}_0(x_1,\dots ,x_m)=\frac{1}{m!}\sum \mathrm{\Phi }(x_{{\alpha }_1},\dots ,x_{{\alpha }_m})$$
where the sum is over all permutations of $m$ integers $1,\dots ,m$.

Motivating Examples

Example 1: Let $m=1$ and $\mathrm{\Phi }(x)=x$. Then, $U=\sum _{i=1}^n{X}_i/n$ is the sample mean.

Example 2: Let $m=2$ and $\mathrm{\Phi }(x_1,x_2)=x_1^2-x_1{x}_2$. Then, $U=\sum _{1\le i<j\le n}(X_i^2-X_i{X}_j)/(n(n-1))$ is the sample variance. A symmetric kernel can be ${\mathrm{\Phi }}_0(x_1,x_2)=(x_1-x_2{)}^2/2$.

Example 3: Let $m=2$ and $\mathrm{\Phi }(x_1,x_2)=I(x_1+x_2>0)$. Then, $U=\sum _{1\le i<j\le 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 ${\zeta }_k=\mathbb{V}({\mathrm{\Phi }}_k(X_1,\dots ,X_k)),k=1,\dots ,m$. Suppose that the kernel $\mathrm{\Phi }$ satisfies $\mathbb{E}{\mathrm{\Phi }}^2(X_1,\dots ,X_m)<\mathrm{\infty }$. Assume that $0<{\zeta }_1<\mathrm{\infty }$. Then,
$$\frac{U-\theta }{\sqrt{\mathbb{V}(U)}}\stackrel{d}{\to }N(0,1)$$
where $\mathbb{V}(U)=\frac{1}{n}{m}^2{\zeta }_1+O(n^{-2})$.

U-statistic

Notations

• $X_1,\dots ,X_n$: $n$ independent random vectors with the same d.f. $F(x)=F(x^{(1)},\dots ,x^{(r)})$.
• $X_{\nu }=(X_{\nu }^{(1)},\dots ,X_{\nu }^{(r)})$: $r$-dimensional random vector.
• $x_1,\dots ,x_n$: sample of $n$ $r$-dimensional vectors.
• $\mathrm{\Phi }(x_1,\dots ,x_m)$: a symmetric function of $m(\le n)$ vector arguments.
• $\theta =\theta (F)$: functional of $F$.

Definition: U-statistic

Consider the function of the sample,

$$\begin{array}{}\text{(4.4)}& U(x_1,\cdots ,x_n)={\left(\begin{array}{c}n\\ m\end{array}\right)}^{-1}{\mathrm{\Sigma }}^{\prime }\mathrm{\Phi }(x_{{\alpha }_1},\cdots ,x_{{\alpha }_m})\end{array}$$

where the kernel $\mathrm{\Phi }$ is symmetric in its $m$ vector arguments and the sum ${\mathrm{\Sigma }}^{\prime }$ is extended over all subscripts $\alpha$ such that

$$1\le {\alpha }_1<{\alpha }_2<\cdots <{\alpha }_m\le n$$

Eq (4.4) can be driven from
$$\begin{array}{}\text{(4.1)}& U=U(x_1,\cdots ,x_n)=\frac{{\mathrm{\Phi }}_0(x_{{\alpha }_1},\cdots ,x_{{\alpha }_m})}{n(n-1)\cdots (n-m+1)}{\mathrm{\Sigma }}^{\prime \prime },\end{array}$$

where ${\mathrm{\Sigma }}^{\prime \prime }$ stands for summation over all permutations $({\alpha }_1,\cdots ,{\alpha }_m)$ of $m$ integers such that

$$\begin{array}{}\text{(4.2)}& 1\le {\alpha }_i\le n,{\alpha }_i\ne {\alpha }_j\text{ if }i\ne j,(i,j=1,\cdots ,m)\end{array}$$

Asymptotic Normality of U-statistic

The Variance of a U-statistic

The Unbiased Estimator and Its Variance

If $\theta =\theta (F)$, we have
$$EU=E\left\{\mathrm{\Phi }(X_1,\cdots ,X_m)\right\}=\theta$$

Let
$$\begin{array}{rl}\text{(5.2)}& {\mathrm{\Phi }}_c(x_1,\cdots ,x_c)& =E\left\{\mathrm{\Phi }(x_1,\cdots ,x_c,X_{c+1},\cdots ,X_m)\right\},(c& =1,\cdots ,m),\end{array}$$

where $x_1,\cdots ,x_c$ are arbitrary fixed vectors and the expected value is taken with respect to the random vectors $X_{c+1},\cdots ,X_m$. Then

$$\begin{array}{}\text{(5.3)}& {\mathrm{\Phi }}_{c-1}(x_1,\cdots ,x_{c-1})=E\left\{{\mathrm{\Phi }}_c(x_1,\cdots ,x_{c-1},X_c)\right\}\end{array}$$

and

$$\begin{array}{}\text{(5.4)}& E\left\{{\mathrm{\Phi }}_c(X_1,\cdots ,X_c)\right\}=\theta ,(c=1,\cdots ,m).\end{array}$$

Define

$$\begin{array}{}\text{(5.5)}& & \mathrm{\Psi }(x_1,\cdots ,x_m)=\mathrm{\Phi }(x_1,\cdots ,x_m)-\theta \text{(5.6)}& & {\mathrm{\Psi }}_c(x_1,\cdots ,x_c)={\mathrm{\Phi }}_c(x_1,\cdots ,x_c)-\theta ,(c=1,\cdots ,m).\end{array}$$

We have

$$\begin{array}{}\text{(5.7)}& {\mathrm{\Psi }}_{c-1}(x_1,\cdots ,x_{c-1})=E\left\{{\mathrm{\Psi }}_c(x_1,\cdots ,x_{c-1},X_c)\right\}\text{(5.8)}& E\left\{{\mathrm{\Psi }}_c(X_1,\cdots ,X_c)\right\}=E\left\{\mathrm{\Psi }(X_1,\cdots ,X_m)\right\}=0,(c=1,\cdots ,m).\end{array}$$

Suppose that the variance of ${\mathrm{\Psi }}_c(X_1,\cdots ,X_c)$ exists, and let

$$\begin{array}{}\text{(5.9)}& {\zeta }_0=0,{\zeta }_c=E\left\{{\mathrm{\Psi }}_c^2(X_1,\cdots ,X_c)\right\},(c=1,\cdots ,m)\end{array}$$

We have

$$\begin{array}{}\text{(5.10)}& {\zeta }_c=E\left\{{\mathrm{\Phi }}_c^2(X_1,\cdots ,X_c)\right\}-{\theta }^2\end{array}$$

Stationary Order of a Functional

If, for some parent distribution $F=F_0$ and some integer $d$, we have ${\zeta }_d\left(F_0\right)=0$, this means that ${\mathrm{\Psi }}_d(X_1,\cdots ,X_d)=0$ with probability 1. By (5.7) and (5.9), ${\zeta }_d=0$ implies ${\zeta }_1=\cdots ={\zeta }_{d-1}=0$.

If ${\zeta }_1\left(F_0\right)=0$, we shall say that the regular functional $\theta (F)$ is stationary for $F=F_0$. If

$$\begin{array}{}\text{(5.11)}& {\zeta }_1\left(F_0\right)=\cdots ={\zeta }_d\left(F_0\right)=0,{\zeta }_{d+1}\left(F_0\right)>0,(1\le d\le m)\end{array}$$

$\theta (F)$ will be called stationary of order $d$ for $F=F_0$.

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

If $({\alpha }_1,\cdots ,{\alpha }_m)$ and $({\beta }_1,\cdots ,{\beta }_m)$ are two sets of $m$ different integers, $1\le {\alpha }_i$, ${\beta }_i\le n$, and $c$ is the number of integers common to the two sets, we have, by the symmetry of $\mathrm{\Psi }$,

$$\begin{array}{}\text{(5.12)}& E\left\{\mathrm{\Psi }(X_{{\alpha }_1},\cdots ,X_{{\alpha }_m})\mathrm{\Psi }(X_{{\beta }_1},\cdots ,X_{{\beta }_m})\right\}={\zeta }_c\end{array}$$

If the variance of $U$ exists, it is equal to

$$\begin{array}{rl}{\sigma }^2(U)& ={\left(\begin{array}{c}n\\ m\end{array}\right)}^{-2}E{\left\{{\mathrm{\Sigma }}^{\prime }\mathrm{\Psi }(X_{{\alpha }_1},\cdots ,X_{{\alpha }_m})\right\}}^2\\ & ={\left(\begin{array}{c}n\\ m\end{array}\right)}^{-2}\sum _{c=0}^m{\mathrm{\Sigma }}^{(c)}E\left\{\mathrm{\Psi }(X_{{\alpha }_1},\cdots ,X_{{\alpha }_m})\mathrm{\Psi }(X_{{\beta }_1},\cdots ,X_{{\beta }_m})\right\}\end{array}$$

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

$$1\le {\alpha }_1<{\alpha }_2<\cdots <{\alpha }_m\le n,1\le {\beta }_1<{\beta }_2<\cdots <{\beta }_m\le n$$

and exactly $c$ equations

$${\alpha }_i={\beta }_j$$

are satisfied. By (5.12), each term in ${\mathrm{\Sigma }}^{(c)}$ is equal to ${\zeta }_c$. The number of terms in ${\mathrm{\Sigma }}^{(c)}$ is easily seen to be

$$\frac{n(n-1)\cdots (n-2m+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 ${\zeta }_0=0$,

$$\begin{array}{}\text{(5.13)}& {\sigma }^2(U)={\left(\begin{array}{l}n\\ 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\end{array}$$

The Variance of a U-statistic: General Case

When the distributions of $X_1,\cdots ,X_n$ are different, $F_{\nu }(x)$ being the d.f. of $X_{\nu }$, let

$$\begin{array}{}\text{(5.14)}& {\theta }_{{\alpha }_1,\cdots ,{\alpha }_m}=E\left\{\mathrm{\Phi }(X_{{\alpha }_1},\cdots ,X_{{\alpha }_m})\right\}\end{array}$$

$$\begin{array}{rl}& {\mathrm{\Psi }}_{c({\alpha }_1,\cdots ,{\alpha }_c){\beta }_1,\cdots ,{\beta }_{m-c}}(x_1,\cdots ,x_c)\\ \text{(5.15)}& =& E\left\{\mathrm{\Phi }(x_1,\cdots ,x_c,X_{{\beta }_1}\dots ,X_{{\beta }_{m-c}})\right\}-{\theta }_{{\alpha }_1,\cdots ,{\alpha }_c,{\beta }_1,\cdots ,{\beta }_{m-c}},& (c=1,\cdots ,m),\end{array}$$

$$\begin{array}{rl}& {\zeta }_{c({\alpha }_1,\cdots ,{\alpha }_c){\beta }_1,\cdots ,{\beta }_{m-c};{\gamma }_1,\cdots ,{\gamma }_{m-c}}\\ \text{(5.16)}& =& E\{{\mathrm{\Psi }}_{c({\alpha }_1,\cdots ,{\alpha }_c){\beta }_1,\cdots ,{\beta }_{m-c}}(X_{{\alpha }_1},\cdots ,X_{{\alpha }_c}){\mathrm{\Psi }}_{c({\alpha }_1,\cdots ,{\alpha }_c){\gamma }_1,\cdots ,{\gamma }_{m-c}}& (X_{{\alpha }_1},\cdots ,X_{{\alpha }_c})\}\\ \text{(5.17)}& {\zeta }_{c,n}=& \frac{c!(m-c)!(m-c)!}{n(n-1)\cdots (n-2m+c+1)}{\mathrm{\Sigma }}_{c({\alpha }_1,\cdots ,{\alpha }_c){\beta }_1,\cdots ,{\beta }_{m-c};{\gamma }_1,\cdots ,{\gamma }_{m-c}}\end{array}$$

where the sum is extended over all subscripts $\alpha ,\beta ,\gamma$ such that

$$\begin{array}{rl}1& \le {\alpha }_1<\cdots <{\alpha }_c\le n,1\le {\beta }_1<\cdots <{\beta }_{m-c}\le n,1\le {\gamma }_1<\cdots {\gamma }_{m-c}\le n\\ {\alpha }_i& \ne {\beta }_j,{\alpha }_i\ne {\gamma }_j,{\beta }_i\ne {\gamma }_j\end{array}$$

Then the variance of $U$ is equal to

$$\begin{array}{}\text{(5.18)}& {\sigma }^2(U)={\left(\begin{array}{l}n\\ 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}\end{array}$$

Properties of the Moments and the Variance

Returning to the case of identically distributed $X$ ‘s, we shall now prove some inequalities satisfied by ${\zeta }_1,\cdots ,{\zeta }_m$ and ${\sigma }^2(U)$ which are contained in the following theorems:

Theorem 5.1 The quantities ${\zeta }_1,\cdots ,{\zeta }_m$ as defined by (5.9) satisfy the inequalities

$$\begin{array}{}\text{(5.19)}& 0\le \frac{{\zeta }_c}{c}\le \frac{{\zeta }_d}{d}\text{ if }1\le c<d\le m\end{array}$$

Theorem 5.2 The variance ${\sigma }^2\left(U_n\right)$ of a U-statistic $U_n=U(X_1,\cdots ,X_n)$, where $X_1,\cdots ,X_n$ are independent and identically distributed, satisfies the inequalities

$$\begin{array}{}\text{(5.20)}& \frac{m^2}{n}{\zeta }_1\le {\sigma }^2\left(U_n\right)\le \frac{m}{n}{\zeta }_m\end{array}$$

$n{\sigma }^2\left(U_n\right)$ is a decreasing function of $n$,

$$\begin{array}{}\text{(5.21)}& (n+1){\sigma }^2\left(U_{n+1}\right)\le n{\sigma }^2\left(U_n\right),\end{array}$$

which takes on its upper bound $m{\zeta }_m$ for $n=m$ and tends to its lower bound $m^2{\zeta }_1$ as $n$ increases:

$$\begin{array}{}\text{(5.22)}& & {\sigma }^2\left(U_m\right)={\zeta }_m\text{(5.23)}& & \underset{n\to \mathrm{\infty }}{lim}n{\sigma }^2\left(U_n\right)=m^2{\zeta }_1\end{array}$$

If $E\left\{U_n\right\}=\theta (F)$ is stationary of order $\ge d-1$ for the d.f. of $X_{\alpha },(5.20)$ may be replaced by

$$\begin{array}{}\text{(5.24)}& \frac{m}{d}{K}_n(m,d){\zeta }_d\le {\sigma }^2\left(U_n\right)\le K_n(m,d){\zeta }_m\end{array}$$

where

$$\begin{array}{}\text{(5.25)}& K_n(m,d)={\left(\begin{array}{l}n\\ 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)\end{array}$$

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 ${\sigma }^2(U)$ is the existence of

$$\begin{array}{}\text{(5.26)}& {\zeta }_m=E\left\{{\mathrm{\Phi }}^2(X_1,\cdots ,X_m)\right\}-{\theta }^2\end{array}$$

or that of $E\left\{{\mathrm{\Phi }}^2(X_1,\cdots ,X_m)\right\}$.

If ${\zeta }_1>0,{\sigma }^2(U)$ is of order $n^{-1}$.

If $\theta (F)$ is stationary of order $d$ for $F=F_0$, that is, if (5.11) is satisfied, ${\sigma }^2(U)$ is of order $n^{-d-1}$. Only if, for some $F=F_0,\theta (F)$ is stationary of order $m$, where $m$ is the degree of $\theta (F)$, we have ${\sigma }^2(U)=0$, and $U$ 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

$$\begin{array}{}\text{(5.27)}& {\delta }_d={\zeta }_d-\left(\begin{array}{l}d\\ 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\end{array}$$

we have

$$\begin{array}{}\text{(5.28)}& {\delta }_d\ge 0,(d=1,\cdots ,m{)}^6\end{array}$$

and

$$\begin{array}{}\text{(5.29)}& {\zeta }_d={\delta }_d+\left(\begin{array}{l}d\\ 1\end{array}\right){\delta }_{d-1}+\cdots +\left(\begin{array}{c}d\\ d-1\end{array}\right){\delta }_1\end{array}$$

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

For proving (5.28) let

$${\eta }_0={\theta }^2,{\eta }_c=E\left\{{\mathrm{\Phi }}_c^2(X_1,\cdots ,X_c)\right\},(c=1,\cdots ,m)$$

Then, by (5.10),

$${\zeta }_c={\eta }_c-{\eta }_0$$

and on substituting this in (5.27) we have

$${\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=1$. Suppose that (5.28) holds for $1,\cdots ,d-1$. Then (5.28) will be shown to hold for $d$.

Let

$$\overline{{\mathrm{\Phi }}_0}(x_1)={\mathrm{\Phi }}_1(x_1)-\theta ,$$

$$\begin{array}{rl}\overline{{\mathrm{\Phi }}_c}& (x_1,x_2,\cdots ,x_{c+1}),(c=1,\cdots ,d-1)\\ ={\mathrm{\Phi }}_{c+1}& (x_1,\cdots ,x_{c+1})-{\mathrm{\Phi }}_c(x_2,\cdots ,x_{c+1}).\end{array}$$

For an arbitrary fixed $x_1$, let

$$\overline{{\eta }_c}\left(x_1\right)=E\{{\overline{{\mathrm{\Phi }}_c}}^2(x_1,X_2,\cdots ,X_{c+1})\},(c=0,\cdots ,d-1)$$

Then, by induction hypothesis,

$$\begin{array}{r}\overline{{\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)\overline{{\eta }_c}\left(x_1\right)\ge 0\end{array}$$

for any fixed $x_1$.

Now,

$$E\left\{\overline{{\eta }_c}\left(X_1\right)\right\}={\eta }_{c+1}-{\eta }_c$$

and hence

$$\begin{array}{rl}E\left\{\overline{{\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)({\eta }_{c+1}-{\eta }_c)\\ & =\sum _{c=0}^d(-1{)}^{d-c}\left(\begin{array}{c}d\\ c\end{array}\right){\eta }_c={\delta }_d\end{array}$$

The proof of Lemma 5.1 is complete.

Proof of Theorems 5.1

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

$$\begin{array}{rl}c{\zeta }_d-d{\zeta }_c& =c\sum _{a=1}^d\left(\begin{array}{c}d\\ a\end{array}\right){\delta }_a-d\sum _{a=1}^c\left(\begin{array}{c}c\\ a\end{array}\right){\delta }_a\\ \text{(5.30)}& & =\sum _{a=1}^c[c\left(\begin{array}{c}d\\ a\end{array}\right)-d\left(\begin{array}{c}c\\ a\end{array}\right)]{\delta }_a+c\sum _{a=c+1}^d\left(\begin{array}{c}d\\ a\end{array}\right){\delta }_a\end{array}$$

From (5.28), and since $c\left(\begin{array}{l}d\\ a\end{array}\right)-d\left(\begin{array}{l}c\\ a\end{array}\right)\ge 0$ if $1\le a\le c\le 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{\zeta }_1\le {\zeta }_c\le \frac{c}{m}{\zeta }_m,(c=1,\cdots ,m)$$

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

$$\begin{array}{}\text{(5.31)}& {\left(\begin{array}{l}n\\ 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}\end{array}$$

we obtain (5.20).

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

For (5.21) we may write

$$\begin{array}{}\text{(5.32)}& D_n\ge 0\end{array}$$

where

$$D_n=n{\sigma }^2\left(U_n\right)-(n+1){\sigma }^2\left(U_{n+1}\right)$$

Let

$$D_n=\sum _{c=1}^m{d}_{n,c}{\zeta }_c$$

Then we have from (5.13)

$$\begin{array}{rl}\text{(5.33)}& & d_{n,c}=n\left(\begin{array}{c}m\\ c\end{array}\right)\left(\begin{array}{c}n-m\\ m-c\end{array}\right){\left(\begin{array}{c}n\\ m\end{array}\right)}^{-1}-(n+1)\left(\begin{array}{c}m\\ c\end{array}\right)& \left(\begin{array}{c}n+1-m\\ m-c\end{array}\right){\left(\begin{array}{c}n+1\\ m\end{array}\right)}^{-1},\end{array}$$

or

$$\begin{array}{rl}& 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}{c}n\\ m\end{array}\right)}^{-1}\{(c-1)n-(m-1{)}^2\},\\ & (1\le c\le m\le n).\end{array}$$

Putting

$$c_0=1+\left[\frac{(m-1{)}^2}{n}\right]$$

where $[u]$ denotes the largest integer $\le u$, we have

$$\begin{array}{ll}{d}_{n,c}\le 0& \text{ if }c\le c_0\\ d_{n,c}>0& \text{ if }c>c_0.\end{array}$$

Hence, by (5.19),

$$d_{n,c}{\zeta }_c\ge \frac{1}{c_0}{\zeta }_{c_0}c{d}_{n,c},(c=1,\cdots ,m)$$

and

$$D_n\ge \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 ${\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 $g$ U-statistics,

$$U^{(\gamma )}={\left(\begin{array}{c}n\\ m(\gamma )\end{array}\right)}^{-1}{\mathrm{\Sigma }}^{\prime }{\mathrm{\Phi }}^{(\gamma )}(X_{{\alpha }_1},\cdots ,X_{{\alpha }_m(\gamma )}),(\gamma =1,\cdots ,g)$$

each $U^{(\gamma )}$ being a function of the same $n$ independent, identically distributed random vectors $X_1,\cdots ,X_n$. The function ${\mathrm{\Phi }}^{(\gamma )}$ is assumed to be symmetric in its $m(\gamma )$ arguments $(\gamma =1,\cdots ,g)$.

Let

$$\begin{array}{r}E\left\{U^{(\gamma )}\right\}=E\left\{{\mathrm{\Phi }}^{(\gamma )}(X_1,\cdots ,X_{m(\gamma )})\right\}={\theta }^{(\gamma )},(\gamma =1,\cdots ,g);\\ \text{(6.1)}& {\mathrm{\Psi }}^{(\gamma )}(x_1,\cdots ,x_{m(\gamma )})={\mathrm{\Phi }}^{(\gamma )}(x_1,\cdots ,x_{m(\gamma )})-{\theta }^{(\gamma )},(\gamma =1,\cdots ,g);\text{(6.2)}& {\mathrm{\Psi }}_c^{(\gamma )}(x_1,\cdots ,x_c)=E\left\{{\mathrm{\Psi }}^{(\gamma )}(x_1,\cdots ,x_c,X_{c+1},\cdots ,X_{m(\gamma )})\right\},(c=1,\cdots ,m(\gamma );\gamma =1,\cdots ,g);\\ \text{(6.3)}& {\zeta }_c^{(\gamma ,\delta )}=E\left\{{\mathrm{\Psi }}_c^{(\gamma )}(X_1,\cdots ,X_c){\mathrm{\Psi }}_c^{(\delta )}(X_1,\cdots ,X_c)\right\},\end{array}$$

$$(\gamma ,\delta =1,\cdots ,g)$$

If, in particular, $\gamma =\delta$, we shall write

$$\begin{array}{}\text{(6.4)}& {\zeta }_c^{(\gamma )}={\zeta }_c^{(\gamma ,\gamma )}=E{\left\{{\mathrm{\Psi }}_c^{(\gamma )}(X_1,\cdots ,X_c)\right\}}^2\end{array}$$

Let

$$\sigma (U^{(\gamma )},U^{(\delta )})=E\left\{(U^{(\gamma )}-{\theta }^{(\gamma )})(U^{(\delta )}-{\theta }^{(\delta )})\right\}$$

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

In a similar way as for the variance, we find, if $m(\gamma )\le m(\delta )$,

$$\begin{array}{}\text{(6.5)}& \sigma (U^{(\gamma )},U^{(\delta )})={\left(\begin{array}{c}n\\ 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 )}.\end{array}$$

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

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

We have from (5.23) and (6.5)

$$\begin{array}{rl}\underset{n\to \mathrm{\infty }}{lim}n{\sigma }^2\left(U^{(\gamma )}\right)& =m^2(\gamma ){\xi }_1^{(\gamma )}\\ \underset{n\to \mathrm{\infty }}{lim}n\sigma (U^{(\gamma )},U^{(\delta )})& =m(\gamma )m(\delta ){\xi }_1^{(\gamma ,\delta )}.\end{array}$$

Hence, if ${\zeta }_1^{(\gamma )}\ne 0$ and ${\zeta }_1^{(\delta )}\ne 0$, the product moment correlation $\rho (U^{(\gamma )},U^{(\delta )})$ between $U^{(\gamma )}$ and $U^{(\delta )}$ tends to the limit

$$\begin{array}{}\text{(6.6)}& \underset{n\to \mathrm{\infty }}{lim}\rho (U^{(\gamma )},U^{(\delta )})=\frac{{\zeta }_1^{(\gamma ,\delta )}}{\sqrt{{\zeta }_1^{(\gamma )}{\zeta }_1^{(\delta )}}}\end{array}$$

The Limit Theorems: i.i.d. Case

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

Notes:
Converge of the Distribution Function:
A sequence of d.f.’s $F_1(x)$, $F_2(x),\cdots$ converges to a d.f. $F(x)$ if $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 $g$-variate normal distribution is called non-singular if the rank $r$ of its covariance matrix is equal to $g$, and singular if $r<g$.

LEMMA 7.1. Let $V_1,V_2,\cdots$ be an infinite sequence of random vectors $V_n=$ $(V_n^{(1)},\cdots ,V_n^{(g)})$, and suppose that the d.f. $F_n(v)$ of $V_n$ tends to a d.f. $F(v)$ as $n\to \mathrm{\infty }$. Let $V_n^{(\gamma {)}^{\prime }}=V_n^{(\gamma )}+d_n^{(\gamma )}$, where

$$\begin{array}{}\text{(7.1)}& \underset{n\to \mathrm{\infty }}{lim}E{\left\{d_n^{(\gamma )}\right\}}^2=0,(\gamma =1,\cdots ,g)\end{array}$$

Then the d.f. of $V_n^{\prime }=(V_n^{(1)},\cdots ,V_n^{(g)})$ tends to $F(v)$.

The Limit Theorem 7.1 and 7.2

Theorem 7.1. Let $X_1,\cdots ,X_n$ be $n$ independent, identically distributed random vectors,

$$X_{\alpha }=(X_{\alpha }^{(1)},\cdots ,X_{\alpha }^{(r)}),(\alpha =1,\cdots ,n)$$

Let

$${\mathrm{\Phi }}^{(\gamma )}(x_1,\cdots ,x_{m(\gamma )}),(\gamma =1,\cdots ,g),$$

be $g$ real-valued functions not involving $n,{\mathrm{\Phi }}^{(\gamma )}$ being symmetric in its $m(\gamma )(\le n)$ vector arguments $x_{\alpha }=(x_{\mathit{\alpha }}^{(1)},\cdots ,x_{\alpha }^{(r)}),(\alpha =1,\cdots ,m(\gamma );\gamma =1,\cdots ,g)$. Define

$$\begin{array}{}\text{(7.2)}& U^{(\gamma )}={\left(\begin{array}{c}n\\ m(\gamma )\end{array}\right)}^{-1}{\mathrm{\Sigma }}^{\prime }{\mathrm{\Phi }}^{(\gamma )}(X_{{\alpha }_1},\cdots ,X_{{\alpha }_m(\gamma )}),(\gamma =1,\cdots ,g)\end{array}$$

where the summation is over all subscripts such that $1\le {\alpha }_1<\cdots <{\alpha }_{m(\gamma )}\le n$. Then, if the expected values

$$\begin{array}{}\text{(7.3)}& {\theta }^{(\gamma )}=E\left\{{\mathrm{\Phi }}^{(\gamma )}(X_1,\cdots ,X_{m(\gamma )})\right\},(\gamma =1,\cdots ;g)\end{array}$$

and

$$\begin{array}{}\text{(7.4)}& E{\left\{{\mathrm{\Phi }}^{(\gamma )}(X_1,\cdots ,X_{m(\gamma )})\right\}}^2,(\gamma =1,\cdots ,g)\end{array}$$

exist, the joint d.f. of

$$\sqrt{n}(U^{(1)}-{\theta }^{(1)}),\cdots ,\sqrt{n}(U^{(0)}-{\theta }^{(\theta )})$$

tends, as $n\to \mathrm{\infty }$, to the g-variate normal d.f. with zero means and covariance matrix $(m(\gamma )m(\delta ){\zeta }_1^{(\gamma ,\delta )})$, where ${\zeta }_1^{(\gamma ,\delta )}$ is defined by (6.3). The limiting distribution is non-singular if the determinant $\left|{\zeta }_1^{(\gamma ,\delta )}\right|$ is positive.

According to Theorem 5.2, ${\sigma }^2(U)$ exceeds its asymptotic value $m^2{\zeta }_1/n$ for any finite $n$. Hence, when $n$ is large but finite, Theorem 7.1 underestimate the variance of $U$. 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

$${\zeta }_1^{(\gamma )}>0,(\gamma =1,\cdots ,g)$$

the joint d.f. of

$$(U^{(1)}-{\theta }^{(1)})/\sigma \left(U^{(1)}\right),\cdots ,(U^{(g)}-{\theta }^{(g)})/\sigma \left(U^{(g)}\right)$$

tends, as $n\to \mathrm{\infty }$, to the $g$-variate normal d.f. with zero means and covariance matrix $\left({\rho }^{(\gamma ,\delta )}\right)$, where

$${\rho }^{(\gamma ,\delta )}=\underset{n\to \mathrm{\infty }}{lim}\frac{\sigma (U^{(\gamma )},U^{(\delta )})}{\sigma \left(U^{(\gamma )}\right)\sigma \left(U^{(\delta )}\right)}=\frac{{\zeta }_1^{(\gamma ,\delta )}}{\sqrt{{\zeta }_1^{(\gamma )}{\zeta }_1^{(\delta )}}},(\gamma ,\delta =1,\cdots ,g).$$

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

$${\zeta }_m^{(\gamma )}=E{\left\{{\mathrm{\Phi }}^{(\gamma )}(X_1,\cdots ,X_{m(\gamma )})\right\}}^2-{\left({\theta }^{(\gamma )}\right)}^2$$

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

$${\zeta }_1^{(\gamma )},\cdots ,{\zeta }_{m-1}^{(\gamma )}\text{, of }{\sigma }^2\left(U^{(\gamma )}\right)\text{, and of }{\zeta }_1^{(\gamma ,\delta )}\le \sqrt{{\zeta }_1^{(\gamma )}{\zeta }_1^{(\delta )}}$$

Now, consider the $g$ quantities

$$Y^{(\gamma )}=\frac{m(\gamma )}{\sqrt{n}}\sum _{\alpha =1}^n{\mathrm{\Psi }}_1^{(\gamma )}\left(X_{\alpha }\right),(\gamma =1,\cdots ,g)$$

where ${\mathrm{\Psi }}_1^{(\gamma )}(x)$ is defined by (6.2). $Y^{(1)},\cdots ,Y^{(g)}$ are sums of $n$ independent, random variables with zero means, whose covariance matrix, by virtue of (6.3), is

$$\begin{array}{}\text{(7.5)}& \left\{\sigma (Y^{(\gamma )},Y^{(\delta )})\right\}=\{m(\gamma )m(\delta ){\xi }_1^{(\gamma ,\delta )}\}\end{array}$$

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

Theorem 7.1 will be proved by showing that the $g$ random variables

$$\begin{array}{}\text{(7.6)}& Z^{(\gamma )}=\sqrt{n}(U^{(\gamma )}-{\theta }^{(\gamma )}),(\gamma =1,\cdots ,g),\end{array}$$

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

According to Lemma 7.1 it is sufficient to show that

$$\begin{array}{}\text{(7.7)}& \underset{n\to \mathrm{\infty }}{lim}E{(Z^{(\gamma )}-Y^{(\gamma )})}^2=0,(\gamma =1,\cdots ,n)\end{array}$$

For proving (7.7), write

$$\begin{array}{}\text{(7.8)}& E{\{Z^{(\gamma )}-Y^{(\gamma )}\}}^2=E{\left\{Z^{(\gamma )}\right\}}^2+E{\left\{Y^{(\gamma )}\right\}}^2-2E\left\{Z^{(\gamma )}{Y}^{(\gamma )}\right\}\end{array}$$

By (5.13) we have

$$\begin{array}{}\text{(7.9)}& E{\left\{Z^{(\gamma )}\right\}}^2=n{\sigma }^2\left(U^{(\gamma )}\right)=m^2(\gamma ){\zeta }_1^{(\gamma )}+O\left(n^{-1}\right)\end{array}$$

and from (7.5),

$$\begin{array}{}\text{(7.10)}& E{\left\{Y^{(\gamma )}\right\}}^2=m^2(\gamma ){\zeta }_1^{(\gamma )}\end{array}$$

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

$$Z^{(\gamma )}=\sqrt{n}{\left(\begin{array}{c}n\\ m(\gamma )\end{array}\right)}^{-1}{\mathrm{\Sigma }}^{\prime }{\mathrm{\Psi }}^{(\gamma )}(X_{{\alpha }_1},\cdots ,X_{{\alpha }_m(\gamma )})$$

and hence

$$E\left\{Z^{(\gamma )}{Y}^{(\gamma )}\right\}=m(\gamma ){\left(\begin{array}{c}n\\ m(\gamma )\end{array}\right)}^{-1}\sum _{\alpha =1}^n\sum ^{\prime }E\left\{{\mathrm{\Psi }}_1^{(\gamma )}\left(X_{\alpha }\right){\mathrm{\Psi }}^{(\gamma )}(X_{{\alpha }_1},\cdots ,X_{{\alpha }_m(\gamma )})\right\}.$$

The term

$$E\left\{{\mathrm{\Psi }}_1^{(\gamma )}\left(X_{\alpha }\right){\mathrm{\Psi }}^{(\gamma )}(X_{{\alpha }_1},\cdots ,X_{{\alpha }_m(\gamma )})\right\}$$

is $={\zeta }_1^{(\gamma )}$ if

$$\begin{array}{}\text{(7.11)}& {\alpha }_1=\alpha \text{ or }{\alpha }_2=\alpha \cdots \text{ or }{\alpha }_{m(\gamma )}=\alpha \end{array}$$

and 0 otherwise. For a fixed $\alpha$, the number of $\mathrm{sets}\{{\alpha }_1,\cdots ,{\alpha }_{m(\gamma )}\}$ such that $1\le {\alpha }_1<\cdots <{\alpha }_{m(\gamma )}\le n$ and (7.11) is satisfied, is $\left(\begin{array}{c}n-1\\ m(\gamma )-1\end{array}\right)$. Thus,

$$\begin{array}{}\text{(7.12)}& E\left\{Z^{(\gamma )}{Y}^{(\gamma )}\right\}=m(\gamma ){\left(\begin{array}{c}n\\ 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 )}\end{array}$$

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

$$\begin{array}{}\text{(7.13)}& U^{(g{)}^{\prime }}=U^{(g)}+\frac{b_n^{(\gamma )}}{\sqrt{n}},(\gamma =1,\cdots ,g)\end{array}$$

where $U^{(\gamma )}$ is defined by (7.2) and $b_n^{(\gamma )}$ is a random variable. If the conditions of Theorem 7.1 are satisfied, and $limE{\left\{b_n^{(\gamma )}\right\}}^2=0,(\gamma =1,\cdots ,g)$, then the joint distribution of

$$\sqrt{n}(U^{(1)\prime }-{\theta }^{(1)}),\cdots ,\sqrt{n}(U^{(g)\prime }-{\theta }^{(g)})$$

tends to the normal distribution with zero means and covariance matrix

$$\{m(\gamma )m(\delta ){\zeta }_1^{(\gamma ,\delta )}\}$$

The Limit Theorem 7.4: Application to Sample Functionals

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

$$\theta (S)=\frac{1}{n^m}\sum _{{\alpha }_1=1}^n\dots \sum _{{\alpha }_m=1}^n\mathrm{\Phi }(X_{{\alpha }_1},\cdots ,X_{{\alpha }_m})$$

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

$$n^m\theta (S)=\left(\begin{array}{l}n\\ m\end{array}\right)U+{\mathrm{\Sigma }}^{\star }\mathrm{\Phi }(X_{{\alpha }_1},\cdots ,X_{{\alpha }_m})$$

where the sum ${\mathrm{\Sigma }}^{\star }$ is extended over all $m$-tuples $({\alpha }_1,\cdots ,{\alpha }_m)$ in which at least one equality $\alpha i={\alpha }_j(i\ne j)$ is satisfied. The number of terms in ${\mathrm{\Sigma }}^{\star }$ is of order $n^{m-1}$. Hence

$$\theta (S)-U=\frac{1}{n}D$$

where the expected value $E\left\{D^2\right\}$, whose existence follows from that of ${\sigma }^2\theta (S)$, is bounded for $n\to \mathrm{\infty }$. Thus, if we put $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 $X_1,\cdots ,X_n$ be a random sample from an r-variate population with d.f. $F(x)=F(x^{(1)},\cdots ,x^{(r)})$, and let

${\theta }^{(\gamma )}(F)=\int \cdots \int {\mathrm{\Phi }}^{(\gamma )}(x_1,\cdots ,x_{m(\gamma )})dF\left(x_1\right)\cdots dF\left(x_m{}^{(\gamma )}\right),(\gamma =1,\cdots ,g)$,

be $g$ regular functionals of $F$, where ${\mathrm{\Phi }}^{(\gamma )}(x_1,\cdots ,x_{m(\gamma )})$ is symmetric in the vectors $x_1,\cdots ,x_{m(\gamma )}$ and does not involve $n$. If $S(x)$ is the d.f. of the random sample, and if the variance of

$${\theta }^{(\gamma )}(S)=\frac{1}{n^m}\sum _{{\alpha }_1=1}^n\cdots \sum _{{\alpha }_m(\gamma )=1}^n{\mathrm{\Phi }}^{(\gamma )}(X_{{\alpha }_1},\cdots ,X_{{\alpha }_m(\gamma )})$$

exists, the joint d.f. of

$$\sqrt{n}\{{\theta }^{(1)}(S)-{\theta }^{(1)}(F)\},\cdots ,\sqrt{n}\{{\theta }^{(\theta )}(S)-{\theta }^{(g)}(F)\}$$

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

$$\{m(\gamma )m(\delta ){\zeta }_1^{(\gamma ,\delta )}\}$$

The Limit Theorem 7.5: Application to Functions of Statistics

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

Theorem 7.5. Let $U^{\prime }=(U^{(1{)}^{\prime }},\cdots ,U^{(g)\prime })$ be a random vector, where $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)},\cdots ,y^{(g)})$ does not involve $n$ and is continuous together with its second order partial derivatives in some neighborhood of the point $(y)=(\theta )=$ $({\theta }^{(1)},\cdots ,{\theta }^{(g)})$, then the distribution of the random variable $\sqrt{n}\{h\left(U^{\prime }\right)-h(\theta )\}$ tends to the normal distribution with mean zero and variance

$$\sum _{\gamma =1}^g\sum _{\delta =1}^{g}m(\gamma )m(\delta ){\left(\frac{\partial h(y)}{\partial y^{(\gamma )}}\frac{\partial h(y)}{\partial y^{(\delta )}}\right)}_{y=\theta }{\zeta }_1^{(\gamma ,\delta )}$$

Applications to particular statistics

• Moments and functions of moments
• Mean different and coefficient of concentration
• Functions of ranks and of the signs of variate differences
• Difference sign correlation
• Rank correlation and grade correlation
• Non-parametric tests of independence
• Mann’s test against trend
• The coefficient of partial difference sign correlation

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.