# estimate the error term in CLT

Let $X_m = \frac{1}{\sqrt{m}}\sum_{k=1}^m Z_k$ where $Z_k$ are iid equally likely on $\{\pm 1\}$. Then $X_m$ convergens to $X \sim \mathcal{N}(0,1)$ in distribution by CLT.

Let $f$ be a smooth bounded function on $\mathbb{R}$. Then $\mathbb{E}[f(X_m)] \to \mathbb{E}[f(X)]$. I wonder if there is any general method to give sharp asymptotic estimate of the error term $\mathbb{E}[f(X_m)] - \mathbb{E}[f(X)]$, which I expect to be $\Theta(1/m)$. The scaling constant should depend on $f$ (as well as the distribution of $Z_k$ if they are not binary).

For law of large number, this type of estimate can be done via the Delta method (e.g., to estimate $\mathbb{E}[f(\bar{Z})] - f(0)$). There must be a counterpart for CLT... I haven't found the Edgeworth expansion useful because it seems to work with distribution with densities.

Edited: To be clear, I am only interested in some specific nice function (e.g., $f(x) = x^2 e^{-x^2/4}$) and finding a sharp expansion for the error term of the form, say, $c/m + o(1/m)$, where $c$ will depend n $f$. As pointed by Mark, the worst-case rate of all bounded smooth function $f$ is $1/\sqrt{m}$, which agrees with the upper bound given by Stein's method.

-
Do you perhaps mean to look at $f(\bar{X})$ instead of $f(X_m)$? For $f(x)=x^2$ your error term doesn't converge to 0. – Yaroslav Bulatov Sep 19 '10 at 19:02
No. I meant $f(X_m)$. For your $f$ the error term is zero. – mr.gondolier Sep 19 '10 at 19:12
oh...Z's are symmetric...so the error term is 0 regardless of m, right? – Yaroslav Bulatov Sep 19 '10 at 19:18
well if something converges to Gaussian weakly, then all its moments must converge. – mr.gondolier Sep 19 '10 at 19:25
Counterpart of Central Limit Theorem gives the distribution of $\sqrt{n}f(\bar{X})$. Distribution of $f(\sqrt{n}\bar{X})$ seems to have unusual behavior, for instance if $Z_i$'s are uniform on {0,1}, mean of $X_m$ goes to infinity, but because $f$ is bounded, distribution of $f(X_m)$ gets squished into a delta function – Yaroslav Bulatov Sep 19 '10 at 20:04

