This seems like a great idea, but is it always possible to split a discrete pdf into columns of equal height with each column having at most 2 identities?
zbp
Indeed it is! Here is a helpful page with a proof of why, as well as suggestions on how to actually build an alias table in linear time (it might not be obvious how to improve beyond the naive n^2 method): http://www.keithschwarz.com/darts-dice-coins/
(The algorithm he cites is called Vose's algorithm)
This seems like a great idea, but is it always possible to split a discrete pdf into columns of equal height with each column having at most 2 identities?
Indeed it is! Here is a helpful page with a proof of why, as well as suggestions on how to actually build an alias table in linear time (it might not be obvious how to improve beyond the naive n^2 method): http://www.keithschwarz.com/darts-dice-coins/
(The algorithm he cites is called Vose's algorithm)