5
$\begingroup$

Let $\{x_1, \ldots, x_n\}$ be a set of $n$ i.i.d. samples from a distribution $p(x)$. I would like to evaluate the distribution of the sum $$ S = \sum_{1\leq i<j\leq n} f(x_i, x_j), $$ where $f$ is a continuous function.

The sample size $n$ is sufficiently large that I cannot approximate the distribution by Monte Carlo simulation. The central limit theorem cannot be applied because the summands are not i.i.d.

Edit: The question is distinct from Limit of a convolution and sum of distribution functions. The linked question considers the behaviour of $P(S>x)$ in the limit $x\rightarrow \infty$. I am however interest in the limit $n\rightarrow\infty$ where $n$ is the number of samples.

Edit: Maybe adding some context will make the question more easily understandable. I am considering interaction rates between distinct entities labelled by an index $i$. A random attribute $x_i$ is associated with each entity and the interaction rate between two individuals $f(x_i, x_j)$ is a function of said attributes. I would like to determine the distribution of the total rate of events $S$. At the moment, I am using a very simple functional form $f(x_i,x_j)=\exp(-a |x_i-x_j|)$.

Improve this question
$\endgroup$
10
  • $\begingroup$ possible duplicate of Limit of a convolution and sum of distribution functions $\endgroup$
    – Xi'an
    Commented Jul 22, 2015 at 12:40
  • $\begingroup$ @Xi'an: I clarified how the question differs. $\endgroup$
    – Till Hoffmann
    Commented Jul 22, 2015 at 12:48
  • $\begingroup$ Any information on $p$ or $f$? (I don't assume $f$ is symmetric, is it?) $\endgroup$
    – Stephan Kolassa
    Commented Jul 22, 2015 at 13:04
  • $\begingroup$ @StephanKolassa: Unfortunately no information on $p$ except that I'm happy to assume it has finite moments. I would prefer to not make the assumption that $f$ is symmetric under exchange but am happy to make the assumption if it helps with the derivation. $\endgroup$
    – Till Hoffmann
    Commented Jul 22, 2015 at 13:07
  • $\begingroup$ My first thought was McDiarmid's inequality, but that's only really helpful here if for all $x, y$, $\min\left( \sup_{x'} \lvert f(x, y) - f(x', y) \rvert, \sup_{y'} \lvert f(x, y) - f(x, y') \rvert \right) < C n^{-3/2}$. Talagrand's inequality could also help for bounded $p(x)$ [which could possibly be worked around via truncation] and convex, Lipschitz $f$ [which I think can't be easily worked around]. $\endgroup$
    – Danica
    Commented Jul 22, 2015 at 16:46

2 Answers 2

Reset to default
1
$\begingroup$

You might start out determining some of the moments of S:

$$E(S)={n \choose 2}E(f(x_1,x_2))$$

$$E(S^2)={n \choose 2}E(f(x_1,x_2)^2)+2{n \choose 3}(E(f(x_1,x_2)f(x_1,x_3))+E(f(x_1,x_2)f(x_2,x_3))+E(f(x_1,x_2)f(x_3,x_2)))+6{n \choose 4}E(f(x_1,x_2))^2$$

either in general or some initial simpler form such as $f(x_i,x_j)=x_i x_j^2$. And then appeal to the central limit theorem.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Clearly the preconditions of the CLT are not guaranteed to hold in this circumstance. What assumptions are you making about $f$ and the distribution of $x_i$ that would allow you to apply the CLT? $\endgroup$
    – whuber ♦
    Commented Jul 22, 2015 at 16:06
  • 1
    $\begingroup$ Sorry, I should have been clearer. By "appeal to the central limit theorem" I'm meaning something more like "hope that the central limit theorem will apply". If all moments of S exist I would think there should be some version of the CLT that can be used. Yes, there would still be more work to do in terms of specifics about the nature of the function $f$. $\endgroup$
    – JimB
    Commented Jul 22, 2015 at 16:12
  • 1
    $\begingroup$ Thank you for the clarification. Although there are versions of the CLT that do allow for lack of independence among random variables in a sequence, they work by maintaining close control over how much dependence there is. It's hard to see how one could get much control here, given the extremely general nature of the question and the extensive interdependencies of the terms in this sum. I think any insight you could share about that would really get to the heart of the matter. $\endgroup$
    – whuber ♦
    Commented Jul 22, 2015 at 16:16
  • 1
    $\begingroup$ As whuber notes, the CLT seems difficult to use here. A moment bound could work: by Markov's inequality, $\DeclareMathOperator{\E}{\mathbb E}\Pr\left( \lvert S - \E S \rvert \ge a \right) \le a^{-k} \E \lvert S - \E S \rvert^k$. You can optimize this bound over $k$; even values are more convenient, since then you don't have to worry about the absolute values. Finding the general central moments of $S$ is probably an unpleasant task, though. $\endgroup$
    – Danica
    Commented Jul 22, 2015 at 16:54
  • $\begingroup$ @Dougal. With maybe a simple example that's symmetric (such as $f(x,y)=x y$), then with Mathematica or Maple, the moments might not be too onerous. And for simple-minded simulations with functions $x y$, $x y^2$, and $x\sqrt{|y|}$ with n = 50 suggests that a normal distribution as a limiting distribution varies as to the quality of the approximation of Pr(S>x) (and, of course, all approximations probably get worse for extreme values of x). $\endgroup$
    – JimB
    Commented Jul 22, 2015 at 18:19
0
$\begingroup$

Answer

After some reading, it turns out that the sum $S$ is a degree-two U-statistic. Its asymptotic distribution in the limit of large $n$ is normal.

The mean and variance of the asymptotic distribution are \begin{align} \mathrm{E}(S)&=\tbinom n2 \mathrm{E}\left(f(x_1, x_2)\right)\\ \mathrm{var}(S)&=\frac{4}{n}\tbinom n2^2\mathrm{cov}\left(f(x_1, x_2), f(x_1, x_3)\right).\\ &=2(n-1)\mathrm{cov}\left(f(x_1, x_2), f(x_1, x_3)\right) \end{align}

Background

Asymptotic normality was proven by Hoeffding in the late 1940s (see the wiki-link for the original reference). Elements of Large Sample Theory provides a nice treatment in chapter 6. For a publicly-available treatment (although not quite as nice), see chapter 10 of these lecture notes: Asymptotic Tools.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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