0
$\begingroup$

In my current problem, I need to sample points in proportion to the weights assigned to them and an original probability density function. Unfortunately, the weights aren't known ahead of time and can't be derived from the original PDF.

I've come up with a solution on my own but would like to know what it's called. It seems useful and simple enough that it should at least have a name / reference.

Sampling according to weights. Pick two points at random. Choose one at random according to weights. Equivalent solution, much less costly. Proof.

Algorithm

  1. Sample two points from the probability distribution function.
  2. Choose one at random with odds equal to W_i / W_j.

In the end, samples a random point with the correct probability based on original PDF and weighting strategy.

Proof

For the discrete case.

Each point i should have O(i)=W_i/(1-W_i) odds of being sampled.

Thus the probability of sampling P(i) = W/sum(W)

If we select point i and j: O(i) = W_i /W_j

The expected value of point j is E(W_j) = (1-W_i) / n

The probability of sampling point i initially is P(S_i)=1 / n.

Substituting: O(i) = n * W_i / (1 - W_i)

P(i | S_i) = nW/sum(W)

Thus P (i) = nW/sum(W) * 1/n = W/sum(W)

QED

$\endgroup$
3
$\begingroup$

Your algorithm doesn't work. Suppose there are 1000 possible values, the value $i=7$ has weight 1,000,000 while the others have weight 1. A correct algorithm should draw value $i=7$ with probability near 1. But your algorithm can only return $i=7$ if it happens to be one of the two points drawn in step 1, and the probability of that is much less than 1.

| cite | improve this answer | |
$\endgroup$

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.