Previous | Next --- Slide 58 of 64
Back to Lecture Thumbnails

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):

(The algorithm he cites is called Vose's algorithm)