# Stein's method proof of the Berry-Esséen theorem

The relevant paper is "An estimate of the remainder in a combinatorial central limit theorem" by Erwin Bolthausen. I would like to understand the estimate on page three right before the sentence "where we used independence of $S_{n-1}$ and $X_n$":

\begin{align}E|f'(S_n) - f'(S_{n-1})| &\le E \bigg(\frac{|X_n|}{\sqrt{n}} \big(1 + 2|S_{n-1}| + \frac{1}{\lambda} \int_0^1 1_{[z,z+\lambda]} (S_{n-1} + t \frac{X_n}{ \sqrt{n}}) dt\big)\bigg) \\ &\le \frac{C}{\sqrt{n}} \big(1 + \delta(\gamma, n-1) / \lambda\big)\end{align}

that is, where $\delta(\gamma, n-1)/\lambda$ shows up, which is the error term in the Berry-Esséen bound.

Here $S_n = \sum_{i=1}^n X_i / \sqrt{n}$ and $X1, \ldots, X_n$ are iid with $E X_i =0$, $E X_i^2 = 1$, and $E|X_i|^3 = \gamma$. Furthermore, denote $\mathcal{L}_n$ to be the set of all sequences of $n$ random variables satisfying the above assumptions, then

$\delta(\lambda, \gamma,n) = \sup \{ |E(h_{z,\lambda} (S_n)) - \Phi(h_{z,\lambda})|: z \in \mathbb{R}, X_1, \ldots, X_n \in \mathcal{L}_n \}$

and $h_{z, \lambda}(x) = ((1 + (z-x)/\lambda) \wedge 1) \vee 0$ and $\delta(\gamma, n)$ is a short hand for $\delta(0,\gamma, n)$, and $h_{z,0}$ is interpreted as $1_{(-\infty, z]}$. I am mainly interested in verifying the second inequality, so I don't need to reproduce the definition of $f$ here, but it is related to $h$.

This paper is freely available online through springer. thanks in advance.

-
Just a quick comment to thank Douglas for adding the link and tidying the formatting – Yemon Choi Mar 28 '10 at 21:52

If you take expectation first with respect to $S_{n-1}$, then by Fubini's theorem the last term gives $$E \left[\frac{|X_n|}{\sqrt{n}}\frac{1}{\lambda} \int_0^1 P\left(z-t\frac{X_n}{\sqrt{n}} \le S_{n-1} \le z-t\frac{X_n}{\sqrt{n}} + \lambda\right) dt\right].$$ Now if $Y$ is a standard Gaussian random variable and $a\in \mathbb{R}$, then $$P(a\le S_{n-1} \le a+\lambda) \le P(a\le Y \le a+\lambda) + 2\delta(\gamma,n-1) \le \frac{\lambda}{\sqrt{2\pi}} + 2\delta(\gamma,n-1),$$ so the expectation above is bounded by $\frac{1}{\sqrt{n}}\left(\frac{1}{\sqrt{2\pi}}+2\frac{\delta(\gamma,n-1)}{\lambda}\right)$.
Hi Mark, thanks a lot for visiting my day-old question. I am still a little concerned about bounding the last term on LHS using $\delta(\gamma, n-1)$. By definition $\delta$ is the levy distance between the softened distribution function of $S_n$ and that of the standard gaussian. But the last term on the LHS is only the self-difference (so to speak) of the distribution of $S_n$ at different points of the real line, so I don't see how it connects back to the gaussian. – John Jiang Mar 29 '10 at 15:55
Whoops, that wasn't what I meant to write. I'll go back and edit when I have a chance. The point is that the probability inside the integral is within $\delta(\gamma,n-1)$ of the corresponding probability for a Gaussian; the integral of the Gaussian probability is bounded by $\lambda/\sqrt{2\pi}$ (because the Gaussian density is bounded by $(2\pi)^{-1/2}$) and so that just goes into the constant. – Mark Meckes Mar 29 '10 at 16:27
I agree that the Gaussian probability is bounded by $\lambda / \sqrt{2 \pi}$ and indeed I thought I could bound that by a constant. But since we are dividing $\delta$ by $\lambda$, and as is revealed in the end by the author, $\lambda$ is of order $1/ \sqrt{n}$, wouldn't that make it insufficient to bound with $c/\sqrt{n}$? – John Jiang Mar 29 '10 at 16:44
I think you may be overlooking the $1/\sqrt{n}$ in the prefactor. I've edited my answer so it should be clearer now (as in, actually correct). – Mark Meckes Mar 29 '10 at 17:59
Yes you are indeed right! The $1/\lambda$ cancels with the $\lambda$ in the integral. Thanks so much. – John Jiang Mar 30 '10 at 0:35