Conditional CLT for a random subset of an IID finite population

Since $E{W}_{N,1}=0$ and ${\sigma }_N^2$ is bounded, Chebyshev gives ${\bar{W}}_N\to 0$ in probability. To show $N^{-1}{\sum }_i{W}_{N,i}^2-{\sigma }_N^2\to 0$, first truncate $W^2$ at a fixed $K$: the truncated variables are bounded, so Chebyshev gives convergence of their row average to its expectation. The expected tail average is at most ${\sup }_{N}E[W_{N,1}^2{\mathbf{1}}_{\{\mathrm{\mid }{W}_{N,1}\mathrm{\mid }>\sqrt{K}\}}]$, which tends to zero as $K\to \mathrm{\infty }$ by uniform integrability. Hence the untruncated average converges to ${\sigma }^2$, and $S_N^2\to {\sigma }^2$.

Conditional on the row, list its centered values in a uniformly random order $a_{N,\pi (1)},\dots ,a_{N,\pi (N)}$ and write $S_j={\sum }_{i\le j}{a}_{N,\pi (i)}$. For $j<N$, $E[a_{N,\pi (j+1)}\mid {\mathcal{F}}_j]=-S_j\mathrm{/}(N-j)$, since the remaining values sum to $-S_j$. Therefore $M_j:=S_j\mathrm{/}(N-j)$ is a martingale for $j\le m_N$, and its increments are bounded by $2{\max }_i\mathrm{\mid }{a}_{N,i}\mathrm{\mid }\mathrm{/}(N-j-1)$. For $j\le m_N-1$, the denominator is at least $n_N$, which is bounded below by a positive multiple of $N$.

For every $\epsilon >0$, a union bound and $W^2\ge {\epsilon }^{2}N$ on $\{\mathrm{\mid }W\mathrm{\mid }>\epsilon \sqrt{N}\}$ give $P\text{\hspace{0.17em}⁣}({\max }_{i\le N}\mathrm{\mid }{W}_{N,i}\mathrm{\mid }>\epsilon \sqrt{N})\le {\epsilon }^{-2}E\text{\hspace{0.17em}⁣}\left[W_{N,1}^2{\mathbf{1}}_{\{\mathrm{\mid }{W}_{N,1}\mathrm{\mid }>\epsilon \sqrt{N}\}}\right]⟶0.$ Together with ${\bar{W}}_N=O_P(1)$, this implies ${\max }_i\mathrm{\mid }{a}_{N,i}\mathrm{\mid }\mathrm{/}\sqrt{N}\to 0$ for $a_{N,i}=W_{N,i}-{\bar{W}}_N$.

First consider any fixed finite population $c_1,\dots ,c_N$ with ${\sum }_i{c}_i=0$ and $\mathrm{\mid }{c}_i\mathrm{\mid }\le L$. For its random order, the martingale $S_j\mathrm{/}(N-j)$ from step 1.2 has increments of absolute value at most $C_{p}L\mathrm{/}N$ through $j\le m_N$, for all sufficiently large $N$. Iterating the conditional Hoeffding bound [F2] with [F7] gives, for each fixed $u>0$, $P_{\pi }(\mathrm{\mid }{S}_j\mathrm{\mid }\mathrm{/}N>u)\le 2\exp (-c_p{u}^{2}N\mathrm{/}{L}^2)$ uniformly in $j\le m_N$; here $\mathrm{\mid }{S}_j\mathrm{\mid }\mathrm{/}N>u$ implies $\mathrm{\mid }{S}_j\mathrm{/}(N-j)\mathrm{\mid }>u$ because $N-j\le N$. A union bound over at most $N$ prefixes makes the maximum divided by $N$ tend to zero. Apply this argument first to the clipped values $W_{N,i}^{(K)}-{\bar{W}}_N^{(K)}$, and then to the centered clipped squares $(W_{N,i}^{(K)}-{\bar{W}}_N^{(K)}{)}^2-\overline{(W_N^{(K)}-{\stackrel{‾}{W}}_N^{(K)}{)}^2}$. For fixed $K$, both are bounded arrays. The average absolute first-power truncation error is at most twice the average of $\mathrm{\mid }{W}_{N,i}\mathrm{\mid }{\mathbf{1}}_{\{\mathrm{\mid }{W}_{N,i}\mathrm{\mid }>K\}}$; its expectation is at most $2K^{-1}{\sup }_{N}E[W_{N,1}^2{\mathbf{1}}_{\{\mathrm{\mid }{W}_{N,1}\mathrm{\mid }>K\}}]$. The average absolute difference of the centered squares tends to zero in probability as $K\to \mathrm{\infty }$: Cauchy--Schwarz bounds it by the square root of the average squared truncation error times the square root of the average $(\mathrm{\mid }{a}_{N,i}\mathrm{\mid }+\mathrm{\mid }{W}_{N,i}^{(K)}-{\bar{W}}_N^{(K)}\mathrm{\mid }{)}^2$, whose first factor is small by uniform integrability and whose second is bounded in probability by step 1.1. Thus, taking $N\to \mathrm{\infty }$ and then $K\to \mathrm{\infty }$, we obtain both ${\max }_{j\le m_N}\frac{\mathrm{\mid }{S}_j\mathrm{\mid }}{N}\to 0,{\max }_{j\le m_N}\frac{\mid {\sum }_{i\le j}(a_{N,\pi (i)}^2-\overline{a_N^2})\mid }{N}\to 0$ in probability.

