Rejection Sampling and Points in the Unit Ball

Status: outline — write experiments and figures here.

Goals¶

• Rejection sampling in 1D and in (\mathbb{R}^d)

• Uniform points in the unit ball vs unit cube

• Why high-d balls look “empty in the middle” (shell concentration)

Outline¶

1. Rejection sampling: accept/reject idea

2. Sampling the unit ball (rejection from the cube; Gaussian direction + radius)

3. Where points live in high dimension

4. Lab: scatter in 2D/3D, radius histogram as (d) grows

Sources¶

• Blum–Hopcroft–Kannan, high-dimensional chapters

• Related demos: high_dim_and_CD, High-Dimensional-Data-and-The-Curse-of-Dimensionality