On why the high dimensional apples are all peel and no core..

["Subbarao Kambhampati" <rao@asu.edu>]

In case you didn't quite figure out why high-dimensional apples are
all peel and no core...

Suppose we have an n-dimensional sphere of radius r. Suppose we remove
a small peel of epsilon thickness from this sphere (apple). What do
you think is the ratio of the remaining volume of the sphere to the
original volume of the sphere?

You would think it will be very close to 1, right?

Think again. As the number of dimensions, n, tends to infinity, this
ratio tends to zero. Another way of putting it is that a
high-dimensional apple is all peel and no core ;-) 

(you can show this fairly easily. We know that a 2-D sphere has
volume (area) proportional to r^2, a 3-d sphere has volume
proportional to r^3, so an n-d sphere has a volume proportional to
r^n. 
If we assume that we removed a peel of thickness e, we are considering
the ratio

[(r-e)/r]^n

Since r-e is smaller than r, if you continue exponentiating it, it
will ultimately go to zero.. 

for r=1, and e= .01, the ratio comes to

97% for 3-d
81% for 20-d
36% for 100-d
0.004% for 1000-d

Recall that it is not all that wierd to think about 1000-dimensional
space, since in information retrieval, we might have several thousands
of keywords...

Rao
[Aug 26, 2002]

ps: Here is another non-intuitive point about high dimensions. If you
   pick two vectors in your space randomly, what is the probability
   that they will be orthogonal to each other? (I.e., their scalar
   (dot) product will be zero?). Obviously it is quite low in 2-D, but
   it is close to 1 in high-D...