Explicitly: You have a computer that is able to pick a real number at random according to the normal distribution: $\mathcal{N}(0,1) = \frac{1}{\sqrt{2\pi}}e^{-x^2/2}$. Which distributions can this computer sample from, provided that your program must terminate after finitely many steps (not almost surely, but logically must terminate)?


For a simpler example, if your computer can sample a 'fair coin', heads 1/2 and tails 1/2, then it can also sample any binary event with probability a dyadic rational: $p/2^n$, $0 \leq p \leq 2^n$ an integer. It can't sample an event with probability $1/3$. The program "Flip two coins, $HH$ is a success, and on $TT$ repeat the experiment" is not allowed because it is not guaranteed to terminate (even though it will terminate with probability $1$).


Since it might be hard to characterize 'all possible' distributions, here's a concrete question: Can you sample from the Haar measure on any compact matrix Lie group?


EDIT: The idea of a random real number has more philosophical and practical subtleties than I realized when posting this question. I encourage commenters to answer based on varying interpretations, but to get the ball rolling how about these restrictions:


1) Given random real numbers x and y, the computer can calculate x + y, xy, and x/y (provided y =/= 0) in one step. (You can also multiply/add/divide by rational numbers)


2) Given a real random number x, the computer can decide in one step if x > 0, x = 0, or x < 0 and act accordingly.


I know this might not accurately model how computers or computer models work, so like I said feel free to play with these assumptions.



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](https://cp4space.wordpress.com/2019/05/24/w2-x2-w2-x2-y2-z2/), it transpires that the construction of the uniform distribution in terms of four Gaussians has an elegant interpretation in the context of quantum computation.


