3.1 One-Sample U-Statistics
Definition 3.1.1. A parameter \(\gamma \) is said to be estimable of degree \(k\) for the family of distributions \(\mathscr {Z}\), if \(k\) is the smallest sample size for which there exists a function \(h(X_1,\, X_2,\, \cdots \, , \, X_k)\) such that \(E\left (h(X_1,\, X_2,\, \cdots \, , \, X_k)\right ) = \gamma \) for every distribution \(F\in \mathscr {Z}\), where \(X_1, \, X_2, \, \cdots \, , \, X_k\) is a random sample from \(F\).
- (i)
- A parameter is estimable (of some degree) if there exists some estimator that is unbiased for every \(F\in \mathscr {Z}\).
- (ii)
- The function \(h(\cdot )\) in definition 3.1.1 is called a kernel of the parameter \(\gamma \).
- (iii)
- Without loss of generality, we can assume that the kernel is symmetric in its argument i.e \(h(x_1, \, x_2, \, \cdots \, , \, x_k) = h(x_{\alpha _1}, \, x_{\alpha _2}\, , \, \cdots \, , \, x_{\alpha _k})\) for every permutation of \((\alpha _1, \, \alpha _2, \, \cdots \, ,\, \alpha _k)\) of the integers \(1, \, 2, \, \cdots \, , \, k\).
For any kernel \(h(X_1,\, X_2,\, \cdots \, , \, X_K)\) we can always create one that is symmetric in its argument by using \[h^*(X_1,\, X_2,\, \cdots \, , \, X_k) = \frac {1}{k!}\, \sum _{\alpha \in A}h(X_{\alpha _1},\, X_{\alpha _2},\, \cdots \, , \, X_{\alpha _k})\] where summation is over \(A = \{\alpha \, |\, \alpha \) is a permutation of the integers \(1, \, 2, \, \cdots \, , \, k\}\).
Definition 3.1.3. A \(U\)-statistic for the estimable parameter \(\gamma \) of degree \(K\) is created with the symmetric kernel \(h(X_1,\, X_2,\, \cdots \, , \, X_K)\) by forming \[U(X_1,\, X_2,\, \cdots \, , \, X_n) = \frac {1}{\binom {n}{k}}\sum _{\beta \in \mathcal {B}}h(X_{\beta _1},\, X_{\beta _2},\, \cdots \, , \, X_{\beta _k})\] where \(\mathcal {B} = \{\beta \, |\,\beta \) is one of \(\binom {n}{k}\) unordered subsets of \(k\) integers chosen without replacement from the set \(\{1, \, 2, \, \cdots \, , \, n\}\}\)
- (i)
- \(U\)-statistic is an unbiased estimator of \(\gamma \) for every \(F\in \mathscr {Z}\) and its symmetric in its arguments.
- (ii)
- If \(\mathscr {Z}\) includes all continuous distributions, it can be shown that such a \(U\)-statistic is the unique MVUE of \(\gamma \).
- (a)
- Let \(\mathscr {Z}\) denote the class of all distributions with finite first moment \(\gamma \), then \(\gamma = E(X) = E(X_1)\). Thus the
mean is an estimable parameter of degree 1 for \(\mathscr {Z}\). The kernel \(h(X_1) = X_1\) or \(h(x) = x\).
We have that \(k = 1\) \begin {align*} U(X_1,\, X_2,\, \cdots \, , \, X_n) & = \frac {1}{\binom {n}{1}}\sum _{\beta \in \mathscr {B}} h\left (X_{\beta }\right ) = \frac {1}{n}\sum ^n_{i = 1} X_i = \overline {X}. \end {align*}
The \(U\)-statistic for first moment or mean is the sample mean.
- (b)
- Let \(\mathscr {Z}\) denote the collection of all distributions with finite variance \(\gamma \) \begin {align*} \gamma & = E\left (X_1^2 - X_1\, X_2\right )\\ \gamma & = E\left (X_1^2\right ) - E\left (X_1\right )\, E\left (X_2\right ) = \sigma ^2. \end {align*}
\(\gamma = \sigma ^2\,\) is an estimable parameter of degree 2.
So we have that \(h(X_1, \, X_2) = X_1^2 - X_1\, X_2\,\) and \(\, h(X_2, \, X_1) = X_2^2 - X_2\, X_1\) \begin {align*} h^*\left (X_1, \, X_2\right ) & = \frac {1}{2}\, \left (h(X_1, \, X_2)\, + \, h(X_2,\, X_1)\right )\\ & = \frac {1}{2}\, \left (X_1^2 - X_1\, X_2 + X_2^2 - X_1\, X_2\right )\\ h^*(X_1\,, \, X_2) & = \frac {1}{2} (X_1 - X_2)^2\, , \end {align*}\[U\text {-Statistic}\,\, = \frac {1}{\binom {n}{2}}\sum _{\beta \in \mathcal {B}}h^*(X_{\beta _1}\, ,\, X_{\beta _2})\, ,\, \hspace {0.4cm} \beta = (\beta _1\, , \, \beta _2)\, , \hspace {0.4cm} \mathcal {B} = \binom {n}{2}\]
\begin {align*} U_2(X_1,\, X_2,\, \cdots \, , \, X_n) & = \frac {1}{\binom {n}{2}}\sum _{\beta \in \mathcal {B}}h^*\left (X_{\beta _1}\, , \, X_{\beta _2}\right )\\ & = \frac {2}{n\, (n - 1)}\, \sum ^n_{i = 1} \frac {1}{2}\, \left (X_i - X_{i + 1}\right )^2\\ & = \frac {2}{n\, (n-1)}\, \sum _{\beta \in \mathcal {B}}\left [\frac {1}{2}\left (\sum ^2_{i=1}X^2_{\beta _i} - 2\,X_{\beta _1}\, X_{\beta _2}\right )\right ]\\ & = \frac {2}{n\, (n-1)}\, \cdot \, \frac {1}{2}\left [\sum ^n_{i = 1} (n - 1)\, X_i^2 - 2\, \underset {i<j}{\sum \sum }X_i\, X_j\right ] \end {align*}
\begin {align*} U_2(X_1,\, X_2,\, \cdots \, , \, X_n) & = \frac {1}{n\, (n-1)}\left (n\, \sum ^n_{i = 1} X_i^2 - \sum ^n_{i = 1}X_i^2 - 2\, \underset {i<j}{\sum \sum }X_i\, X_j\right )\\\\ & = \frac {1}{n\, (n - 1)}\left [n\, \sum ^n_{i = 1} X_i^2 - \left (\sum ^n_{i = 1} X^2_i + 2\, \underset {i<j}{\sum \sum }X_i\, X_j\right )\right ]\\\\ & = \frac {1}{n\, (n - 1)}\, \left [n\, \sum ^n_{i = 1}X_i^2 - \left (\sum ^n_{i = 1} X_i\right )^2\right ]\\\\ & = \frac {1}{n\, (n - 1)}\, \cdot \, n\, \left [\sum ^n_{i = 1} X_i^2 - \frac {1}{n}\,\left (\sum ^n_{i = 1}(X_i)\right )^2\right ]\\\\ & = \frac {1}{n - 1}\left (\sum ^n_{i = 1} X_i^2 - n\, \overline {X}^2\right )\\\\ & = \frac {1}{n - 1}\sum ^n_{i = 1} \left (X_i - \overline {X}\right )^2\\ U_2(X_1,\, X_2,\, \cdots \, , \, X_n)& = S^2. \end {align*}
Thus the \(U\)-statistics for the population variance is the well-known sample variance.
Example 3.1.6 (a). Suppose we want to estimate the probability that a distribution assigns to positive numbers. We can let \[\Psi (x) = \begin {cases} 1 & \text {if}\, \, x> 0\\ 0 & \text {otherwise}.\\ \end {cases}\] Then \(E\left (\Psi (x)\right ) = Prob(X > 0)\).
Note 3.1.7. that \(\Psi (x)\) provides unbiased estimator of \(P(X>0)\) for each distribution \(F(\cdot )\). Thus
\begin {align*} U_3(X_1,\, X_2,\, \cdots \, , \, X_n) = & \frac {1}{n}\,\left (\text {the number of } X_i\, 's\, \text {that are positive}\right )\\ & \text {i.e kernel} = \Psi (x)\, \text {parameter is probability }\hspace {0.1cm} k\hspace {0.1cm}\text {is}\hspace {0.2cm}1\\ = & \frac {1}{n}\, \mathcal {B} \end {align*}
where \(\mathcal {B}\) is the statistic used in the sign test.
Example 3.1.8 ((b)). Consider the parameter \(\gamma = P\left (X_1 + X_2>0\right )\) where \(X_1, \, X_2\,\) are independent observations
from \(F(\cdot )\). The kernel is \(h(X_1\, , \, X_2) = \Psi (X_1 + X_2)\) which is symmetric in it’s argument since \(\Psi (X_1 + X_2) = \Psi (X_2 + X_1)\) and the degree is 2, i.e
\(K = 2\).
Thus \begin {align*} U_4(X_1,\, X_2,\, \cdots \, , \, X_n) & = \frac {1}{\binom {n}{2}}\, \sum _{\beta \in \mathcal {B}} \, h\left (X_{\beta _1}\, , \, X_{\beta _2}\right ) = \frac {2}{n\, (n - 1)}\, \sum _{\beta \in \mathcal {B}}\, \left (\Psi \left (X_{\beta _1}+X_{\beta _2}\right )\right ). \end {align*}
\[\binom {n}{k}\, \binom {k}{c}\, \binom {n - k}{k-c} = \frac {n!}{c!\, (k - 1)!\, (k - c)!\, (n - 2k + c)!}\]
\[U_4(X_1,\, X_2,\, \cdots \, , \, X_n) = \frac {2}{n\, (n - 1)}\, T\] where \(T\) is the number of pairs \((i,j)\) such that \(X_i + X_j > 0\) for two independent samples.
Let us develop a general expression for the variance of a \(U\)-statistic. Let \(\gamma \) be an estimable parameter
of degree \(k\) with a symmetric kernel \(h(X_1,\, X_2,\, \cdots \, , \, X_k)\).
Let \(\,Z_1 = h(X_1, \, X_2, \, \cdots \, , \, X_c\, , \, X_{c + 1}, \, X_{c + 2}, \, \cdots \, , X_k)\,\) and
\(\,Z_2 = h(X_1, \, X_2, \, \cdots \, , \, X_c\, , \, X_{k + 1}, \, X_{k + 2}, \, \cdots \, , X_{2k-c})\,\) i.e \(Z_1\) and \(Z_2\) have \(c\) elements in common.
The covariance of \(Z_1\) and \(Z_2\) is \begin {align*} \Im _c & = Cov(Z_1\, , \, Z_2) = E(Z_1\, Z_2) - E(Z_1)\, E(Z_2)\\ & = E(Z_1\, Z_2) - \gamma ^2\\ & = E\left \{h(X_1, \, \cdots \, X_c, \, \cdots \,, \, X_k)\, h(X_1, \, \cdots \, , \, X_c, \, \cdots \, , \, X_{2k - c})\right \} - \gamma ^2 \end {align*}
\begin {align*} \Im _c & = E\left \{h(X_{\beta _1}, \, X_{\beta _2}, \, \cdots \, , \, X_{\beta _k})\, h(X_{\beta _1'}, \, X_{\beta _2'}, \, \cdots \, , \, X_{\beta _k'})\right \} - \gamma ^2\hspace {0.3cm}\cdots \hspace {0.3cm} 3.1.6\\ \Im _c & = Cov\left (h(X_{\beta _1}, \, X_{\beta _2}, \, \cdots \, , \, X_{\beta _k})\,,\, h(X_{\beta _1'}, \, X_{\beta _2'}, \, \cdots \, , \, X_{\beta _k'})\right )\hspace {0.3cm}\cdots \hspace {0.3cm} 3.1.7 \end {align*}
where \(\beta = (\beta _1, \, \beta _2, \, \cdots \, , \, \beta _k)\) and \(\beta ' = (\beta _1', \, \beta _2', \, \cdots \, , \, \beta _k')\) are subsets of the integers \(\{1, \, 2, \,\cdots \, ,\, n\}\) having exactly \(c\) integers in common.
Note that if \(\mathcal {B}\) and \(\mathcal {B}'\) have no integers in common, then \(h(X_{\beta _1}, \, X_{\beta _2}, \, \cdots \, , \, X_{\beta _k})\) and
\(h(X_{\beta _1'}, \, X_{\beta _2'}, \, \cdots \, , \, X_{\beta _k'})\) are independent , then \(\Im _c = 0\) i.e \(\Im _0 = 0\) \begin {align*} var(U) & = E\left \{\left [\frac {1}{\binom {n}{k}}\sum _{\beta \in \mathcal {B}}\left (h(X_{\beta _1}, \, X_{\beta _2}, \, \cdots \, , \, X_{\beta _k})\right ) - \gamma \right ]^2\right \}\\ & = \frac {1}{\left [\binom {n}{k}\right ]^2}\sum _{\beta \in \mathcal {B}}\sum _{\beta '\in \mathcal {B}'}E\left ((h(X_{\beta _1}, \, X_{\beta _2}, \, \cdots \, , \, X_{\beta _k})-\gamma )\, (h(X_{\beta _1'}, \, X_{\beta _2'}, \, \cdots \, , \, X_{\beta _k'}) - \gamma )\right )\\ & = \frac {1}{\left [\binom {n}{k}\right ]^2}\, \sum _{\beta \in \mathcal {B}}\sum _{\beta ^*\in \mathcal {B}'}Cov\left (h(X_{\beta _1}, \, X_{\beta _2}, \, \cdots \, , \, X_{\beta _k})\, , \, h(X_{\beta _1'}, \, X_{\beta _2'}, \, \cdots \, , \, X_{\beta _k'})\right )\hspace *{0.5cm}\cdots \hspace {0.3cm} 3.1.8 \end {align*}
All the terms in 3.1.8 for which \(\mathcal {B}\) and \(\mathcal {B}'\) have exactly \(c\) elements in common have the same covariance
namely \(\Im \).
The number of such terms is
\[\binom {n}{k}\, \binom {k}{c}\,\binom {n - k}{k - c}.\]
Therefore \begin {align*} var(U) & = \frac {1}{\left [\binom {n}{k}\right ]^2}\, \sum ^k_{c = 0} \binom {n}{k}\,\binom {k}{c}\, \binom {n - k}{k-c}\, \Im _c\\\\ & = \frac {1}{\binom {n}{k}}\, \sum ^k_{c = 1}\binom {k}{c}\, \binom {n - k}{k - c}\, \Im _c, \hspace {0.3cm} \text {since}\hspace {0.1cm} \Im _0 = 0\hspace {0.2cm} (\Im _0 = 0)\\\\ var(U) & = \frac {1}{\binom {n}{k}}\sum ^k_{c = 1} \binom {k}{c}\, \binom {n - k}{k - c}\, \Im _c.\hspace {0.5cm}\cdots \cdots \hspace {0.3cm} 3.1.9 \end {align*}
Example 3.1.9. Consider the \(U\)-statistic \(\overline {X}\) for the population mean \(\mu \). (See example 3.1.3(a)) \[h(X) = X\,,\hspace {0.3cm} K = 1\, ,\hspace {0.3cm} c = 1\] \begin {align*} var(U_1) & = var(\overline {X}) = \frac {1}{\binom {n}{1}}\, \binom {1}{1}\, \binom {n - 1}{0}\, \Im _1 = \frac {1}{n}\, \Im _1 \end {align*}
\[\Im _1 = cov\left (h(x)\, ,\, h(x)\right ) = cov\left (X\, , \, X\right ) = var(X) = \sigma ^2.\] Therefore \begin {align*} var(U_1) = var(\overline {X}) = \frac {1}{n}\, \sigma ^2 = \frac {\sigma ^2}{n}. \end {align*}
Theorem 3.1.10. Let \(U(X_1, \, X_2, \, \cdots \, , \, X_n)\) be a \(U\)-statistic with a symmetric kernel
\(h(X_1, \, X_2, \, \cdots \, , \, X_k)\). If \(E\left (h^2(X_1, \, X_2, \, \cdots \, , \, X_k)\right ) < \infty \), then
\[\lim _{n\rightarrow \infty }\, n\, var\left (U(X_1, \, X_2, \, \cdots \, , \, X_n)\right ) = K^2\, \Im _1.\]
Proof. The hypothesis \(\, \left (E\left (h^2(X_1, \, X_2, \, \cdots \, , \, X_k)\right ) < \infty \right )\,\) implies that the variance of
\(h(X_1, \, X_2, \, \cdots \, , \, X_k)\) exists i.e \(\Im _k = var\left (h(X_1, \, X_2, \, \cdots \, , \, X_k)\right )\). Thus from the 3.1.9 and
\(0\leq \Im _c\leq \Im _k\). \begin {align*} n\, var(U) & = n\, \cdot \, \frac {1}{\binom {n}{k}}\, \sum ^k_{c = 1} \binom {k}{c}\, \binom {n - k}{k - c}\, \Im _c\\ & = \sum ^k_{c = 1}n\, \cdot \, \frac {(n - k)!\, k!}{n!}\, \cdot \, \frac {k!}{(k - c)!\, c!}\, \cdot \, \frac {(n - k)!}{(k - c)!\, (n - 2k + c)!}\, \, \Im _c\\\\ & = \sum ^k_{c = 1}\left (\frac {k!}{(k - c)!}\right )^2\frac {1}{c!}\, \frac {(n - k)!\, (n - k)!}{(n - 1)!\, (n - 2k + c)!}\, \Im _c\\\\ & = \sum ^k_{c = 1} L_c\, \frac {(n - k)!\, (n-k)!}{(n - 1)!\, (n - 2k + c)!}\, \Im _c\hspace {0.4cm}\text {where}\hspace {0.4cm} L_c = \left (\frac {k!}{(k - c)!}\right )^2\frac {1}{c!}\\\\ & = \sum ^k_{c = 1} L_c\, \Im _c\, \frac {n\, (n-k)!\, (n-k)\, (n-k - 1)\, \cdots \, (n-2k+c+1)\, (n-2k+ c)!}{n\,(n-1)\,(n-2)\, \cdots \, (n - k + 1)\,(n-k)!\, (n-2k+c)!} . \end {align*}
The number of terms in the numerator involving \(n\) is \(\, 1 + (2k - c - 1 - k + 1) = k - c + 1\). The number of terms involving \(n\) is \(\, k - 1 - 0 + 1 = k\). Therefore when \(c = 1\), there are equal number of terms involving \(n\) the numerator and the denominator. \[\lim _{n\rightarrow \infty }\, n\, var(U) = L_1\, \Im _1 \,+ \, \lim _{n\rightarrow \infty }\sum ^k_{c = 2} L_c\, \Im _c\, \frac {(n - k)!\, (n - k)!}{(n - 1)!\, (n - 2k + c)!}.\] Therefore \begin {align*} \lim _{n\rightarrow \infty }\, n \, var(U)\, & = L_1\, \Im _1 = \left (\frac {k!}{(k - 1)!}\right )^2\, \cdot \, \frac {1}{1!}\, \cdot \, \Im _1 = K^2\, \Im _1. \end {align*} □
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.