3
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ 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$? $\endgroup$
    – Matt F.
    Sep 3 at 2:03
  • 1
    $\begingroup$ (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})$. $\endgroup$ Sep 3 at 10:17
  • 1
    $\begingroup$ 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? $\endgroup$
    – anon
    Sep 4 at 22:26
  • $\begingroup$ 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}] $\endgroup$ Sep 5 at 18:06
  • 1
    $\begingroup$ Here is one answer with precise estimates and references that I gave several years ago. $\endgroup$
    – cardinal
    Sep 25 at 18:01

1 Answer 1

4
$\begingroup$

$\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 \begin{equation} 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. \end{equation}

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

enter image description here


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

$\endgroup$
2
  • 1
    $\begingroup$ (+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. $\endgroup$
    – cardinal
    Sep 25 at 18:06
  • $\begingroup$ @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). $\endgroup$ Sep 25 at 20:53

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.