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?

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.

  • This is significantly better than my answer (no rounding error), and I was not aware of this method. Cool! I've dabbled quite a bit in arithmetic coding and such, and never saw this crop up. – orlp Aug 11 at 4:59

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.