Skip to content
nonconvexcard

Simulate the measure of a spherical cap

CodingIntermediate⏱ 30 minHigh-Dim Probabilityspherecapsimulationconcentration

Problem

Estimate by simulation the fraction of the uniform measure on Sd−1S^{d-1} lying in the cap {u:⟨u,θ⟩≥t}\{u : \langle u,\theta\rangle \ge t\}, for d∈{3,10,100,1000}d \in \{3, 10, 100, 1000\} and t∈{0.1,0.3,0.5}t\in\{0.1, 0.3, 0.5\}. Compare with the bound e−dt2/2e^{-dt^2/2} and with the exact density ∝(1−s2)(d−3)/2\propto(1-s^2)^{(d-3)/2}. Explain why naive Monte Carlo fails for large dd and moderate tt, and what to do about it.

Implement it, then check the implementation against something you can verify independently.

Write it

Solve it here7 tests · Python runs in your browser
⌘/Ctrl + ↵ to run · limit 60s · draft saved in this browser
7 tests will run against your code. The first run downloads the Python runtime — several megabytes, once per browser.

Hints

Hints — 0 of 3 revealed

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems
SolvedProblemFieldTypeDifficultyTime
Simulate distance contrast runClassical MLCodingBeginner30 min
Volume concentrates near the boundaryHigh-Dim ProbabilityNumericalBeginner15 min
Balls into bins, with one choice and with two runAI SystemsCodingIntermediate1 hour
Cache hit rates under Zipf popularity runAI SystemsCodingIntermediate1 hour
Distance contrast and the failure of nearest neighboursClassical MLProofIntermediate30 min