Central limit theorem for resampling

Question

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$?

Answer 1

This is no sooner cross-posted to Mathoverflow.net than is expertly answered by Iosif Pinelis, finally. I copy his answer below for interested people.

---

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*} \text{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 \begin{equation} A_n:=\{\max_{k\in[n]}J_k\le n^{1/3}\} \end{equation} (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 \begin{equation} \text{Var}\,S_n=E\,\text{Var}(S_n|\vec J)+\text{Var}\,E(S_n|\vec J) =E\frac1n\sum_1^n J_k^2+Var\,0=E J_1^2=2-1/n\to2. \end{equation}