Central Limit Theorem with Random Number of Summands

A sum may be observed at a random index, for instance when the number of observations depends on the data. Replacing that index by a nearby deterministic one introduces an increment of the partial-sum process. The main problem is to show that this increment is small on the central-limit scale.

Theorem 1. Let \((X_i)_{i\geq1}\) be i.i.d. with mean zero and variance one, and let \(S_k=\sum_{i=1}^kX_i\). Let \(\nu_n\) be positive integer-valued random variables on the same probability space. If \(\nu_n/n\xrightarrow{P}\nu\) for a random variable satisfying \(0<\nu<\infty\) almost surely, then \(S_{\nu_n}/\sqrt{\nu_n}\Rightarrow \mathcal{N}(0,1)\). Independence between the index and the observations is not required.

The proof separates the random index from the fluctuation of the partial sums. An approximation lemma first records when small errors multiplied by bounded-in-probability terms leave a limiting distribution unchanged. A maximal inequality will then control the error caused by changing the index.

Lemma 2. Suppose \(A_n=X_{m,n}+\sum_{j=1}^kY_{m,n}^{(j)}Z_{m,n}^{(j)}\), where \(k\) is fixed. Assume \(X_{m,n}\Rightarrow F\) as \(n\to\infty\) for each fixed \(m\), and, for each \(\varepsilon>0\) and \(j\),

\[\lim_{m\to\infty}\limsup_{n\to\infty}P(|Y_{m,n}^{(j)}|>\varepsilon)=0,\qquad\lim_{M\to\infty}\limsup_{m\to\infty}\limsup_{n\to\infty}P(|Z_{m,n}^{(j)}|>M)=0.\]

Then \(A_n\Rightarrow F\).

Proof.

Let \(R_{m,n}=A_n-X_{m,n}\). For \(\delta,M>0\),

\[P(|R_{m,n}|>\delta)\leq\sum_{j=1}^kP(|Y_{m,n}^{(j)}|>\delta/(kM))+\sum_{j=1}^kP(|Z_{m,n}^{(j)}|>M).\]

First take \(n\to\infty\), then \(m\to\infty\), and finally \(M\to\infty\). The error probability tends to zero. At a continuity point \(x\) of \(F\), use

\[P(X_{m,n}\leq x-\delta)-P(|R_{m,n}|>\delta)\leq P(A_n\leq x)\leq P(X_{m,n}\leq x+\delta)+P(|R_{m,n}|>\delta).\]

Choose \(x\pm\delta\) to be continuity points, take the limits in the stated order, and let \(\delta\downarrow0\).

◻

Proof of the theorem. We first prove the asymptotic independence fact needed when the index depends on the observations. Let \(A\) be any fixed event on the underlying probability space, and let \(H_n\) be uniformly bounded and measurable with respect to \(\sigma(X_j:j\geq k_n)\), where \(k_n\to\infty\). Put \(\mathscr F_\infty=\sigma(X_1,X_2,\ldots)\), \(U=\mathbb E(\mathbf1_A\mid\mathscr F_\infty)\), and \(U_K=\mathbb E(\mathbf1_A\mid X_1,\ldots,X_K)\). Conditional-expectation approximation gives \(\mathbb E|U-U_K|\to0\). For \(k_n>K\), independence of disjoint blocks gives \(\mathbb E(U_KH_n)=\mathbb P(A)\mathbb EH_n\). Consequently

\[|\mathbb E(\mathbf1_AH_n)-\mathbb P(A)\mathbb EH_n| =|\mathbb E((U-U_K)H_n)| \leq\sup_n\|H_n\|_\infty\,\mathbb E|U-U_K|\longrightarrow0,\]

where \(n\to\infty\) is taken before \(K\to\infty\). This argument also covers events \(A\) not generated by the observations. The conditional-expectation approximation itself follows by approximating the bounded \(\mathscr F_\infty\)-measurable variable \(U\) in \(L^1\) by functions of finitely many coordinates, and using the \(L^1\) contraction of conditional expectation.

For deterministic \(t>0\), put \(N_n=\lfloor nt\rfloor\) and discard the first \(\ell_n=\lfloor\sqrt n\rfloor\) summands. Their normalized sum has second moment \(\ell_n/N_n\to0\). The remaining normalized sum obeys the ordinary i.i.d. CLT and is measurable with respect to a block whose first index tends to infinity. Applying the preceding fact to a bounded Lipschitz function \(h\) of that sum, and then restoring the discarded terms, proves

