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.

  • 2
    $\begingroup$ Reviving this after 10 years! The final bound shown in the proof looks like: $\delta(\gamma, n) \leq c\frac{\gamma}{\sqrt{n}}+\frac{\delta(\gamma, n-1)}{2}$. The goal is show that $\delta(\gamma, n) \leq C\frac{\gamma}{\sqrt{n}}$ Using induction and the fact that $\delta(\gamma, 1) \leq 1$, I can get this statement, but not for a universal constant $C$. Each time the induction is implied the constant increases by a multiplicative factor larger than 1. Could anyone who has looked at this paper help me out with the induction part? Thank you! $\endgroup$
    – colin
    Jul 13 '21 at 20:25

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

  • $\begingroup$ 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. $\endgroup$
    – John Jiang
    Mar 29 '10 at 15:55
  • $\begingroup$ 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. $\endgroup$ Mar 29 '10 at 16:27
  • $\begingroup$ 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}$? $\endgroup$
    – John Jiang
    Mar 29 '10 at 16:44
  • $\begingroup$ 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). $\endgroup$ Mar 29 '10 at 17:59
  • $\begingroup$ Yes you are indeed right! The $1/\lambda$ cancels with the $\lambda$ in the integral. Thanks so much. $\endgroup$
    – John Jiang
    Mar 30 '10 at 0:35

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.