Let $R_{N,k}$ be the mean of the values remaining before draw $k$, let $s_{N,k-1}^2$ be their finite-population variance, and let ${\mathcal{F}}_{N,k}$ reveal the first $k$ draws. The Doob martingale for the final sample sum has increments $D_{N,k}=\frac{n_N}{N-k}(a_{N,\pi (k)}-R_{N,k}),1\le k\le m_N\mathrm{.}$ Indeed, after draw $k$ the conditional expected contribution of the remaining $m_N-k$ draws is $(m_N-k)$ times the new remaining mean; subtracting the previous conditional expectation gives the displayed coefficient. The increments are centered and square-integrable.

Before draw $j+1$, the remaining set has size $N-j\ge n_N\asymp N$. Its mean is $-S_j\mathrm{/}(N-j)$, and its raw second moment is $\overline{a_N^2}-\frac{1}{N-j}{\sum }_{i\le j}(a_{N,\pi (i)}^2-\overline{a_N^2})\mathrm{.}$ Both differ uniformly from $0$ and $\overline{a_N^2}$, respectively, by $o_P(1)$ by step 2.2. The remaining finite-population variance therefore differs uniformly from $S_N^2=N\overline{a_N^2}\mathrm{/}(N-1)$ by $o_P(1)$; the factors $(N-j)\mathrm{/}(N-j-1)$ tend uniformly to $1$ because $N-j\ge n_N\asymp N$. Hence ${\max }_{j\le m_N}\mathrm{\mid }{s}_{N,j}^2-S_N^2\mathrm{\mid }\to 0$.

A uniform draw from the $N-k+1$ remaining values has variance $((N-k)\mathrm{/}(N-k+1))s_{N,k-1}^2$. On $\{S_N^2>0\}$, the predictable clock of ${\sum }_{k\le m_N}{D}_{N,k}\mathrm{/}\sqrt{m_N{n}_N{S}_N^2\mathrm{/}N}$ is $\frac{1}{m_N{n}_N{S}_N^2\mathrm{/}N}{\sum }_{k=1}^{m_N}\frac{n_N^2{s}_{N,k-1}^2}{(N-k)(N-k+1)}\mathrm{.}$ Define the normalized increments and their clock to be zero on $\{S_N^2=0\}$. By step 1.1, $S_N^2{\to }_P{\sigma }^2>0$, so this zero-variance event has probability tending to zero. On its complement, step 3.1 permits replacing each $s_{N,k-1}^2$ uniformly by $S_N^2$ with relative $o_P(1)$ error. The remaining deterministic sum telescopes: $n_N^2{\sum }_{k=1}^{m_N}\frac{1}{(N-k)(N-k+1)}=n_N^2(\frac{1}{n_N}-\frac{1}{N})=\frac{m_N{n}_N}{N}\mathrm{.}$ Thus the defined normalized clock tends to $1$ in probability, in agreement with the finite-population variance in [F5]. The normalized terminal sum equals $T_N$ also on $\{S_N^2=0\}$ by the statement's convention.

