Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 38 ยท Sampling Methods

Sampling Points in Shapes and on Spheres

Pick uniformly random points in a disk, a triangle and on a sphere, avoid the classic mistakes, and see why high-dimensional balls hold little volume.

Geometry problems are a natural home for Monte Carlo: the area of a strange region, the average distance between two random points, the light arriving from a random direction. All of them need uniform sampling in a shape: every region of equal area (or volume) is equally likely to receive the point. This lesson shows the correct recipes and the tempting wrong ones.

Rectangles and boxes

The easy case: choose each coordinate independently. For a rectangle [a, b] ร— [c, d] use x = rng.uniform(a, b) and y = rng.uniform(c, d). The same works for boxes in any number of dimensions.

A trap: the disk

To get a uniform point in the unit disk, a natural idea is "random radius r in [0, 1], random angle ฮธ in [0, 2ฯ€)". That is wrong: the points bunch up near the center, because the ring at small radius has little area but receives as many points as a big ring.

The area of a thin ring of radius r is proportional to r. So the radius must have density proportional to r, i.e. CDF rยฒ. By inverse transform, take r = โˆšU.

Python Wrong versus right disk sampling

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The correct fraction inside radius 0.5 is the area ratio ฯ€(0.5)ยฒ/ฯ€ = 0.25; the wrong method gives about 0.5.

Rejection for odd shapes

For a region A with a simple bounding box, use rejection: sample uniformly in the box and keep points inside A. Accepted points are uniform in A. The acceptance rate is area(A)/area(box), so this is the same dart idea as before. It is the easiest correct method for shapes defined by an inequality, such as the ellipse xยฒ/4 + yยฒ โ‰ค 1.

Uniform points in a triangle

For a triangle with corners A, B, C, there is a neat direct recipe. Draw u, v uniform on (0, 1). If u + v > 1, replace them by 1 โˆ’ u, 1 โˆ’ v (this folds the unit square's upper triangle onto the lower one). Then the point

Text
P = A + uยท(B โˆ’ A) + vยท(C โˆ’ A)

is uniform in the triangle. Skipping the folding step would put points in the whole parallelogram, outside the triangle.

Python Uniform points in a triangle

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The mean of a uniform sample in a triangle is its centroid, (A+B+C)/3, a handy test.

Directions: points on a sphere

For a random direction in 3D (a point on the surface of a unit sphere), a naive choice of two uniform angles bunches points near the poles. The right method uses the normal distribution:

  1. Draw d independent standard normals Zโ‚, โ€ฆ, Z_d.
  2. Divide the vector by its length.

The standard normal density in d dimensions depends only on distance from the origin (it is rotation-symmetric), so the direction is uniform on the sphere. This works in any dimension.

Python Uniform directions with normals

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A famous result by Archimedes says the height of a uniform point on a sphere is uniform on [โˆ’1, 1], which the output confirms. A naive sampler using a uniform polar angle fails this check.

The curse of dimensionality: balls get empty

How much of the cube [โˆ’1, 1]^d is occupied by the unit ball? Estimate by rejection: the fraction of uniform cube points with ฮฃ xแตขยฒ โ‰ค 1. In 2 dimensions it is ฯ€/4 โ‰ˆ 0.785; in 3 it is ฯ€/6 โ‰ˆ 0.524; and it plunges quickly after.

Python The ball fills almost none of a high-dimensional cube

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

At d = 12 the exact ratio is about 0.0001, so plain rejection wastes nearly every point. This is the "curse of dimensionality" for sampling, and why high-dimensional problems need smarter methods (variance reduction and MCMC, later chapters).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. To sample uniformly in the unit disk using polar coordinates, the radius should be

    Area grows like rยฒ, so the radius CDF is rยฒ and inverse transform gives r = โˆšU.
  2. 2. How do you pick a uniformly random direction in d dimensions?

    The standard normal vector has a rotation-symmetric density, so its direction is uniform.
  3. 3. A uniform sample in a triangle with corners A, B, C has mean close to

    The centroid is the average of the corners, and the mean of a uniform distribution on the triangle is its centroid.
  4. 4. Why does plain rejection (cube to ball) fail in 12 dimensions?

    The ratio of the ball's volume to the cube's volume shrinks rapidly with dimension.

Summary

  • Sample boxes coordinate by coordinate; use rejection for regions defined by inequalities.
  • In a disk, take r = โˆšU and a uniform angle; plain uniform r is wrong.
  • In a triangle, fold u + v > 1 back and use A + u(Bโˆ’A) + v(Cโˆ’A).
  • Normalize a vector of standard normals to get a uniform direction in any dimension.
  • Ball-to-cube volume ratio collapses with dimension, so rejection becomes hopeless.

Next: Hit-or-Miss Integration