In a blog post Kent Beck describes several solutions to this problem: you want to roll a loaded die with specified probabilities. post 
He offers a naive solution and a clever solution by Vose. His solutions demonstrates Smalltalk. I chose CoffeeScript.
Kent Beck illustrates the trick to the Vose algorithm: Take the "excess" from a tall column (a in our example) and glue it to a short column (like c). Keep doing this until all the columns are the same height.
Create the die with a collection of probability-value pairs: 1/2 ⟹ a, 1/3 ⟹ b, 1/6 ⟹ c. This die, when rolled, will produce a half the time, b a third, and c a sixth.
The naive implementation is to generate a random index between zero and one (0..1], then go through the probabilities until you have accumulated more than the index.
# naive (linear time) solution linearDraw = (normalizedChoices) -> index = Math.random() for {choice, chance} in normalizedChoices return choice if (index -= chance) < 0
Now the constant time solution, this with a sample structure representing the results of preprocessing.
# vose (constant time) solution flip = (heads, chance=1, tails) -> -> if chance > Math.random() then heads else tails constantDraw = (flipChoices) -> index = Math.floor flipChoices.length * Math.random() choice = flipChoices[index] choice?() or choice sample = [ 'a' 'b' flip 'a', .5, 'c' ]
Flip is a function that returns a function. The sample data structure encodes optional flips by evaluating flip with the appropriate choices.
References
A Linear Algorithm For Generating Random
Numbers With a Given Distribution by
Michael D. Vose pdf