1. Introduction
Let 
$Z, Z_i$
, 
$i=1, 2, \ldots$
, be independent and identically distributed (i.i.d.) non-negative random variables with positive mean 
$\mu$
and finite variance 
$\sigma^2$
, let 
$T_0 = 0, $
for 
$n \ge 1$
let 
$T_n = \sum_{i=1}^n Z_i$
, and let 
$X_t = \max \{ n\,:\, {{T_n}} \le t\}$
. Then 
$(X_t, t \ge 0)$
is a classical renewal process.
Renewal processes are a cornerstone in applied probability and appear in a number of applications; see, for example, [Reference Omey and Vesilo10] and references therein. Since, in applications, time is finite, a quantification of the rate of convergence to normal is desirable. Also note that 
$X_t$
only takes on values in 
$\{ 0, 1, \ldots\}$
. In [Reference Englund8] it is shown that when 
$\gamma\,:\!= \textrm{E} ( | Z - \mu|^3) < \infty$
then
\begin{equation*} \sup_{n } \left| \textrm{P} (X_t < n) - \Phi \left( \frac{( n\mu - t) \sqrt{\mu}}{\sigma \sqrt{t}}\right) \right| \le 4 \left( \frac{\gamma}{\sigma} \right)^3 \left( \frac{\sqrt{\mu}}{\sqrt{t}\,} \right)^\frac12 , \end{equation*}
where 
$\Phi$
is the cumulative distribution function (CDF) of the standard normal distribution. Also in [Reference Englund8], a similar bound is indicated when Z possesses moments of order 
$\alpha$
for some 
$2 < \alpha < 3$
. Under the third moment assumption this bound was generalised to the bivariate case in [Reference Ahmad1], which in turn was generalised to a k-variate process in [Reference Niculescu and Omey9]. The result was extended in [Reference Roginsky11] to allow for non-identically distributed inter-arrival times 
$Z_i$
, again under third moment assumptions. In [Reference Billingsley3, Theorem 17.3], a functional central limit theorem for the renewal process is shown. In particular, as 
$t \rightarrow \infty$
, 
$X_t$
is asymptotically normally distributed with mean 
$\frac{t}{\mu}$
and variance 
$\frac{\sigma^2 t }{ \mu^3}$
. Hence, second moments suffice for the normal approximation. Unfortunately, [Reference Billingsley3] does not give a bound on the rate of convergence.
Explicit constants in such bounds are the gateway to quantitative applications of the results. In applications there is not usually an infinite amount of data available, and hence asymptotic results as the sample size tends to infinity are of limited value in applications, even when the order of the convergence is given, unless exact bounds are available. An illustration can be found in [Reference Chernoff7]. As a second example, in [Reference Arratia, Martin, Reinert and Waterman2] explicit bounds lead to a recommended sequence length to guarantee that a given confidence level in a statistical test procedure is achieved.
In this paper we provide an explicit bound on the rate of convergence in the case that Z has only second moments; this bound is of order 
$t^{-\frac{1}{2}}$
. This bound clearly shows the range of renewal events n for which the approximation is informative, dependent on the time t as well as the mean and the variance of the renewal process. As an intermediate result we provide explicit constants for a non-uniform Berry–Esseen theorem, quantifying [Reference Chen and Shao5, Theorem 2.2] (also [Reference Chen, Goldstein and Shao4, Theorem 8.1]). The explicit bound provides a quantitative tool to assess the quantile of interest based on the interplay between the quantile, the number of summands, the decay of the second moments of the summands, and the behaviour of truncated third absolute moments of the summands. Our main tool is Stein’s method.
The paper is organised as follows. In Section 2 we introduce the notation, we give some bounds on the tail of the normal distribution, and we provide some background from Stein’s method. Section 3 gives the main result, with a proof. The proof is based on the approach to obtain a non-uniform bound from sums of i.i.d. random variables in [Reference Chen, Goldstein and Shao4, Chapter 8], while deriving explicit bounds for the required intermediary results from that chapter. Proofs of auxiliary results are given in Section 4. For convenience, in the Appendix we re-state results from [Reference Chen, Goldstein and Shao4] which are used in this paper.
2. Notation, tail bounds, and results from Stein’s method
2.1. Notation
Let 
$Z_n$
, 
$n\geq {1}$
, be i.i.d. positive random variables. Let 
$T_0=0$
and 
$T_n = Z_{{1}} + \cdots + Z_{{n}}$
, 
$n \geq 1$
. The process 
$X=(X_t, t\geq0)$
defined by 
$X_t = {{\max}}\left\{n \geq 0 \,:\, T_n \leq t\right\}$
is the renewal process of interest.
For a renewal process 
$X_t$
whose inter-arrival times 
$Z_i$
have mean 
$\mu$
and variance 
$\sigma^2$
, and 
${n \geq 1}$
, 
$t \in \{0, 1, \ldots, \}$
fixed, we aim to compare
\begin{equation*}\textrm{P}( X_t \le n) = \textrm{P}\left( \frac{X_t - \frac{t}{\mu}}{\sigma \sqrt{t} \mu^{-\frac32}} \le \frac{(n \mu - t)\sqrt{\mu}}{\sigma \sqrt{t}} \right)\end{equation*}
to
\begin{equation*}\Phi\left(\frac{(n \mu - t)\sqrt{\mu}}{\sigma \sqrt{t}}\right).\end{equation*}
The probability 
$\textrm{P} ( X_t = 0) = \textrm{P} (Z_1 > t)$
is not of interest for a normal approximation and is not considered in this paper.
2.2. Normal tail bounds
The following results will be useful when we develop the bounds. Firstly, for every 
$w>0$
, the standard normal tail bound
\begin{align}\frac{1}{4(1+w^2)}\textrm{e}^{-\frac{w^2}{2}}\leq \Phi({-}w)= 1-\Phi(w) \leq \min\left(\frac{1}{2},\frac{1} {w\sqrt{2\pi}\,} \right)\textrm{e}^{-\frac{w^2}{2}} \end{align}
holds. This is a well-known result, see for example inequality (2.11) and p. 243 in [Reference Chen, Goldstein and Shao4]. The next result assesses the smoothness of the standard normal CDF, as follows.
Lemma 2.1. For 
$\mu>0$
, 
$\sigma>0$
, 
$n \ge 1$
, and 
$t>0$
,
\begin{equation*}I \,:\!= \left| \Phi \left( \frac{n \mu -t }{\sigma \sqrt{n}} \right) - \Phi \left( \frac{( n\mu - t) \sqrt{\mu}}{\sigma \sqrt{t}}\right)\right|\leq \begin{cases}\frac{\sqrt{2}}{\textrm{e} \sqrt{\pi}\,} \frac{\sigma}{\sqrt{t \mu }\,}& \mbox{if}\; \,t \le n \mu , \\[4pt] \frac{16 }{ \textrm{e}^2 \sqrt{2 \pi }\, } \frac{{t^2}\sigma^3 }{{n^{\frac{1}{2}} \mu^2}{(t - n \mu)^2(\sqrt{n \mu t} + t)} }& \mbox{if}\,\, t> n \mu.\end{cases}\end{equation*}
2.3. Results from Stein’s method
Stein’s method, originating from [Reference Stein12], is a powerful tool to assess distances between distributions. The proof of the statements below can be found in [Reference Chen, Goldstein and Shao4, pp. 13–16]. Let W be a random variable and suppose that the aim is to bound 
$| \textrm{P}(W \le z) - \Phi (z)| $
for all real z. For fixed 
$z \in \mathbb{R}$
, the unique bounded solution 
$f(w)\,:\!=f_z(w)$
of the so-called Stein equation,
\begin{equation} f^{\prime}(w)-wf(w)=\textbf{1}({w \leq z}) -\Phi(z) , \end{equation}
is given by
\begin{equation} f_z(w) = \begin{cases}\sqrt{2\pi}\textrm{e}^{w^2/2}\Phi(w)[1-\Phi(z)] & \mbox{if} \;w \leq z , \\[5pt] \sqrt{2\pi}\textrm{e}^{w^2/2}\Phi(z)[1-\Phi(w)] & \mbox{if} \;w>z.\\ \end{cases} \end{equation}
With this solution,
\begin{equation} \textrm{P}(W \le z) - \Phi (z) = \textrm{E} \{\,f^{\prime}(W) - W f(W) \}\end{equation}
and the right-hand side depends only on the distribution of W and can often be bounded using Taylor expansion. Moreover, for the solution 
$f_z$
of the Stein equation (2.2), 
$wf_z(w)$
is an increasing function of w, and for all real w,
\begin{align}|\,f^{\prime}_z(w)| &\leq 1 , \end{align}
\begin{align}0
< f_z(w) &\leq \min\left(\frac{\sqrt{2\pi}}{4}, \frac{1}{|z|}\right). \end{align}
3. A non-uniform bound for the renewal central limit theorem
Our main result is Theorem 3.1. As mentioned before, we restrict our attention to the regime with 
$n \ge 1$
.
Theorem 3.1. (Bound for the renewal central limit theorem under second moment assumptions.) Let 
$X=(X_t, t\geq 0)$
be a renewal process whose inter-arrival times 
$Z_n$
, 
$n\geq {1}$
, have finite mean 
$\mu \in (0,\infty)$
and finite variance 
$\sigma^2 \in (0,\infty)$
. Then, for 
$n \ge 1$
,
\begin{align*} &\left| \textrm{P} (X_t \le n) - \Phi \left( \frac{( n\mu - t) \sqrt{\mu}}{\sigma \sqrt{t}}\right) \right| \\ &\qquad\ \leq \textbf{1}( t \le n \mu) \frac{\sqrt{2}}{\textrm{e} \sqrt{\pi}\,} \frac{\sigma}{\sqrt{t} \mu } + \textbf{1}( t > n \mu) \frac{32 }{ \textrm{e}^2 \sqrt{2 \pi }\, } \frac{1}{\sqrt{t} } \left( \frac{\sigma^3 }{\mu^2\sqrt{t}\, } + \frac{ \sigma }{ (224)^2 \sqrt{\mu}\,}\right) \\ &\qquad\quad\ + 50\,990 \left(1+\left|\frac{t- n\mu} {\sigma \sqrt{n}}\right|\right)^{-2} .\end{align*}
Before we prove this result, here are some remarks.
1. The bound is valid for all
$n \ge 1$
, but for very small n it will be large, as it should be, as the sum of a few random variables is in general not close to a normal distribution.2. The explicit value of the constant in Theorem 3.1 is large. This is because the calculation of the constant is not optimized. As a result, the bound is not informative for small values of n.
3. The bound illustrates the interplay between t and n. For t much larger, or much smaller, than
$n \mu$
, the bound is of the order
$t^{-\frac{1}{2}}$
. For fixed t, as
$n \rightarrow \infty$
the bound approaches
$\frac{\sqrt{2}}{e \sqrt{\pi}\,} \frac{\sigma}{\sqrt{t} \mu } $
. For
$t = c n \mu$
with
$c > 0$
,
${{c \ne 1}}$
, the bound is of order
$n^{-\frac12}$
as
$n\rightarrow \infty$
. The bound deteriorates for t close to the expectation
$n \mu$
.4. When the inter-arrival times have a finite moment of order
$\alpha \in (2,3)$
, letting
$\gamma_\alpha = \{ \textrm{E} |Z - \mu|^\alpha\}^\frac{1}{\alpha} $
, [Reference Englund8, Theorem 2] gives as a bound
where
\begin{equation*} \sup_n \left| \textrm{P} (N(t)
< n ) - \Phi \left(\frac{ (n \mu - t)\sqrt{{\mu}}}{\sigma \sqrt{t}} \right) \right| \le C \left( \frac{\gamma_\alpha}{\sigma} \right)^\alpha \left( \frac{\mu}{t}\right)^{\frac12 \alpha -1},\end{equation*}
$\sigma$
is the square root of the variance; C is a universal constant which is not given explicitly. In contrast, Theorem 3.1 gives an explicit bound. Moreover, our result does not require the evaluation of fractional moments.5. The proof of [Reference Englund8, Theorem 2] relies strongly on nifty case-by-case considerations for the values of n in relation to t, with the cases strongly related to the third moment. While the proof cannot be adapted easily, the proof of Theorem 3.1 also involves careful case-by-case considerations for the values of n in relation to t.
6. Theorem 3.1 does not assume the existence of finite third moments. It holds as long as the inter-arrival times have finite variance. As an example where Theorem 3.1 applies but which is out of the range of the results in [Reference Englund8], assume that the inter-arrival times
$Z_i$
are discrete with probability mass function proportional to
$\frac{1}{n^3 (\log n)^2}$
. Then the inter-arrival times have second moments but no higher moments.
For the proof of Theorem 3.1, recall that, for 
$n \ge 1$
, 
$T_n = \sum_{i=1}^n Z_i$
has mean 
$n \mu $
and variance 
$n \sigma^2$
, and 
$\textrm{P}(X_t \le n) = \textrm{P} (T_n \ge t)$
. Moreover, the standardised 
$T_n$
satisfies the central limit theorem. We decompose
\begin{eqnarray}{\textrm{P} (X_t \le n) - \Phi \left( \frac{( n\mu - t) \sqrt{\mu}}{\sigma \sqrt{t}}\right)} &\,=\,& \textrm{P} (T_n \ge t) - \left\{ 1 - \Phi \left( \frac{t - n \mu }{\sigma \sqrt{n}} \right) \right\} \end{eqnarray}
\begin{eqnarray} &&+ \ \Phi \left( \frac{n \mu -t }{\sigma \sqrt{n}} \right) - \Phi \left( \frac{( n\mu - t) \sqrt{\mu}}{\sigma \sqrt{t}}\right).\end{eqnarray}
We bound the terms (3.1) and (3.2) separately. For (3.2) we employ the tail bounds for the normal distribution from Lemma 2.1. If the 
$Z_i$
had third moments, then bounding term (3.1) via Stein’s method would be straightforward, as follows. Letting 
${\tilde{T_n}} = \frac{T_n - n \mu}{\sigma \sqrt{n}} $
be the standardised version of 
$T_n$
, and setting 
${\tilde{T_n}}^{(i)} = {\tilde{T_n}} - \frac{Z_i - \mu}{\sigma \sqrt{n}\,}$
, which is independent of 
$Z_i$
, Taylor expansion on the right-hand side of (2.4) gives that, for some (random) 
$0 < \theta <1$
,
\begin{eqnarray*}\textrm{E} \{ {\tilde{T_n}} \,f ({\tilde {T_n}}) \}&\,=\,& \sum_{i=1}^n \textrm{E} \left\{ \frac{Z_i - \mu}{\sigma \sqrt{n}} [ f({\tilde {T_n}}^{(i)}) + ({\tilde {T_n}} - {\tilde {T_n}}^{(i)}) \,f^{\prime}({\tilde {T_n}}^{(i)}) \right. \\&&\left. + \ \frac12 ({\tilde {T_n}} - {\tilde {T_n}}^{(i)})^2 f^{\prime\prime}( \theta {\tilde {T_n}}^{(i)} + (1 - \theta) {\tilde {T_n}} ) ] \right\} \\&\,=\,& \sum_{i=1}^n \textrm{E} \left\{ \left( \frac{Z_i - \mu}{\sigma \sqrt{n}} \right)^2\right\} \textrm{E} \{\,f^{\prime}({\tilde {T_n}}^{(i)}) \} \\&& + \ \frac12 \sum_{i=1}^n\textrm{E} \left\{ \left(\frac{Z_i - \mu}{\sigma \sqrt{n}}\right) ^3 f^{\prime\prime}( \theta {\tilde {T_n}}^{(i)} + (1 - \theta) {\tilde {T_n}} ) \right\} ,\end{eqnarray*}
which is close to 
$ \textrm{E} \{ \,f^{\prime}({\tilde {T_n}}) \} $
when 
$\sum_{i=1}^n\textrm{E} \Big\{ \Big| \frac{Z_i - \mu}{\sigma \sqrt{n}}\Big|^3 \Big\} $
is small. When 
$\textrm{E} \{ Z_i^3 \}$
does not exist, this argument breaks down. Instead, for (3.1) truncation arguments and case-by-case arguments will be employed. With such arguments we derive non-uniform bounds using ideas from [Reference Chen, Goldstein and Shao4, Chapter 8] – our Theorem 3.2 is a version of [Reference Chen, Goldstein and Shao4, Theorem 8.1] but with the constants in the bound made explicit. This bound is of interest in its own right and hence we give it as a theorem.
Theorem 3.2. Let 
$\xi_1, \xi_2, \ldots \xi_n$
be independent random variables with mean 0 and finite variances such that 
$\sum_{i=1}^n \textrm{Var} (\xi_i) = 1$
. Let W denote their sum, 
$W=\sum_{i=1}^n \xi_i$
. Let
\begin{equation*}\beta_2 = \sum_{i=1}^n \textrm{E} \xi_i^2 \textbf{1}({|\xi_i|> 1}) \quad \mbox{and} \quad \beta_3 = \sum_{i=1}^n \textrm{E} |\xi_i|^3 \textbf{1}({|\xi_i|\leq 1}).\end{equation*}
Then, for all 
$z\in \mathbb{R}$
,
\begin{equation}|\textrm{P}(W \leq z)-\Phi(z)|\leq 2\sum_{i=1}^n \textrm{P}\left(|\xi_i|>\frac{1\vee |z|}{4}\right) + C(1+|z|)^{-2}(\beta_2+\beta_3), \end{equation}
where
\begin{equation*}C\leq \begin{cases}15 & if\; \beta_2+\beta_3\geq 1,\\37 & if\;\beta_2+\beta_3<1 \;and\; |z|\leq 2,\\25\,431 & if\; \beta_2+\beta_3<1 \;and\; |z|>2.\end{cases} \end{equation*}
The proof of Theorem 3.2 is found in Section 4. The proof of Theorem 3.1 is now almost immediate.
Proof of Theorem 3.1. First, term (3.2) is bounded directly in Lemma 2.1. The bound arising from (3.1) is less than 1 only when
\begin{equation*}\frac{| t - n \mu| }{\sigma \sqrt{n}} \ge \sqrt{50\,990} -1.\end{equation*}
Hence, if 
$\frac{| t - n \mu| }{\sigma \sqrt{n}} \le 224$
, the claim is trivially true. So we apply Lemma 2.1 for 
$\frac{| t - n \mu| }{\sigma \sqrt{n}} > 224$
, which turns the non-uniform bound for the regime 
$t > n \mu$
and 
$n \ge 1$
into a uniform bound for the regime 
$ \frac{ t - n \mu }{\sigma \sqrt{n}} > 224$
, for which we have
\begin{equation*}\frac{t}{t - n \mu} \le 1 + \frac{n \mu}{ 224 \sigma \sqrt{n}\,}\end{equation*}
so that
\begin{eqnarray*}{\frac{16 }{ e^2 \sqrt{2 \pi }\, } \frac{t^2\sigma^3 }{\sqrt{n} \mu^2(t - n \mu)^2(\sqrt{n \mu t} + t)} } & \,\le\, & \frac{32 }{ \textrm{e}^2 \sqrt{2 \pi }\, } \frac{1}{\sqrt{t }\, }\left( \frac{\sigma^3 }{\mu^2\sqrt{t}\, } + \frac{ \sigma }{ (224)^2 \sqrt{\mu}\,}\right) . \end{eqnarray*}
This gives the first part of the bound.
For term (3.1), using Theorem 3.2 it remains to show that
\begin{equation*} 2\sum_{i=1}^n \textrm{P}\left(|\xi_i|>\frac{1\vee |z|}{4}\right) \le 128 \left(\frac{1}{1+|z|}\right)^2 \end{equation*}
with 
$\xi_i = \frac{Z_i - \mu}{\sigma \sqrt{n}}$
, and then apply this inequalty to 
$z = \big| \frac{t - n \mu}{\sigma \sqrt{n}} \big| .$
Note that 
$\frac{1+|z|}{2}\leq 1\vee |z|$
. So, using Markov’s inequality,
\begin{align*}\sum_{i=1}^n \textrm{P}\left(|\xi_i|>\frac{1\vee |z|}{4}\right) &\leq \sum_{i=1}^n \textrm{P}\left(|\xi_i|>\frac{1+|z|}{8}\right)\\&\leq \left(\frac{8}{1+|z|}\right)^2 \sum_{i=1}^n \textrm{E} \xi_i^2 = \left(\frac{8}{1+|z|}\right)^2 .\end{align*}
This gives the assertion.□
Remark 2. With the notation from Theorem 3.2, under the same assumptions as for Theorem 3.1, using [Reference Englund6, Theorem 3.3] with 
$\xi_i =\frac{Z_i - \mu}{\sigma \sqrt{n}} $
to bound (3.2) gives the bound
\begin{align*} &{\left| \textrm{P} (X_t \le n) - \Phi \left( \frac{( n\mu - t) \sqrt{\mu}}{\sigma \sqrt{t}}\right) \right| } \nonumber \\& \qquad\qquad\quad\leq \frac{1}{\sqrt{t}} \max \left\{ \frac{\sqrt{2}}{\textrm{e} \sqrt{\pi}\,} \frac{\sigma}{\mu } , \frac{32 }{ \textrm{e}^2 \sqrt{2 \pi }\, } \left( \frac{\sigma^3 }{\mu^2\sqrt{t}\, } + \frac{\sigma}{(224)^2 \sqrt{\mu}\,} \right) \right\} + 4 ( 4 \beta_2 + 3 \beta_3).\end{align*}
The terms 
$\beta_2 $
and 
$\beta_3$
depend on n as well as on t in an implicit fashion but may be straightforward to calculate in some situations.
Example 1. Theorem 3.1 enables us to assess the rate of convergence in the central limit theorem for example for a renewal process 
$X_t$
whose inter-arrival times 
$Z_i $
follow a 
$\mbox{Pareto} \;({m}, \alpha)$
-distribution with 
$\alpha \in (2,3)$
for 
$i\geq 1$
. The probability density function of this distribution is 
$ f_{Z_i}(x)=\alpha m^\alpha x^{-(\alpha +1)} \textbf{1}( x\geq m)$
. This distribution has mean 
$\mu=\frac{\alpha m}{\alpha-1}$
, finite second moment, and variance 
$\sigma^2=\frac{\alpha m^2}{(\alpha-2)(\alpha-1)^2}$
, but infinite third moment. Then Theorem 3.1 gives that
\begin{align*} & { \left|\textrm{P} (X_t \le n) - \Phi \left( \frac{\sqrt{ (\alpha -1) (\alpha-2) }}{\sqrt{ m t } } \left( \frac{\alpha}{\alpha-1} m n - t \right) \right)\right| }\\ &\quad\qquad\qquad\leq\frac{\sqrt{2}}{\textrm{e} \sqrt{\pi \alpha(\alpha-2) t}\,} \, I + 50\,990\left(1 + \sqrt{\frac{\alpha-2}{\alpha}} \left|\frac{(\alpha -1) t - \alpha m n}{m \sqrt{n}} \right|\right)^{-2}\end{align*}
with
\begin{equation*} I = \textbf{1}\left( t \leq \frac{\alpha mn}{\alpha-1} \right)+ \frac{16}{\textrm{e}} \left( \frac{m}{ (\alpha-1) (\alpha-2) \sqrt{t}\,} + \frac{\sqrt{\alpha m}}{(224)^2 \sqrt{(\alpha-1)}\, } \right) \textbf{1}\left( t > \frac{\alpha mn}{\alpha-1} \right).\end{equation*}
Figure 1 illustrates the bound for a renewal process with Pareto 
$(3,\ 2.5)$
inter-arrival times at time 
$t = 3600$
; the bound tends to 0 as 
$n \rightarrow \infty.$
Bound for a renewal process with Pareto 
$(3,\ 2.5)$
inter-arrival times at time t = 3600.
4. Remaining proofs of results
Proof of Lemma 2.1. To bound 
$I = \left| \Phi \left( \frac{n \mu -t }{\sigma \sqrt{n}} \right) - \Phi \left( \frac{( n\mu - t) \sqrt{\mu}}{\sigma \sqrt{t}}\right)\right| $
we consider two cases.
Case 1: 
$n \mu \ge t$
: If 
$t \le n \mu$
then 
$\frac{n \mu}{t} \ge 1$
and
\begin{eqnarray*}I&\,\leq\,& \frac{1}{\sqrt{2 \pi}\, } \frac{n \mu -t}{\sigma \sqrt{n}}\left( \frac{\sqrt{n \mu}}{\sqrt{t}} -1 \right) \exp\left\{-\frac12 \left( \frac{n \mu -t}{\sigma \sqrt{n}} \right)^2\right\} \\&\,\leq\,& \frac{1}{\sqrt{2 \pi}\, } \frac{\sigma \sqrt{n}}{ t + \sqrt{ t n \mu}\,} \sup_{x \ge 0} \left\{ x^2 \textrm{e}^{-\frac12 x^2} \right\} \\&\,\leq\,& \frac{\sqrt{2}}{\textrm{e} \sqrt{\pi }\, } \frac{\sigma }{ \sqrt{ t \mu}\,} .\end{eqnarray*}
Case 2: 
$t > n \mu $
: If 
$t > n \mu$
then 
$\frac{n \mu}{t} < 1$
and
\begin{eqnarray*}I&\,\le\,& \frac{1}{\sqrt{ 2 \pi}\,} \frac{t - n \mu }{\sigma \sqrt{n}} \left( 1 - \frac{\sqrt{n \mu}}{ \sqrt{t}}\right) \exp\left\{-\frac12 \left( \frac{( t - n\mu ) }{\sigma \sqrt{n}} \frac{\sqrt{n \mu}}{\sqrt{t}} \right)^2 \right\} \\&\,\le\,&\frac{1}{\sqrt{ 2 \pi}\,}\frac{{t^2}\sigma^3 {n^{\frac{3}{2}}}}{{(n \mu)^2}{(t - n \mu)^2(\sqrt{n \mu t} + t)} } \sup_{x \ge 0} \left\{ x^4 \textrm{e}^{-\frac12 x^2} \right\} \\&\,\le\,& \frac{16 }{ \textrm{e}^2 \sqrt{2 \pi }\, } \frac{{t^2}\sigma^3 }{{n^{\frac{1}{2}} \mu^2}{(t - n \mu)^2(\sqrt{n \mu t} + t)} } .\end{eqnarray*}
This completes the proof.□
4.1. Proof of Theorem 3.2
For the proof of Theorem 3.2 we first show an auxiliary result, Lemma 4.1, which gives an explicit bound for [Reference Chen, Goldstein and Shao4, Lemma 8.4].
Let 
$\xi_1, \ldots ,\xi_n$
denote independent random variables with zero means and variances summing to one. Let W denote their sum, 
$W=\sum_{i=1}^n \xi_i$
. We consider the truncated random variables and their sums:
\begin{equation}\overline{x_i}=\xi_i\textbf{1}({\xi_i\leq 1}), \qquad \overline{W}=\sum_{i=1}^n \overline{x_i}, \qquad \overline{W}^{(i)}=\overline{W}-\overline{x_i}. \end{equation}
Lemma 4.1. Let 
$f_z$
denote the solution to the Stein equation (2.2). For 
$z>2$
and for all 
$s\leq\break t\leq 1$
, we have
\begin{align*} &{\textrm{E} \!\left[(\overline{W}^{(i)}+\overline{x_i}) f_z(\overline{W}^{(i)}+\overline{x_i}) - (\overline{W}^{(i)}+t)f_z(\overline{W}^{(i)}+t)\right]} \\ &\qquad\qquad\leq \left(25.8+\frac{20e^{\textrm{e}^2-2}}{\sqrt{2\pi}}\right) \textrm{e}^{-\frac{z}{2}}\min(1,|s|+|t|). \end{align*}
Proof of Lemma 4.1. Let 
$g(w)=(wf_z(w))^{\prime}$
. Then, for all 
$s\leq t\leq 1$
,
\begin{equation*}\textrm{E} \!\left[\left(\overline{W}^{\left(i\right)}+t\right) f_z\left(\overline{W}^{\left(i\right)}+t\right)-\left(\overline{W}^{\left(i\right)}-s\right) f_z\left(\overline{W}^{\left(i\right)}-s\right)\right] = \int_s^t \textrm{E} g\left(\overline{W}^{\left(i\right)}+u\right) \, \textrm{d} u. \end{equation*}
Using (2.3), we can compute that
\begin{equation*}g(w) = \begin{cases} \sqrt{2\pi}(1-\Phi(z))\big((1+w^2)\textrm{e}^{w^2/2}\Phi(w)+\frac{w}{\sqrt{2\pi}\,}\big) & \mbox{if} \;w \leq z , \\[3pt] \sqrt{2\pi}\Phi(z)\big((1+w^2)\textrm{e}^{w^2/2}(1-\Phi(w))-\frac{w}{\sqrt{2\pi}\,}\big) & \mbox{if} \;w>z.\\ \end{cases} \end{equation*}
Instead of 
$w\leq z$
, we consider whether or not 
$w\leq \frac{z}{2}$
. We split the problem into four cases.
Case 1. If 
$w\leq 0$
, then (5.4) from [Reference Chen and Shao5] gives
\begin{equation}\sqrt{2\pi}(1+w^2)\textrm{e}^{w^2/2}\Phi(w)+w \leq \frac{2}{1+|w|^3} \quad \mbox{for}\; w\leq 0. \end{equation}
In this case 
$w\leq 0<z$
, so
\begin{equation}g(w)\leq (1-\Phi(z))\frac{2}{1+|w|^3}\leq \frac{4(1+z^2)(1+z^3)}{1+|w|^3} \textrm{e}^{\frac{z^2}{8}}(1-\Phi(z)). \end{equation}
Case 2. If 
$0<w\leq \frac{z}{2}$
, then
\begin{align}g(w)&\leq (1-\Phi(z))(3(1+z^2)\textrm{e}^{\frac{z^2}{8}}+z) \nonumber\\&\leq \frac{4(1+z^2)(1+z^3)}{1+|w|^3} \textrm{e}^{\frac{z^2}{8}}(1-\Phi(z)).\end{align}
Case 3. If 
$\frac{z}{2}<w\leq z$
, then
\begin{align}g(w)&\leq \sqrt{2\pi}(1-\Phi(z))\bigg((1+z^2)\textrm{e}^{z^2/2}+\frac{z}{\sqrt{2\pi}\,}\bigg)\nonumber\\&\leq 8(1+z^2)\textrm{e}^{z^2/2}(1-\Phi(z)). \end{align}
Case 4. If 
$z<w$
, then replacing w by 
$-w$
in (4.2) gives
\begin{equation*}\sqrt{2\pi}(1+w^2)\textrm{e}^{w^2/2}\Phi({-}w)-w \leq \frac{2}{1+|w|^3}.\end{equation*}
In this case, we use the standard normal tail bound (2.1) to obtain
\begin{align}g(w)&\leq \Phi(z)\frac{2}{1+|w|^3} \leq 2= 8(1+z^2)\textrm{e}^{\frac{z^2}{2}} \frac{\textrm{e}^{-z^2/2}}{4(1+z^2)} \leq 8(1+z^2)e^{\frac{z^2}{2}}(1-\Phi(z)).\end{align}
\begin{equation*}g(w) \leq \begin{cases}\frac{4(1+z^2)(1+z^3)}{1+|w|^3} \textrm{e}^{\frac{z^2}{8}}(1-\Phi(z)) & \mbox{if}\; w\leq \frac{z}{2} , \\8(1+z^2)\textrm{e}^{\frac{z^2}{2}}(1-\Phi(z)) & \mbox{if}\; w>\frac{z}{2}.\\ \end{cases} \end{equation*}
So, for any 
$u \in [s,t]$
, since 
$z>2$
we have
\begin{align*}\textrm{E} g(\overline{W}^{(i)}+u)&= \textrm{E}\left[g(\overline{W}^{(i)}+u)\textbf{1}_{\overline{W}^{(i)}+u\leq \frac{z}{2}}\right] + \textrm{E}\left[g(\overline{W}^{(i)}+u)\textbf{1}_{\overline{W}^{(i)}+u> \frac{z}{2}}\right] \\&\leq \textrm{E}\left[\frac{1}{1+|\overline{W}^{(i)}+u|^3}\right]4(1+z^2)(1+z^3)\textrm{e}^{\frac{z^2}{8}}(1-\Phi(z))\\& \quad + 8(1+z^2)\textrm{e}^{\frac{z^2}{2}}(1-\Phi(z))\textrm{P}\left(\overline{W}^{(i)}+u>\frac{z}{2}\right)\\&\leq \textrm{E} \left[\frac{1}{1+|\overline{W}^{(i)}+u|^3}\right]4(1+z^2)(1+z^3)\textrm{e}^{\frac{z^2}{8}} \frac{1}{z\sqrt{2\pi}\,}\textrm{e}^{-\frac{z^2}{2}} \\& \quad + 8(1+z^2)\textrm{e}^{\frac{z^2}{2}} \frac{1}{z\sqrt{2\pi}\,} \textrm{e}^{-\frac{z^2}{2}} \textrm{P}(\textrm{e}^{2u}\textrm{e}^{2\overline{W}^{(i)}}>\textrm{e}^z).\end{align*}
Using Markov’s inequality, since 
$u\leq t\leq 1$
, we obtain
\begin{align}\textrm{E} g(\overline{W}^{(i)}+u)&\leq \frac{4(1+z^2)(1+z^3)\textrm{e}^{-\frac{3z^2}{8}}}{z\sqrt{2\pi}} \textrm{E} \left[\frac{1}{1+|\overline{W}^{(i)}+u|^3}\right] \nonumber \\ & \quad + \frac{8(1+z^2)}{z\sqrt{2\pi}}\textrm{e}^{2u-z} \textrm{E} \big[\textrm{e}^{2\overline{W}^{(i)}}\big] \nonumber\\&\leq \frac{4(1+z^2)(1+z^3)\textrm{e}^{-\frac{3z^2}{8}}}{z\sqrt{2\pi}} + \frac{8(1+z^2)}{z\sqrt{2\pi}}\textrm{e}^2 \textrm{e}^{-z} \textrm{e}^{\textrm{e}^2-3}\nonumber \\&\leq \left(25.8+\frac{20}{\sqrt{2\pi}\,}\textrm{e}^{\textrm{e}^2-2}\right) \textrm{e}^{-\frac{z}{2}}, \end{align}
where we used [Reference Chen, Goldstein and Shao4, Lemma 8.2] with 
$t=2$
and 
$\alpha=B=1$
. So, for 
$z>2$
, from (4.7) we have
\begin{align*}\int_s^t \textrm{E} g(\overline{W}^{(i)}+u) \, \textrm{d} u &\leq \left(25.8+\frac{20e}{\sqrt{2\pi}\,}\textrm{e}^{\textrm{e}^2-3}\right) \textrm{e}^{-\frac{z}{2}}(t-s) \nonumber\\&\leq \left(25.8+\frac{20\textrm{e}^{\textrm{e}^2-2}}{\sqrt{2\pi}}\right) \textrm{e}^{-\frac{z}{2}} (|t|+|s|). \end{align*}
The assertion follows.□
Proof of Theorem 3.2. Note that it is enough to consider 
$z\geq 0$
. To see this, replacing W by 
$-W$
gives
\begin{equation*}|\textrm{P}({-}W\leq z)-\Phi(z)|=|\textrm{P}({-}W\geq z)-\Phi({-}z)|=|\textrm{P}(W\leq -z)-\Phi({-}z)| . \end{equation*}
The case 
$\beta_2+\beta_3\geq 1$
:
We start with the case 
$\beta_2+\beta_3\geq 1$
. Note that
\begin{equation*} |\textrm{P}( W \le z) - \Phi (z) | = | \textrm{P} (W > z) - ( 1 - \Phi(z))| \le \textrm{P}(W>z) + 1-\Phi(z).\end{equation*}
As W is the sum of independent random variables with zero means and variances less than or equal to 1, we apply [Reference Chen, Goldstein and Shao4, Lemma 8.1] with 
$B=1$
and 
$p=2$
to obtain
\begin{align}\textrm{P}(W\geq z)&\leq \textrm{P}\left(\max_{1\leq i\leq n}|\xi_i|> \frac{z\vee 1}{2}\right) + \textrm{e}^2\left(1+\frac{z^2}{2}\right)^{-2}\nonumber\\&\leq \sum_{i=1}^n \textrm{P}\left(|\xi_i|>\frac{z\vee 1}{4}\right) + \textrm{e}^2\left(1+\frac{z^2}{2}\right)^{-2} .\end{align}
To write (4.8) as a bound of the form (3.3), we bound 
$\textrm{e}^2(1+\frac{z^2}{2})^{-2}$
by 
$1.867\textrm{e}^2(1+z)^{-2}$
.
For 
$1-\Phi(z)$
we apply the standard normal tail bound (2.1) and obtain
\begin{align}|\textrm{P}(W\leq z)-\Phi(z)|&\leq \textrm{P}(W\geq z) +|1-\Phi(z)|\nonumber\\&\leq \sum_{i=1}^n \textrm{P}\left(|\xi_i|>\frac{z\vee 1}{4}\right) + 1.867\textrm{e}^2(1+z)^{-2}(\beta_2+\beta_3) \nonumber\\&\;\;\;\; + \min\left(\frac{1}{2},\frac{1}{z\sqrt{2\pi}\,}\right)\textrm{e}^{-\frac{z^2}{2}}. \end{align}
Now we bound the standard normal tail bound in (4.9) by
\begin{equation}\min\left(\frac{1}{2},\frac{1}{z\sqrt{2\pi}\,}\right)\textrm{e}^{-\frac{z^2}{2}} \leq 1.176(1+z)^{-2}. \end{equation}
Substituting (4.10) into (4.9) gives that, for 
$z\geq 0$
,
\begin{align*}|\textrm{P}(W\leq z)-\Phi(z)|&\leq\sum_{i=1}^n \textrm{P}\left(|\xi_i|>\frac{z\vee 1}{4}\right) + (1.867\textrm{e}^2+1.176)(1+z)^{-2}(\beta_2+\beta_3)\nonumber\\&\leq 2\sum_{i=1}^n \textrm{P}\left(|\xi_i|>\frac{1\vee |z|}{4}\right) + (1.867\textrm{e}^2+1.176)(1+|z|)^{-2}(\beta_2+\beta_3). \end{align*}
Since 
$1.867\textrm{e}^2+1.176< 15$
, we have proved the theorem for the case 
$\beta_2+\beta_3 \geq 1$
.
The case 
$\beta_2+\beta_3 <1$
and 
$z \le 2$
:
Next, we consider the case 
$\beta_2+\beta_3 <1$
. We distinguish whether or not 
$z>2$
.
If 
$z\in [0, 2]$
, then we use the uniform bound [Reference Chen, Goldstein and Shao4, (3.31)], which states that
\begin{equation*} \sup_{z\in \mathbb{R}} |\textrm{P}(W\leq z)-\Phi(z)| \leq 4.1(\beta_2+\beta_3). \end{equation*}
We bound 
$4.1$
by 
$37(1+|z|)^{-2}$
for 
$z\in [0, 2]$
because 
$4.1\times (1+2)^2 <37$
. So we have
\begin{equation*}|\textrm{P}(W\leq z)-\Phi(z)|\leq 2\sum_{i=1}^n \textrm{P}\left(|\xi_i|>\frac{1\vee |z|}{4}\right) + 37(1+|z|)^{-2}(\beta_2+\beta_3). \end{equation*}
Thus we have proved the theorem when 
$\beta_2+\beta_3 <1$
and 
$z\in[0,2]$
.
The case 
$\beta_2+\beta_3 <1$
and 
$z > 2$
:
Our remaining task is to prove the theorem when 
$\beta_2+\beta_3 <1$
and 
$z>2$
. Recall the notations 
$\overline{x_i}=\xi_i\textbf{1}_{\xi_i\leq 1}$
, 
$\overline{W}=\sum_{i=1}^n \overline{x_i}$
, and 
$\overline{W}^{(i)}=\overline{W}-\overline{x_i}$
. The idea is to show that 
$\textrm{P}(W>z)$
is close to 
$\textrm{P}(\overline{W}>z)$
for 
$z>2$
. Observing that
\begin{align*}\{W>z\}&=\{W>z, \max_{1\leq i\leq n}\xi_i >1\}\cup \{W>z, \max_{1\leq i\leq n}\xi_i \leq 1\} \nonumber\\ &\subset \{W>z, \max_{1\leq i\leq n}\xi_i >1\}\cup\{\overline{W}>z\} \end{align*}
and 
$W\geq \overline{W}$
, 
$\textrm{P}(\overline{W}>z)$
yields
\begin{equation}\textrm{P}(\overline{W}>z)\leq \textrm{P}(W>z)\leq \textrm{P}(\overline{W}>z)+\textrm{P}(W>z, \max_{1\leq i\leq n}\xi_i >1). \end{equation}
From [Reference Chen, Goldstein and Shao4, Lemma 8.3], with 
$p=2$
and 
$z>2$
,
\begin{equation}\textrm{P}(W \geq z, \max_{1\leq i\leq n}\xi_i >1) \leq 2\sum_{i=1}^n \textrm{P}\left(|\xi_i|>\frac{z}{4}\right) + \textrm{e}^2\left(1+\frac{z^2}{8}\right)^{-2}\beta_2. \end{equation}
For a bound of type (3.3), we bound 
$(1+\frac{z^2}{8})^{-2}$
by 
$4(1+z)^{-2}$
. Thus, from (4.11) and (4.12),
\begin{align*}|\textrm{P}(W\geq z)-P(\overline{W}>z)| &\leq 2\sum_{i=1}^n \textrm{P}\left(|\xi_i|>\frac{z}{4}\right) + \textrm{e}^2\left(1+\frac{z^2}{8}\right)^{-2}\beta_2\\&\leq 2\sum_{i=1}^n \textrm{P}\left(|\xi_i|>\frac{z}{4}\right) + 4\textrm{e}^2(1+z)^{-2} (\beta_2+\beta_3),\end{align*}
where for the last inequality we used that 
$\beta_3 \ge 0$
.
Hence, using the triangle inequality, we have, for 
$z>2$
,
\begin{align*}|\textrm{P}(W\leq z)-\Phi(z)| &\leq |\textrm{P}(W\geq z)-\textrm{P}(\overline{W}>z)|+ |\textrm{P}(\overline{W}>z)-\Phi({-}z)| \\ &\leq 2\sum_{i=1}^n P\left(|\xi_i|>\frac{z}{4}\right) + 4\textrm{e}^2(1+z)^{-2} (\beta_2+\beta_3) + |\textrm{P}(\overline{W}\leq z)-\Phi(z)|.\end{align*}
Note that for 
$z>2$
, we can bound 
$\textrm{e}^{-\frac{z}{2}} \le \frac{16}{\textrm{e}^{1.5}}(1+z)^{-2}$
.
Now we claim that, for 
$z>2$
,
\begin{equation} |\textrm{P}(\overline{W}\leq z)-\Phi(z)|\leq 7115 \textrm{e}^{-\frac{z}{2}}(\beta_2+\beta_3).\end{equation}
If (4.13) holds, then for 
$z>2$
, bounding 
$\textrm{e}^{-\frac{z}{2}} \le \frac{16}{\textrm{e}^{1.5}}(1+z)^{-2}$
, we obtain
\begin{align}|\textrm{P}(W\leq z)-\Phi(z)| &\leq2\sum_{i=1}^n \textrm{P}\left(|\xi_i|>\frac{z}{4}\right)+ \left(4\textrm{e}^2+\frac{16}{\textrm{e}^{1.5}}\times7115\right)(1+z)^{-2}(\beta_2+\beta_3) \nonumber \\&\leq2\sum_{i=1}^n \textrm{P}\left(|\xi_i|>\frac{1\vee |z|}{4}\right)+ 25\,431(1+|z|)^{-2}(\beta_2+\beta_3), \end{align}
which proves the theorem when 
$\beta_2+\beta_3<1$
and 
$z>2$
, and therefore completes the proof of Theorem 3.2. So our remaining work is to prove (4.13).
Proof of (4.13):
We use Stein’s method as well as properties of the solution 
$f_z$
to the Stein equation (2.2). We define the function
\begin{equation*}\overline{K_i}(t)=\textrm{E}[\overline{x_i}(\textbf{1}_{0 \leq t \leq \overline{x_i}}- \textbf{1}_{\overline{x_i} \leq t <0})] , \end{equation*}
where 
$\overline{x_i}=\xi_i \textbf{1}_{\xi_i\leq 1}$
. Equation (8.24) in [Reference Chen, Goldstein and Shao4] and 
$\sum_{i=1}^n \textrm{E}{\xi_i}^2=1$
give
\begin{equation}\sum_{i=1}^n \int_{-\infty}^1 \overline{K_i}(t) \, \textrm{d} t = \sum_{i=1}^n \textrm{E}\overline{x_i}^2 = 1- \sum_{i=1}^n \textrm{E}[{\xi_i}^2 \textbf{1}_{\xi_i>1}]. \end{equation}
Using the independence between 
$\overline{W}^{(i)}$
and 
$\overline{x_i}$
,
\begin{align}\textrm{E}\left[\overline{W}f_z(\overline{W})\right] &= \sum_{i=1}^n \textrm{E}\left[\overline{x_i}f_z(\overline{W})\right]\nonumber\\&=\sum_{i=1}^n \textrm{E}[\overline{x_i}(\,f_z(\overline{W})-f_z(\overline{W}^{(i)}) )]+ \sum_{i=1}^n\textrm{E}\overline{x_i} \textrm{E}[\,f_z(\overline{W}^{(i)})]\nonumber\\&=\sum_{i=1}^n \textrm{E}\left[\overline{x_i} \int_0^{\overline{x_i}} f^{\prime}_z(\overline{W}^{(i)}+t) \, \textrm{d} t\right] + \sum_{i=1}^n \textrm{E}\overline{x_i} \textrm{E}[ f_z(\overline{W}^{(i)})] .\end{align}
The first term in (4.16) can be written as
\begin{eqnarray*}\lefteqn{\sum_{i=1}^n \textrm{E}\left[\overline{x_i} \int_0^{\overline{x_i}} f^{\prime}_z(\overline{W}^{(i)}+t) \, \textrm{d} t\right] }\\&=& \sum_{i=1}^n \textrm{E}\int_{-\infty}^1 f^{\prime}_z(\overline{W}^{(i)}+t) \overline{x_i} \textbf{1}_{0 \leq t \leq \overline{x_i}} \, \textrm{d} t - \sum_{i=1}^n \textrm{E}\int_{-\infty}^1 f^{\prime}_z(\overline{W}^{(i)}+t) \overline{x_i} \textbf{1}_{\overline{x_i}\leq t<0} \, \textrm{d} t\\&= &\sum_{i=1}^n \int_{-\infty}^1 \textrm{E}[\,f^{\prime}_z(\overline{W}^{(i)}+t)] \; \overline{K_i}(t) \, \textrm{d} t ,\end{eqnarray*}
where the last equality follows from independence. Therefore,
\begin{equation}\textrm{E}[\overline{W}f_z(\overline{W})] = \sum_{i=1}^n \int_{-\infty}^1 \textrm{E}[\,f^{\prime}_z(\overline{W}^{(i)}+t)] \; \overline{K_i}(t) \, \textrm{d} t + \sum_{i=1}^n \textrm{E}\overline{x_i} \textrm{E} [\,f_z(\overline{W}^{(i)})]. \end{equation}
Next, we replace w by 
$\overline{W}$
and take expectations in the Stein equation (2.2), together with (4.15) and (4.17), to obtain
\begin{align}\textrm{P}(\overline{W}\leq z)-\Phi(z)&= \textrm{E}[\,f^{\prime}_z(\overline{W})] - \textrm{E}[\overline{W}f_z(\overline{W})] \nonumber \\&=\textrm{E}[\,f^{\prime}_z(\overline{W})]\left(\sum_{i=1}^n \int_{-\infty}^1 \overline{K_i}(t) \, \textrm{d} t+\sum_{i=1}^n \textrm{E}[{\xi_i}^2 \textbf{1}_{\xi_i>1}]\right) \nonumber \\&= \sum_{i=1}^n \textrm{E}[{\xi_i}^2 \textbf{1}_{\xi_i>1}] E[\,f^{\prime}_z(\overline{W})] \end{align}
\begin{align}& \qquad\qquad\qquad\qquad + \sum_{i=1}^n \int_{-\infty}^1 \textrm{E}[\,f^{\prime}_z(\overline{W}^{(i)}+\overline{x_i}) - f^{\prime}_z(\overline{W}^{(i)}+t)] \overline{K_i}(t) \, \textrm{d} t \end{align}
\begin{align}& \quad + \sum_{i=1}^n \textrm{E}[\xi_i \textbf{1}_{\xi_i> 1}] E[ f_z(\overline{W}^{(i)})] \end{align}
\begin{align}\hspace*{-34pt}&= R_1 + R_2 + R_3. \nonumber\end{align}
In order to prove (4.13), we bound each of 
$R_1$
given in (4.18), 
$R_2$
given in (4.19), and 
$R_3$
given in (4.20) and show that the sum of the three bounds is less than or equal to 
$7115\textrm{e}^{-\frac{z}{2}}(\beta_2+\beta_3)$
for 
$z>2$
.
Bound for 
$R_1$
:
For 
$R_1= \sum_{i=1}^n \textrm{E}[{\xi_i}^2 \textbf{1}_{\xi_i>1}] \textrm{E}[\,f^{\prime}_z(\overline{W})]$
, substituting (2.3) into the Stein equation (2.2) gives
\begin{align*}f^{\prime}_z(w)&=w f_z(w) + \textbf{1}_{w \leq z}-\Phi(z) \\&=\begin{cases}(\sqrt{2\pi}w\textrm{e}^{w^2/2}\Phi(w)+1)(1-\Phi(z))& \mbox{if} \;w \leq z , \\[4pt] (\sqrt{2\pi}w\textrm{e}^{w^2/2}(1-\Phi(w))-1)\Phi(z) & \mbox{if}\; w>z.\end{cases}\end{align*}
Using (2.5),
\begin{align*}\textrm{E}|\,f^{\prime}_z(\overline{W})|&= \textrm{E}[|\,f^{\prime}_z(\overline{W})|\textbf{1}_{\overline{W}\leq \frac{z}{2}}] + \textrm{E}[|\,f^{\prime}_z(\overline{W})|\textbf{1}_{\overline{W}>\frac{z}{2}}]\\&= \textrm{E}[(\sqrt{2\pi}w\textrm{e}^{w^2/2}\Phi(w)+1)(1-\Phi(z))\textbf{1}_{\overline{W}\leq \frac{z}{2}})]+ \textrm{E}[|\,f^{\prime}_z(\overline{W})| \textbf{1}_{\overline{W} >\frac{z}{2}}]\\&\leq\left(\sqrt{2\pi}\; \frac{z}{2} \textrm{e}^{z^2/8}+1\right)(1-\Phi(z)) + \textrm{P}\left(\overline{W} >\frac{z}{2}\right).\end{align*}
By Markov’s inequality, 
$\textrm{P}\left(\overline{W} >\frac{z}{2}\right)=\textrm{P} \big(\textrm{e}^{\overline{W}} >\textrm{e}^{\frac{z}{2}}\big) \leq \textrm{e}^{-\frac{z}{2}}\textrm{E}[\textrm{e}^{\overline{W}}]$
. By definition 
$\overline{x_i}\leq 1$
, so 
$\textrm{E}\overline{x_i}\leq 0$
and 
$\sum_{i=1}^n \textrm{E}{\overline{x_i}}^2\leq 1$
. Applying [Reference Chen, Goldstein and Shao4, Lemma 8.2] with 
$\alpha=B=t=1$
gives
\begin{equation*}\textrm{E}[\textrm{e}^{\overline{W}}]\leq \exp(\textrm{e}-1-1)=\textrm{e}^{\textrm{e}-2}.\end{equation*}
Again employing the standard normal tail bound (2.1),
\begin{align*}\textrm{E}|\,f^{\prime}_z(\overline{W})|&\le \frac{1}{2}\textrm{e}^{-\frac{3}{8}z^2} + \frac{1}{z\sqrt{2\pi}}\textrm{e}^{-\frac{z^2}{2}} + \textrm{e}^{-\frac{z}{2}}\textrm{e}^{\textrm{e}-2}\\&\le \frac{1}{2}\textrm{e}^{-\frac{1}{2}}\textrm{e}^{-\frac{z}{2}} +\frac{\textrm{e}^{-1}}{2\sqrt{2\pi}} \textrm{e}^{-\frac{z}{2}} + \textrm{e}^{-\frac{z}{2}}\textrm{e}^{\textrm{e}-2}.\end{align*}
Hence, we have shown that
\begin{align}|R_1|&\leq \left(\frac{1}{2}\textrm{e}^{-\frac{1}{2}}+\frac{\textrm{e}^{-1}}{2\sqrt{2\pi}\,}+\textrm{e}^{\textrm{e}-2}\right) \textrm{e}^{-\frac{z}{2}} \sum_{i=1}^n \textrm{E}[{\xi_i}^2 \textbf{1}_{\xi_i>1}]\nonumber\\&\leq \left( \frac{1}{2}\textrm{e}^{-\frac{1}{2}}+\frac{\textrm{e}^{-1}}{2\sqrt{2\pi}\,}+\textrm{e}^{\textrm{e}-2}\right) \textrm{e}^{-\frac{z}{2}} (\beta_2+\beta_3). \end{align}
Bound for 
$R_2$
:
For 
$R_2= \sum_{i=1}^n \int_{-\infty}^1 \textrm{E}[\,f^{\prime}_z(\overline{W}^{(i)}+\overline{x_i}) - f^{\prime}_z(\overline{W}^{(i)}+t)] \overline{K_i}(t) \, \textrm{d} t$
, we use the Stein equation (2.2) to write 
$R_2$
as the sum of two quantities and then bound them separately:
\begin{align*}R_2 &= \sum_{i=1}^n \int_{-\infty}^1 \textrm{E}[(\overline{W}^{(i)}+\overline{x_i}) f_z(\overline{W}^{(i)}+\overline{x_i}) + \textbf{1}_{\overline{W}^{(i)}+\overline{x_i} \leq z} - \Phi(z) \nonumber\\& \qquad \qquad \quad - (\overline{W}^{(i)}+t)f_z(\overline{W}^{(i)}+t) - \textbf{1}_{\overline{W}^{(i)}+t \leq z}+\Phi(z) ] \overline{K_i}(t) \, \textrm{d} t \nonumber\\&= \sum_{i=1}^n \int_{-\infty}^1 \textrm{E}[\textbf{1}_{\overline{W}^{(i)}+\overline{x_i} \leq z}- \textbf{1}_{\overline{W}^{(i)}+t \leq z}]\overline{K_i}(t) \, \textrm{d} t \nonumber\\& \quad + \sum_{i=1}^n \int_{-\infty}^1 \textrm{E}[(\overline{W}^{(i)}+\overline{x_i}) f_z(\overline{W}^{(i)}+\overline{x_i})-(\overline{W}^{(i)}+t)f_z(\overline{W}^{(i)}+t)]\overline{K_i}(t) \, \textrm{d} t\nonumber\\&= R_{21}+R_{22}. \end{align*}
Since the difference between two indicator functions is always less than or equal to 1, 
$R_{21}$
can be bounded by
\begin{align*}R_{21}&\leq \sum_{i=1}^n \int_{-\infty}^1 \textrm{E}[\textbf{1}_{\overline{x_i} \leq t} \textrm{P}(z-t<\overline{W}^{(i)} \leq z-\overline{x_i}|\overline{x_i})] \overline{K_i}(t) \, \textrm{d} t.\end{align*}
Applying [Reference Chen, Goldstein and Shao4, Proposition 8.1] with 
$a=z-t$
and 
$b=z-\overline{x_i}$
gives
\begin{align}R_{21} &\leq \sum_{i=1}^n \int_{-\infty}^1 \textrm{E}[6(\!\min(1, t- \overline{x_i})+\beta_2+\beta_3)\textrm{e}^{-\frac{z-t}{2}}] \overline{K_i}(t) \, \textrm{d} t\nonumber\\&\leq6\textrm{e}^{-\frac{z}{2}}\textrm{e}^{\frac{1}{2}} \sum_{i=1}^n \int_{-\infty}^1 \textrm{E}[\!\min(1, |t|+|\overline{x_i}|)+\beta_2+\beta_3] \overline{K_i}(t) \, \textrm{d} t \nonumber \\&\le 6\textrm{e}^{-\frac{z}{2}}\textrm{e}^{\frac{1}{2}} (\beta_2 + \beta_3) +6\textrm{e}^{-\frac{z}{2}}\textrm{e}^{\frac{1}{2}} \sum_{i=1}^n \int_{-\infty}^1 \textrm{E}[\!\min(1, |t|+|\overline{x_i}|)] \overline{K_i}(t) \, \textrm{d} t ,\end{align}
where we used (4.15) for the last step. Note that 
$\textbf{1}_{0 \leq t\leq \overline{x_i}}+\textbf{1}_{\overline{x_i} \leq t<0} \leq \textbf{1}_{|t|\leq |\overline{x_i}|}$
, so 
$\overline{K_i}(t) \leq \textrm{E}[|\overline{x_i}| \textbf{1}_{|t|\leq |\overline{x_i}|}]$
. Moreover, as both 
$\min(1, |t|+|\overline{x_i}|)$
and 
$|\overline{x_i}| \textbf{1}_{|t|\leq |\overline{x_i}|}$
are increasing functions of 
$|\overline{x_i}|$
, they are positively correlated. So
\begin{align*}\textrm{E}[\!\min(1, |t|+|\overline{x_i}|)] \overline{K_i}(t) &\leq \textrm{E}[\!\min(1, |t|+|\overline{x_i}|)] \textrm{E}[|\overline{x_i}| \textbf{1}_{|t|\leq |\overline{x_i}|}]\\&\leq \textrm{E}[\!\min(1, |t|+|\overline{x_i}|) |\overline{x_i}| \textbf{1}_{|t|\leq |\overline{x_i}|}] \\&\leq 2\textrm{E}[\!\min(1, |\overline{x_i}|) |\overline{x_i}| \textbf{1}_{|t|\leq |\overline{x_i}|}].\end{align*}
This gives
\begin{align}\sum_{i=1}^n \int_{-\infty}^1 \textrm{E}[\!\min(1, |t|+|\overline{x_i}|)] \overline{K_i}(t) \, \textrm{d} t &\leq \sum_{i=1}^n \int_{-\infty}^1 2\textrm{E}[\!\min(1, |\overline{x_i}|) |\overline{x_i}| \textbf{1}_{|t|\leq |\overline{x_i}|}] \, \textrm{d} t \nonumber \\&\leq 4\sum_{i=1}^n \textrm{E}[\!\min(1, |\overline{\xi_i}|) |\overline{\xi_i}|^2]= 4(\beta_2+\beta_3). \end{align}
Substituting (4.23) into (4.22),
\begin{align*}R_{21}\leq 6\textrm{e}^{-\frac{z}{2}}\textrm{e}^{\frac{1}{2}} (4+1) (\beta_2+\beta_3) = 30\textrm{e}^{\frac{1}{2}}(\beta_2+\beta_3)\textrm{e}^{-\frac{z}{2}}. \end{align*}
Similarly, we can construct a lower bound for 
$R_{21}$
by symmetry:
\begin{align*}R_{21}&\geq \sum_{i=1}^n \int_{-\infty}^1 \textrm{E}[-\textbf{1}_{t \leq \overline{x_i}} \textrm{P}(z-\overline{x_i}<\overline{W}^{(i)} \leq z-t |\overline{x_i})] \overline{K_i}(t) \, \textrm{d} t \nonumber\\&\geq - \sum_{i=1}^n \int_{-\infty}^1 \textrm{E}[6(\!\min(1, \overline{x_i}-t)+\beta_2+\beta_3) \textrm{e}^{-\frac{z-\overline{x_i}}{2}}] \overline{K_i}(t) \, \textrm{d} t\nonumber\\&\geq - 6\textrm{e}^{-\frac{z}{2}}\textrm{e}^{\frac{1}{2}} \sum_{i=1}^n \int_{-\infty}^1 \textrm{E}[\!\min(1, |t|+|\overline{x_i}|)+\beta_2+\beta_3] \overline{K_i}(t) \, \textrm{d} t. \end{align*}
Proceeding now as for (4.23) gives that 
$R_{21}\geq -30\textrm{e}^{\frac{1}{2}}(\beta_2+\beta_3)\textrm{e}^{-\frac{z}{2}}$
, and therefore
\begin{equation} |R_{21}|\leq 30\textrm{e}^{\frac{1}{2}}(\beta_2+\beta_3)\textrm{e}^{-\frac{z}{2}}. \end{equation}
For 
$R_{22}$
, since 
$wf_z(w)$
is increasing in w, Lemma 4.1 gives
\begin{align*}R_{22}&\leq \sum_{i=1}^n \int_{-\infty}^1 \textrm{E}[\textbf{1}_{t\leq \overline{x_i}}(\overline{W}^{(i)}+\overline{x_i}) f_z(\overline{W}^{(i)}+\overline{x_i})|\overline{x_i} -(\overline{W}^{(i)}+t)f_z(\overline{W}^{(i)}+t)]\overline{K_i}(t) \, \textrm{d} t \nonumber \\&\leq \left(25.8+\frac{20\textrm{e}^{\textrm{e}^2-2}}{\sqrt{2\pi}}\right) \textrm{e}^{-\frac{z}{2}} \sum_{i=1}^n \int_{-\infty}^1 \textrm{E}[\!\min(1, |\overline{x_i}|+|t|)]\overline{K_i}(t) \, \textrm{d} t \nonumber\\&\leq \left(103.2+\frac{80}{\sqrt{2\pi}\,}\textrm{e}^{\textrm{e}^2-2}\right) \textrm{e}^{-\frac{z}{2}}(\beta_2+\beta_3). \end{align*}
Here we used (4.23) for the last step. A lower bound for 
$R_{22}$
can be obtained by symmetry:
\begin{align*}R_{22}&\geq \sum_{i=1}^n \int_{-\infty}^1 \textrm{E}[\textbf{1}_{\overline{x_i}\leq t} (\overline{W}^{(i)}+\overline{x_i}) f_z(\overline{W}^{(i)}+\overline{x_i})|\overline{x_i} -(\overline{W}^{(i)}+t)f_z(\overline{W}^{(i)}+t)]\overline{K_i}(t) \, \textrm{d} t \nonumber\\&\geq -\sum_{i=1}^n \int_{-\infty}^1 \textrm{E}[\textbf{1}_{\overline{x_i}\leq t} (\overline{W}^{(i)}+t)f_z(\overline{W}^{(i)}+t)-(\overline{W}^{(i)}+\overline{x_i}) f_z(\overline{W}^{(i)}+\overline{x_i})|\overline{x_i}]\overline{K_i}(t) \, \textrm{d} t \nonumber\\&\geq -\left(103.2+\frac{80}{\sqrt{2\pi}\,}\textrm{e}^{\textrm{e}^2-2}\right) \textrm{e}^{-\frac{z}{2}}(\beta_2+\beta_3). \end{align*}
Therefore, we have shown that
\begin{equation}|R_{22}|\leq \left(103.2+\frac{80}{\sqrt{2\pi}}\textrm{e}^{\textrm{e}^2-2}\right)\textrm{e}^{-\frac{z}{2}} (\beta_2+\beta_3). \end{equation}
Collecting (4.24) and (4.25) gives
\begin{equation}|R_2|\leq |R_{21}|+|R_{22}|\leq \left(30\textrm{e}^\frac{1}{2}+103.2+\frac{80}{\sqrt{2\pi}\,}\textrm{e}^{\textrm{e}^2-2}\right)\textrm{e}^{-\frac{z}{2}}(\beta_2+\beta_3). \end{equation}
Bound for 
$R_3$
:
Finally, for 
$R_3=\sum_{i=1}^n \textrm{E}[\xi_i \textbf{1}_{\xi_i> 1}] \textrm{E}[ f_z(\overline{W}^{(i)})]$
, we use similar arguments as for 
$R_1$
:
\begin{align*} \textrm{E}|\,f_z(\overline{W}^{(i)})|&= \textrm{E}\left[|\,f_z(\overline{W}^{(i)})|\textbf{1}_{\overline{W}^{(i)}\leq \frac{z}{2}}\right] + \textrm{E}\left[|\,f_z(\overline{W}^{(i)})|\textbf{1}_{\overline{W}^{(i)}>\frac{z}{2}}\right]\\&\leq \sqrt{2\pi} \; \textrm{e}^{\frac{z^2}{8}} (1-\Phi(z)) + \textrm{E}\left[|\,f_z(\overline{W}^{(i)})| \textbf{1}_{\overline{W}^{(i)} > \frac{z}{2}}\right].\end{align*}
From (2.6), 
$0<f_z\leq \min\big(\frac{\sqrt{2\pi}}{4},\frac{1}{|z|}\big) =\frac{1}{|z|}\leq \frac{1}{2}$
for 
$z>2$
. The standard normal tail bound (2.1) and [Reference Chen, Goldstein and Shao4, Lemma 8.2] with 
$\alpha=B=t=1$
give
\begin{align*} \textrm{E}|\,f_z(\overline{W}^{(i)})|&\leq \sqrt{2\pi}\textrm{e}^{\frac{z^2}{8}}\frac{1}{z\sqrt{2\pi}\,} \textrm{e}^{-\frac{z^2}{2}} + \frac{1}{2} \textrm{P}\left(\overline{W}^{(i)} >\frac{z}{2}\right) \\&\leq \frac{1}{z}\textrm{e}^{-\frac{3}{8}z^2} + \frac{1}{2} \textrm{e}^{-\frac{z}{2}}\textrm{e}^{\textrm{e}-2}\\&\leq \frac{1}{2} \textrm{e}^{-\frac{1}{2}} \textrm{e}^{-\frac{z}{2}}+ \frac{1}{2} \textrm{e}^{-\frac{z}{2}}\textrm{e}^{\textrm{e}-2} .\end{align*}
Hence, we have shown that
\begin{align}|R_3|&\leq \frac{1}{2}(\textrm{e}^{-\frac{1}{2}}+\textrm{e}^{\textrm{e}-2})\textrm{e}^{-\frac{z}{2}} \sum_{i=1}^n\textrm{E}[\xi_i \textbf{1}_{\xi_i> 1}] \nonumber\\&\leq \frac{1}{2}(\textrm{e}^{-\frac{1}{2}}+\textrm{e}^{\textrm{e}-2}) \textrm{e}^{-\frac{z}{2}}(\beta_2+\beta_3).\end{align}
Applying (4.21), (4.26), and (4.27) to (4.18), (4.19), and (4.20) respectively, we have
\begin{align*}|P(\overline{W}\leq z)-\Phi(z)|&\leq \left(31\textrm{e}^{-\frac{1}{2}}+\frac{3}{2}\textrm{e}^{\textrm{e}-2}+103.2+\frac{0.5\textrm{e}^{-1} +80\textrm{e}^{\textrm{e}^2-2}} {\sqrt{2\pi}}\right)\textrm{e}^{-\frac{z}{2}}(\beta_2+\beta_3) \nonumber\\&\leq 7115\textrm{e}^{-\frac{z}{2}}(\beta_2+\beta_3) \end{align*}
This completes the proof of (4.13) and therefore the proof of (4.14). Thus we have proved the theorem when 
$\beta_2+\beta_3<1$
and 
$z>2$
, and hence we have completed the proof of Theorem 3.2.□
Acknowledgements
The authors would like to thank Aihua Xia (Melbourne) for helpful discussions, and the anonymous referee as well as the editor for thoughtful queries and comments. Part of this work was completed while Ce Yang was a student at the University of Oxford.
Appendix A. Results from [Reference Chen, Goldstein and Shao4]
For convenience, we provide here some results from [Reference Chen, Goldstein and Shao4] which we use in this paper.
Let 
$\xi_1, \ldots ,\xi_n$
denote independent random variables with zero means and variances summing to 1. Let W denote their sum, 
$W=\sum_{i=1}^n \xi_i$
. We consider the truncated random variables and their sums as given in (4.1).
In [Reference Chen, Goldstein and Shao4, Proposition 8.1] it is shown that, for all real 
$a<b$
and 
$i=1, \dots ,n$
,
\begin{equation*} \textrm{P}(a \leq \overline{W}^{(i)} \leq b) \leq 6(\!\min(1,b-a)+ \beta_2 +\beta_3)\textrm{e}^{-\frac{a}{2}} .\end{equation*}
Moreover, Lemmas 8.1 and 8.2 in [Reference Chen, Goldstein and Shao4] give the next result.
Lemma A.1. [Lemmas 8.1 and 8.2] Let 
$\eta_1, \ldots ,\eta_n$
be independent random variables satisfying 
$\textrm{E}\eta_i \leq0$
for 
$1\leq i \leq n$
and 
$\sum_{i=1}^n \textrm{E}\eta_i^2 \leq B^2$
. Then, for 
$x>0$
and 
$p\geq 1$
, with 
$S_n=\sum_{i=1}^n \eta_i$
,
\begin{equation*}\textrm{P}(S_n \geq x) \leq \textrm{P}\left(\max_{1\leq i\leq n}\eta_i > \frac{x\vee B}{p}\right) + \textrm{e}^p\left(1+\frac{x^2}{pB^2}\right) ^{-p} .\end{equation*}
If, moreover, for some 
$\alpha>0$
, 
$\eta_i \leq \alpha$
for all 
$1\leq i\leq n$
, then, for 
$t>0$
,
\begin{equation*} \textrm{E} \textrm{e}^{tS_n} \leq \exp(\alpha^{-2}(\textrm{e}^{t\alpha}-1-t\alpha) B^2).\end{equation*}
Lemma 8.3 in [Reference Chen, Goldstein and Shao4] with 
$t=1$
gives the next result.
Lemma A.2. [Lemma 8.3] Let 
$\xi_1, \ldots ,\xi_n$
be independent random variables with zero means and variances summing to 1. Let 
$W=\sum_{i=1}^n \xi_i$
and 
$\beta_2$
be given as above. Then, for 
$z \geq 2$
and 
$p \geq 2$
,
\begin{equation*}\textrm{P} \big(W \geq z, \max_{1\leq i\leq n}\xi_i >1\big) \leq 2\sum_{i=1}^n \textrm{P} \left(|\xi_i|>\frac{z}{2p}\right) + \textrm{e}^p\left(1+\frac{z^2}{4p}\right)^{-p}\beta_2.\end{equation*}
