3
$\begingroup$

It turns out that many things behave very differently in high dimensional space. The below paragraph is picked from a book. I need extra help to understand. The book says,

if you pick a random point in a unit square (a $1\times 1$ square), it will have only about a $0.4\%$ chance of being located less than $0.001$ from a border( In other words, it is very unlikely that a random point will be extreme along any dimension). But in a $10,000$-dimensional unit hypercube (a $1\times 1\times 1\times 1\times 1\times 1\ldots \times 1$ cube with ten thousand 1s), this probability is greater than $99.99999\%$. Most points in a high dimensional hypercube are very close to the border.

Q) What is the author trying to convey from the above paragraph?

If you pick two points randomly in a unit square, the distance between these two points will be, on average roughly $0.52$. If you pick two points in a unit 3D cube, the average distance will be roughly $0.66$. Now If you two points picked randomly in a $1,000,000$ dimensional hypercube, the average distance will be about approx $408$?

How is it possible?

$\endgroup$
3
$\begingroup$

Along each direction for a unit cube, we have $2$ boundaries. To be less than $0.01$ from a bounday in a $d$-dimensional unit cube, it is not inside the cube of side length $1-2\times 0.001$ sharing the same centroid as the original cube.

The corresponding volume for that is $(1-2\times 0.01)^d$ where $d$ is the coresponding dimension.

$$\left(1-\left( 1-2\times 0.001\right)^2\right) \times 100 \% \approx 0.3996\%$$

$$\left(1-\left( 1-2\times 0.001\right)^{10,000}\right) \times 100 \% \approx 99.999999798\%$$

When we first computed the answer for $2$ dimension, we might carelessly conclude that most points are not closed to the boundary. The moral of the story is be careful not to generalize what we believe without proof to higher dimension.

Your second question is also known as Hypercube line picking of which its computation is non-trivial. We know that

$$\frac13 \sqrt{d} \le \Delta(d) \le \sqrt{\frac{d}{18}\left( 1+2\sqrt{1-\frac{3}{5d}}\right)}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.