Fast sampling from discrete space

Question

Assume we are given a set $X = \{x_1,...,x_n \}$ of size $n$, and a probability distribution $P$ over $X$. I am interested in an algorithm $A$ which can sample from $X$ according to $P$, i.e. $\Pr(A=x_i) =p_i$.

More specifically, I assume $A$ can generate a uniformly distributed real number in the interval $[0,1]$ in a constant time, and try to characterize the distributions $P$ which can be sampled in $o(|X|)$ time.

For example, if $P$ is the uniform distribution, I can assign to each element of $X$ a string from $\{0,1\}^{\log(n)}$, then sample each bit uniformly (toss of a coin) and independently, which means I can sample in $O(\log(n))$ time. Are there distributions such that any algorithm requires $\Omega(|X|)$ time? Are there known results in this direction?

Answer 1

The Alias Method provides a means of sampling from a discrete distribution in $O(1)$ time, with $O(n)$ space and $O(n)$ pre-processing time.

Answer 2

Sampling can always be done in $O(\log n)$ time. As a precomputation, compute the prefix sums $p_1$, $p_1+p_2$, $p_1+p_2+p_3$, etc., and put them in an array. To randomly sample from $P$, pick a random real number $r \in [0,1]$ (via a uniform distribution), then use binary search to find the first index $i$ such that $p_1+\dots+p_{i-1} \le r$, then output $x_i$. I will let you prove why this is correct.