MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Just a quick comment to thank Douglas for adding the link and tidying the formatting – Yemon Choi Mar 28 '10 at 21:52
up vote 3 down vote accepted

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)$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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