# CLT convergence rate for sum of uniforms (in TV distance)

Suppose $$X_1, \cdots, X_n \sim_{\mathrm{iid}} U([-1,1])$$, where $$U([-1, 1])$$ denotes the continuous uniform distribution over the interval $$[-1, 1]$$ (so $$E[X_i] = 0$$ and $$\text{Var}[X_i]= 1/3$$). Let $$D_n$$ denote the distribution of the following sum, scaled to have unit variance: $$\sqrt{\frac{3}{n}} \sum_{i = 1}^n X_i \sim D_n.$$ Note that $$D_n$$ is a scaled and shifted version of the Irwin-Hall distribution. Is it known how quickly $$D_n$$ converges to $$\mathcal{N}(0, 1)$$ (i.e. the standard normal distribution) in total variation (TV) distance? Some quick experimentation for small values of $$n$$ in Mathematica possibly indicates $$\Delta_{\mathrm{TV}}\left(D_n, \mathcal{N}(0, 1) \right)\stackrel{?}{\le} O\left(\frac{1}{n}\right),$$ but I couldn't find a simple way to try to prove it. The closest thing I could find is the Berry–Esseen theorem, but that only gives a bound on the the Kolmogorov–Smirnov distance (i.e. max difference in CDFs), which does not generally imply a TV distance bound.

I would appreciate any help. Thanks so much!

EDIT: [Only keep reading if you want to see the empirical results for small $$n$$.]

Below are the empirical values for $$\Delta_{\mathrm{TV}}\left(D_n, \mathcal{N}(0, 1) \right)$$ (computed in Mathematica by N[1/2*Integrate[Abs[PDF[NormalDistribution[0, 1], x] - Sqrt[n/3]*PDF[UniformSumDistribution[n, {-1, 1}], x*Sqrt[n/3]]], {x, -Infinity, Infinity}]] for varying values of $$n$$):

$$n$$ $$\Delta_{\mathrm{TV}}$$
$$1$$ $$0.1976779590175315$$
$$2$$ $$0.05124700117544534$$
$$3$$ $$0.027101879212265846$$
$$4$$ $$0.019292677385873307$$
$$5$$ $$0.014897694156660687$$
$$6$$ $$0.012364908454190667$$
$$7$$ $$0.010492076525242137$$
$$8$$ $$0.009125408176875193$$
$$9$$ $$0.008072492963113527$$
$$10$$ $$0.007237608640375671$$
$$11$$ $$0.00655926922222608$$
$$12$$ $$0.005997229294516531$$
$$13$$ $$0.0055239287588410195$$
$$14$$ $$0.005119885056770444$$
$$15$$ $$0.00477093097015108$$

Computing a linear regression on top of the log-log version of the table for $$5 \leq n \leq 15$$ gives $$\ln(\Delta_{\mathrm{TV}}) \approx -2.53629 - 1.03812 \ln(n)$$ with $$R^2 \ge 0.9999$$. For this reason (i.e. because $$- 1.03812 < -1$$ and $$R^2$$ is very close to $$1$$), it seemed like $$\Delta_{\mathrm{TV}} \le O\left( \frac{1}{n} \right)$$ is empirically possible.

