Skip to main content
edited body
Source Link
anon
  • 43
  • 4

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(n) \approx -2.53629 - 1.03812 \ln(\Delta_{\mathrm{TV}})$$\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.

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(n) \approx -2.53629 - 1.03812 \ln(\Delta_{\mathrm{TV}})$ 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.

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.

Added empirical justification for possible O(1/n) bound.
Source Link
anon
  • 43
  • 4

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(n) \approx -2.53629 - 1.03812 \ln(\Delta_{\mathrm{TV}})$ 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.

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!

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(n) \approx -2.53629 - 1.03812 \ln(\Delta_{\mathrm{TV}})$ 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.

Post Undeleted by anon
Post Deleted by anon
Source Link
anon
  • 43
  • 4

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!