What is the computational complexity of sampling from any of these cases? I mean the computational complexity of the most efficient existing algorithm, not a possible algorithm or a lower bound.

  1. Finite discrete probability distribution $p_1, ..., p_N$: I think this is $O(\log N)$. I tested sampling using python function np.random.choice and the log plot was linear. Also, I think this is true based on this paper: https://people.mpi-inf.mpg.de/~kbringma/paper/2012ICALP.pdf

  2. A continuous distribution with closed-form pdf and CDF, for example, exponential distribution. From python implementation, it seems to be $O(1)$ but I'm not sure how to test that.

  3. A continuous distribution with closed-form pdf while CDF is not closed form, for example, normal distribution. It seems to be $O(1)$

What about sampling from truncated versions of these distributions? Could anyone also suggest reference/references on this topic?

  • $\begingroup$ O(1) for discrete distributions: see keithschwarz.com/darts-dice-coins for a very nice discussion. $\endgroup$ Commented May 5, 2021 at 9:38
  • $\begingroup$ The complexity depends on the algorithm. A huge number of algorithms are extant, with many specialized algorithms developed for various distributional families. $\endgroup$
    – whuber
    Commented May 6, 2021 at 14:05