# Concentration of sum of pairwise squared Euclidean distances of random vectors

Let $X_1, \ldots, X_n$ be independent random vectors in $B(0, D) \subset R^d$ ($\ell_2$ ball of radius $D$ centered at the origin). I am trying to find the concentration of the following quantity around its expectations: $$f(X_1, \ldots, X_n) = \frac{1}{n^2} \sum_{1 \leq i,j \leq n} \|X_i - X_j \|_2^2$$ Using McDiarmid's inequality, I can show that $$\Pr(|f(X_1,\ldots,X_n) - \mathbb{E} f(X_1,\ldots,X_n)| \geq \epsilon) \leq 2 \exp\left(- \frac{2n\epsilon^2}{16D^4}\right).$$ This tells me that with high probability, $\epsilon \sim O(1/\sqrt{n})$.

Usually sum of $n$ independent random variables concentrate with the similar dependence on $n$ (that is, $O(1/\sqrt{n})$) unless I use Berstein's inequality. And it is believed that in some sense, among functions of independent random variables, sums are the least concentrated.

In my situation, the function is a sum of $n^2$ non-independent random variables (if you think of $Z_{ij} = \| X_i - X_j \|_2^2$ as a random variable). So I believe that the concentration should be better than $O(1/\sqrt{n})$.

Does anybody have any idea of how such a guarantee can be achieved? Or can anybody show that the $O(1/\sqrt{n})$ is the best I can hope for?

-
I think you should expect to get something like $O(1/n)$. I think the random variables behave essentially as if they were independent, so that you're summing $n^2$ random variables of variance $\Theta(1)$ (assuming $d$ and $D$ are fixed), and dividing by $n^2$. The variance should be $\Theta(1/n^2)$, so the standard deviation should be something like $1/n$. –  Anthony Quas Mar 13 at 18:44
Notice that this is a (multivariate) $U$-statistic. I would start by searching with those terms. Have you already looked at the case $d = 1$? –  cardinal Mar 14 at 0:56
Are your $X_i$ uniformly distributed in the ball? If so, you may be able to do better using logarithmic Sobolev inequalities (but I haven't thought through the normalizations to be sure). –  Mark Meckes Mar 14 at 14:56
@cardinal Thanks for the pointer to U-statistic. The function is basically a V-statistic (in this case, it is same as the U-statistic barring a normalization factor). The results for the concentration of U-statistics (and V-statistics) generally show that $\epsilon \sim O(1/\sqrt{n})$ but can be improved to $O(1/n)$ at best with Berstein style results. It appears that I might not be able to do better than $\epsilon \sim O(1/n)$. –  PRam Mar 18 at 17:04
Wouldn't it suffice simply to calculate the dispersion of $f$? You can calculate it easily: each term is equal to $\langle X_i-X_j, X_i-X_j \rangle$, so it's quite easy to work with them, there are no square roots or other nasties. And to calculate the dispersion you need only individual dispersions (easy), and covariances (not too difficult, too). (Perhaps, you'll find it easier to use linearity first, so you have the sum of the terms of the types $\langle X_i, X_i \rangle$ and $\langle X_i, X_j \rangle$, this will simplify the further calculations.)
Either the dispersion decreases quicker than $1/n$, and then you are done by Chebyshev inequality. Or it does not, and then no hope for quicker than $O(1/\sqrt{n})$ decrease.
My personal opinion here is that the decrease is indeed $O(1/\sqrt{n})$. For the following reason: the number you evaluate is some kind of a variance, evaluated for your sample $X_1,\dots,X_n$. I would be surprised if there existed a method more efficient than the standard $\hat{\sigma}_n^2$, that has a variance of $\sim 1/n$. In fact, my intuition tells me that your $f$ is proportional to $\hat{\sigma}_n^2$ (or to the sum of its diagonal elements in the $d$-dimensional case).