4
$\begingroup$

If $X_i$ is a sequence of $d$ dimensional i.i.d. integer valued random vectors with covariance matrix $\Sigma$ and $\mathbb{E}(X_i) = \mu$. Let each element of $X_i$ be chosen i.u.d. from $\{-1,1\}$. We know from the multidimensional central limit theorem that

$$ \frac{1}{\sqrt{n}}\sum_{i=1}^n (X_i - \mu)\ \stackrel{D}{\rightarrow}\ \mathcal{N}_d(0,\Sigma).$$

There are in fact a whole series of multivariate central limit theorems that weaken the requirements for dependence and/or that the summands must be identical. See for example Theorems D.18A onwards.

These convergence results appear all to require that the dimension size $d$ is fixed.

What happens if the dimension size $d$ grows as a function of the number of terms in the sum? For example, say $d = \lfloor \sqrt{n} \rfloor$ or $d = \lfloor > \frac{n}{\ln n}\rfloor$. Are there results which say under what conditions $\frac{1}{\sqrt{n}}\sum_{i=1}^n (X_i - \mu)$ converges to a multivariate Gaussian?

To be clear, for a fixed $n$ all the vectors in the sum will have the same dimension $d$. However, that dimension will be a function of $n$ and my assumption is that for $d=n$, say, then it may be hard to argue that $ \frac{1}{\sqrt{n}}\sum_{i=1}^n (X_i - \mu)$ is well approximated by $\mathcal{N}_n(0,\Sigma)$.

$\endgroup$
9
  • 1
    $\begingroup$ What does sum of vectors of different dimensions mean? $\endgroup$
    – Pig
    Jan 13, 2016 at 19:21
  • $\begingroup$ @user31814 All the vectors in the sum have the same dimension $d$. My question is about whether, as $d$ increases with the number of summands $n$, we still get convergence in distribution to a multivariate Gaussian. The standard multivariate CLT talks about a fixed dimension $d$ which does not increase with the number of terms that are being summed. $\endgroup$
    – Simd
    Jan 13, 2016 at 19:29
  • 1
    $\begingroup$ If the dimension of $X_i$ is $d_i$,$d_i\nearrow \infty$, how do you add vectors of different dimensions? $\endgroup$ Jan 13, 2016 at 20:46
  • $\begingroup$ @LiviuNicolaescu I apologize for any confusion. For a given value $n$ the dimension of all the variables $X_i$ is fixed to be $d$. That is each vector in the sum for a given $n$ has the same dimension. It might be easier to fix $n$ and ask for the closeness of $X_1+\dots+X_n$ to the $d$-dimensional Gaussian distribution as Ryan O'Donnell suggests. Having said that, my real interest is in a local limit types results rather than merely convergence in distribution. Overall my concern is how close $d$ can be to $n$ for us still to some sort of convergence for large $n$. $\endgroup$
    – Simd
    Jan 13, 2016 at 22:07
  • 2
    $\begingroup$ @dorothy Thus you are talking about a triangular array $X_{in}$, $1\leq i\leq n$ where for each $n$, $X_{1n}, \dotsc, X_{nn}$ are iid of dimension $d_n$. The covariance $\Sigma_n$ is a $d_n\times d_n$ matrix. In particular it also depends on $n$. You need to formulate the question more precisely. $\endgroup$ Jan 14, 2016 at 0:53

2 Answers 2

8
$\begingroup$

I interpret this as being about (Berry--Esseen-style) closeness of $X_1 + \cdots + X_n$ to the $d$-dimensional Gaussian distribution, when $n$ is fixed and when the dependence on the dimension $d$ is carefully taken into account.

It depends on what class of 'tests' you use to measure closeness, but the best general result along these lines I know is from Bentkus, "A Lyapunov type bound in Rd":

http://epubs.siam.org/doi/abs/10.1137/S0040585X97981123

He shows closeness for all convex test sets, with the dependence on the dimension being $d^{1/4}$.

$\endgroup$
2
  • 1
    $\begingroup$ Thank you. Do you feel that if $d \approx \sqrt{n}$ say that the distribution of $X_1 + \dots + X_n$ can be arbitrarily far from $d$-dimensional Gaussian? Or to ask another related question, is $d^{1/4}$ optimal in some sense? $\endgroup$
    – Simd
    Jan 13, 2016 at 20:02
  • $\begingroup$ It's not known if the $d^{1/4}$ is optimal (the best lower bounds are only logarithmic, I think), but I think there is some feeling that it may in fact be optimal. Partly this comes from the feeling that the main contributor to the error comes from the 'Gaussian surface area' of sets. And it is known (thanks to Fedja Nazarov, scholar.google.com/…) that there are convex sets in $d$ dimensions with Gaussian surface area proportional to $d^{1/4}$. This hasn't been turned into a lower bound, though, as far as I know. $\endgroup$ Apr 19, 2016 at 20:03
1
$\begingroup$

Actually for some weaker metrics (like the multivariate Kolmogorov metric for instance) the central limit convergence takes place in much larger dimension than the one provided by Bentkus. Typically the dimension is allowed to be almost exponential in n. You may have a look to: http://arxiv.org/abs/1412.3661

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.