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.

  • $\begingroup$ 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$? $\endgroup$ – 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$.

| cite | improve this answer | |
  • 1
    $\begingroup$ +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.? $\endgroup$ – antkam Apr 30 '19 at 21:02
  • $\begingroup$ 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. $\endgroup$ – madprob May 1 '19 at 0:02
  • $\begingroup$ However, note that OP states that $\phi$ is smooth and has a compact support. Therefore, $\phi$ is bounded. $\endgroup$ – madprob May 1 '19 at 0:04
  • $\begingroup$ 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. $\endgroup$ – antkam May 1 '19 at 1:31
  • 1
    $\begingroup$ 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. $\endgroup$ – Michael May 4 '19 at 23:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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