Sampling particles according to their distance

I'm trying to draw 2 particles out of $$n$$ particles, where the probability for drawing the particles is proportional to a Gaussian of their displacement: $$p(\boldsymbol{x}_i,\boldsymbol{x}_j) \propto \exp [ - ||\boldsymbol{x}_i - \boldsymbol{x}_j||^2 / 2 \sigma^2]$$ where points $$\boldsymbol{x}$$ are in generally 3D space.

The normalization is $$\sum_{i=1}^n \sum_{j>i} p(\boldsymbol{x}_i, \boldsymbol{x}_j)$$.

1. I can compute the CDF following the usual way of sampling discrete distributions - but this is expensive for large number of particles, since we need to compute $$\binom{n}{2}$$ terms.

2. I read about the acceptance-rejection method i.e. finding an easier to sample distribution which can be scaled to be everywhere greater than this one, and then using rejection sampling. This sounds great, but as usual I don't know a good choice for this envelope distribution.

Is this problem commonly studied? Do better methods exist? Or is it obvious what a good candidate for an envelope should be?

Thanks

Edit: the particles in my application are points in 3D space - what I wrote below for a 1D case may not be possible to adapt to 3D, so I am still looking for a solution. I am now convinced this answer was wrong, and am still looking for a better solution.

Edit: I clarified that the points are positions in generally 3D space.

• There are some ways to bound these probabilities, but there are two tricky aspects to an algorithm that makes use of them: (i) to generate a candidate without performing any $O(n^2)$ operations and (ii) to perform the accept-reject without having too high a rejection rate. It does seem as if perhaps it might be possible to do it in $O(n\log n)$ per draw. Will you need only a single pair-draw with a given set of $x$-values or will you be drawing many such pairs? (it may at least be possible to get reasonable average performance by improving the envelope progressively as pairs are generated) – Glen_b Jun 17 at 10:09
• Do these x-values tend to be clustered? Spaced apart? Do they look like random draws from some distribution? – Glen_b Jun 17 at 10:12
• @Glen_b Thanks for your comment, I will be drawing many such pairs. I posted one solution below, perhaps there are way to improve it. Also: the points are not required to follow any particular distribution (they come from a physical dataset). – smörkex Jun 17 at 18:41
• Thanks. I understand that they're not required to do anything in particular, since you present them as fixed observations, but if you're aware of likely configurations it may help. – Glen_b Jun 18 at 1:21