The expected edge length of a cube is equal to $e_{D}(f) = f^{1/D}$, why is that?

Question

section 1.4.3 of the book "Machine Learning - A Probabilistic Perspective" gives an example about KNN:

the input is two dimensional, we have three classes, and K = 10

here is Figure 1.15

here is Figure 1.16

the expected edge length of this cube

$e_{D}(f) = f^{1/D}$

why is that? is this formula an existing formula in geometric?

Answer 1

I don't know how you define the "expected" edge length of the cube without knowing the algorithm by which the cube is grown, but it is true that if data are randomly scattered according to a uniform distribution inside a $D$-dimensional hypercube of unit edge length, a $D$-dimensional hypercube with edge length $f^{1/D}$ inside the unit hypercube is expected to contain $f$ times the total number of data points.

This follows from the fact that the expected number of uniformly-distributed points in a given volume inside the unit hypercube is proportional to the volume. That is, if you construct a region that encloses half the total volume of the unit hypercube, you expect it to contain half the points distributed within the unit hypercube.

The volume of the unit hypercube is $1.$ The volume of a hypercube of edge length $s$ is $s^D.$ If you have a hypercube of edge length $s = f^{1/D}$, the volume of that hypercube is $(f^{1/D})^D = f.$