\[\mathbb E\left[\mathbf1_A h\left(\frac{S_{\lfloor nt\rfloor}}{\sqrt{\lfloor nt\rfloor}}\right)\right] \longrightarrow\mathbb P(A)\mathbb Eh(Z),\qquad Z\sim\mathcal{N}(0,1).\tag{1}\]

The error from restoring the terms is at most the Lipschitz constant times \(\sqrt{\ell_n/N_n}\), by Cauchy–Schwarz.

Now fix \(0<a<b<\infty\). Partition \([a,b]\) into finitely many disjoint intervals \(I_j\) of length at most \(\delta<a/4\), assigning shared endpoints to just one interval. Set \(A_j=\{\nu\in I_j\}\), choose the midpoint \(t_j\), and write \(N_{j,n}=\lfloor nt_j\rfloor\). Let \(A_0=\{\nu\notin[a,b]\}\), and define

\[W_{n,\delta}=\sum_j\mathbf1_{A_j}\frac{S_{N_{j,n}}}{\sqrt{N_{j,n}}} +\mathbf1_{A_0}\frac{S_n}{\sqrt n}.\]

Equation (1), summed over this fixed finite partition, gives \(W_{n,\delta}\Rightarrow Z\). In particular these approximants are tight, with asymptotic tail bounds independent of the partition because every fixed-partition limit is the same normal law.

On \(A_j\cap\{|\nu_n/n-\nu|\leq\delta\}\), the two indices differ by at most \(L_n=\lceil2n\delta+2\rceil\) and are at least \(na/2\) for large \(n\). For each \(j\), let

\[B_{j,n}=\left\{\max_{|k-N_{j,n}|\leq L_n}|S_k-S_{N_{j,n}}|>u\sqrt n\right\}.\]

All indices in the window are positive for large \(n\), since \(2\delta<a/2\). Kolmogorov's maximal inequality applied separately to the forward increments and to the backward increments in reverse order gives

\[\mathbb P(B_{j,n})\leq\frac{2L_n}{u^2n}\leq\frac{C(\delta+n^{-1})}{u^2}.\]

The event \(B_{j,n}\) depends only on observations with indices at least \(N_{j,n}-L_n+1\to\infty\). The asymptotic independence calculation therefore gives \(\mathbb P(A_j\cap B_{j,n})=\mathbb P(A_j)\mathbb P(B_{j,n})+o(1)\). Summing over the fixed partition costs \(\sum_j\mathbb P(A_j)\leq1\), rather than its number of cells. Since \(\mathbb P(|\nu_n/n-\nu|>\delta)\to0\),

\[\limsup_n\mathbb P\left(\left|S_{\nu_n}-\sum_j\mathbf1_{A_j}S_{N_{j,n}}\right|>u\sqrt n,\ a\leq\nu\leq b\right) \leq\frac{C\delta}{u^2}.\tag{2}\]

It remains to compare denominators. On the same good event in \(A_j\),

\[\frac{S_{\nu_n}}{\sqrt{\nu_n}}-\frac{S_{N_{j,n}}}{\sqrt{N_{j,n}}} =\frac{S_{\nu_n}-S_{N_{j,n}}}{\sqrt{\nu_n}} +\frac{S_{N_{j,n}}}{\sqrt{N_{j,n}}} \left(\sqrt{\frac{N_{j,n}}{\nu_n}}-1\right),\]

\[\left|\sqrt{\frac{N_{j,n}}{\nu_n}}-1\right| =\frac{|N_{j,n}-\nu_n|}{\sqrt{\nu_n}(\sqrt{N_{j,n}}+\sqrt{\nu_n})} \leq\frac{2L_n}{na}.\]

The first error tends to zero in the iterated limit \(n\to\infty\), \(\delta\downarrow0\), by (2) and \(\nu_n\geq na/2\); the second does so by the tightness of \(W_{n,\delta}\) and the displayed bound. Explicitly, for any \(\varepsilon>0\),

\[\lim_{\delta\downarrow0}\limsup_n \mathbb P\left(\left|\frac{S_{\nu_n}}{\sqrt{\nu_n}}-W_{n,\delta}\right|>\varepsilon\right) \leq\mathbb P(\nu\notin[a,b]).\]

Apply the distribution-function sandwich from Lemma 2 to \(W_{n,\delta}\), whose limit is normal. First take \(n\to\infty\), then \(\delta\downarrow0\), then \(a\downarrow0\) and \(b\uparrow\infty\), and finally let the sandwich width tend to zero. The excluded probability vanishes because \(0<\nu<\infty\) almost surely, and the normal distribution function is continuous. This proves the claimed CLT. ◻