# sampling from an unnormalised distribution

If one has to sample (with replacement) from a population $(x_1,x_2,\ldots)$ with weights $(\omega_1,\omega_2,\ldots)$, possibly infinite (although this is asking too much without further details), a standard simulation procedure is to sum these weights $\omega_i$ into $$\mathfrak{s}=\sum_i\omega_i$$ assumed to be finite, sort the weights $\omega_i$ and generate a Uniform $U(0,\mathfrak{s})$ $\iota$ that will compare with the cumulated weights$$\iota\le\omega_1\,,\iota\le\omega_1+\omega_2\,,\ldots$$until it meets the inequality.

However, this can prove very costly when the population is huge (and most often impossible when it is countably infinite) and when the $\omega_i$ are themselves costly to numerically compute. I thus wonder at alternatives that would produce samples from this weighted population without first computing the normalisation $\mathfrak{s}=\sum_i\omega_i$. One such alternative is to run a Metropolis-Hastings algorithm aiming at $\mathbf{\omega}=(\omega_1,\omega_2,\ldots)$ with local proposals, but one may object this is not "exact".

• I'm having trouble seeing how this could have any general solution for a countably infinite population. There would seem to be no assurance that any sampling procedure would ever find the largest weights in any reasonable time. That suggests narrowing the question to include some assumptions that might somehow characterize and limit the range of weights or population values.
– whuber
Feb 23, 2018 at 15:22
• if the weights are not sorted then there's no solution. some big weight $w_i$ may pop up at $i>>1$, that would messup your algorithm. there has to be constraints Feb 24, 2018 at 4:49
• @Taylor: the question came to me when working on a large population where computing the sum is indeed an issue, as we already stand in a parallelised framework. Feb 25, 2018 at 7:52
• So communication between threads/processes is the big bottleneck? If you could figure out a reasonable proposal then accept-reject would mean each process doesn’t need to be sent all the unnornalized weights(which would give you the sum for free almost); it just needs to look one of them up to evaluate the ratio, which could be held in the master process. And those are only being read so you don’t need to worry about race conditions. Feb 25, 2018 at 17:29
• You might be able to do this with some form of reservoir sampling, see e.g. blog.plover.com/prog/weighted-reservoir-sampling.html. This would be most useful if you were interested in collecting a large number of samples on a single pass through the set of weights, but perhaps less so if you wanted a single sample and wanted not to have to see all of the weights.
– πr8
Oct 30, 2018 at 0:42

The question is too general, as @whuber points out, to be answered. For instance, you could think of $\{x_1,x_2,...\}$ to be an enumeration of the rational numbers (this can be done, of course), and $\{\omega_1,\omega_2,...\}$ to be an infinite sequence of weights with $\sum\omega_j=1$ and $\omega_j>0$ for all $j$ (perhaps computationally difficult to calculate). This is, clearly, a terribly difficult scenario as the rationals are dense in ${\mathbb R}$.