# Simulate a discrete random variable

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?

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.

• IMO a segment tree is overkill as the intervals are known to be disjoint. – Yves Daoust Oct 15 '18 at 8:36

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.