Rohin Shah comments on [AN #140]: Theoretical models that predict scaling laws

[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}}$.