Alias method

“You are given an n-sided die where side i has probability p_i of being rolled. What is the most efficient data structure for simulating rolls of the die?”

A very similar question was posted to me recently  :

• http://stackoverflow.com/questions/4511331/randomly-selecting-an-element-from-a-weighted-list
• http://stackoverflow.com/questions/3120035/indexing-count-of-buckets/3120179#3120179

The approaches above are very cool, and illustrate the use of augmented search trees.

However, it seems there is a better method for this problem – and it has been out there for a while now. This was a fascinating read :

• Darts, Dice, and Coins: Sampling from a Discrete Distribution

Additional pointers for the alias method:

• https://prxq.wordpress.com/2006/04/17/the-alias-method/
• https://en.wikipedia.org/wiki/Alias_method