# Random index central limit theorem

This problem is from Durrett's Probability: Theory and Examples, Chapter 2.

Let $X_1,\ldots, X_n, \ldots$ be i.i.d. with $EX_i =0$ and $EX_i^2 = \sigma^2 \in (0, \infty)$, and let $S_n = X_1 +...+X_n$. Let $N_n$ be a sequence of nonnegative integer-valued random variables and $a_n$ a sequence of integers with $a_n \rightarrow \infty$ and $N_n/a_n =1$ in probability. How do you show the following?

$$\frac{S_{N_n}}{\sigma\sqrt{a_n}} \stackrel{weak}{\longrightarrow} \chi .$$

The hint said to use Kolmogorov's (maximal) inequality to show $$\frac{S_{N_n}}{\sigma \sqrt{a_n}}-\frac{S_{a_n}}{\sigma\sqrt{a_n}} \rightarrow 0$$ in probability. To be honest I'm still baffled, since I cannot control $\operatorname{Var}(S_{a_n}-S_{N_n})$, and I'm even baffled about where the maximality come in. To reiterate Kolmogorov's inequality: $$\Pr \left( \max_{1\leq k\leq n} |S_k| \geq x \right) \leq \frac{\operatorname{Var}(S_n)}{x^2} .$$

-
Heidi I edited the question to fix the TeX. Can you double-check the question to make sure everything is correct? (Also I think the very first equation is missing a subscript $n$ in $S_{N}$. Also perhaps you should define what $\chi$ is.) –  Srivatsan Sep 17 '11 at 19:15
you are right!, $\Chi$ is N(0,1) I believe. –  Heidi Sep 17 '11 at 19:34
The assertion that $S_{N_n}/\sigma \sqrt{a_n} \rightarrow S_{a_n}/\sigma\sqrt{a_n}$ has no meaning since the RHS depends on $n$ (and Durett DOES NOT suggest to prove this). –  Did Sep 17 '11 at 20:01
Sorry: Durrett with two r's. –  Did Sep 17 '11 at 20:42
thank you. i meant to say something else, see correction. –  Heidi Sep 17 '11 at 22:01

You are probably stuck because the random variable $N_n$ may assume far too many values for Kolmogorov's inequality to provide an effective upper bound. This suggests to deal separately with the case when $N_n$ is around $a_n$ (which, by Kolmogorov's inequality, should yield small values of $S_{N_n}-S_{a_n}$) and with the case when $N_n$ is far from $a_n$ (which, from the hypothesis that $N_n/a_n\to1$ in probability, should have small probability).
Hence, let us introduce, for a given positive $\varepsilon$, the event $$A_n=[(1-\varepsilon) a_n\leqslant N_n\leqslant (1+\varepsilon) a_n].$$ On the one hand, $N_n/a_n\to1$ in probability hence $A_n$ is typical in the sense that $\mathrm P(\Omega\setminus A_n)\to0$.
On the other hand, $|S_{N_n}-S_{a_n}|\leqslant |S_{N_n}-S_{(1-\varepsilon) a_n}|+|S_{a_n}-S_{(1-\varepsilon) a_n}|$ hence, on the event $A_n$, $$|S_{N_n}-S_{a_n}|\leqslant 2M_n,\qquad M_n=\sup\limits_{1\leqslant k\leqslant 2\varepsilon a_n}|T_k|,\qquad T_k=S_{(1-\varepsilon) a_n+k}-S_{(1-\varepsilon) a_n}.$$ Now, we are back to the realm where Kolmogorov's inequality applies, and yields $$\mathrm P(M_n\geqslant x\sqrt{a_n})\leqslant (a_nx^2)^{-1}\mathrm{Var}(T_{2\varepsilon a_n})=(a_nx^2)^{-1}(2\varepsilon a_n)\sigma^2=2\varepsilon x^{-2}\sigma^2.$$ Putting our two estimates together yields $$\mathrm P(|S_{N_n}-S_{a_n}|\geqslant 2x\sqrt{a_n})\leqslant\mathrm P(\Omega\setminus A_n)+\mathrm P(M_n\geqslant x\sqrt{a_n})\leqslant\mathrm P(\Omega\setminus A_n)+2\varepsilon x^{-2}\sigma^2.$$ This proves that, for every positive $\varepsilon$, $$\limsup\limits_{n\to\infty}\ \mathrm P(|S_{N_n}-S_{a_n}|\geqslant 2x\sqrt{a_n})\leqslant2\varepsilon x^{-2}\sigma^2,$$ hence $\mathrm P(|S_{N_n}-S_{a_n}|\geqslant2x\sqrt{a_n})\to0$ for every $x$, that is, $S_{N_n}/\sqrt{a_n}-S_{a_n}/\sqrt{a_n}\to0$ in probability.
By the usual central limit theorem, since $a_n\to+\infty$, $S_{a_n}/\sqrt{a_n}$ converges in distribution to a centered gaussian distribution with variance $\sigma^2$, hence $S_{N_n}/\sqrt{a_n}$ converges in distribution to the same centered gaussian distribution with variance $\sigma^2$.