Normal Approximation under Local Dependence
1. Finite-Sample
Sampling without replacement creates dependence: once an item is selected, it is no longer available for a later draw. This dependence reduces the variance of the sample mean. We first calculate that reduction, then compare fixed-size sampling with independent Bernoulli selection. The final examples use symmetrisation to construct U-statistics.
Let a finite population have labelled values \(x_{N,1},\ldots,x_{N,N}\); labels remain distinct even if values coincide. Draw \(1\leq n\leq N\) labels uniformly without replacement, with \(N>1\), and denote their values by \(X_1,\ldots,X_n\). Define
Each draw has mean \(\bar X_N\) and variance \(s_N^2\). For distinct draws, conditional expectation gives \(\mathbb{E}[X_j\mid X_i]=(N\bar X_N-X_i)/(N-1)\), hence
The factor \((N-n)/(N-1)\) is the finite population correction. It is one for a single draw and zero for a census.
The variance calculation identifies the correct normalising scale. A central limit theorem for \(\overline X_n\) then requires a condition preventing a few population values from dominating that variance.
Theorem 1. Along a sequence of finite populations and sample sizes with \(1\leq n<N\) and \(s_N^2>0\), suppose
Then,
We deduce Theorem 1 from a result due to Hajék.
Theorem 2 (Hájek). Assume \(s_N^2>0\) and \(\min(n,N-n)\to\infty\) along the sequence of sampling experiments. Put
Then, for every \(\varepsilon > 0\),
if and only if (2) holds.
This criterion is Hájek’s Theorem 3.1 (1960), pp. 365–367. His population values \(y_{\nu i}-\bar y_\nu\) correspond to \(s_N\delta_{N,i}\). His sample-total variance is \(ns_N^2(N-n)/(N-1)\); replacing \(N-1\) by \(N\) in the threshold is equivalent because the condition holds for every \(\varepsilon>0\). We prove sufficiency below. Necessity is the second part of Hájek’s theorem, including its treatment of arrays that fail the maximal-variance condition.
Proposition 3. Suppose \(0<\operatorname{Var}(\widetilde X_n)<\infty\), \((\widetilde X_n-\mathbb{E}\widetilde X_n)/\sqrt{\operatorname{Var}(\widetilde X_n)}\Rightarrow Z\), and
Then \((X_n-\mathbb{E}X_n)/\sqrt{\operatorname{Var}(X_n)}\Rightarrow Z\).
Proof. Put \(a_n=\sqrt{\operatorname{Var}(\widetilde X_n)}\), \(b_n=\sqrt{\operatorname{Var}(X_n)}\), and \(D_n=(X_n-\mathbb{E}X_n)-(\widetilde X_n-\mathbb{E}\widetilde X_n)\). The assumption guarantees all these second moments exist, and centering cannot increase the second moment:
The reverse triangle inequality gives \(|b_n-a_n|\leq\|D_n\|_2\), hence \(b_n/a_n\to1\); in particular \(b_n>0\) eventually. Chebyshev gives \(D_n/a_n\to0\) in probability. Consequently,
by Slutsky. ◻
Proof.
Sufficiency in Theorem 2. Center the population, so \(\sum_jx_{N,j}=0\), and put \(p=n/N\), \(r_N^2=Np(1-p)=n(N-n)/N\). Let \(I_j\) be independent Bernoulli \(p\) variables. Their selected total is \(\widetilde S=\sum_jI_jx_{N,j}\), with variance \(s_N^2r_N^2\). Its centered summands are \((I_j-p)x_{N,j}\). Since their absolute values are at most \(|x_{N,j}|\), their normalized Lindeberg sum is at most
which tends to zero by the displayed tail criterion. Thus \(\widetilde S/(s_Nr_N)\Rightarrow \mathcal{N}(0,1)\).
Couple this sample to one of size \(n\). If \(B=\sum_jI_j>n\), remove \(B-n\) selected labels uniformly; if \(B<n\), add \(n-B\) labels uniformly from the complement. By exchangeability, the resulting sample is uniform of size \(n\). Conditional on \(B\), the changed labels form a uniform subset of size \(d=|B-n|\) of the population. Their signed sum \(\widetilde S-S\) is centered and has conditional variance \(ds_N^2(N-d)/(N-1)\leq ds_N^2\) when \(d\geq1\), and zero when \(d=0\). Therefore
Here \(r_N^2\geq\frac12\min(n,N-n)\to\infty\). Proposition 3 transfers the limit to the fixed-size sample. The stronger maximum condition in Theorem 1 makes the tail sum zero eventually, since \(\max_j\delta_{N,j}^2/r_N^2\to0\), and so proves that theorem as well.
◻
2. U-Statistics
Let \(X_1,\ldots,X_n\) be i.i.d. real-valued observations, and let \(h\) be a symmetric measurable kernel of fixed degree \(r\leq n\). A nonsymmetric kernel can first be averaged over its \(r!\) argument permutations. The parameter is
for some \(r \leq n\). Note \(h(X_1,\dots,X_r)\) only depends on the first \(r\) arguments, so the displayed estimator based on a single kernel value uses only part of the sample. To estimate \(\theta\) without favouring particular sample positions, an estimator of \(\theta\) should use more than an arbitrarily selected group of \(r\) arguments it takes.
To estimate \(\theta\), average the kernel over all choices of observations. This removes the arbitrary choice of a particular subset and gives an estimator of \(\theta\) that is unchanged when the sample is reordered.
Definition 4. The \(U\)-statistic with kernel \(h\) is defined as
The sum ranges over all increasing index tuples \(1\leq\beta_1<\cdots<\beta_r\leq n\). Thus each unordered subset occurs once. Symmetry of the kernel makes the ordering within that subset immaterial.
Assume \(\mathbb{E}h(X_1,\ldots,X_r)^2<\infty\). Averaging gives \(\mathbb{E}U=\theta\) and \(\operatorname{Var}(U)\leq\operatorname{Var}(h(X_1,\ldots,X_r))\); equality is possible. More precisely, conditioning on the full ordered sample gives
Exchangeability makes every choice of \(r\) sample positions have the same conditional weight. The conditional-variance identity proves the variance bound.
The conditional-expectation identity also follows without assuming distinct observations. Average \(h(X_{\pi(1)},\ldots,X_{\pi(r)})\) over all \(n!\) permutations \(\pi\). Each subset appears \(r!(n-r)!\) times, so this average is \(U\). Multiplying by any bounded symmetric function of the full sample and using exchangeability shows that \(U\) has the defining integral identity of the displayed conditional expectation. It is measurable with respect to the order statistics, even when ties occur.
For the normal limit define \(h_1(x)=\mathbb{E}[h(x,X_2,\ldots,X_r)]-\theta\) and \(\zeta_1=\mathbb{E}h_1(X_1)^2\). When \(\zeta_1>0\),
To check the remainder estimate, subtract \(\theta+\sum_{j=1}^rh_1(x_j)\) from the kernel. The residual has conditional mean zero given any single argument. Two residual kernel values therefore have zero covariance when their index sets share at most one observation. Only \(O(n^{2r-2})\) pairs remain, and each covariance is bounded by the residual second moment. Division by \(\binom nr^2\) proves the bound. For \(r=1\) the remainder is zero. The ordinary CLT and Slutsky finish the argument. If \(\zeta_1=0\), the first projection vanishes and this nondegenerate normal limit does not apply.
In more detail, let \(g(x_1,\ldots,x_r)=h(x_1,\ldots,x_r)-\theta-\sum_{j=1}^rh_1(x_j)\). Each observation belongs to \(\binom{n-1}{r-1}\) subsets, giving the coefficient \(r/n\) of the first projection. Jensen shows \(\mathbb{E}g^2<\infty\). If two subsets share exactly one index \(i\), their remaining observations are conditionally independent given \(X_i\), and both residual conditional means are zero. Their covariance is therefore zero; disjoint subsets are independent. For a fixed first subset, at most
second subsets intersect it in at least two indices. With \(\binom nr=O(n^r)\) first subsets and Cauchy–Schwarz bounding every covariance by \(\mathbb{E}g^2\), the residual variance is \(O(n^{-2})\). Hence \(\sqrt n R_n\to0\) in \(L^2\), which justifies the stated Slutsky step.
Example 5. The mean is a \(U\)-statistic of degree 1, and the kernel is \(h(X_i) = X_i\). The \(U\)-statistic in closed form is \(\frac{1}{n} \sum_{1 \leq k \leq n} h(X_k)\). The central limit theorem gives the (usual) asymptotic normality.
Example 6. The variance is a \(U\)-statistic of degree 2, and the kernel is \(h(X_i, X_j) = \frac12 (X_i - X_j)^2\). The \(U\)-statistic in closed form is \(\frac{1}{n-1} \sum_{1 \leq k \leq n} (X_k - \overline{X}_n)^2\).
Example 7 (Signed Ranked Statistic). Let \(\theta = \mathop{\mathrm{\mathbf{P}}}(X_1 + X_2 > 0)\) be the parameter of interest. The corresponding kernel function is \(h(x,y) = \mathbb 1 \set{x+y > 0}\) (clearly). The \(U\)-statistic is
This tests if the distribution of observations is located at (or around) zero.
For the variance example, the algebra behind the closed form is
Dividing by \(2\binom n2=n(n-1)\) gives the usual unbiased sample variance. Its expectation exists under a finite second moment. Applying the general normal-limit result to this kernel additionally requires a finite fourth moment and a positive first-projection variance.
For the signed-rank kernel, \(h_1(x)=1-F(-x)-\theta\), so \(\zeta_1=\operatorname{Var}(F(-X_1))\). The null \(\theta=1/2\) alone does not determine this variance. Suppose instead that \(F\) is continuous and symmetric about zero. Then \(F(-x)=1-F(x)\), \(F(X_1)\sim\operatorname{Unif}(0,1)\), and \(\theta=1/2,\ \zeta_1=1/12\). The projection result gives
Thus the one-sided test rejecting above \(z_{1-\alpha}=\Phi^{-1}(1-\alpha)\) has asymptotic level \(\alpha\) for each continuous symmetric null distribution.
To relate this to Wilcoxon’s statistic, let \(R_i^+=\#\{j:|X_j|\leq|X_i|\}\) and \(W^+=\sum_iR_i^+1_{\{X_i>0\}}\). With no zero observations or ties in absolute value, each unordered pair contributes one to \(W^+\) exactly when the observation with larger absolute value is positive, which is equivalent to the pair sum being positive. The diagonal terms contribute the number of positive observations. Hence
Under the continuous symmetric null, conditional on the absolute values the signs are independent fair signs. This also proves the exact distribution-free representation \(W^+\overset d=\sum_{j=1}^njB_j\) with independent \(B_j\sim\operatorname{Bernoulli}(1/2)\).