# Let $X,Y,X_1,X_2,\ldots$ be i.i.d. and $\phi(x,y)$ a test function. Does $\frac{1}{N^2}\sum_{i,j}\phi(X_i,X_j)\to\mathbb E\phi(X,Y)$ a.s.?

Suppose we are given a distribution $$\mu$$ on $$\mathbb R^d$$, and a smooth function $$\phi:\mathbb R^d\times\mathbb R^d\to\mathbb R$$ with compact support. Let $$X_i$$ be i.i.d. random variables with distribution $$\mu$$. Then is it the case that $$\frac{1}{N^2}\sum_{i,j=1}^N\phi(X_i,X_j)\to\int_{\mathbb R^d\times\mathbb R^d}\!\phi(x,y)\,\mathrm d\mu(x)\,\mathrm d\mu(y)?$$ For single-variable $$\phi$$, this is just the strong law of large numbers, but I don't quite see how to prove it here.

• Can't you use integration by parts and the Glivenko-Cantelli theorem? Write the sum as the double integral of the emipirical cdf against some mixed partial derivative of $\phi$? – kimchi lover Apr 29 '19 at 22:28

Let $$f(X_1,\ldots,X_n) = \frac{\sum_{i,j}\phi(X_i,X_j)}{N^2}$$. Since $$\phi$$ is smooth and defined on a compact support, it is bounded by some $$k \in \mathbb{R}^{+}$$. Therefore, for every $$i$$, $$|f(X_1,\ldots,X_i,\ldots,X_n)-f(X_1,\ldots,X_i^*,\ldots,X_n)| \leq \frac{2k}{n}$$. It follows from McDiarmid's inequality that

$$P(|f(X_1,\ldots,X_n)-E[f(X_1,\ldots,X_n)]| \geq \epsilon) \leq 2\exp(-0.5\epsilon^2k^{-1}n)$$

Also observe that $$\theta_n := E[f(X_1,\ldots,X_n)] = \frac{nE[\phi(X_1,X_1)] + n(n-1)E[\phi(X_1,X_2)]}{n^2}$$ and $$\theta := E[\phi(X_1,X_2)] = \lim_n \theta_n$$.

\begin{align*} \sum_{n}P(|f(X_1,\ldots,X_n)-\theta| \geq \epsilon) &\leq \sum_{n}P(|f(X_1,\ldots,X_n)-\theta_n| \geq \epsilon - |\theta_n-\theta|) \\ &\leq \sum_n 2\exp(-0.5(\epsilon - |\theta_n-\theta|)^2k^{-1}n) < \infty \end{align*}

It follows from Borel-Cantelli that $$f(X_1,\ldots,X_n)$$ converges a.s. to $$\theta$$.

• +1. This proof relies on the existence of the bound $k$. Can you comment on, or perhaps even better give a counter-example, where $\phi$ is unbounded in such a way that $f()$ does not converge to $\theta$? E.g., I would imagine $E[f()]$ still converges to $\theta$ (even if $\phi$ is not bounded) so any counterexample may only violate convergence a.s.? – antkam Apr 30 '19 at 21:02
• For example, if $X_{1},\ldots,X_{n}$ are i.i.d. $N(0,1)$ and $\phi(x,y) = xy^{-1}$, then $\phi(X_i,X_j) \sim Cauchy$ for every $i \neq j$. Therefore, $f(X_1,\ldots,X_n)$ does not converge. – madprob May 1 '19 at 0:02
• However, note that OP states that $\phi$ is smooth and has a compact support. Therefore, $\phi$ is bounded. – madprob May 1 '19 at 0:04
• I understand that the OP stmt implies $\phi$ is bounded, and your proof is correct. I was just wondering what examples of unbounded $\phi$ would make the convergence false. Thanks for bringing up Cauchy -- it is an interesting example. In that case, does RHS $= 0$ (by symmetry?), or is RHS also undefined? If RHS is undefined, this example generalizes to any $\phi$ with an undefined mean. I was more wondering if there is a case where e.g. RHS is defined and finite, but LHS either does not converge, or converges to a different value. – antkam May 1 '19 at 1:31
• The same result should hold whenever there is a finite constant $B$ such that $E[\phi(X_i,X_j)^2] \leq B$ for all $i,j$ (including $i=j$). It may also hold if we only require $E[|\phi(X_i,X_j)|]\leq B$ for all $i,j$ but that would require a lot more work. – Michael May 4 '19 at 23:01