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.
- Sample two points from the probability distribution function.
- 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.
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)