Which distributions can you sample if you can sample a Gaussian?

This is by no means a complete classification, although I'm surprised that no-one has mentioned that we can easily construct the most well-known continuous distributions from rational functions of $N(0,1)$ variables.

Let $\{ X_1, X_2, X_3, \dots \}$ be independent $N(0,1)$ random variables. Then we have:

• $\textrm{Gamma}(\frac{n}{2},\frac{1}{2}) = X_1^2 + \dots + X_n^2$
• $\textrm{Beta}(\frac{n}{2},\frac{m}{2}) = \dfrac{X_1^2 + \dots + X_n^2}{X_1^2 + \dots + X_{n+m}^2}$
• $\textrm{Uniform}[0,1] = \dfrac{X_1^2 + X_2^2}{X_1^2 + X_2^2 + X_3^2 + X_4^2}$ (special case of Beta)

You can also get the Student's $t$-distribution, amongst other things (slightly more complicated, but still a rational function of independent $N(0,1)$ random variables).

Anyway, by adding and multiplying by constants, we can rescale those distributions:

• $\textrm{Uniform}[a,b] = \dfrac{a(X_1^2 + X_2^2) + b(X_3^2 + X_4^2)}{X_1^2 + X_2^2 + X_3^2 + X_4^2}$
• $\textrm{Gamma}(\frac{n}{2},\lambda) = 2\lambda(X_1^2 + \dots + X_n^2)$
• $\textrm{Exponential}(\lambda) = 2\lambda(X_1^2 + X_2^2)$ (special case of Gamma)

I think that being able to construct the uniform distribution is probably my favourite of these results, not least because it's not immediately obvious from the construction that it should be uniform.

EDIT: On deeper investigation, it transpires that the construction of the uniform distribution in terms of four Gaussians has an elegant interpretation in the context of quantum computation.

Just want to observe that if $X$ is $\mathcal N(0,1)$ and $Y$ has any distribution with a strictly increasing* cdf $F_Y$ such that $F_Y^{-1} \circ F_X$ is computable (in whatever model of computability you are working with), then each one is sampleable from the other.

Indeed suppose we have a $\mathcal N(0,1)$ random variable $X$ with cdf $F_X$.

Note the random variable $F_Y(Y)$ is uniform on $[0,1]$.

Suppose we obtain a sample value $x$ from $X$. Then $F_Y^{-1}(F_X(x))$ is a sample value from $Y$: $$ \mathbb P(Y\le F_Y^{-1}(F_X(x))) = \mathbb P(F_Y(Y)\le F_X(x))=F_X(x)=\mathbb P(X\le x). $$ *Actually it's enough that $Y$ have a strictly increasing cdf on an interval that it a.s. belongs to.

However, $x\mapsto e^x$ is not BSS-computable, so there may not be that many such $Y$'s if you use that model.

Lie groups are made up of spheres and it is easy to sample from spheres, so it is easy to sample from Haar measure. We can sample from $S^{n-1}\subset\mathbb R^n$ by taking $n$ normal samples, assuming that they aren't all zero, and normalizing the vector to lie on the unit sphere, using square roots. $SO(n)$ acts on $S^{n-1}$, preserving the standard measure, with stabilizer conjugate to $SO(n-1)$. By induction we can sample from $SO(n-1)$, so we can sample from $SO(n)$. Other compact connected groups have similar structures. If we want to sample from disconnected groups, we must divide our sample space into $n$ regions of equal measure. This may be tricky for the difficult distribution, but it is easy for the circle, given trig functions.