Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
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 '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 '13 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 '13 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 '13 at 17:04
Suppose your points were instead on the surface the ball, say by projecting them outwards. This is much the same question for large d. However now the distances are pairwise uncorrelated, so var(f) is O(1/n^2). Have you computed correlations between distances and hence the variance in your case? –  guest Apr 1 at 8:52

3 Answers 3

You're right, you can get a better concentration inequality with $\epsilon \sim O(1/n)$ considering that's a sum of $n^2$ dependent random variables. You first need to use decoupling for $U$-statistics that relates the dependent setting to the independent one as it is shown in [1]. In your case, you can show that there exist a constant $C$ such that

$ P\left(\left| \frac{1}{n^2} \sum_{1 \leq i \ne j \leq n} \|X_i - X_j \|_2^2 - \mathbb{E}f\right| \ge t\right) \le \\ \qquad \qquad C P\left(C\left|\frac{1}{n^2} \sum_{1 \leq i \ne j \leq n} \|X_i^{(1)} - X_j^{(2)} \|_2^2 - \mathbb{E}f\right| \ge t\right) , $

where $X_i^{(1)}, X_i^{(2)}$ are independent copies of $X_i$. Then you can apply the McDiarmid inequality on the sum of $n(n-1)$ independent terms and get an inequality achieving the rate $O(1/n)$. Moreover, as your U-statistic is symmetric you can reverse this inequality to get a lower bound and convince you that you can't do better.

[1] de la Peña, V. H., & Montgomery-Smith, S. J. (1995). Decoupling inequalities for the tail probabilities of multivariate U-statistics. The Annals of Probability, 806-816. Avialable : http://arxiv.org/pdf/math/9309211v2.pdf

share|improve this answer

I wanted to comment but don't have enough reputation yet. With regards to showing the optimality of the $O(1/\sqrt{n})$ rate, can you try the following strategy? Fix $d = 1$ and $D = 1$. Let $X_1, \ldots, X_n$ be iid Rademacher random variables (i.e taking values $1$ and $-1$ each with probability $1/2$). Then the random variable $f(X_1, \ldots, X_n)$ simplifies to $2 n^2 - 2 \sum_{1 \leq i, j \leq n} X_i X_j$, and we equivalently care about the concentration properties of $\sum_{1 \leq i, j \leq n} X_i X_j$. This is just the simplest possible Rademacher chaos of order two.

Now, you might try looking for lower bounds on the probability that the 2nd order Rademacher chaos is outside some radius $t$ of its expectation. Upper bounds are known, for instance in http://projecteuclid.org/download/pdf_1/euclid.aop/1055425791 and the references in that paper to earlier results by Talagrand and by Ledoux. Perhaps they've also shown optimality of the rates, which would be sufficient for your purposes. I don't think the linked paper shows rate optimality, but try the Talagrand or Ledoux papers.

share|improve this answer

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

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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