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.

  • $\begingroup$ IMO a segment tree is overkill as the intervals are known to be disjoint. $\endgroup$ – 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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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