On $\{S_N^2>0\}$, since $n_N\mathrm{/}(N-k)\le 1$ and $\mathrm{\mid }{R}_{N,k}\mathrm{\mid }\le {\max }_i\mathrm{\mid }{a}_{N,i}\mathrm{\mid }$, step 2.1 gives ${\max }_{k\le m_N}\frac{\mathrm{\mid }{D}_{N,k}\mathrm{\mid }}{\sqrt{m_N{n}_N{S}_N^2\mathrm{/}N}}\le \frac{2{\max }_i\mathrm{\mid }{a}_{N,i}\mathrm{\mid }}{\sqrt{m_N{n}_N{S}_N^2\mathrm{/}N}}⟶0$ in probability. Under the zero-variance convention of step 4.1, the normalized increments are zero on $\{S_N^2=0\}$ as well; since $S_N^2{\to }_P{\sigma }^2>0$, the maximum normalized increment tends to zero in probability. Therefore, for each fixed $\eta >0$, every term in the normalized martingale Lindeberg sum is zero with probability tending to one.

Suppose conditional convergence failed along a subsequence. From steps 1.1 and 2.1, choose a further subsequence on which $S_N^2\to {\sigma }^2>0$ and ${\max }_i\mathrm{\mid }{a}_{N,i}\mathrm{\mid }\mathrm{/}\sqrt{N}\to 0$ almost surely. For each positive rational $\eta$, the probability that the normalized clock differs from $1$ by more than $\eta$ tends to zero by step 4.1. Its conditional probability given the row therefore tends to zero in probability by Markov's inequality. A diagonal further subsequence makes all those conditional probabilities tend to zero almost surely. For almost every resulting sequence of rows, the conditional clock converges in probability to $1$; the normalized increments have a deterministic uniform bound tending to zero by step 5.1, so for every fixed $\eta >0$ the Lindeberg sum on that row's permutation space is exactly zero for all sufficiently large rows. The conditional permutation spaces may vary with $N$, whereas the array definition [F3] is stated on one fixed probability space. To justify using the martingale CLT in this setting, repeat the proof of [F1] with the row-specific conditional laws ${\mathbb{P}}_N^{\pi }$ and expectations ${\mathbb{E}}_N^{\pi }$. Every conditional expectation and variance estimate is formed within one row, and no joint event involving different rows is used. In particular, the only bounded-convergence step in [F1]'s proof can be read rowwise: if ${\mathrm{\Gamma }}_N\to 1$ in probability under laws ${\mathbb{P}}_N$, then for bounded continuous $f$ and any $\delta >0$, $\mid {\mathbb{E}}_{N}f({\mathrm{\Gamma }}_N)-f(1)\mid \le {\sup }_{\mathrm{\mid }x-1\mathrm{\mid }\le \delta }\mathrm{\mid }f(x)-f(1)\mathrm{\mid }+2\mathrm{\parallel }f{\mathrm{\parallel }}_{\mathrm{\infty }}{\mathbb{P}}_N(\mathrm{\mid }{\mathrm{\Gamma }}_N-1\mathrm{\mid }>\delta ),$ which tends to zero after $N\to \mathrm{\infty }$ and then $\delta \downarrow 0$. All other steps of the proof of [F1], including the Lindeberg estimate and the predictable-clock truncation, are already rowwise; hence that characteristic-function proof yields the martingale CLT for these finite permutation rows. Pad each row with zero increments. The conditional CDF converges to $\mathrm{\Phi }$ at every $t$, contradicting the assumed failure. Thus it converges in probability at each $t$.

Finally, choose $T$ so that $\mathrm{\Phi }(-T)$ and $1-\mathrm{\Phi }(T)$ are small, and partition $[-T,T]$ into finitely many points where adjacent $\mathrm{\Phi }$ values differ by at most $\epsilon$. Monotonicity of each conditional CDF bounds its deviation between grid points by the endpoint deviations plus $\epsilon$. Pointwise convergence at the finite grid and the tail bounds yield uniform convergence in probability. The convention when $S_N^2=0$ affects an event whose probability tends to zero by step 1.1 and ${\sigma }^2>0$.