How to sample points uniformly from a finite volume region?

Question

Lets say we have a finite volume, but not necessarily bounded, region in $\mathbb{R}^d$ like $R = \{(x, y) \in \mathbb{R}^2 \mid x \in (0, 1)\, y \in (1, 1/\sqrt{x})\}$. This has finite area since $\int_0^1 \frac{1}{\sqrt{x}} - 1\,dx = 1$. How can one sample points uniformly from that region?

Answer 1

Here is a practical solution:

First, generate a random number $r_x\in(0,1)$. Then calculate $x$ such that $\int_0^x(\frac{1}{\sqrt t}-1)dt=r_x$. This gives you your $x$-coordinate.

Next, generate a random number $r_y\in(1,\frac{1}{\sqrt x})$. This gives you your $y$-coordinate.

Answer 2

I would probably use a Markov chain Monte Carlo type algorithm to sample from this measure. That means, you generate a Markov chain that is stationary with respect to the uniform distribution on $R$. Given that certain ergodic properties hold, you will eventually obtain samples from your measure.

In this case, a Metropolis-Hastings algorithm could look like this.

1. Choose $x^0 \in R$.
   2. For $m = 1,...$
   3. Set $x' = x^{m-1} + y$, where $y \sim \mathrm{N}(0, \Sigma)$
   4. If $x' \in R$:
      5. $x^{m} := x'$
   5. Else:
      7. $x^{m} := x^{m+1}$

$\Sigma$ is a positive definite matrix. The Markov chain $(x^m)_{m=1}^\infty$ should then be stationary with respect to your uniform measure and strongly ergodic. However, this algorithm is probably not very efficient.

The problem of sampling uniform random variables on weird sets appears in nested sampling; so maybe this is a good point to start for you.

Answer 3

(this should be posted as a comment to TonyK's answer, but I lack the karma)

TonyK's answer has the correct approach - the other answers people have given are inaccurate or off-topic. The idea (in case you don't understand) is that you want to sample the area uniformly, so you use area as a parameter: that is, you parameterize the points in the region by the area from the edge of the sample region to a given sample point.

One slight improvement to TonyK's answer, is that the algebra turns out to be simpler if you calculate the $y$ coordinate first. I'll spare you the details because the math is straightforward once you understand the basic approach, but the final solution is as follows:

Generate two random numbers $R_1$ and $R_2$ distributed uniformly in $(0,1)$; then the desired sample point $(x,y)$ is given by $x=R_2 R_1^2$ and $y=1/R_1$.