Simulate distance contrast

CodingBeginner⏱ 30 minClassical MLsimulationcontrastdimensionknn

Problem

Simulate $N$ points in $\R^d$ and measure the contrast $(\max_i\|x_i-q\| - \min_i\|x_i-q\|)/\min_i\|x_i-q\|$ as $d$ grows.

Confirm the contrast decays and identify the rate.
Repeat with data lying on a $d_0$ -dimensional subspace embedded in $\R^d$ and show the contrast is governed by $d_0$ .
Repeat with an anisotropic covariance with a power-law spectrum and comment.

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

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.

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

Problem	Field	Type	Difficulty	Time
Johnson–Lindenstrauss dimension arithmetic	High-Dim Probability	Numerical	Beginner	15 min
Two different curses of dimensionality	Classical ML	Numerical	Beginner	15 min
A sufficient condition for correct retrieval	RAG	Proof	Intermediate	30 min
Balls into bins, with one choice and with two run	AI Systems	Coding	Intermediate	1 hour
Cache hit rates under Zipf popularity run	AI Systems	Coding	Intermediate	1 hour