I’m interested in writing an algorithm to sample random numbers from some Probability Distribution Function, $P(x)$. We may assume that the Cumulative Distribution Function for $P(x)$, $C(x)$, is also known.

I know that many algorithms use Inverse Transform Sampling to sample pesudo-random numbers from PDF’s. This method finds a random number $n$ according to some PDF $P(x)$ by solving $n = C^{-1}(U)$, with $U approx text{Uniform}(0,1)$ (see for more).

This method works well for PDF’s with easily invertible CDF’s. Suppose, however, that some CDF is difficult or *impossible* to invert. What other methods (preferably of equal simplicity, if viable) for sampling (psuedo)-random numbers, according to some PDF are available?