LinkedIn

Weighted Sampling from a Probability Distribution

Members only

Given a probability distribution over `N` categories (e.g. an M-faced biased die or softmax weights), draw a sample in `O(log N)`. The canonical solution is inverse-CDF sampling — build a cumulative p...