12
$\begingroup$

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.

$\endgroup$
12
  • 6
    $\begingroup$ It really comes down to what you mean by "can't/impossible", I think. There are cases when the cdf and the pdf are very expensive to evaluate, for example, which would make most methods prohibitive, and it's not hard to come up with distributional shapes where good envelope-bounds on the pdf (for an accept-reject that mostly avoids function evaluation) are not readily available. So it would fail the case you already exclude and we could make $F$ even more expensive (per deviate, on average) to calculate than using accept-reject (which would exclude trying to use numerical inversion of the cdf) $\endgroup$ – Glen_b Aug 25 '16 at 23:58
  • 3
    $\begingroup$ We cannot draw uniform random samples from the set of irrational numbers on the interval (0,1) using a computer. Proof is left as an exercise for the reader. $\endgroup$ – Cliff AB Aug 25 '16 at 23:59
  • 2
    $\begingroup$ @Cliff AB This can be handled by interval arithmetic. Define an (the smallest) interval around each computer evaluable (rational) point such that the entirety of [0,1] is covered by these intervals. For each computer evaluable "uniform" drawn, evaluate t(with outward rounding) rhe interval inverse of the cumulative distribution function on this interval argument. That will produce an interval sample of the random variable,100% guaranteed to contain the true sample. $\endgroup$ – Mark L. Stone Aug 26 '16 at 0:13
  • 2
    $\begingroup$ What I am getting at is since you already count sufficiently inefficient accept reject as "impossible", if you make it expensive enough that any other approach you know about is worse (requires more calculation) you would presumably consider those "impossible" as well. Constructing expensive-to-evaluate F's and f's isn't that hard, and making them so that obvious ways of avoiding actually calculating either most of the time is also inefficient seems to be possible ,,, ctd $\endgroup$ – Glen_b Aug 26 '16 at 0:33
  • 1
    $\begingroup$ ctd ... (but collectively, people are pretty ingenious, so what seems very hard one day may be feasible if you come up with a nice idea that gets around most of the problem). If we say "approximation to such-and-such accuracy is fine" then many of these difficulties can be got around in many cases (for example, one might be able to construct large lookup tables / generation-from-histograms, say, such that most of the time you generate approximate values reasonably fast). $\endgroup$ – Glen_b Aug 26 '16 at 0:34
15
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ If $F(x$ is not known, then what is known? Obviously that is relevant. If you don't know anything, you won't be able to do anything. If you know something, then it depends on what that something is. $\endgroup$ – Mark L. Stone Aug 26 '16 at 11:19
  • $\begingroup$ @Tim In fact, it is quite common that we don't know F(X), but we can generate samples from it. That is a typical scenario in Monte Carlo (stochastic) simulation. $\endgroup$ – Mark L. Stone Aug 26 '16 at 14:27
  • $\begingroup$ @Tim: If you're not interested in this story, it's not clear what story you are interested in. In response to Glen_b's comment, you said you were not concerned with inefficient sampling. This method, while inefficient, will allow you to sample from any pdf (assuming it's not so ill behaved that numerical integration fails, but I don't think anyone cares about using such distributions). So unless you are interested in, say, distributions that are discontinuous at an infinite number of places, this should be the answer to your question: yes we can. $\endgroup$ – Cliff AB Aug 26 '16 at 15:32
  • $\begingroup$ Actually, if $F$ is known but not $F^{-1}$, this is a problem. $\endgroup$ – Xi'an Sep 3 '16 at 18:47
  • 1
    $\begingroup$ It depends what you mean by problem. If $F$ is known, then per my answer, $F^{-1}(y) = inf(x:F(x) \ge y)$ is always well-defined and can be solved numerically. It might not be as fast as you'd like, so if that's what you mean by problem, o.k. If that's not what you mean, then what is the problem? $\endgroup$ – Mark L. Stone Sep 3 '16 at 18:58
7
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ If you only know the moment generating function, you could use the saddlepoint approximarion and then simulate from that. $\endgroup$ – kjetil b halvorsen Sep 3 '16 at 20:31
  • 1
    $\begingroup$ @Xi'an You left out the word "efficiently". In the worst case, you can numerically invert the numerical inversion of the transform. That will do the job, maybe not "efficiently", but it will do it. $\endgroup$ – Mark L. Stone Sep 3 '16 at 21:53
  • 3
    $\begingroup$ @kjetilbhalvorsen: the saddlepoint approximation is the solution proposed in the link I put. But it is an approximation! $\endgroup$ – Xi'an Sep 4 '16 at 4:35
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ ...but the question is about univariate distributions. There are lots of examples of complicated models where MCMC fails to converge even after enormous number of iterations. $\endgroup$ – Tim Aug 26 '16 at 8:38
  • $\begingroup$ @Tim And that's exactly why I said marginal posterior, which means univariate ... It seems to me you do not have clear what you are asking. The first two answers are clear in that theoretically, it is possible to sample from any distribution provided you know it. $\endgroup$ – Noah Aug 26 '16 at 8:45
  • 1
    $\begingroup$ I vote to put this question [ON HOLD] until the OP clarifies what he is asking and stop changing the question every time a new answer appears in order to make the answers inapplicable. $\endgroup$ – Noah Aug 26 '16 at 8:46
  • $\begingroup$ I am not changing my question "every time a new answer appears" ... Obviously statistical model with likelihood and prior is not univariate since it is declared in terms of conditional distribution. It is univariate if you sample from the posterior, but then I guess that you assume that we already have the marginal distribution so there is no problem with intracable posterior. $\endgroup$ – Tim Aug 26 '16 at 8:55
  • 1
    $\begingroup$ You confuse marginal with univariate, when those two notions have no connection. Univariate means the random variable is in $\mathbb{R}$, while marginal means the distribution can be represented as an integral against another density. Actually, using this integral representation means a univariate rv can be simulated by first simulating a multivariate rv. $\endgroup$ – Xi'an Sep 3 '16 at 18:50
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.