The Berry–Esseen Inequality

Derives Lemma A20.2. For \(a=0\) both sides vanish. For \(a>0\) the substitution \(u=ax\) (Equation (11.27)) turns the left side into \(a\int_{-\infty}^{\infty}\left(1-\cos u\right)u^{-2}\dd u\), and the integrand is even, so it suffices to show \(\int_{0}^{\infty}\left(1-\cos u\right)u^{-2}\dd u=\pi/2\). Integrate by parts (Equation (11.28)) with \(u^{-2}\dd u=-\dd\left(u^{-1}\right)\):

by Lemma A18.5. Both boundary terms vanish: at infinity because the numerator is bounded by \(2\), and at zero because \(1-\cos u\le u^{2}/2\). Oddness of \(\cos(ax)\) in \(a\) — it is even — gives the case \(a<0\) from the case \(-a>0\).

Derives Lemma A20.3. Non-negativity and evenness are immediate, and Equation (A20.2) with \(a=T\) gives \(\int K_{T}=\pi T/(\pi T)=1\). For the tail bound use \(1-\cos\le2\), so that \(K_{T}(x)\le2/(\pi Tx^{2})\) and

For Equation (A20.4): the sine part of \(\ee^{\ii tx}\) pairs with an even function and integrates to zero, so the transform is \(\int\cos(tx)K_{T}(x)\dd x\), which is real. Write the numerator of the integrand, \(\left(1-\cos(Tx)\right)\cos(tx)\), using the product formula \(\cos A\cos B=\tfrac12\left[\cos(A-B)+\cos(A+B)\right]\):

the constants cancelling because \(-1+\tfrac12+\tfrac12=0\). Dividing by \(\pi Tx^{2}\), integrating, and applying Equation (A20.2) three times,

From Equations (A20.2) and (A20.5) (divide by \(\pi Tx^{2}\) and integrate each of the three pieces). For \(\abs{t}\le T\) the two moduli on the right are \(T+t\) and \(T-t\), so the bracket is \(\pi(T-\abs{t})\) and the value is \(1-\abs{t}/T\). For \(t>T\) they are \(T+t\) and \(t-T\), whose half-sum is \(\pi t=\pi\abs{t}\), and the bracket vanishes; the case \(t<-T\) is the mirror image.

Derives Lemma A20.4. Let \(h\) vanish outside \([-T,T]\) and put \(A(a)=\int_{\R}h(t)\ee^{-\ii ta}\dd t\). Since \(\ee^{-\ii\left(t+\pi/a\right)a}=-\ee^{-\ii ta}\), the substitution \(t\mapsto t+\pi/a\) (Equation (11.27)) gives \(A(a)=-\int_{\R}h(t-\pi/a)\ee^{-\ii ta}\dd t\), so

The function \(h\) is uniformly continuous on \(\R\) (Theorem 11.25 on a compact interval containing the support with room to spare, and \(h\equiv0\) outside), so the integrand tends to \(0\) uniformly and the interval length stays bounded.

