6
$\begingroup$

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".

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – whuber Feb 23 '18 at 15:22
  • 2
    $\begingroup$ 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 $\endgroup$ – Aksakal Feb 24 '18 at 4:49
  • 1
    $\begingroup$ @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. $\endgroup$ – Xi'an Feb 25 '18 at 7:52
  • 1
    $\begingroup$ 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. $\endgroup$ – Taylor Feb 25 '18 at 17:29
  • 1
    $\begingroup$ 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. $\endgroup$ – πr8 Oct 30 '18 at 0:42
2
$\begingroup$

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}$.

Perhaps focusing on the finite scenario may help to narrow down your question, or on ordered sequences, or so ...

$\endgroup$
  • $\begingroup$ This sounds rather like a comment since it does not give any answer to the question $\endgroup$ – Tim Feb 24 '18 at 8:30
  • $\begingroup$ @Tim Please make it a comment. New members are not allowed to make comments. $\endgroup$ – rationale Feb 24 '18 at 9:57

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.