Stein's method typically gives good Berry-Esseen type bounds for smooth test functions. See Chapter III of Stein's book (entirely viewable in Google Books). For example, specializing to your case of symmetric Bernoulli summands, equation (37) on p. 38 gives $$\vert \mathbb{E}f(X_m)-\mathbb{E}f(X)\vert \le \frac{2\Vert f' \Vert_\infty}{\sqrt{m}}.$$ For more general summands, there is some simple dependence on the third and fourth moments as well as $\Vert f \Vert_\infty$.

Also, I'm pretty sure that $m^{-1/2}$ is the correct rate here even for Bernoullis, although I can't find a reference for a lower bound at the moment. Why do you expect better?

-
Mark, thanks for your reply. See my example below. Maybe I made a mistake? – mr.gondolier Sep 20 '10 at 15:42
It might be the case, that the answer to the question Estimates for the normal approximation of the binomial distribution will help for the lower bound... – tampis Sep 25 '15 at 12:45

The Berry-Esseen theorem is a classical result of this sort. It predicts errors on the order of $m^{-1/2}$, however.

-
I didn't find Berry-Esseen directly applicable. It deals with CDF , that is, those $f$ which is indicator of a half-open interval. Maybe you can enlighten me how to do it. In fact I am more interested in lower bound. To give an example why $m^{-1/2}$ is not tight, consider $f(x) = x^4$. Then the error term equals $2/m$. – mr.gondolier Sep 19 '10 at 19:14
@mr.gondolier: Is $f(x) = x^4$ allowed? You state in the question that $f(x)$ is bounded. – Robby McKilliam Sep 19 '10 at 22:45
My argument is as follows: if an unbounded function like $x \mapsto x^4$ has an error term like $1/m$, I am positive that we can find a bounded function (e.g. by truncation) whose error term does not exceed $1/m$, which is strictly smaller than $1/\sqrt{m}$ Nate stated. – mr.gondolier Sep 19 '10 at 22:53
BTW, results giving error on the order of $m^{-1/2}$ assume non-zero derivatives. In your case, $f(\bar{X})$ converges to 0 at the rate of $m^{-2}$, this follows from Taylor expansion of $f(\bar{X})$ around 0 – Yaroslav Bulatov Sep 20 '10 at 19:03

If $X_m$ has cumulative distribution function $F_m$, and $X$ has cumulative distribution function $F$, then (at least formally) integration by parts gives you $$E(f(X_m))-E(f(X))=\int (F_m(x)-F(x)) df(x).$$ Now you can apply the Berry-Esseen bound.

-
Also instead of Berry-Esseen it is better to apply non-uniform Berry-Esseen, i.e. something like (do not remember the constants exactly) $$|F_m(x) - F(x)| \le {\mathrm{const}\over\sqrt{m}} {1\over 1+x^3}$$ – Paul Yuryev Sep 20 '10 at 1:52

Your conjecture is correct. Suppose that (say) $f$ has a bounded $5$th derivative. Then
$$Ef(X_m) - Ef(X)=-\frac{Ef''''(X)+o(1)}{12m}. \tag{1}$$ Indeed, let $$Z_{mj}:=\frac{Z_j}{\sqrt m},\quad Y_{mj}:=\frac{Y_j}{\sqrt m},\quad T_{mk}:=\sum_{j=1}^{k-1}Z_{mj}+\sum_{j=k+1}^m Y_{mj},$$ where $Z_1,\dots,Z_m,Y_1,\dots,Y_m$ are independent random variables and $Y_j\sim N(0,1)$. Note that $EZ_{mj}^p=EY_{mj}^p$ for $p=0,\dots,3$, $EZ_{mj}^4=\tfrac1{m^2}$, $EY_{mj}^4=\tfrac3{m^2}$. Also, $Z_{mk}$ is independent of $T_{mk}$ for each $k$, and so is $Y_{mk}$. Moreover, $Ef''''(T_{mk})\to Ef''''(X)$ uniformly in $k=1,\dots,m$ (as $m\to\infty$); this should be as easy to show as the convergence $Ef(X_m) \to Ef(X)$, mentioned in the question.

Now one has
$$Ef(X_m) - Ef(X)=\sum_{k=1}^m D_k, \tag{2}$$ where
$$D_k:=E[f(T_{mk}+Z_{mk})-f(T_{mk}+Y_{mk})]$$ $$=\sum_{p=0}^4\frac1{p!}\,Ef^{(p)}(T_{mk})E(Z_{mk}^p-Y_{mk}^p)+O(E(|Z_{mk}|^5+|Y_{mk}|^5))$$ $$=\tfrac1{4!}\,(Ef''''(X)+o(1))(\tfrac1{m^2}-\tfrac3{m^2})+O(m^{-5/2})$$ by Taylor's expansion, with $o(1)$ uniform in $k=1,\dots,m$. Now $(1)$ follows immediately from $(2)$.

-

Sorry this is NOT an answer to my question... just some clarafications.

The reason I think $m^{-1/2}$ is not tight is as follows. For example, take $f$ to be the characteristic function, we have

$\mathbb{E}[e^{itX_m}] = (\mathbb{E}[e^{it Z/\sqrt{m}}])^m = (1 - t^2/(2m) + o(1/m))^m \to e^{-t^2/2} = \mathbb{E}[e^{itX}]$

at rate $1/m$, because $m\log(1-1/m) \to -1$ at rate $1/m$.

Also, it seems all moments of $X_m$ converge to the moments of $X$ at rate $1/m$. Doing a Taylor expansion for those nice $f$ should also yield a rate of $1/m$?

-
I'm not convinced by your heuristic for the characteristic function because you only get the $1/m$ rate for convergence of the log once $m \gg t^2$. So your argument shows that $\mathbb{E} e^{itX_m} \to \mathbb{E} e^{itX}$ at rate $1/m$, but with an implicit constant that may depend on $t$. Likewise, if $f$ is a polynomial, then $\mathbb{E} f(X_m) \to \mathbb{E} f(X)$ at rate $1/m$ with an implicit constant that may depend on the degree and coefficients of $f$. If, as you suggest above, you do a truncation and Taylor expansion you may lose some of that rate. – Mark Meckes Sep 20 '10 at 16:05
Just to clarify: You are correct about the $1/m$ rate for certain very nice functions, but I think that for the class of all bounded smooth functions the correct rate is $1/\sqrt{m}$, and that the loss is somehow due to the lack of uniformity in that $1/m$ rate for very nice functions. – Mark Meckes Sep 20 '10 at 16:09
I agree that there exists $f$ such that $1/sqrt{m}$ is tight. In fact I am not looking for uniform estimates but rather for a specific function $f(x) = x^2 e^(-x^2/4)$. In my OP, I said the scaling constant will depend on the function $f$. Based also on numerical result, I believe its rate is $1/m$. Do you think there is any method to produce a sharp expansion of the form $c/m + o(1/m)$? Any lower bound idea? – mr.gondolier Sep 20 '10 at 16:36
Okay, so you only expect $1/m$ for a specific $f$ you're interested in. You should edit the original question to make that clear, since it sounds like you're saying you expect $1/m$ for an arbitrary smooth bounded $f$. (I don't have an answer offhand but I'll think about it when I have some time.) – Mark Meckes Sep 20 '10 at 17:23