Stephen Welch comments on [AN #140]: Theoretical models that predict scaling laws

[Stephen Welch]

Some simple algebraic manipulation tells us that distance between points would then scale as D^(-1/​d).

This is a really helpful summary! I’m having trouble following this step here and in the original work—could someone point me in the right direction as to why this follows from needing ~2^d as many points to make the “net” twice as fine?

[Rohin Shah]

Say that at dataset size $D_0$, the distance between points is $x_0$. Now consider a new distance $x$ -- what is the corresponding $D$ we need?

Intuitively, for each factor of 2 that $x$ is smaller than $x_0$ (which we can quantify as ${\log }_2\left(\frac{x_0}{x}\right)$), we need to multiply by another factor of $2^d$.

So $D=D_0\times (2^d{)}^{{\log }_2\left(\frac{x_0}{x}\right)}=D_0\times (2^{{\log }_2\left(\frac{x_0}{x}\right)}{)}^d=D_0\times (\frac{x_0}{x}{)}^d$

$(\frac{D}{D_0}{)}^{\frac{1}{d}}=\frac{x_0}{x}$

$x=x_0(\frac{D}{D_0}{)}^{-\frac{1}{d}}$

That is, the distance scales as $D^{-\frac{1}{d}}$.

[Osher Lerner]

Oh hi! I linked your video in another comment without noticing this one. Great visual explanation!