Fixing Random, Part 26

We know from our exploration of the weighted integer distribution that we can think of our probability distributions as making a rectangle where various sub-rectangles are associated with particular values; we then “throw a dart” at the rectangle to sample from the distribution; where it lands gives us the sample. But for the purposes of this series, we’re going to try to find ways to sample from a distribution that has a particular PDF without doing any quadrature approximations or any integral calculus. Next time on FAIC: We know how to efficiently sample from any small, discrete distribution with integer weights, but distributions based on arbitrary PDFs are much harder beasts to tame.

Source: ericlippert.com