Simulate a discrete random variable

Question

We have a discrete random variable $X$ with the following probability distribution \begin{equation*} p(X=i)=p_i,\quad i=1,2,\ldots 1000, \quad \sum_{i=1}^{1000}p_i=1. \end{equation*} How we can apply the efficient method (from the view of speed) to simulate random variable $X$ except the "Inverse Transform" and "Acceptance-Rejection" methods?

Answer 1

Precompute the prefix sum of the $p_i$ and store it in an array.

Then draw a random number in $[0,1)$ and find the array element just larger than it, by dichotomic search. The index of the element is your random variable.

The computation of the prefix sum will cost you $N$ additions, and every drawing $\log_2N$ comparisons.

---

E.g. let the probabilities be $0.1,0.3,0.2,0.4$. You form the array

$$0,0.1,0.3,0.6,1.0.$$

Then the uniform drawing of, say $0.314$ yields $3$ in two comparisons.

---

If your distribution is somewhat smooth, there could be ways to lower the $\log N$ behavior by means of an approximate inverse transform. But as the computational budget is already as low as $\log_21000=10$ comparisons, there is little you can do.

Answer 2

The main problem here is that the $p_i$ can be arbitrary (as long as they sum up to 1) so there is no way to use a simple formula so you need some kind of lookup. An adequate representation of such a probability distribution is a binary tree. Construct it in a way that large probabilities correspond to nodes with low depth. This allows you to generate random bits and then you choose that path that corresponds to the bit, 0 -> left, 1 -> right.