We have great variety of methods for random generation from univariate distributions (inverse transform, accept-reject, Metropolis-Hastings etc.) and it seems that we can sample from literally any valid distribution – is that true?
Could you provide any example of univariate distribution that is impossible to random generate from? I guess that example where it is impossible does not exist (?), so let's say that by "impossible" we mean also cases that are very computationally expensive, e.g. that need brute-force simulations like drawing huge amounts of samples to accept just a few of them.
If such example does not exist, can we actually prove that we can generate random draws from any valid distribution? I'm simply curious if there exists counterexample for this.
Best Answer
If you know the cumulative distribution function, $F(x)$, then you can invert it, whether analytically or numerically, and use the inverse transform sampling method to generate random samples https://en.wikipedia.org/wiki/Inverse_transform_sampling .
Define $F^{-1}(y) = inf(x:F(x) \ge y)$. This will handle any distribution, whether continuous, discrete, or any combination. This can always be solved numerically, and perhaps analytically. Let U be a sample from a random variable distributed as Uniform[0,1], i.e., from a uniform[0,1] random number generator. Then $F^{-1}(U)$, defined as above, is a random sample from a random variable having distribution $F(x)$.
This may not be the fastest way of generating random samples, but it is a way, presuming that F(x) is known.
If F(x) is not known, then that's a different story.