Succinct sampling from discrete distributions
Karl Bringmann, Kasper Green Larsen · 2013
We revisit the classic problem of sampling from a discrete distribution: Given n non-negative w-bit integers x1,..,xn, the task is to build a data structure that allows sampling i with probability proportional to xi. The classic solution is Walker's alias method that takes, when implemented on a Word RAM, O(n) preprocessing time, O(1) expected query time for one sample, and n(w+2lg(n)+o(1)) bits of space. Using the terminology of succinct data structures, this solution has redundancy 2n lg(n)+o(n) bits, i.e., it uses 2n lg(n)+o(n) bits in addition to the information theoretic minimum required for storing the input. In this paper, we study whether this space usage can be improved.