Does there exist any univariate distribution that we can't sample from?

Question

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.

Answer 1

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.

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 $\textrm{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.

Answer 2

When a distribution is only defined by its moment generating function $\phi(t)=\mathbb{E}[\exp\{tX\}]$ or by its characteristic function $\Phi(t)=\mathbb{E}[\exp\{itX\}]$, it is rare to find ways of generating from those distributions.

A relevant example is made of $\alpha$-stable distributions, which have no known form for density or cdf, no moment generating function, but a closed form characteristic function.

In Bayesian statistics, posterior distributions associated with intractable likelihoods or simply datasets that are too large to fit in one computer can been seen as impossible to (exactly) simulate.

Answer 3

Assuming you refer to continuous distributions. By using the probability integral transform, you can simulate from any univariate distribution $F$ by simulating $u \sim (0,1)$ and then taking $F^{-1}(u)$. So, we can simulate a uniform, then that part is done. The only thing that may preclude the simulation from $F$ is that you cannot calculate its inverse $F^{-1}$, but this has to be related to computational difficulties, rather than something theoretical.

Answer 4

Now that your question evolved into "difficult to sample from", just take any model with an intractable likelihood, assign a prior distribution to the model parameters ${\bf \theta} = (\theta_1,...,\theta_d)$, and suppose that you are interested in the marginal posterior distribution of one of the entries $\theta_j$. This implies that you need to sample from the posterior, which is intractable due to the the intractability of the likelihood.

There are methods to approximately sample from this posterior in some cases, but no exact general method exists at the moment.

Answer 5

Not sure if this is really an answer ... I am guessing (but do not know) that one cannot sample from an only finitely additive distribution. An example would be the uniform distribution on the rational numbers, which only can exist as a finitely additive distribution. To see this, let $(q_i)_{i=1}^\infty$ be an enumeration of the rationals. Since the distribution is uniform, $P(X=q_i)=0$ for any individual $i$, so $\sum_{i=1}^\infty P(X=q_i)=0$ but $P(X\in \mathbb{Q})=1$.

If this answer looks strange and even irrelevant, look at more practical examples which are sometimes used in Bayesian inference: A uniform prior distribution on a real parameter, such as the mean of a normal distribution, say $\mu$. That can be modeled by a "density" (not a real probability density) which is identically one: $\pi(\mu) = 1$. Such a prior can be used in Bayesian analysis (and is sometimes used, see the classic book by Box & Tiao), but we cannot sample from it. And, the probability distribution defined that way is only finitely additive, which you can see by an argument similar to the rational number example above.

Answer 6

Could you provide any example of univariate distribution that is impossible to random generate from?

Let $c$ be Chaitin's Constant, and sample the (distribution of the) random variable which is constantly $c$.

If you're only interested in sampling random variables whose values can be reasonably approximated by 64-bit floating-point numbers, or you have some similar tolerance for finite error in the value, and you weren't representing your samples a Turing machines anyways, consider this:

Let $X \sim \text{Ber}(p)$ with $p = 1 - c$ and try to sample it. The values $0$ and $1$ are perfectly representable (in e.g. 64 bit floats with no error), but I think you'll generate them at incorrect frequencies unless you solve the halting problem.

The two CDFs are piecewise constant: one is $0$ on $(-∞, c)$ and $1$ on $[c, ∞)$. The other is $0$ on $(-∞, 0)$, then $c$ on $[0, 1)$ and $1$ on $[1, ∞)$. That is, one makes $c$ relevant on the $x$-axis, the other on the $y$-axis. I'm not sure which makes sampling most difficult, so pick the one you (dis)like the most ;-)

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.

In this case, obvious answer seems obvious:

• Sample uniformly the prime factors of $n$ where $n$ is large (i.e. break RSA).
• Sample the preimages of a cryptographic hash function (i.e. generate bitcoin and break git and mercurial).
• Sample the set of optimal Go strategies (with Chinese superko rules, which make all games finite—as far as I understand).

A bit more formally: I give you a large instance of an NP-complete problem (or EXP-complete, etc.) and ask you to uniformly sample the set of solutions for me.

Probably I should accept $\bot$ as a solution to no-instances (and no-instances only, and it would be the only solution). I should also come up with a bijection between e.g. integers (assuming you want to sample members of $\mathbb{R}$) and solutions—which is often fairly trivial, just treat base 2 representations as truth assignments for my SAT instance, for example, and maybe use $-1$ to represent $\bot$.

You can easily check whether any given truth assignment satisfies my SAT instance, and having checked them all you know whether any one does, so I have fully specified a CDF by giving you a boolean formula (or circuit), yet to sample the corresponding distribution you have to essentially become something at least as powerful as a SAT-solvability oracle.

---

So I gave you an uncomputable number which should throw sand in your gears, and I gave you a CDF that's slow to calculate. Maybe the next obvious question to ask is something like this: is there a CDF represented in some efficient form (e.g. can be evaluated in polynomial time) such that it's hard to generate samples with that distribution? I don't know the answer to that one. I don't know the answer to that one.