# Concentration of the deviation of the V-statistic with addition of a single point

Let $X_1, \ldots, X_n, X_{n+1}$ be i.i.d. random vectors in $B(0, D/2) \subset R^d$ ($\ell_2$ ball of radius $D/2$ centered at the origin). I am trying to find any upper bound on the following quantity: \begin{equation*} f(X_1, \ldots, X_n, X_{n+1} ) = \frac{1}{(n+1)^2} \sum_{1\leq i, j \leq n+1} \| X_i - X_j \|^2 - \frac{1}{n^2} \sum_{1 \leq i,j \leq n} \|X_i - X_j \|^2 \end{equation*} This quantity effectively measures the increase/deviation in the average pairwise squared distances (V-statistics with respect to the pairwise distance function)in a set of $n$ points when a new random vector (from the same distribution) is added to the set.

Naively, the first term on the RHS can be bounded by the diameter $D$, while the second term is always greater than or equal to zero. This implies the following upper bound on $f$: $$f(X_1,\ldots, X_n, X_{n+1}) \leq \frac{2 n D^2}{(n + 1)^2}.$$ The goal is to do better than this, which is why I am exploring concentration inequalities. Let $Z = f(X_1, \ldots, X_n, X_{n+1})$ and $Z_i' = f(X_1, \ldots, X_{i - 1}, X_i', X_{i+1}, \ldots, X_{n+1})$ be the value of the function with the swap of the $i^{th}$ random vectors. Then we have $\forall i = 1, \ldots, n$, $$|Z - Z_i'|\leq \frac{6 D^2}{(n+1)^2} = c_i,$$ and $$|Z - Z_{n+1}'| \leq \frac{2 D^2 n}{(n+1)^2} = c_{n+1}.$$ Then by McDiarmid's inequality, we have $$\Pr \left( Z - \mathbb{E} Z > \epsilon \right) \leq \exp \left(- 2 \epsilon^2 / C \right),$$ where $C = \sum_{i = 1}^{n + 1} c_i^2 = \sum_{i = 1}^n c_i^2 + c_{n+1}^2 = \frac{4 D^4}{(n + 1)^4} (n^2 + 9n).$ This gives us an upper bound on the deviation as $Z - \mathbb{E} Z \leq \frac{2 D^2}{n + 1} \sqrt{ \log (1/\delta)}$ with probability $1 - \delta$ (for $n \geq 5$, $2(n + 1)^2 > n^2 + 9n$).

Assuming $X_1, \ldots, X_n$ i.i.d. from the distribution $\mathcal{D}$, we can show that $$\mathbb{E} Z = \frac{\mathbb{E}_{X,Y \sim \mathcal{D}^2} \| X - Y \|^2}{n ( n + 1 )}.$$ What we see here now is that McDiarmid's inequality tells us that $Z - \mathbb{E} Z \leq O(1 / n)$ while $\mathbb{E} Z \sim O(1 / n^2)$, which implies that $Z \leq O(1 / n)$ with high probability.

What is confusing me is the fact that I can get the same $O(1/n)$ bound naively without using any concentration/high probability argument! So I want to understand why the concentration argument is not helping me here and/or how I can use some other kind of concentration result to get something better than the naive bound.

P.S. I did try to compute the variance $Var(Z)$ and (under some assumptions) I can show that $Var(Z) \leq O(1/n^3)$. Is there some concentration inequality that allows me to use a bound on the variance? (I was not able to see how I could use the bound on the variance in the log-Sobolev inequalities)

-