3.3 The Projection Principle and One Sample \(U\)-Statistics Theorem
The obstacle is that a \(U\)-statistic is not a sum of independent terms. Every observation appears in many of the \(\binom {n}{k}\) summands, so the summands are dependent and the central limit theorem cannot be applied to them directly.
The projection principle circumvents this. Rather than attack the statistic as it stands, we find a sum of independent terms that is close to it — the projection — prove asymptotic normality for that sum, and then show the difference vanishes fast enough that the two share a limiting distribution. The projection is the sum of the conditional expectations of \(U-\gamma \) given each single observation, which is precisely the part of the statistic that each observation contributes on its own.
We want to show that under certain conditions standardised one-sample \(U\)-statistics have limiting normal distribution. For each \(U\)-statistic we obtain a related random variable that
- (i)
- has an easily established limiting normal distributions.
- (ii)
- is asymptotically equivalent to the \(U\)-statistics of interest in the sense their difference converges to zero in quadratic mean.
Let \(X_1, \, X_2, \, \cdots \, , \, X_n\) denote \(iid\) random variables with cdf \(F(x)\). Let \(W = w(X_1, \, X_2, \, \cdots \, , \, X_n)\) and \(W\) has limiting normal distribution with \(w\) being
symmetrical in its arguments. We will work with \(W^* = W - E(W)\) hence \(E(W*) = 0\).
Consider a class of random variables, each member of which is a sum of \(iid\) random variables.
\begin {equation} \mathcal {V} = \left \{V:\, V = \sum ^n_{i = 1} K(x_i),\, \text {where}\hspace {0.2cm} K(\cdot )\hspace {0.2cm} \text {is some real valued function}\right \} \end {equation}
Definition 3.3.1. The projection of \(W^*\) on \(\mathcal {V}\) is given by \[V^* = \sum ^n_{i = 1} K^*(x_i),\] where \(K^*(x) = E\left (W^*/X_i = x\right )\). \(V^*\) is a member of \(\mathcal {V}\) that is closest in some sense to \(W^*\).
Example 3.3.3. Consider \(\gamma = var(X) = \sigma ^2\) and \[U_2 = \frac {1}{n(n-1)}\left \{(n-1)\sum ^n_{i=1}X_i^2 - 2\, \underset {i<j}{\sum \sum } X_i\,X_j\right \}\] We now fix \(X_i = x\) and take the expected value of \(U_2 - \gamma \) with respect to the other \(n-1\) of \(X_j\, 's\hspace {0.3cm} j = 1, \, 2, \, \cdots \, n\). \begin {align*} & E\left [U_2\left (X_1, \, X_2, \, \cdots \, , \, X_n\right )-\gamma / X_i = x\right ]\\ & = \frac {1}{n(n-1)}\left \{(n-1)[x^2 + (n-1)(\gamma + \mu ^2)] - 2\, \binom {n-1}{2}\, \mu ^2 - 2(n-1)\mu \, x\right \} - \gamma \\ & = \frac {1}{n(n-1)}\left ((n-1)x^2 + (n-1)^2 \gamma + (n-1)^2\mu ^2 - (n-1)(n-2)\mu ^2 - 2(n-1)\mu \, x\right ) - \gamma \\ & = \frac {1}{n}(x^2 + (n-1)\gamma + (n-1)\mu ^2 - (n-2)\mu ^2 - 2\mu \, x) - \gamma \\ & = \frac {1}{n} \, \left (x^2 + (n - 1)\gamma + \mu ^2 - 2\mu \, x\right ) - \gamma \\ & = \frac {1}{n}\, \left ((x - \mu )^2 + (n - 1)\gamma - n\gamma \right )\\ & = \frac {1}{n}\left ((x - \mu )^2 - \gamma \right ). \end {align*}
\begin {align*} K^*(x) & = \frac {1}{n}\, \left ((x- \mu )^2 - \gamma \right )\\ K^*(x) &= E\left (U_2(X_1, \, X_2, \, \cdots \, , \, X_n) - \gamma / X_i = x\right )\\ \sum ^n_{i = 1} K^*(x_i) & = \sum ^n_{i = 1} E\left (U_2(X_1, \, X_2, \, \cdots \, , \, X_n) - \gamma / X_i = x\right )\\ &= \frac {1}{n}\sum ^n_{i = 1}(x_i - \mu )^2 - \gamma . \end {align*}
\(V^*_2 = \frac {1}{n}\sum ^n_{i = 1}(x_i - \mu )^2 - \gamma \,\) is the projection of \(U_2(X_1, \, X_2, \, \cdots \, , \, X_n) - \gamma \) on \(\mathcal {V}\).
- (a)
- \(V^*\) has expected value of zero like \(U_2(X_1, \, X_2, \, \cdots \, , \, X_n) - \gamma \).
- (b)
- The asymptotic distribution of \(V^*_2\) is easily established from the usual central limit theorem, since it is a sum of \(iid\) random variables.
\(*\) What is the projection of \(U_1(X_1, \, X_2, \, \cdots \, , \, X_n) - \mu ?\)
The general expression of the projection on a one-sample \(U\)-statistics can be constructed.
If \(h(X_1, \, X_2, \, \cdots \, , \, X_k)\) denotes a symmetric kernel, let \(h_1(x) = E\left (h(x_1, \, x_2, \, \cdots \, , \, x_k)\right )\) \[h_1(x) = E\left (h(x_1, \, x_2, \, \cdots \, , \, x_k)\right ) = E\left (h(X_1, \, X_2, \, \cdots \, , \, X_k, \, x)\right )\] \[E\left (h_1(x)\right ) = E_{X_1}\left [E\left (h(x_1, \, x_2, \, \cdots \, , \, x_k)/X_1 = x\right )\right ] = \gamma \] \begin {align*} var\left (h_1(X_1)\right ) & = E\left (h^2_1(X_1)\right ) - \gamma ^2\\ & = E_{X_1}\left [E\left (h(X_1, \, X_2, \, \cdots \, , \, X_k)h(X_1, \, X_{k +1}, \, X_{k + 2}, \, \cdots \, , \, X_{2k - 1})/X_1\right ) - \gamma ^2\right ]\\ & = E\left [h(X_1, \, X_2, \, \cdots \, , \, X_k)h(X_1, \, X_{k + 1}, \, X_{k + 2}, \, \cdots \, , \, X_{2k - 1})\right ] - \gamma ^2\\ & = \Im _1 \end {align*}
Lemma 3.3.5. If \(U(\cdot )\) is a one-sample \(U\)-statistics for an estimable parameter \(\gamma \) of degree \(k\) and a symmetric kernel \(h(\cdot )\), then the projection of \(U(\cdot )-\gamma \) on \(\mathcal {V}\) is given by \[V^* = \frac {k}{n}\sum ^n_{i = 1} \left \{h_1(x_i) - \gamma \right \}\] where \(h_1(x) = E\left (h(X_1, \, X_2, \, \cdots \, , \, X_k)\right )\).
Proof. \begin {align*} E\left (U(X_1, \, X_2, \, \cdots \, , \, X_n) - \gamma / X_i = x\right ) =& E\left \{\frac {1}{\binom {n}{k}}\sum _{\beta \in \mathcal {B}}h(X_{\beta _1}, \, X_{\beta _2}, \, \cdots \, , \, X_{\beta _k})-\gamma / X_i = x\right \}\\ = & \frac {1}{\binom {n}{k}}\left \{\binom {n-1}{k} + \sum _{\beta '\in \mathcal {B}'}E\left (h(X_{\beta '_1}, \, X_{\beta '_2}, \, \cdots \, , \, X_{\beta '_k})\right )/ X_i = x\right \}\\ & - \gamma \end {align*}
where \(\beta '\) is the collection of all subsets of \(k\) of the integers \(1, \, 2, \, \cdots \, , \, n\) that include the integer \(i\). \begin {align*} & = \frac {(n - k)\gamma }{n} + \frac {1}{\binom {n}{k}}\sum _{\beta '\in \mathcal {B}'}E\left (h(X_{\beta '_1}, \, X_{\beta '_2}, \, \cdots \, , \, X_{\beta '_k})/X_i = x\right ) - \gamma \\ & = \frac {-k\gamma }{n} + \frac {1}{\binom {n}{k}}\binom {n-1}{k -1} \, h_1(x)\\ & = \frac {-k\gamma }{n} + \frac {k!\, (n-k)!}{n!} \cdot \frac {(n-1)!}{(k - 1)!\, (n - k)!}\, h_1(x)\\ & = \frac {-k\gamma }{n} + \frac {k}{n}\, h_1(x)\\ & = \frac {k}{n}\, \left (h_1(x) - \gamma \right ). \end {align*}
\[\therefore \, \sum ^n_{i = 1}E\left (U(X_1, \, X_2, \, \cdots \, , \, X_n)- \gamma /X_i = x_i\right ) = \frac {k}{n}\sum ^n_{i = 1}\left (h_1(x_i) - \gamma \right ).\] □
Lemma 3.3.6. Suppose \(W^* = W^*(X_1, \, X_2,\, \cdots \, ,\, X_n)\) treats \(n\, \)iid random variables \(X_1, \, X_2,\, \cdots \, ,\, X_n\) symmetrically and \(E(W^*) = 0\). Let \(V^*\) to be the projection of \(W^*\) onto \(\mathcal {V}\). i.e \[V^* = \sum ^n_{i = 1}K^*(X_i)\] where \(K^*(x) = E(W^*/ X_i = x)\). Then for any \(V\in \mathcal {V}\) \[E\left \{(W^*-V^*)^2\right \} \, \leq \, E\left \{(W^* - V)^2\right \}.\]
Proof. \begin {align*} E\left \{(W^* - V)^2\right \} & = E\left \{(W^* - V^* + V^* - V)^2\right \}\\ & = E(W^* - V^*)^2 + E(V^* - V)^2 + 2E\left \{(W^* - V^*)\, (V^* - V)\right \}\hspace {0.3cm} \cdots \cdots \hspace {0.4cm} (a) \end {align*}
Using \(V = \sum ^n_{i = 1} K(x_i)\) and \(V^* = \sum ^n_{i = 1} K^*(x_i)\) we write \[E(W^* - V^*)\, (V^* - V) \, = \, \sum ^n_{i=1}E\left \{(W^* - V^*)\, \left (K^*(x_i) - K(x_i)\right )\right \}\] now \begin {align*} E(W^* - V^*)\, \left (K^*(x_i) - K(x_i)\right ) & = E_{X_i}\left (E(W^* - V^*)\left (K^*(x_i) - K(x_i)\right )\big /X_i\right )\\ & = E_{X_i}\left (K^*(x_i) - K(x_i)\right )\, E\left ((W^* - V^*)\big /X_i\right ). \end {align*}
However \begin {align*} E\left \{(W^*-V^*)\big /X_i = x\right ) & = E\left \{W^*\big /X_i = x - K^*(x)\right ) - (n-1)\, E\left (K^*(x_j)\right )\\ & = K^*(x) - K^*(x)\\ & = 0. \end {align*}
Since \(E\left (K^*(x_j)\right ) = E(W^*) = 0\). Therefore \((a)\) becomes \[E(W^* - V^*)^2 = E(W^* - V^*)^2 + E(V^* - V)^2\] \(\implies \hspace {0.2cm} E(W^* - V^*)^2 \leq E(W^* - V)^2\, \) since \(E(V^* -V)^2\geq \). Hence the result. □
Now we are in a position to prove the theorem due to Hoeffding(1948) that establishes the asymptotic normality of standardised one-sample \(U\)-statistic. It proves an example of a central limit theorem for dependent random variables.
Theorem 3.3.7 (Hoeffding One-Sample \(U\)-Statistic Theorem). Let \(X_1, \, X_2, \, \cdots \, , \, X_n\) denote a random sample from some population. Let \(\gamma \) be an estimable parameter of degree \(K\) with symmetric kernel \(h(x_1, \, x_2, \, \cdots \, , \, x_K)\). If \(E\left \{h^2(X_1, \, X_2, \, \cdots \, , \, X_K)\right \} < \infty \) and if \[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}\) consists of subsets of \(K\) integers chosen without replacements from \(\{1, \, 2, \, \cdots \, , \, n\}\) then \(\sqrt {n}\left (U(X_1, \, X_2, \, \cdots \, , \, X_n)-\gamma \right )\) has a limiting normal distribution with mean zero and variance \(K^2\, \Im _1\) provided
Proof. Denote \(U(X_1, \, X_2, \, \cdots \, , \, X_n)\) by \(U_n\) \begin {equation} nE\left \{(U_n - \gamma - V^*_n)^2\right \} = n\, E\left (U_n - \gamma \right )^2 + n\, E\left (V^*_n\right )^2 - 2n\, E\left ((U_n - \gamma )\, V^*_n\right ) \end {equation} where \(V^*_n\) is the projection of \(U_n - \gamma \) given by lemma 3.3.3
Consider \(\, n\, E\left \{(U_n - \gamma )\, V^*_n\right \}\) \begin {align*} n\, E\left \{(U_n - \gamma )\, V^*_n\right \} & = n\, E\left \{\frac {1}{\binom {n}{k}}\sum _{\beta \in \mathcal {B}}h(X_{\beta _1}, \, X_{\beta _2}, \, \cdots \, , \, X_{\beta _k})\,\times \, \frac {k}{n}\sum ^n_{i = 1} (h_1(X_i) - \gamma )\right \}\\ & = \frac {k}{\binom {n}{k}}\sum ^n_{i = 1}\sum _{\beta \in \mathcal {B}} E\left \{(h(X_{\beta _1}, \, X_{\beta _2}, \, \cdots \, , \, X_{\beta _k})-\gamma )(h_1(X_i) - \gamma )\right \} \end {align*}
Note 3.3.8. if \(i \not \in \{\beta _1, \, \beta _2, \, \cdots \,, \, \beta _k\}\) then \(E\left (h(X_{\beta _1}, \, X_{\beta _2}, \, \cdots \, , \, X_{\beta _k}) - \gamma )(h_1(X_i) - \gamma \right ) = 0\) and if \(i\in \{\beta _1, \, \beta _2, \, \cdots \, , \, \beta _k\}\), then \(\left ((h(X_{\beta _1}, \, X_{\beta _2}, \, \cdots \, , \, X_{\beta _k}) -\gamma )(h_1(X_i) - \gamma )\right ) = \Im _1\). Since each \(i = 1, \, 2,\, \cdots \, ,\, n\) occurs in \(\binom {n - 1}{k - 1}\) of the possible sets \(\{\beta _1, \, \beta _2, \, \cdots \, , \, \beta _k\}\) we have
\begin {align*} n\, E\left ((U_n - \gamma ) \, V_n^*\right ) & = \frac {n\, k}{\binom {n}{k}}\, \binom {n - 1}{k - 1}\, \Im _1\\ & = \frac {nk\, k!\, (n-k)!}{n!}\, \frac {(n-1)!}{(k- 1)!\, (n - k)!}\, \Im _1\\ & = K^2\, \Im _1. \end {align*}
Then 3.2 becomes \begin {align*} n\, E\left \{(U_n - \gamma - V^*_n)^2\right \} & = n\, E\left (U_n - \gamma \right )^2 + n\, E\left (V^*_n2\right )^2 - 2K^2\, \Im _1\\ & = n\, E\left (U_n - \gamma \right )^2 + K^2\, \Im _1 - 2K^2\, \Im _1 \end {align*}
Thus \begin {align*} \lim _{n\rightarrow \infty } n\, E\left \{(U_n - \gamma - V^*_n)^2\right \} & =\lim _{n\rightarrow \infty } n\, E\left \{\underbrace {\left (U_n - \gamma \right )^2}_{K^2\Im _1}\right \} - K^2\, \Im _1\\ & = 0. \end {align*}
\begin {equation} \sqrt {n}\, (U_n - \gamma ) \, \underset {\longrightarrow }{L} \, N\left (0, \frac {K^2\, \Im _1}{n}\right ) \end {equation} \(\sqrt {n}\, (U_n - \gamma )\) and \(\sqrt {n}\, V^*_n\) have the same limiting distribution. The central limit theorem and 3.3 show that \(\, \sqrt {n}\, V^* \longrightarrow \, N(0,K^2\Im _1)\). □
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.