I have the following problem. I must sample from a discrete distribution that is changing at each sort.

Let me explain, with a "vivid" description, I draw a color ball from a bag. The probability associated with each color is different (for this part I could choose an alias method, for example, the Vose's algorithm). BUT, after I choose a paint can, I paint the ball with this color and I put it back in the bag. So, If I use a classical alias method, I have to initialize prob and alias each time and it takes time. So, I wonder if an algorithm derived from the alias method exists for this kind of problem. As only two probabilities are changed at each iteration, I could imagine that the initialization part could be done in a very efficient way.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.