Derives Lemma A20.5. Let \(a<x\) be a common continuity point. Applying Equation (A18.9) to \(F_{1}\) and to \(F_{2}\) and subtracting — both limits exist, so their difference is the limit of the difference — gives, for every \(T'\ge T\),

and since \(h\) vanishes outside \([-T,T]\) the integral does not depend on \(T'\) and no limit is needed. Split it into its two terms. By Lemma A20.4 the term carrying \(\ee^{-\ii ta}\) tends to \(0\) as \(a\rightarrow-\infty\) through continuity points, while \(F_{1}(a)\rightarrow0\) and \(F_{2}(a)\rightarrow0\). What survives is Equation (A20.7).

Derives Lemma A20.6. Equation (15.31) at order one gives \(\abs{\ee^{\ii x}-1-\ii x}\le\min\left(x^{2}/2,\,2\abs{x}\right)\). Put \(x=tX\), take expectations, use \(\abs{\avg{Z}}\le\avg{\abs{Z}}\) and divide by \(\abs{t}\):

the last step splitting the expectation at \(\abs{X}=K\) and using one branch of the minimum on each piece, exactly as at Equation (15.32). Given \(\varepsilon>0\) choose \(K\) with the second term below \(\varepsilon/2\) — possible because \(\avg{\abs{X}}\) is finite — and then \(\abs{t}<\varepsilon/K^{2}\).

Derives Theorem A20.7. Write \(H=F-G\), so \(\abs{H}\le1\) and \(\Delta\le1\) is finite; if \(\Delta=0\) there is nothing to prove, and if the integral on the right is infinite the inequality is trivial, so assume both finite and \(\Delta>0\). Let \(W\) have density \(K_{T}\), independently of everything else, and let \(F_{T},G_{T}\) be the distribution functions of \(U+W\) and \(V+W\), where \(U\) has distribution function \(F\) and \(V\) has \(G\). Both are continuous, being convolutions with a density, and by Proposition 15.43(iii) and Equation (A20.4) their transforms are \(\psi_{F}\,\hat{K}_{T}\) and \(\psi_{G}\,\hat{K}_{T}\) with \(\hat{K}_{T}(t)=\left(1-\abs{t}/T\right)\) on \([-T,T]\) and \(0\) outside. Since \(K_{T}\) is even,

The transform side. The function \(\left(\psi_{F}-\psi_{G}\right)\hat{K}_{T}/(\ii t)\) is continuous — at \(t=0\) because Lemma A20.6, applicable since both first absolute moments are finite, gives \(\psi_{F}(t)-\psi_{G}(t)=\ii t\left(\avg{U}-\avg{V}\right) +o(\abs{t})\), and at \(t=\pm T\) because \(\hat{K}_{T}\) vanishes there — and is supported in \([-T,T]\). So Lemma A20.5 applies, and since \(\abs{\hat{K}_{T}}\le1\),

The kernel side. Put \(\eta=\Delta/(2m)\) and \(\kappa=\int_{\abs{s}>\eta}K_{T}(s)\,\dd s\), so that \(\kappa\le4/(\pi T\eta)=8m/(\pi T\Delta)\) by Lemma A20.3. Let \(\varepsilon\in(0,\Delta/2)\). Two cases, according to which sign of \(H\) realises the supremum.

Suppose first \(\sup_{x}H(x)=\Delta\) and pick \(b\) with \(H(b)>\Delta-\varepsilon\). For \(y\ge b\) the mean value theorem (Theorem 11.35) gives \(G(y)\le G(b)+m(y-b)\), while \(F(y)\ge F(b)\); hence \(H(y)\ge H(b)-m(y-b)\). Put \(x_{\ast}=b+\eta\). For \(\abs{s}\le\eta\) the point \(x_{\ast}+s\) lies at distance \(\eta+s\in[0,2\eta]\) to the right of \(b\), so

Insert this in Equation (A20.9). The term \(-ms\) integrates to zero against the even kernel over the symmetric set \(\abs{s}\le\eta\); outside it, \(H\ge-\Delta\). Therefore

From Equations (A20.9) and (A20.11) (split the convolution at \(\abs{s}=\eta\), use the wedge bound inside and \(H\ge-\Delta\) outside, then insert \(\kappa\le8m/(\pi T\Delta)\)).

If instead \(\sup_{x}\left(-H(x)\right)=\Delta\), pick \(b\) with \(H(b)<-\Delta+\varepsilon\) and put \(x_{\ast}=b-\eta\). For \(y\le b\) the same mean value theorem gives \(G(y)\ge G(b)-m(b-y)\) and \(F(y)\le F(b)\), so \(H(y)\le H(b)+m(b-y)\); for \(\abs{s}\le\eta\) the point \(x_{\ast}+s\) lies at distance \(\eta-s\in[0,2\eta]\) to the left of \(b\) and \(H(x_{\ast}+s)\le-\Delta/2+\varepsilon-ms\). The same two steps give \(H_{T}(x_{\ast})\le-\Delta/2+\varepsilon+12m/(\pi T)\).

In both cases \(\abs{H_{T}(x_{\ast})}\ge\Delta/2-\varepsilon-12m/(\pi T)\). Combining with Equation (A20.10), letting \(\varepsilon\downarrow0\) and multiplying by \(2\) gives Equation (A20.8).

Derives Lemma A20.8. The discriminant argument of Lemma 15.63, applied to the nowhere-negative quadratic \(s\mapsto\avg{(sV+W)^{2}}\) without centring — which is all that proof uses, as Proposition 15.24 already records — gives \(\avg{VW}^{2}\le\avg{V^{2}}\avg{W^{2}}\) for any \(V,W\) of finite second moment. Take \(V=\abs{Y}^{1/2}\) and \(W=\abs{Y}^{3/2}\): \(1=\avg{Y^{2}}^{2}\le\avg{\abs{Y}}\,\avg{\abs{Y}^{3}} =\avg{\abs{Y}}\,\beta\). Take \(V=\abs{Y}\), \(W=1\): \(\avg{\abs{Y}}^{2}\le\avg{Y^{2}}=1\). Combining, \(1\le\beta\).

Derives Lemma A20.9. Write \(\psi\) for the common characteristic function of the \(Y_{i}\) and \(s=t/\sqrt{n}\), so that \(\psi_{Z_{n}}(t)=\psi(s)^{n}\) by Proposition 15.43(ii) and (iii). Fix \(t\) with \(\abs{t}\le T_{n}\); then \(\beta\abs{s}\le\tfrac12\), and since \(\beta\ge1\) by Lemma A20.8 also \(\abs{s}\le\tfrac12\).

Step 1: the quadratic expansion. Equation (15.31) at order two, with \(x=sY\), expectations taken and \(\avg{Y}=0\), \(\avg{Y^{2}}=1\) used, gives

Since \(\beta\abs{s}\le\tfrac12\) one has \(\beta\abs{s}^{3}/6\le s^{2}/12\), so

In particular \(\psi(s)\neq0\), and \(\psi(s)^{n}=\ee^{n\ln\psi(s)}\) with the principal logarithm — for an integer power the branch is immaterial.

Step 2: the logarithm. For \(\abs{w}\le\tfrac12\) the principal logarithm satisfies

Now \(n\omega+\tfrac12t^{2}=nr\), because \(ns^{2}=t^{2}\), and \(\abs{nr}\le\beta\abs{t}^{3}/(6\sqrt{n})\) by Equation (A20.14). Also, using Equation (A20.15) and then \(\abs{t}/n\le1/(2\beta\sqrt{n})\le\beta/(2\sqrt{n})\) — the last step being \(1/\beta\le\beta\), valid since \(\beta\ge1\) —

Adding, and using \(\tfrac16+\tfrac{49}{288}=\tfrac{97}{288}<\tfrac12\),

From Equations (A20.14), (A20.15) and (A20.16) (add the cubic remainder of the expansion to the quadratic error of the logarithm, using \(\beta\abs{t}\le\sqrt{n}/2\)).

Step 3: exponentiate. On \(\abs{t}\le T_{n}\),

so by Equation (A20.17) the real part of \(n\ln\psi(s)\) is at most \(-t^{2}/2+t^{2}/4=-t^{2}/4\), and the same bound holds trivially for \(\Re\left(-t^{2}/2\right)\). For complex \(a,b\),

since \(\Re\left(b+u(a-b)\right)=(1-u)\Re b+u\Re a\) is a convex combination. Taking \(a=n\ln\psi(s)\) and \(b=-t^{2}/2\) and inserting Equation (A20.17) gives Equation (A20.13).

Proof of Theorem A20.1. Derives Theorem A20.1. Put \(Y_{i}=(X_{i}-\mu)/\sigma\), so the \(Y_{i}\) are independent and identically distributed with mean \(0\), variance \(1\) and \(\beta=\avg{\abs{Y}^{3}}=\rho/\sigma^{3}\), and \(Z_{n}=n^{-1/2}\sum_{i}Y_{i}\) is the statistic of the theorem. Apply Theorem A20.7 with \(F=F_{n}\), \(G=\Phi\) and \(T=T_{n}=\sqrt{n}/(2\beta)\). The comparison function qualifies: \(\Phi\) is non-decreasing and differentiable with \(\Phi'=\varphi\le1/\sqrt{2\pi}\), so \(m=1/\sqrt{2\pi}\); and both distributions have finite first moments, namely zero. Then, by Lemma A20.9,

From Equations (A20.8) and (A20.13) (insert the transform estimate into the smoothing inequality at \(T=T_{n}=\sqrt{n}/(2\beta)\)). Extend the first integral to all of \(\R\), which only increases it, and evaluate it by the substitution \(t=2u\) together with the Gaussian moment \(\int u^{2}\ee^{-u^{2}}\dd u=\sqrt{\pi}/2\) (Proposition 15.29, rescaled):

The first term of Equation (A20.19) is therefore at most \(\left(4\sqrt{\pi}/\pi\right)\beta/(2\sqrt{n}) =2\beta/\sqrt{\pi n}\), and

since \(2/\sqrt{\pi}=1.1284\) and \(48/\left(\pi\sqrt{2\pi}\right)=6.0954\). That is Equation (A20.1). Note that no step required \(n\) to be large: the inequality holds for every \(n\ge1\), being vacuous — because \(\Delta_{n}\le1\) always — until \(n\) exceeds about \(52\beta^{2}\).