• If the pdf of $D_n$ is greater than the standard normal pdf in $k$ connected regions, then the total variation distance is at most $2k$ times the K-S distance. So graphing those $k$ regions (and computing $k$) for a few different $n$ might help solve the problem quickly. For example: Is $k\le 3$ for all $n$?
– user44143
Commented Sep 3, 2022 at 2:03
• (i) Berry-Esseen type bounds in relative entropy, and hence TV (by Pinsker's inequality), are thoroughly discussed in the following PTRF paper link.springer.com/content/pdf/10.1007/s00440-013-0510-3.pdf. (ii) Are you sure about the empirically observed $O(1/n)$ rate? Can you please share some of these empirical results in your post? In particular, this seems to defy the usual Monte Carlo error $O(1/\sqrt{n})$. Commented Sep 3, 2022 at 10:17
• Thanks for the comments and the reference! Indeed, it looks like the PTRF paper gives a $O(1/\sqrt{n})$ bound by Theorem 1.1. Thanks for sharing! I just added experimental justification for the possible $O(1/n)$ bound. Is there any hope for (validity or proof) of that?
– anon
Commented Sep 4, 2022 at 22:26
• Thanks for the Mathematica code snippet! Here is a slight modification to help "see" the rate: ListLogLogPlot[{Table[ NIntegrate[ Abs[PDF[NormalDistribution[0, 1], x] - Sqrt[n/3]* PDF[UniformSumDistribution[n, {-1, 1}], Sqrt[n/3] x]], {x, -Infinity, Infinity}], {n, 1, 15}], Table[0.1/n, {n, 1, 15}]}, PlotStyle -> {Red, Blue}] Commented Sep 5, 2022 at 18:06
• Here is one answer with precise estimates and references that I gave several years ago. Commented Sep 25, 2022 at 18:01

$$\newcommand\dee{\Delta_{\mathrm{TV}}}\newcommand{\vpi}{\varphi}$$Let $$f_n$$ denote the pdf of $$\begin{equation*} S_n:=\sqrt{\frac3n} \sum_{i=1}^n X_i \end{equation*}$$ and let $$\vpi$$ denote the standard normal pdf. Then $$\begin{equation*} \dee(D_n,N(0,1))=\int|f_n-\vpi|\le I_{n1}+I_{n2}+I_{n3}, \tag{1}\label{1} \end{equation*}$$ where $$\begin{equation*} I_{n1}:=\int_{|x|\le\sqrt{3n}}|f_n(x)-\vpi(x)|\,dx, \end{equation*}$$ $$\begin{equation*} I_{n2}:=\int_{|x|>\sqrt{3n}}f_n(x)\,dx, \end{equation*}$$ $$\begin{equation*} I_{n3}:=\int_{|x|>\sqrt{3n}}\vpi(x)\,dx. \end{equation*}$$

We bound $$I_{n1}$$ using the asymptotic expansion in the central limit theorem given (say) by Theorem 7 (with $$k=5$$ and $$l=1$$) on p. 175 in the book by Petrov. Noting also Lemma 10 on p. 173 and the expressions for $$Q_{kn}(x)$$ on p. 138 of the same book, as well as the fact that $$EX_i=EX_i^3=0$$ for all $$i$$, we see that $$\begin{equation*} f_n(x)=\vpi(x)\Big(1+\frac{P_2(x)}n\Big)+O\Big(\frac1{n^{3/2}}\Big) \end{equation*}$$ uniformly in all real $$x$$, where $$P_2$$ is a certain polynomial. It follows that $$I_{n1}=O(1/n)$$. Also, $$I_{n2}=0$$, since $$|S_n|\le\sqrt{\frac3n}\,n=\sqrt{3n}$$. Finally, it is easy to see that $$I_{n3}=o(1/n)$$.

Thus, by \eqref{1},
$$\begin{equation*} \dee(D_n,N(0,1))=O(1/n), \tag{2}\label{2} \end{equation*}$$ as desired.

In fact, $$P_2(x)=\frac1{20}(3-6x^2+x^4)$$, and hence, slightly modifying the above reasoning, we see that $$\begin{equation*} \dee(D_n,N(0,1))\sim\frac cn, \end{equation*}$$ where $$$$c:=\int\vpi|P_2|= \frac{e^{-3/2-\sqrt{3/2}}}{5\sqrt\pi} \Big(e^{\sqrt{6}} \sqrt{9-3\sqrt{6}}+\sqrt{9+3\sqrt{6}}\,\Big) \\ =0.140030\ldots.$$$$

Here is the graph $$\big\{\big(n,\frac nc\,\dee(D_n,N(0,1))\big)\colon n\in\{3,\dots,15\}\big\}$$:

Following the lines of the proof, it easy to see that \eqref{2} will hold whenever, say, the $$X_i$$'s are iid with $$EX_i=EX_i^3=0$$ and light enough distribution tails (in your case, the $$X_i$$'s are iid symmetric random variables with no distribution tails), provided that there is some natural $$k$$ such that $$S_k$$ has an absolutely continuous pdf with integrable derivative (in your case, $$k=2$$ will do).

• (+1) Uspensky (1937) provides a similar result, in flavor, based on a straightforward analysis of characteristic functions, as detailed in this answer. Empirically, the bound seems reasonably tight. Commented Sep 25, 2022 at 18:06
• @cardinal : Thank you for your comment. I actually own the Uspensky book, but had not noticed that result (which is for the Kolmogorov distance, though). Commented Sep 25, 2022 at 20:53