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

  • 1
    $\begingroup$ Could you be more specific concerning what you suppose such a theorem might assert? "Resampling" covers an awful lot of ground! $\endgroup$ – whuber May 7 '19 at 18:56
  • $\begingroup$ @whuber: You are right that I need to be more specific. I added an example. $\endgroup$ – Hans May 7 '19 at 22:31
  • 2
    $\begingroup$ Don't cross-post. If you want a question to have more attention, you can add a bounty. If you want to have the question appear elsewhere, you can flag the question for migration. meta.stackexchange.com/questions/64068/… $\endgroup$ – Sycorax Oct 7 '19 at 18:01
  • 2
    $\begingroup$ That's not how this site works. If you want to debate the merits of cross-posting, you can open a question of meta.SO. If you want avoid down-votes, use the site in accordance with the community norms. $\endgroup$ – Sycorax Oct 7 '19 at 18:59
  • 1
    $\begingroup$ Click the word "flag" below the post, click "in need of moderator intervention," then write a note requesting migration. Only moderators can do migration. $\endgroup$ – Sycorax Oct 7 '19 at 19:06

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

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}

| cite | improve this answer | |
  • $\begingroup$ Would the downvoter care to explain which part of the question and the rigorous answer/proof he thinks is wrong or does not like? $\endgroup$ – Hans Oct 7 '19 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.