Say I have a (generally high-dimensional) random variable $X$ with known, continuous CDF $F(X)$.

Is there a good algorithm for drawing values of $X$ that doesn't require that I calculate the joint density?

I'm specifically interested in the GEV distribution used in the latent variable formulation of the nested logit: $$F\left(\vec\nu\right) = \exp\left(- ∑_{n ∈ N} \left(∑_{k∈n} \exp\left(\frac{-\nu_k}{λ_n}\right)\right)^{λ_n}\right).$$ That distribution should have analytic PDFs, but they're pretty gross (and are going to get even grosser with multiple layers of nests).

[Edit: this question was labelled a duplicate of Inverse of cumulative density function for Multivariate Normal Distribution. It's not obvious why -- is the assumption that the inverse-transform algorithm is the only algorithm for drawing from a CDF? That doesn't seem right.]

  • $\begingroup$ I guess I could just use MCMC-MH, if I approximate the pdf $f(\vec\nu)$ with the probability of being in some small neighbourhood of $\vec\nu$ $\endgroup$
    – Wilbur
    Commented Apr 27, 2023 at 9:13

1 Answer 1


The MCMC-MH algorithm requires the ratio of the PDFs at the proposal value $x'$ and the existing value $x_t$. Let $K$ be the dimension of $X$. We can approximate the ratio by looking at the ratio of probabilities that $X$ is in a neighbourhood of $x'$ or $x_t$ $$ \frac{f(x')}{f(x)} = \frac{\lim_{e \to 0}P[X \in x' \pm e]/e^K}{ \lim_{e \to 0}P[X \in x_t \pm e]/e^K} = \lim_{e \to 0} \frac{P[X \in x' \pm e]}{ P[X \in x_t \pm e]} \approx \frac{P[X \in x' \pm \epsilon]}{ P[X \in x_t \pm \epsilon]}, $$ where the approximation should hold for small $\epsilon$.

However it's not obvious how to use that approximation in log-space, which will likely be important given that both the numerator and the denominator will be very close to 0. In particular, $$ \log P[X \in x' \pm \epsilon] = \log\left(P[X < x' + \epsilon] - P[X < x' - \epsilon] \right) \\ \neq \log\left(P[X < x' + \epsilon]\right) - \log \left(P[X < x' - \epsilon] \right). $$

  • $\begingroup$ Since this is approximate, you cannot conclude at an exact simulation anyway. You should look for a latent structure such that $F$ appears like an integrated probability. For instance, the exponential of a sum equal to the product of exponentials hints at this probability being the probability of a maximum of rvs. $\endgroup$
    – Xi'an
    Commented May 6, 2023 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.