Suppose that Φ(x1,...,xm) is a function of m random variables and X1,...,Xn are i.i.d. observations from c.d.f. F(x). Assume n>m.
Make inference about θ=θ(F)=EF[Φ(X1,...,Xm)]
Note: θ 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 U=(mn)−1Σ′Φ(Xi1,...,Xim)=n(n−1)...(n−m+1)11≤i1<...<im≤n∑Φ(Xi1,...,Xim)
where Σ′ stands for summation over all permutations of m integers i1,...,im such that 1≤i1<...<im≤n.
Here, U is a function of the sample X1,...,Xn called a U-statistic. The Φ function is called the kernel and m is the degree of the functional θ(F).
Symmetry of Kernel
For convenience, we assume that Φ is symmetric in its arguments, which means Φ(...,xi,...,xj,...)=Φ(...,xj,...,xi,...)
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) is not symmetric, there exist a symmetric Φ0(x1,...,xm) such that Φ0(x1,...,xm)=m!1∑Φ(xα1,...,xαm)
where the sum is over all permutations of m integers 1,...,m.
Motivating Examples
Example 1: Let m=1 and Φ(x)=x. Then, U=∑i=1nXi/n is the sample mean.
Example 2: Let m=2 and Φ(x1,x2)=x12−x1x2. Then, U=∑1≤i<j≤n(Xi2−XiXj)/(n(n−1)) is the sample variance. A symmetric kernel can be Φ0(x1,x2)=(x1−x2)2/2.
Example 3: Let m=2 and Φ(x1,x2)=I(x1+x2>0). Then, U=∑1≤i<j≤nI(xi+xj>0)/(n(n−1)) is related to one sample Wilcoxon statistics.
Asymptotic Normality of U-statistic: A Simple Version
Define ζ1=σ2(Φ1(X1)). X1,...,Xn are i.i.d. observations from c.d.f. F(x). Suppose that the kernel Φ satisfies EΦ2(X1,...,Xm)<∞. Assume that 0<ζ1<∞. Then, σ2(U)U−θdN(0,1)
where σ2(U)=nm2ζ1+O(n−2) .
U-statistic
Notations
X1,...,Xn: n independent random vectors with the same d.f. F(x)=F(x(1),...,x(r)).
Xν=(Xν(1),...,Xν(r)): r-dimensional random vector.
x1,...,xn: sample of nr-dimensional vectors.
Φ(x1,...,xm): a symmetric function of m(≤n) vector arguments.
θ=θ(F): functional of F.
Definition: U-statistic
Consider the function of the sample,
U(x1,⋯,xn)=(nm)−1Σ′Φ(xα1,⋯,xαm)(4.4)
where the kernel Φ is symmetric in its m vector arguments and the sum Σ′ is extended over all subscripts α such that
1≤α1<α2<⋯<αm≤n
Asymptotic Normality of U-statistic
The Variance of a U-statistic
The Unbiased Estimator and Its Variance
If θ=θ(F), we have E{U}=E{Φ(X1,⋯,Xm)}=θ
Let Φc(x1,⋯,xc)(c=E{Φ(x1,⋯,xc,Xc+1,⋯,Xm)},=1,⋯,m),(5.2)
where x1,⋯,xc are arbitrary fixed vectors and the expected value is taken with respect to the random vectors Xc+1,⋯,Xm.
We can rewrite (5.2) in a more familiar form, which is called Hoeffding's projection:
Suppose that the variance of Ψc(X1,⋯,Xc) exists, and let
ζ0=0,ζc=E{Ψc2(X1,⋯,Xc)},(c=1,⋯,m)(5.9)
We have
ζc=E{Φc2(X1,⋯,Xc)}−θ2(5.10)
Stationary Order of a Functional
If, for some parent distribution F=F0 and some integer d, we have ζd(F0)=0, this means that Ψd(X1,⋯,Xd)=0 with probability 1. By (5.7) and (5.9), ζd=0 implies ζ1=⋯=ζd−1=0.
If ζ1(F0)=0, we shall say that the regular functional θ(F) is stationary for F=F0. If
θ(F) will be called stationary of order d for F=F0.
The Variance of a U-statistic: i.i.d. Case
If (α1,⋯,αm) and (β1,⋯,βm) are two sets of m different integers, 1≤αi, βi≤n, and c is the number of integers common to the two sets, we have, by the symmetry of Ψ,
Returning to the case of identically distributed X 's, we shall now prove some inequalities satisfied by ζ1,⋯,ζm and σ2(U) which are contained in the following theorems:
Theorem 5.1 The quantities ζ1,⋯,ζm as defined by (5.9) satisfy the inequalities
0≤cζc≤dζd if 1≤c<d≤m(5.19)
Theorem 5.2 The variance σ2(Un) of a U-statistic Un=U(X1,⋯,Xn), where X1,⋯,Xn are independent and identically distributed, satisfies the inequalities
nm2ζ1≤σ2(Un)≤nmζm(5.20)
nσ2(Un) is a decreasing function of n,
(n+1)σ2(Un+1)≤nσ2(Un),(5.21)
which takes on its upper bound mζm for n=m and tends to its lower bound m2ζ1 as n increases:
σ2(Um)=ζmn→∞limnσ2(Un)=m2ζ1(5.22)(5.23)
If E{Ln}=θ(F) is stationary of order ≥d−1 for the d.f. of Xα,(5.20) may be replaced by
dmKn(m,d)ζd≤σ2(Un)≤Kn(m,d)ζm(5.24)
where
Kn(m,d)=(nm)−1c=d∑m(m−1c−1)(n−mm−c)(5.25)
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) is the existence of
ζm=E{Φ2(X1,⋯,Xm)}−θ2(5.26)
or that of E{Φ2(X1,⋯,Xm)}.
If ζ1>0,σ2(U) is of order n−1.
If θ(F) is stationary of order d for F=F0, that is, if (5.11) is satisfied, σ2(U) is of order n−d−1. Only if, for some F=F0,θ(F) is stationary of order m, where m is the degree of θ(F), we have σ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:
From (5.28), and since c(da)−d(ca)≥0 if 1≤a≤c≤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≤mcζm,(c=1,⋯,m)
Applying these inequalities to each term in (5.13) and using the identity
By (5.33) and (5.31), the latter sum vanishes. This proves (5.32).
For the stationary case ζ1=⋯=ζ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(γ)=(nm(γ))−1Σ′Φ(γ)(Xα1,⋯,Xαm(γ)),(γ=1,⋯,g)
each U(γ) being a function of the same n independent, identically distributed random vectors X1,⋯,Xn. The function Φ(γ) is assumed to be symmetric in its m(γ) arguments (γ=1,⋯,g).
Hence, if ζ1(γ)=0 and ζ1(δ)=0, the product moment correlation ρ(U(γ),U(δ)) between U(γ) and U(δ) tends to the limit
n→∞limρ(U(γ),U(δ))=ζ1(γ)ζ1(δ)ζ1(γ,δ)(6.6)
The Limit Theorems: i.i.d. Case
In this section the vectors Xα will be assumed to be identically distributed.
Notes:
Converge of the Distribution Function:
A sequence of d.f.'s F1(x), F2(x),⋯ converges to a d.f. F(x) if limFn(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 V1,V2,⋯ be an infinite sequence of random vectors Vn=(Vn(1),⋯,Vn(g)), and suppose that the d.f. Fn(v) of Vn tends to a d.f. F(v) as n→∞. Let Vn(γ)′=Vn(γ)+dn(γ), where
n→∞limE{dn(γ)}2=0,(γ=1,⋯,g)(7.1)
Then the d.f. of Vn′=(Vn(1),⋯,Vn(g)) tends to F(v).
The Limit Theorem 7.1 and 7.2
Theorem 7.1. Let X1,⋯,Xn be n independent, identically distributed random vectors,
Xα=(Xα(1),⋯,Xα(r)),(α=1,⋯,n)
Let
Φ(γ)(x1,⋯,xm(γ)),(γ=1,⋯,g),
be g real-valued functions not involving n,Φ(γ) being symmetric in its m(γ)(≤n) vector arguments xα=(xα(1),⋯,xα(r)),(α=1,⋯,m(γ);γ=1,⋯,g). Define
where the summation is over all subscripts such that 1≤α1<⋯<αm(γ)≤n. Then, if the expected values
θ(γ)=E{Φ(γ)(X1,⋯,Xm(γ))},(γ=1,⋯;g)(7.3)
and
E{Φ(γ)(X1,⋯,Xm(γ))}2,(γ=1,⋯,g)(7.4)
exist, the joint d.f. of
n(U(1)−θ(1)),⋯,n(U(g)−θ(g))
tends, as n→∞, to the g-variate normal d.f. with zero means and covariance matrix (m(γ)m(δ)ζ1(γ,δ)), where ζ1(γ,δ) is defined by (6.3). The limiting distribution is non-singular if the determinant ζ1(γ,δ) is positive.
According to Theorem 5.2, σ2(U) exceeds its asymptotic value m2ζ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
ζ1(γ)>0,(γ=1,⋯,g)
the joint d.f. of
(U(1)−θ(1))/σ(U(1)),⋯,(U(g)−θ(g))/σ(U(g))
tends, as n→∞, to the g-variate normal d.f. with zero means and covariance matrix (ρ(γ,δ)), where
Proof of Theorem 7.1. The existence of (7.4) entails that of
ζm(γ)=E{Φ(γ)(X1,⋯,Xm(γ))}2−(θ(γ))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(δ)
Now, consider the g quantities
Y(γ)=nm(γ)α=1∑nΨ1(γ)(Xα),(γ=1,⋯,g)
where Ψ1(γ)(x) is defined by (6.2). Y(1),⋯,Y(g) are sums of n independent, random variables with zero means, whose covariance matrix, by virtue of (6.3), is
{σ(Y(γ),Y(δ))}={m(γ)m(δ)ξ1(γ,δ)}(7.5)
By the Central Limit Theorem for vectors (cf. Cramer [1, p. 112]), the joint d.f. of (Y(1),⋯,Y(ρ)) 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
Z(γ)=n(U(γ)−θ(γ)),(γ=1,⋯,g),(7.6)
have the same joint limiting distribution as Y(1),⋯,Y(g).
According to Lemma 7.1 it is sufficient to show that
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)+nbn(γ),(γ=1,⋯,g)(7.13)
where U(γ) is defined by (7.2) and bn(γ) is a random variable. If the conditions of Theorem 7.1 are satisfied, and limE{bn(γ)}2=0,(γ=1,⋯,g), then the joint distribution of
n(U(1)′−θ(1)),⋯,n(U(g)′−θ(g))
tends to the normal distribution with zero means and covariance matrix
{m(γ)m(δ)ζ1(γ,δ)}
The Limit Theorem 7.4: Extension to Sample Functionals
The theorem 7.3 applies, in particular, to the regular functionals θ(S) of the sample d.f.,
θ(S)=nm1α1=1∑n…αm=1∑nΦ(Xα1,⋯,Xαm)
in the case that the variance of θ(S) exists. For we may write
nmθ(S)=(nm)U+Σ∗Φ(Xα1,⋯,Xαm)
where the sum Σ∗ is extended over all m-tuples (α1,⋯,αm) in which at least one equality αi=αj(i=j) is satisfied. The number of terms in Σ∗ is of order nm−1. Hence
θ(S)−U=n1D
where the expected value E{D2}, whose existence follows from that of σ2{θ(S)}, is bounded for n→∞. Thus, if we put U(γ)′=θ(γ)(S), the conditions of Theorem 7.3 are fulfilled. We may summarize this result as follows:
Theorem 7.4. Let X1,⋯,Xn be a random sample from an r-variate population with d.f. F(x)=F(x(1),⋯,x(r)), and let
be g regular functionals of F, where Φ(γ)(x1,⋯,xm(γ)) is symmetric in the vectors x1,⋯,xm(γ) and does not involve n. If S(x) is the d.f. of the random sample, and if the variance of
tends to the g-variate normal d.f. with zero means and covariance matrix
{m(γ)m(δ)ζ1(γ,δ)}
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 U or U′.
Theorem 7.5. Let U′=(U(1)′,⋯,U(g)′) be a random vector, where U(γ) 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)) does not involve n and is continuous together with its second order partial derivatives in some neighborhood of the point (y)=(θ)=(θ(1),⋯,θ(g)), then the distribution of the random variable n{h(U′)−h(θ)} tends to the normal distribution with mean zero and variance
By Theorem 7.1, n(d−δ) is asymptotically normal if ζ2(δ) exists.
If Y1,⋯,Yn do not assume negative values, the coefficient of concentration is defined by
G=2Yˉd
where Yˉ=ΣYα/n.G is a function of two U-statistics. If the Yα 's are identically distributed, if E{Y2} exists, and if μ=E{Y}>0, then, by Theorem 7.5, n(G−δ/2μ) tends to be normally distributed with mean 0 and variance
[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.