Programming and probability: Sampling from a discrete distribution over an infinite set

[[Originally posted at RandomSeed]] This post is an introductory tutorial which presents a simple algorithm for sampling from a discrete probability distribution $p(k)$ defined over a countably infinite set. We also show how to use higher-order programming to implement the algorithm in a modular and reusable way, and how to amortize the cost of sampling … Read more