vendredi 24 août 2018

Obtain values from multiple distributions with a single generator roll

I am trying to implement the Alias method, also described here. This is an algorithm which allows to sample from a weighted N-sided dice in O(1).

The algorithm calls for the generation of two values:

  • An uniformly distributed integer i in [0, N]
  • An uniformly distributed real y in [0, 1)

The paper specifies that these two numbers can be obtained by a single real number x between [0, N). From x one can then derive two values as:

  • i = floor(x)
  • y = x - i

Now, the other implementations that I have seen call for the random number generator two times, one to generate i and one to generate y. Given that I am using a fairly expensive generator (std::mt19937) and that I need to sample many times, I was wondering if there was a better approach in terms of performance, while preserving the quality of the result.

I'm not sure whether using an uniform_real_distribution to generate x makes sense as if N is large then y's distribution is going to get sparser as doubles are not uniformly distributed. Is there maybe a way to call the engine, get the random bits out, and then generate i and y from them directly?




Aucun commentaire:

Enregistrer un commentaire