Monday, September 19, 2011  Follow-up: Sampling a discrete
distribution  This is a follow-up to my last post, on a puzzle
about "Sampling a discrete distribution" (see my comment there
for the solution I originally thought of).  As an anonymous
commenter (Rex?) points out, a nice elementary solution that has
been known for a long time. I admit to not knowing this solution
ahead of time, and use the fact that it's not really my field as
an excuse. Here I want to summarize this solution for
educational purposes.  Imagine each sample in the distribution
is a vase containing liquid proportional to the probability of
the outcome.  We classify these vases into 3 types: LO —
 probability less than 1/n GOOD –  probability precisely 1/n
HI –  probability greater then 1/n  In the ideal case when every
vase is GOOD, we are done (uniform sampling). If not, we  move
towards this ideal case by inductively applying the following
subroutine:  ** Pick a LO vase (say, with x amount of liquid)
and a HI vase (with y amount of li