samedi 25 juillet 2020

Sampling without replacement given probabilities of objects being in sample

I've seen algorithms for weighted sampling without replacement such as the Efraimidis & Spirakis algorithm explained in the second answer to this question: Faster weighted sampling without replacement. My problem is that I don't have access to weights, and rather have access to the probabilities of each element being in the sample.

For example, given that the Efraimidis & Spirakis algorithm is trying to choose 3 integers from the integers 1 to 6, and is given the weights [0.995, 0.001, 0.001, 0.001, 0.001, 0.001] for the respective 6 integers, the algorithm's samples contain each of the integers with the following probabilities:

1: 1.00000
2: 0.39996
3: 0.39969
4: 0.39973
5: 0.40180
6: 0.39882

(This data is taken from the same question discussed above).

The problem is that I only have access to those resulting probabilities. Is there any way to convert these probabilities to weights, or is there another algorithm or a modification to this algorithm that can perform sampling without replacement using probabilities rather than weights.




Aucun commentaire:

Enregistrer un commentaire