# Central limit theorem for resampling

This is a cross-post from stats.stackexchange.com. No answer has appeared there. Since this is a theoretical question, mathoverflow.net seems to be a more appropriate venue for it.

What is the analog of the central limit theorem or concentration theorem for resampling, say, an i.i.d. samples? Are there any references for this topic?

Here is a simple example. Suppose there are $$n$$ i.i.d. random variables $$\{x_1,x_2,\cdots,x_n\}$$ with mean $$0$$ and standard deviation $$1$$. We sample uniformly randomly with replacement from this set $$n$$ times and obtain random variables $${y_1,y_2,\cdots,y_n}$$. What is the distribution of the mean $$\displaystyle y=\frac1{\sqrt n}\sum_{i=1}^ny_i$$ as $$n\to\infty$$?

First, we need to fix the notation a bit. Let $$X_1,X_2,\dots$$ be iid zero-mean unit-variance random variables (r.v.'s). For each natural $$n$$, let the $$n$$-tuple $$(J_1,\dots,J_n):=(J_{n,1},\dots,J_{n,n})$$ of r.v.'s be independent of the $$X_k$$'s and have the multinomial distribution with parameters $$n,1/n,\dots,1/n$$. For each $$k\in[n]:=\{1,\dots,n\}$$, the value of $$J_k=J_{n,k}$$ is the number of times the value $$X_k$$ was selected into the "re-sample" from the "sample" $$X_1,\dots,X_n$$.
Let $$\begin{equation*} S_n:=\frac1{\sqrt n}\,\sum_{k=1}^n J_k X_k, \end{equation*}$$ so that $$S_n$$ equals $$\sqrt n$$ times what you denoted by $$y$$. We have to find the limit distribution of $$S_n$$ (as $$n\to\infty$$). Let us show that this limit distribution is $$N(0,2)$$.

Indeed, note first here that the characteristic function (c.f.) $$g_n$$ of $$S_n$$ is given by the formula $$\begin{equation*} g_n(t):=Ee^{itS_n}=EE(e^{itS_n}|J_1,\dots,J_n)=E\prod_{k=1}^n f(J_kt/\sqrt n) \end{equation*}$$ for real $$t$$, where $$f$$ is the c.f. of $$X_1$$. Next, the joint moment generating function (mgf) $$M_n$$ of $$(J_1,\dots,J_n)$$ is given by the formula $$\begin{equation*} M_n(t_1,\dots,t_n):=Ee^{t_1J_1+\cdots+t_nJ_n}=\Big(\frac1n\,\sum_{k=1}^n e^{t_k}\Big)^n \end{equation*}$$ for real $$t_1,\dots,t_n$$. This follows because (i) the random vector $$(J_1,\dots,J_n)$$ is the sum of the $$n$$ iid random vectors $$(I_{1,1},\dots,I_{1,n}),\dots,(I_{n,1},\dots,I_{n,n})$$, where $$I_{j,k}$$ is the indicator that the value selected from the "sample" $$X_1,\dots,X_n$$ at the $$j$$th step was that of $$X_k$$ and (ii) the joint mgf of the random vector $$(I_{1,1},\dots,I_{1,n})$$ is $$(t_1,\dots,t_n)\mapsto\frac1n\,\sum_{k=1}^n e^{t_k}$$.

Hence, for any distinct $$k$$ and $$l$$ in $$[n]$$ $$\begin{equation*} EJ_k^2=EJ_1^2=\frac{d^2}{dt^2}M_n(t,0,\dots,0)\Big|_{t=0}=2-1/n=2+O(1/n), \end{equation*}$$ $$\begin{equation*} EJ_k^4=EJ_1^4=\frac{d^4}{dt^4}M_n(t,0,\dots,0)\Big|_{t=0}=15+O(1/n), \end{equation*}$$ $$\begin{equation*} EJ_k^2 J_l^2=EJ_1^2 J_2^2=\frac{\partial^4}{\partial t^2\partial u^2}M_n(t,u,0,\dots,0)\Big|_{t=0,u=0}=4+O(1/n). \end{equation*}$$ So, for $$\begin{equation*} W:=J_1^2+\cdots+J_n^2 \end{equation*}$$ we have $$\begin{equation*} EW=nEJ_1^2=2n+O(1), \end{equation*}$$ $$\begin{equation*} EW^2=nEJ_1^4+n(n-1)EJ_1^2 J_2^2=4n^2+O(n), \end{equation*}$$ and hence $$\begin{equation*} Var\,W=O(n). \end{equation*}$$ So, for any real $$\epsilon>0$$, $$\begin{equation*} P(|W-2n|>\epsilon n)=O(1/n)\to0, \end{equation*}$$ so that $$\frac Wn\to2$$ in probability. Also, for the event $$$$A_n:=\{\max_{k\in[n]}J_k\le n^{1/3}\}$$$$ (on which all the $$J_k$$'s are small enough) and its complement $$A_n^c$$ we have $$\begin{equation*} P(A_n^c)\le nP(J_1>n^{1/3})\le n\,EJ_1^4/n^{4/3}=O(1/n^{1/3})\to0 \end{equation*}$$ and hence $$P(A_n)\to1$$ and $$1_{A_n}\to1$$ in probability. Moreover, $$\begin{equation*} f(s)=Ee^{isX_1}=1+is\,EX_1+(is)^2EX_1^2/(2+o(1))=1-s^2/(2+o(1))=e^{-s^2/(2+o(1))} \end{equation*}$$ as $$\mathbb R\ni s\to0$$. So, for each real $$t$$
$$\begin{equation*} 1_{A_n}\prod_{k=1}^n f(J_kt/\sqrt n)=1_{A_n}\exp\Big(-\frac{t^2W}{(2+o(1))n}\Big)\to e^{-t^2} \end{equation*}$$ in probability. On the other hand, $$|f(s)|=|Ee^{isX_1}|\le E|e^{isX_1}|=E1=1$$ for all real $$s$$. Hence, $$\begin{equation*} \Big|1_{A_n^c}\prod_{k=1}^n f(J_kt/\sqrt n)\Big|\le1_{A_n^c}\to0 \end{equation*}$$ in probability for each real $$t$$. So, by dominated convergence, $$\begin{equation*} g_n(t)=E\prod_{k=1}^n f(J_kt/\sqrt n) =E1_{A_n}\prod_{k=1}^n f(J_kt/\sqrt n)+E1_{A_n^c}\prod_{k=1}^n f(J_kt/\sqrt n) \to e^{-t^2} \end{equation*}$$ for each real $$t$$.

Thus, the distribution of $$S_n$$ converges to $$N(0,2)$$, as claimed.

That the asymptotic variance of $$S_n$$ is $$2$$ (rather than $$1$$, as might have been expected) stems from the fact that $$EJ_k^2=2-1/n\to2$$. To have another look at this phenomenon, we can let $$\vec J:=(J_1,\dots,J_n)$$ and write $$$$Var\,S_n=E\,Var(S_n|\vec J)+Var\,E(S_n|\vec J) =E\frac1n\sum_1^n J_k^2+Var\,0=E J_1^2=2-1/n\to2.$$$$

• @Hans : No problem. I am going to delete my previous comment. Also, I have no objections against your suggested edit. – Iosif Pinelis Oct 4 '19 at 23:14
• I am puzzling over the validity of the application of the dominated convergence theorem which calls for pointwise convergence for the sequence of the integrand. I suppose $A_n$ is there to make sure $g_n(t)$ converges pointwise with respect to $(J_1,J_2,\cdots,J_n)$ in the set $\{|W-2n|>\epsilon n)\}\cap A_n$. However, convergence in probability does not imply (almost sure) pointwise convergence. Am I missing something? – Hans Oct 5 '19 at 0:18
• @Hans : Convergence in probability is enough for dominated convergence; see e.g. math.stackexchange.com/questions/751647/… – Iosif Pinelis Oct 6 '19 at 0:25
• +1 and accepted. Bravo! Do I learn a lot every time I read your answer or not? :-) Thank you, Iosif! Three questions. 1) Do you not like my small edit with regard to $|f|<1$, as it was rejected? Did you or someone else reject it? 2) Would you please be so kind as to add the reference and link to the theorem you provided in the above comment to the answer for posterity? 3) Would you please be so kind as to add an explicit line of the rationale for introducing $A_n$ also for posterity? – Hans Oct 6 '19 at 22:27
• @Hans : 1) I did not see or reject your edit concerning $|f|\le1$, and I have now added this detail. 2) I have added the reference to dominated convergence. 3) I have added an explanation for how $A_n$ was defined. – Iosif Pinelis Oct 7 '19 at 0:17